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

Abstract

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

How to cite

top

Castiglione, 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. [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. [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. [3] J. Berstel, L. Boasson, O. Carton and I. Fagnot, Sturmian trees. Theor. Comput. Syst.46 (2010) 443–478. Zbl1209.68394MR2592178
  4. [4] J.P. Borel and C. Reutenauer, On Christoffel classes. RAIRO-Theor. Inf. Appl. 450 (2006) 15–28. Zbl1085.68116MR2197281
  5. [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. [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. [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. [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. [9] T. Knuutila, Re-describing an algorithm by Hopcroft. Theoret. Comput. Sci.250 (2001) 333–363. Zbl0952.68077MR1795249
  10. [10] M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications 90. Cambridge University Press (2002). Zbl1001.68093MR1905123
  11. [11] E.F. Moore, Gedaken experiments on sequential, in Automata Studies. Annals of Mathematical Studies34 (1956) 129–153. MR78059
  12. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.