Approximation to the smallest regular expression for a given regular language

• Type: Article in International Scientific Journal
• Date: 2005

Authors

delgado, m (Author) FCUP; morais, j (Author) Other

Journal

The Journal is awaiting validation by the Administrative Services.

Title: INTERACTIVE SYSTEMS: DESIGN, SPECIFICATION, AND VERIFICATION

Vol. 15

Pages: 312-314

Indexing

ISI Web of Knowledge - 22 Citations

Scopus - 25 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-000-5X9

Abstract (EN): A regular expression that represents the language accepted by a given finite automaton can be obtained using the the state elimination algorithm. The order of vertex removal affects the size of the resulting expression. We use here an heuristic to compute an approximation to the order of vertex removal that leads to the smallest regular expression obtainable this way.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 3