Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T05:24:32.369Z Has data issue: false hasContentIssue false

Hopcroft's algorithmand tree-like automata

Published online by Cambridge University Press:  15 March 2011

G. Castiglione
Affiliation:
Università di Palermo, Dipartimento di Matematica e Applicazioni, via Archirafi, 34, 90123 Palermo, Italy; giusi@math.unipa.it
A. Restivo
Affiliation:
Università di Palermo, Dipartimento di Matematica e Applicazioni, via Archirafi, 34, 90123 Palermo, Italy; giusi@math.unipa.it
M. Sciortino
Affiliation:
Università di Palermo, Dipartimento di Matematica e Applicazioni, via Archirafi, 34, 90123 Palermo, Italy; giusi@math.unipa.it

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
© EDP Sciences, 2011