An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton

DOI10.1007/978-3-642-02979-0_4zbMath1248.68301OpenAlexW2010588138MaRDI QIDQ3637336

Markus Holzer, Andreas Maletti

Publication date: 9 July 2009

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02979-0_4

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

Hyper-minimisation Made Efficient ⋮ An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton ⋮ Better Hyper-minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Path-based depth-first search for strong and biconnected components
• On the Hopcroft's minimization technique for DFA and DFCA
• A strong-connectivity algorithm and its applications in data flow analysis
• Algorithms for dense graphs and networks on the random access computer
• Hopcroft’s Algorithm and Cyclic Automata
• Hyper-minimizing minimized deterministic finite state automata
• Hyper-Minimization in O(n 2)
• Minimal NFA Problems are Hard
• Implementation and Application of Automata
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• Depth-First Search and Linear Graph Algorithms
• Minimal cover-automata for finite languages

This page was built for publication: An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton