On the complexity of Hopcroft's state minimization algorithm

DOI10.1007/978-3-540-30500-2_4MaRDI QIDQ5464005zbMATH OpenOpenAlexFDO

Authors Jean Berstel, Olivier Carton

Publication date 17 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b105090

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Hopcroft’s Algorithm and Cyclic Automata
• On extremal cases of Hopcroft's algorithm
• Average complexity of Moore's and Hopcroft's algorithms
• A challenging family of automata for classical minimization algorithms
• On Extremal Cases of Hopcroft’s Algorithm

Cited in

(26)

• On the Hopcroft's minimization technique for DFA and DFCA
• Re-describing an algorithm by Hopcroft
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• On extremal cases of Hopcroft's algorithm
• Minimisation of automata
• Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Hopcroft's algorithm and tree-like automata
• A challenging family of automata for classical minimization algorithms
• Forward bisimulations for nondeterministic symbolic finite automata
• Hopcroft’s Algorithm and Cyclic Automata
• The average complexity of Moore's state minimization algorithm is O( n n)
• Hopcroft’s Minimization Technique: Queues or Stacks?
• Deterministic Pushdown Automata and Unary Languages
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• On Extremal Cases of Hopcroft’s Algorithm
• A graph theoretic approach to automata minimality
• scientific article; zbMATH DE number 4119632 (Why is no real title available?)
• Standard Sturmian words and automata minimization algorithms
• Morphisms and Minimisation of Weighted Automata
• Epichristoffel Words and Minimization of Moore Automata
• On the average complexity of Moore's state minimization algorithm
• Lowerbounds for Bisimulation by Partition Refinement
• Circular Sturmian words and Hopcroft's algorithm
• Average complexity of Moore's and Hopcroft's algorithms
• The state complexity of \(L^{2}\) and \(L^k\)

This page was built for publication: On the complexity of Hopcroft's state minimization algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5464005)