State Elimination Ordering Strategies: Some Experimental Results

Nelma Moreira
( Universidade do Porto)
Davide Nabais
(Universidade do Porto)
Rogério Reis
(Universidade do Porto)

Recently, the problem of obtaining a short regular expression equivalent to a given finite automaton has been intensively investigated. Algorithms for converting finite automata to regular expressions have an exponential blow-up in the worst-case. To overcome this, simple heuristic methods have been proposed.

In this paper we analyse some of the heuristics presented in the literature and propose new ones. We also present some experimental comparative results based on uniform random generated deterministic finite automata.

In Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 139–148.
Published: 7th August 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.31.16 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org