Hopcroft's algorithm and tree-like automata

Risultato della ricerca: Article

4 Citazioni (Scopus)

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.
Lingua originaleEnglish
pagine (da-a)59-75
Numero di pagine17
RivistaRAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS
Volume45
Stato di pubblicazionePublished - 2011

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Science Applications

Fingerprint Entra nei temi di ricerca di 'Hopcroft's algorithm and tree-like automata'. Insieme formano una fingerprint unica.

  • Cita questo