Implementation of state elimination using heuristics

Jae Hee Ahn, Yo Sub Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


State elimination is an intuitive and easy-to-implement algorithm that computes a regular expression from a finite-state automaton (FA). The size of a regular expression from state elimination depends on the state removal sequence. Note that it is very hard to compute the shortest regular expression for a given FA in general and we cannot avoid the exponential blow-up from state elimination. Nevertheless, we notice that we may have a shorter regular expression if we choose a good removal sequence. This observation motivates us to examine heuristics based on the structural properties of an FA and implement state elimination using the heuristics that run in polynomial time. We demonstrate the effectiveness of our algorithm by experiments.

Original languageEnglish
Title of host publicationImplementation and Application of Automata - 14th International Conference, CIAA 2009, Proceedings
Number of pages10
Publication statusPublished - 2009
Event14th International Conference on Implementation and Application of Automata, CIAA 2009 - Sydney, NSW, Australia
Duration: 2009 Jul 142009 Jul 17

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5642 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other14th International Conference on Implementation and Application of Automata, CIAA 2009
CitySydney, NSW

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Implementation of state elimination using heuristics'. Together they form a unique fingerprint.

Cite this