User: Guest  Login
Document type:
Technical Report 
Author(s):
Hermann Gruber; Markus Holzer 
Title:
Provably Shorter Regular Expressions from Deterministic Finite Automata 
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...    »
 
Keywords:
finite automata; regular expressions; state elimination algorithm; descriptional complexity 
Year:
2008 
Year / month:
2008-02-01 00:00:00 
Pages:
23