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

Fingerprint

Automata
Automata and Formal Languages
Binary trees
Formal languages
Finite automata
Deterministic Finite Automata
Labeled Trees
Tree Automata
Binary Tree
Queue
Upper and Lower Bounds
Binary

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Mathematics(all)

Cita questo

@article{9b1e3d3272ff429382b418c037d9011f,
title = "Hopcroft's algorithm and tree-like automata",
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{\'i}guez-Pat{\'o}n.",
author = "Antonio Restivo and Marinella Sciortino and Giuseppa Castiglione",
year = "2011",
language = "English",
volume = "45",
pages = "59--75",
journal = "RAIRO - Theoretical Informatics and Applications",
issn = "0988-3754",
publisher = "EDP Sciences",

}

TY - JOUR

T1 - Hopcroft's algorithm and tree-like automata

AU - Restivo, Antonio

AU - Sciortino, Marinella

AU - Castiglione, Giuseppa

PY - 2011

Y1 - 2011

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

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.

UR - http://hdl.handle.net/10447/60415

M3 - Article

VL - 45

SP - 59

EP - 75

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

SN - 0988-3754

ER -