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

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