Benutzer: Gast  Login
Titel:

Provably Shorter Regular Expressions from Deterministic Finite Automata

Dokumenttyp:
Technical Report
Autor(en):
Hermann Gruber; Markus Holzer
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 moderat...     »
Stichworte:
finite automata; regular expressions; state elimination algorithm; descriptional complexity
Jahr:
2008
Jahr / Monat:
2008-02-01 00:00:00
Seiten/Umfang:
23
 BibTeX