On Extremal Cases of Hopcroft’s Algorithm

Research output: Chapter in Book/Report/Conference proceedingChapter

4 Citations (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.
Original languageEnglish
Title of host publicationImplementation and Application of Automata
Pages14-23
Number of pages10
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Castiglione, G., Restivo, A., & Sciortino, M. (2009). On Extremal Cases of Hopcroft’s Algorithm. In Implementation and Application of Automata (pp. 14-23). (Lecture Notes in Computer Science).