Hopcroft's algorithm and tree-like automata

Castiglione, G.; Restivo, A.; Sciortino, M.

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.

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