### Abstract

Lingua originale | English |
---|---|

pagine (da-a) | 59-75 |

Numero di pagine | 17 |

Rivista | RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS |

Volume | 45 |

Stato di pubblicazione | Published - 2011 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software
- Computer Science Applications
- Mathematics(all)

### Cita questo

**Hopcroft's algorithm and tree-like automata.** / Restivo, Antonio; Sciortino, Marinella; Castiglione, Giuseppa.

Risultato della ricerca: Article

*RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS*, vol. 45, pagg. 59-75.

}

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 -