Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2011__45_1_59_0,
author = {Castiglione, G. and Restivo, A. and Sciortino, M.},
title = {Hopcroft's algorithm and tree-like automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {59--75},
publisher = {EDP-Sciences},
volume = {45},
number = {1},
year = {2011},
doi = {10.1051/ita/2011011},
mrnumber = {2776854},
zbl = {1220.68066},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011011/}
}
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 SP - 59 EP - 75 VL - 45 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011011/ DO - 10.1051/ita/2011011 LA - en ID - ITA_2011__45_1_59_0 ER -
%0 Journal Article %A Castiglione, G. %A Restivo, A. %A Sciortino, M. %T Hopcroft's algorithm and tree-like automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 59-75 %V 45 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011011/ %R 10.1051/ita/2011011 %G en %F ITA_2011__45_1_59_0
Castiglione, G.; Restivo, A.; Sciortino, M. Hopcroft's algorithm and tree-like automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 1, pp. 59-75. doi: 10.1051/ita/2011011
Cité par Sources :