# Hopcroft's algorithm and tree-like automata

G. Castiglione; A. Restivo; M. Sciortino

RAIRO - Theoretical Informatics and 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 45.1 (2011): 59-75. <http://eudml.org/doc/222033>.

@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},

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

language = {eng},

month = {3},

number = {1},

pages = {59-75},

publisher = {EDP Sciences},

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

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

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

DA - 2011/3//

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; automata minimization

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

ER -

## References

top- 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
- 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.68029
- J. Berstel, L. Boasson, O. Carton and I. Fagnot, Sturmian trees. Theor. Comput. Syst.46 (2010) 443–478. Zbl1209.68394
- J.P. Borel and C. Reutenauer, On Christoffel classes. RAIRO-Theor. Inf. Appl.450 (2006) 15–28. Zbl1085.68116
- G. Castiglione, A. Restivo and M. Sciortino, Hopcroft's algorithm and cyclic automata, in LATA. Lecture Notes in Computer Science5196 (2008) 172–183. Zbl1163.68021
- 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.68289
- G. Castiglione, A. Restivo and M. Sciortino, On extremal cases of hopcroft's algorithm. Theoret. Comput. Sci.411 (2010) 3414–3422 . Zbl1214.68193
- 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.
- T. Knuutila, Re-describing an algorithm by Hopcroft. Theoret. Comput. Sci.250 (2001) 333–363. Zbl0952.68077
- M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications90. Cambridge University Press (2002). Zbl1001.68093
- E.F. Moore, Gedaken experiments on sequential, in Automata Studies. Annals of Mathematical Studies 34 (1956) 129–153.
- 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.68060
- 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.
- 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.68028
- 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.