Name
Abstract | ||
|---|---|---|
We continue our work [H. Gruber, M. Holzer: Provably shorter regular expressions from deterministic finite automata (extended abstract). In Proc. DLT , LNCS 5257, 2008] on the problem of finding good elimination orderings for the state elimination algorithm, one of the most popular algorithms for the conversion of finite automata into equivalent regular expressions. Here we tackle this problem both from the theoretical and from the practical side. First we show that the problem of finding optimal elimination orderings can be used to estimate the cycle rank of the underlying automata. This gives good evidence that the problem under consideration is difficult, to a certain extent. Moreover, we conduct experiments on a large set of carefully chosen instances for five different strategies to choose elimination orderings, which are known from the literature. Perhaps the most surprising result is that a simple greedy heuristic by [M. Delgado, J. Morais: Approximation to the smallest regular expression for a given regular language. In Proc. CIAA , LNCS 3317, 2004] almost always outperforms all other strategies, including those with a provable performance guarantee. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02979-0_22 | CIAA |
Keywords | Field | DocType |
equivalent regular expression,m. delgado,empirical results,short regular expressions,smallest regular expression,optimal elimination ordering,good elimination ordering,finite automata,m. holzer,state elimination algorithm,elimination ordering,provably shorter regular expression,regular language,greedy heuristic,deterministic finite automata,regular expression | Quantum finite automata,Discrete mathematics,Combinatorics,Regular expression,Automata theory,Nondeterministic finite automaton,Nested word,Deterministic finite automaton,Regular language,Mathematics,ω-automaton | Conference |
Volume | ISSN | Citations |
5642 | 0302-9743 | 2 |
PageRank | References | Authors |
0.36 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hermann Gruber | 1 | 185 | 13.28 |
| Markus Holzer | 2 | 192 | 22.14 |
| Michael Tautschnig | 3 | 425 | 25.84 |