State Elimination Heuristics for Short Regular Expressions

Article type: Research Article

Authors: Han, Yo-Sub

Affiliations: Department of Computer Science, Yonsei University, Seoul 120-794, Republic of Korea. [email protected]

Note: [] Han was supported by Basic Sci. Research Program through NRF funded by MEST (2010-0009168, 2012R1A1A2044562). Address for correspondence: Department of Computer Science, Yonsei University, Seoul 120-794, Republic of Korea

Abstract: State elimination is an intuitive and easy-to-implement algorithm that computes a regular expression from a finite-state automaton (FA). It is very hard to compute the shortest regular expression for a given FA in general and we cannot avoid the exponential blow-up. This implies that state elimination cannot avoid the exponential blow-up either. Nevertheless, since the size of a regular expression by state elimination depends on the state removal sequence, we can have a shorter regular expression if we choose a better removal sequence for state elimination. This observation motivates us to examine state elimination heuristics based on the structural properties of the input FA and implement state elimination using the heuristics that run in polynomial time. We demonstrate the effectiveness of our algorithm by experiment results.

Keywords: finite-state automata, regular expressions, state elimination, heuristics

DOI: 10.3233/FI-2013-952

Journal: Fundamenta Informaticae, vol. 128, no. 4, pp. 445-462, 2013