On Extremal Cases of Hopcroft’s Algorithm

Risultato della ricerca: Chapter

4 Citazioni (Scopus)

Abstract

In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different sequences of refinements of the set of the states that lead to the final partition. We find an infinite family of binary automata for which such a process is unique. Some recent papers (cf. [3,7,1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated to circular words. However, automata minimization can be achieved also in linear time when the alphabet has only one letter (cf. [14]), so in this paper we face the tightness of the algorithm when the alphabet contains more than one letter. In particular we define an infinite family of binary automata representing the worst case of Hopcroft’s algorithm. They are automata associated to particular trees and we deepen the connection between the refinement process of Hopcroft’s algorithm and the combinatorial properties of such trees.
Lingua originaleEnglish
Titolo della pubblicazione ospiteImplementation and Application of Automata
Pagine14-23
Numero di pagine10
Stato di pubblicazionePublished - 2009

Serie di pubblicazioni

NomeLecture Notes in Computer Science

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • ???subjectarea.asjc.1700.1700???

Fingerprint Entra nei temi di ricerca di 'On Extremal Cases of Hopcroft’s Algorithm'. Insieme formano una fingerprint unica.

Cita questo