# Hopcroft's algorithm and tree-like automata

G. Castiglione; A. Restivo; M. Sciortino

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

- Volume: 45, Issue: 1, page 59-75
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCastiglione, G., Restivo, A., and Sciortino, M.. "Hopcroft's algorithm and tree-like automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 45.1 (2011): 59-75. <http://eudml.org/doc/273082>.

@article{Castiglione2011,

abstract = {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.},

author = {Castiglione, G., Restivo, A., Sciortino, M.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {automata minimization; Hopcroft's algorithm; word trees},

language = {eng},

number = {1},

pages = {59-75},

publisher = {EDP-Sciences},

title = {Hopcroft's algorithm and tree-like automata},

url = {http://eudml.org/doc/273082},

volume = {45},

year = {2011},

}

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

PB - EDP-Sciences

VL - 45

IS - 1

SP - 59

EP - 75

AB - 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.

LA - eng

KW - automata minimization; Hopcroft's algorithm; word trees

UR - http://eudml.org/doc/273082

ER -

## References

top- [1] J. Berstel and O. Carton, On the complexity of Hopcroft's state minimization algorithm, in CIAA. Lecture Notes in Computer Science3317 (2004) 35–44. Zbl1115.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. Zbl1173.68029MR2543335
- [3] J. Berstel, L. Boasson, O. Carton and I. Fagnot, Sturmian trees. Theor. Comput. Syst.46 (2010) 443–478. Zbl1209.68394MR2592178
- [4] J.P. Borel and C. Reutenauer, On Christoffel classes. RAIRO-Theor. Inf. Appl. 450 (2006) 15–28. Zbl1085.68116MR2197281
- [5] G. Castiglione, A. Restivo and M. Sciortino, Hopcroft's algorithm and cyclic automata, in LATA. Lecture Notes in Computer Science5196 (2008) 172–183. Zbl1163.68021MR2540322
- [6] G. Castiglione, A. Restivo and M. Sciortino, On extremal cases of hopcroft's algorithm, in CIAA. Lecture Notes in Computer Science5642 (2009) 14–23. Zbl1248.68289MR2550006
- [7] G. Castiglione, A. Restivo and M. Sciortino, On extremal cases of hopcroft's algorithm. Theoret. Comput. Sci.411 (2010) 3414–3422 . Zbl1214.68193MR2723795
- [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. Zbl0293.94022MR403320
- [9] T. Knuutila, Re-describing an algorithm by Hopcroft. Theoret. Comput. Sci.250 (2001) 333–363. Zbl0952.68077MR1795249
- [10] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications 90. Cambridge University Press (2002). Zbl1001.68093MR1905123
- [11] E.F. Moore, Gedaken experiments on sequential, in Automata Studies. Annals of Mathematical Studies34 (1956) 129–153. MR78059
- [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 . Zbl0574.68060MR828517
- [13] A. Paun, M. Paun and A. Rodríguez-Patón, Hopcroft's minimization technique: Queues or stacks? in CIAA. Lecture Notes in Computer Science5148 (2008) 78–91. Zbl1172.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. Zbl1168.68028MR2522446
- [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).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.