Re-describing an algorithm by Hopcroft (Q1589443): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Q4091421 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An O(n \text{log} n) implementation of the standard method for minimizing n-state finite automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3325046 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4692772 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Partitioning a graph in \(O(|A|\log_ 2|V|)\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: AUTOMATE, a computing package for automata and finite semigroups / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3619797 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3323279 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Describing an algorithm by Hopcroft / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quicksort / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4045961 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3862379 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algebraic and structural automata theory. Transl. of algebraiczna i structuralna teoria automatów (PWN, Warsaw, 1985) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Three Partition Refinement Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: A linear time solution to the single function coarsest partition problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: \textit{Grail}: A C++ library for automata and expressions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Minimisation of acyclic deterministic automata in linear time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5588675 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Implementing Quicksort programs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4763344 / rank
 
Normal rank

Revision as of 10:11, 3 June 2024

scientific article
Language Label Description Also known as
English
Re-describing an algorithm by Hopcroft
scientific article

    Statements

    Re-describing an algorithm by Hopcroft (English)
    0 references
    12 December 2000
    0 references
    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.
    0 references
    finite automata
    0 references
    algorithms
    0 references
    minimization
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers