State elimination heuristics for short regular expressions

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)445-462
Number of pages18
JournalFundamenta Informaticae
Issue number4
Publication statusPublished - 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Information Systems
  • Computational Theory and Mathematics


Dive into the research topics of 'State elimination heuristics for short regular expressions'. Together they form a unique fingerprint.

Cite this