Hopcroft's algorithm and tree-like automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 1, pp. 59-75.

Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have running time with the same asymptotic growth rate. In particular, we provide a lower and upper bound for the running time of the algorithm expressed in terms of combinatorial properties of the trees. We consider also tree-like automata associated to trees constructed by de Brujin words, and we prove that a queue implementation of the waiting set gives a Θ(n log n) execution while a stack implementation produces a linear execution. Such a result confirms the conjecture given in [A. Paun, M. Paun and A. Rodríguez-Patón. Theoret. Comput. Sci. 410 (2009) 2424-2430.] formulated for a family of unary automata and, in addition, gives a positive answer also for the binary case.

DOI : 10.1051/ita/2011011
Classification : 68Q45, 68Q25
Mots clés : automata minimization, Hopcroft's algorithm, word trees
@article{ITA_2011__45_1_59_0,
     author = {Castiglione, G. and Restivo, A. and Sciortino, M.},
     title = {Hopcroft's algorithm and tree-like automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {59--75},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {1},
     year = {2011},
     doi = {10.1051/ita/2011011},
     mrnumber = {2776854},
     zbl = {1220.68066},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2011011/}
}
TY  - JOUR
AU  - Castiglione, G.
AU  - Restivo, A.
AU  - Sciortino, M.
TI  - Hopcroft's algorithm and tree-like automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2011
SP  - 59
EP  - 75
VL  - 45
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011011/
DO  - 10.1051/ita/2011011
LA  - en
ID  - ITA_2011__45_1_59_0
ER  - 
%0 Journal Article
%A Castiglione, G.
%A Restivo, A.
%A Sciortino, M.
%T Hopcroft's algorithm and tree-like automata
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2011
%P 59-75
%V 45
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2011011/
%R 10.1051/ita/2011011
%G en
%F ITA_2011__45_1_59_0
Castiglione, G.; Restivo, A.; Sciortino, M. Hopcroft's algorithm and tree-like automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 1, pp. 59-75. doi : 10.1051/ita/2011011. http://www.numdam.org/articles/10.1051/ita/2011011/

[1] J. Berstel and O. Carton, On the complexity of Hopcroft's state minimization algorithm, in CIAA. Lecture Notes in Computer Science 3317 (2004) 35-44. | Zbl

[2] J. Berstel, L. Boasson and O. Carton, Continuant polynomials and worst-case behavior of Hopcrofts minimization algorithm. Theoret. Comput. Sci. 410 (2009) 2811-2822. | MR | Zbl

[3] J. Berstel, L. Boasson, O. Carton and I. Fagnot, Sturmian trees. Theor. Comput. Syst. 46 (2010) 443-478. | MR | Zbl

[4] J.P. Borel and C. Reutenauer, On Christoffel classes. RAIRO-Theor. Inf. Appl. 450 (2006) 15-28. | Numdam | MR | Zbl

[5] G. Castiglione, A. Restivo and M. Sciortino, Hopcroft's algorithm and cyclic automata, in LATA. Lecture Notes in Computer Science 5196 (2008) 172-183. | MR | Zbl

[6] G. Castiglione, A. Restivo and M. Sciortino, On extremal cases of hopcroft's algorithm, in CIAA. Lecture Notes in Computer Science 5642 (2009) 14-23. | MR | Zbl

[7] G. Castiglione, A. Restivo and M. Sciortino, On extremal cases of hopcroft's algorithm. Theoret. Comput. Sci. 411 (2010) 3414-3422 . | MR | Zbl

[8] J.E. Hopcroft, An n log n algorithm for mimimizing the states in a finite automaton, in Theory of machines and computations (Proc. Internat. Sympos. Technion, Haifa, 1971). Academic Press, New York (1971), 189-196. | MR | Zbl

[9] T. Knuutila, Re-describing an algorithm by Hopcroft. Theoret. Comput. Sci. 250 (2001) 333-363. | MR | Zbl

[10] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications 90. Cambridge University Press (2002). | MR | Zbl

[11] E.F. Moore, Gedaken experiments on sequential, in Automata Studies. Annals of Mathematical Studies 34 (1956) 129-153. | MR

[12] R. Paige, R.E. Tarjan and R. Bonic, A linear time solution to the single function coarsest partition problem. Theoret. Comput. Sci. 40 (1985) 67-84 . | MR | Zbl

[13] A. Paun, M. Paun and A. Rodríguez-Patón, Hopcroft's minimization technique: Queues or stacks? in CIAA. Lecture Notes in Computer Science 5148 (2008) 78-91. | Zbl

[14] A. Paun, M. Paun and A. Rodríguez-Patón, On the hopcroft's minimization technique for dfa and dfca. Theoret. Comput. Sci. 410 (2009) 2424-2430. | MR | Zbl

[15] B. Watson, A taxonomy of finite automata minimization algorithms. Technical Report 93/44, Eindhoven University of Technology, Faculty of Mathematics and Computing Science (1994).

Cité par Sources :