Re-describing an algorithm by Hopcroft
J. Hopcroft introduced already in 1970 an \(O(n\log n)\)-time algorithm for minimizing a finite deterministic automaton of \(n\) states. Although the existence of the algorithm is widely known, its theoretical justification, correctness and running time analysis are not. We give here a tutorial reconstruction of Hopcroft's algorithm focusing on a firm theoretical basis, clear correctness proofs and a well-founded computational analysis. Our analysis reveals that if the size of the input alphabet \(m\) is not fixed, then Hopcroft's original algorithm does not run in time \(O(mn\log n)\) as is commonly believed in the literature. The \(O(mn\log n)\) holds, however, for the variation presented later by D. Gries and for a new variant given in this article. We also propose a new efficient routine for refining the equivalence classes constructed in the algorithm and suggest a computationally sound heuristics as an enhancement.
- \textit{Grail}: A C++ library for automata and expressions
- A linear time solution to the single function coarsest partition problem
- Algebraic and structural automata theory. Transl. of algebraiczna i structuralna teoria automatów (PWN, Warsaw, 1985)
- An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata
- AUTOMATE, a computing package for automata and finite semigroups
- Describing an algorithm by Hopcroft
- scientific article; zbMATH DE number 3854429 (Why is no real title available?)
- scientific article; zbMATH DE number 3856413 (Why is no real title available?)
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3460178 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 194781 (Why is no real title available?)
- scientific article; zbMATH DE number 742905 (Why is no real title available?)
- scientific article; zbMATH DE number 3307592 (Why is no real title available?)
- Implementing Quicksort programs
- Minimisation of acyclic deterministic automata in linear time
- Partitioning a graph in \(O(|A|\log_ 2|V|)\)
- Quicksort
- Three Partition Refinement Algorithms
- On the Hopcroft's minimization technique for DFA and DFCA
- An algorithm to compute the character access count distribution for pattern matching algorithms
- A reduction technique for weighted grouping problems
- On extremal cases of Hopcroft's algorithm
- From generic partition refinement to weighted tree automata minimization
- Minimisation of automata
- Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
- Average case analysis of Moore's state minimization algorithm
- Revisiting Shinohara's algorithm for computing descriptive patterns
- Minimal separating sequences for all pairs of states
- Efficient deterministic finite automata split-minimization derived from Brzozowski's algorithm
- Hopcroft's algorithm and tree-like automata
- Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
- Hopcroft’s Algorithm and Cyclic Automata
- Hopcroft’s Minimization Technique: Queues or Stacks?
- Bisimilarity Minimization in O(m logn) Time
- On Extremal Cases of Hopcroft’s Algorithm
- A graph theoretic approach to automata minimality
- Fast brief practical DFA minimization
- Cycle-aware minimization of acyclic deterministic finite-state automata
- Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence
- Efficient Coalgebraic Partition Refinement
- Efficient and modular coalgebraic partition refinement
- Around Hopcroft’s Algorithm
- Subsequential transducers: a coalgebraic perspective
- Construction of minimal deterministic finite automata from biological motifs
- Distributed coalgebraic partition refinement
- Generic partition refinement and weighted tree automata
- Explicit Hopcroft's trick in categorical partition refinement
- Linear kernels and linear-time algorithms for finding large cuts
- Circular Sturmian words and Hopcroft's algorithm
- Average complexity of Moore's and Hopcroft's algorithms
- An automata-theoretic approach to the word problem for \(\omega\)-terms over R
- A split-based incremental deterministic automata minimization algorithm
- Description and analysis of a bottom-up DFA minimization algorithm
- A search algorithm for subshift attractors of cellular automata
This page was built for publication: Re-describing an algorithm by Hopcroft
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589443)
