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.
@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},
volume = {45},
year = {2011},
pages = {59-75},
doi = {10.1051/ita/2011011},
mrnumber = {2776854},
zbl = {1220.68066},
language = {en},
url = {http://dml.mathdoc.fr/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, Tome 45 (2011) pp. 59-75. doi : 10.1051/ita/2011011. http://gdmltest.u-ga.fr/item/ITA_2011__45_1_59_0/
[1] and , On the complexity of Hopcroft's state minimization algorithm, in CIAA. Lecture Notes in Computer Science 3317 (2004) 35-44. | Zbl 1115.68417
[2] , and , Continuant polynomials and worst-case behavior of Hopcrofts minimization algorithm. Theoret. Comput. Sci. 410 (2009) 2811-2822. | MR 2543335 | Zbl 1173.68029
[3] , , and , Sturmian trees. Theor. Comput. Syst. 46 (2010) 443-478. | MR 2592178 | Zbl 1209.68394
[4] and , On Christoffel classes. RAIRO-Theor. Inf. Appl. 450 (2006) 15-28. | Numdam | MR 2197281 | Zbl 1085.68116
[5] , and , Hopcroft's algorithm and cyclic automata, in LATA. Lecture Notes in Computer Science 5196 (2008) 172-183. | MR 2540322 | Zbl 1163.68021
[6] , and , On extremal cases of hopcroft's algorithm, in CIAA. Lecture Notes in Computer Science 5642 (2009) 14-23. | MR 2550006 | Zbl 1248.68289
[7] , and , On extremal cases of hopcroft's algorithm. Theoret. Comput. Sci. 411 (2010) 3414-3422 . | MR 2723795 | Zbl 1214.68193
[8] , An log 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] , Re-describing an algorithm by Hopcroft. Theoret. Comput. Sci. 250 (2001) 333-363. | MR 1795249 | Zbl 0952.68077
[10] , Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications 90. Cambridge University Press (2002). | MR 1905123 | Zbl 1001.68093
[11] , Gedaken experiments on sequential, in Automata Studies. Annals of Mathematical Studies 34 (1956) 129-153. | MR 78059
[12] , and , A linear time solution to the single function coarsest partition problem. Theoret. Comput. Sci. 40 (1985) 67-84 . | MR 828517 | Zbl 0574.68060
[13] , and , Hopcroft's minimization technique: Queues or stacks? in CIAA. Lecture Notes in Computer Science 5148 (2008) 78-91. | Zbl 1172.68522
[14] , and , On the hopcroft's minimization technique for dfa and dfca. Theoret. Comput. Sci. 410 (2009) 2424-2430. | MR 2522446 | Zbl 1168.68028
[15] , A taxonomy of finite automata minimization algorithms. Technical Report 93/44, Eindhoven University of Technology, Faculty of Mathematics and Computing Science (1994).