Name
Abstract | ||
|---|---|---|
We consider the absolute worst case time complexity for Hopcroft's minimization algorithm applied to unary languages (or a modification of this algorithm for cover automata minimization). We show that in this setting the worst case is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. We refine a previous result by showing that the Berstel/Carton example reported before is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also when considering the setting of cover automata and an algorithm based on the Hopcroft's method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list is desirable for the case of unary languages in the setting of deterministic finite automata. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-70844-5_9 | CIAA |
Keywords | Field | DocType |
lifo implementation,absolute worst case time,minimization technique,cover automata minimization,unary language,deterministic automaton,cover automaton,worst case,minimization algorithm,deterministic finite automaton,previous result,time complexity,deterministic finite automata | Quantum finite automata,Discrete mathematics,Automata theory,Deterministic automaton,Unary operation,Nested word,Unary language,Deterministic finite automaton,Algorithm,DFA minimization,Mathematics | Conference |
Volume | ISSN | Citations |
5148 | 0302-9743 | 1 |
PageRank | References | Authors |
0.38 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrei Paun | 1 | 743 | 74.92 |
| Mihaela Paun | 2 | 100 | 13.49 |
| Alfonso Rodríguez-Patón | 3 | 435 | 51.44 |