TUM-I0805techreporthttp://drehscheibe.in.tum.de/forschung/pub/reports/2008/TUM-I0805.ps.gz; http://drehscheibe.in.tum.de/forschung/pub/reports/2008/TUM-I0805.pdf.gz@techreport{TUM-I0805,
DOCUMENT-NAME = {/forschung/pub/reports/2008/TUM-I0805.ps.gz; /forschung/pub/reports/2008/TUM-I0805.pdf.gz},
URL = {http://drehscheibe.in.tum.de/forschung/pub/reports/2008/TUM-I0805.ps.gz; http://drehscheibe.in.tum.de/forschung/pub/reports/2008/TUM-I0805.pdf.gz},
CATEGORY = {Technical Report},
REVISION-DATE = {2008-02-01},
PAGES = {23},
AUTHOR = {Hermann Gruber and Markus Holzer},
CLASSIFICATION = {F.1, F.4.3, G.2.2},
KEYWORDS = {finite automata, regular expressions, state elimination algorithm, descriptional complexity},
VERSION = {1.0},
YEAR = {2008},
TYPE = {techreport},
ABSTRACT = {We study the problem of finding good elimination orderings for the state elimination algorithm, which is one of the most popular algorithms for the conversion of finite automata into equivalent regular expressions. Based on graph separator techniques we are able to describe elimination strategies that remove states in large induced subgraphs that are ``simple'' like, e.g., independent sets or subgraphs of bounded treewidth, of the underlying automaton, that lead to regular expressions of moderate size. In particular, we show that there is an elimination ordering such that every language over a binary alphabet accepted by an $n$-state {\em deterministic\/} finite automaton has alpbabetic width at most~$O(1.742^n)$, which is, to our knowledge, the algorithm with currently the best known performance guarantee.\\ Finally, we apply our technique to the question on the effect of language operations on regular expression size. In case of the intersection operation we prove an upper bound which matches, up to a small factor, a lower bound recently obtained in (Gelade and Neven, STACS 2008; Gruber and Holzer, ICALP 2008), and thus settles an open problem stated in (Ellul et al., JALC 2005).},
TITLE = {Provably Shorter Regular Expressions from Deterministic Finite Automata},
FORMAT = {Postscript, gzipped; PDF, gzipped},
}
finite automata, regular expressions, state elimination algorithm, descriptional complexityfinite automata, regular expressions, state elimination algorithm, descriptional complexityTechnical Report232008We study the problem of finding good elimination orderings for the state elimination algorithm, which is one of the most popular algorithms for the conversion of finite automata into equivalent regular expressions. Based on graph separator techniques we are able to describe elimination strategies that remove states in large induced subgraphs that are ``simple'' like, e.g., independent sets or subgraphs of bounded treewidth, of the underlying automaton, that lead to regular expressions of moderate size. In particular, we show that there is an elimination ordering such that every language over a binary alphabet accepted by an <i>n</i>-state <i>deterministic\/</i> finite automaton has alpbabetic width at most~<i>O(1.742^n)</i>, which is, to our knowledge, the algorithm with currently the best known performance guarantee.<br> Finally, we apply our technique to the question on the effect of language operations on regular expression size. In case of the intersection operation we prove an upper bound which matches, up to a small factor, a lower bound recently obtained in (Gelade and Neven, STACS 2008; Gruber and Holzer, ICALP 2008), and thus settles an open problem stated in (Ellul et al., JALC 2005).Hermann GruberHermann GruberMarkus HolzerMarkus HolzerProvably Shorter Regular Expressions from Deterministic Finite Automata