Hopcroft's algorithm and tree-like automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 45 (2011) no. 1, p. 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 : https://doi.org/10.1051/ita/2011011
Classification:  68Q45,  68Q25
Keywords: 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},
     publisher = {EDP-Sciences},
     volume = {45},
     number = {1},
     year = {2011},
     pages = {59-75},
     doi = {10.1051/ita/2011011},
     zbl = {1220.68066},
     mrnumber = {2776854},
     language = {en},
     url = {http://www.numdam.org/item/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, Volume 45 (2011) no. 1, pp. 59-75. doi : 10.1051/ita/2011011. http://www.numdam.org/item/ITA_2011__45_1_59_0/

[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 1115.68417

[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 2543335 | Zbl 1173.68029

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

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

[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 2540322 | Zbl 1163.68021

[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 2550006 | Zbl 1248.68289

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

[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 403320 | Zbl 0293.94022

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

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

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

[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 828517 | Zbl 0574.68060

[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 1172.68522

[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 2522446 | Zbl 1168.68028

[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).