An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
From MaRDI portal
Publication:1959648
DOI10.1016/j.tcs.2010.05.029zbMath1206.68173OpenAlexW2090431024MaRDI QIDQ1959648
Andreas Maletti, Markus Holzer
Publication date: 7 October 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.05.029
Related Items (10)
OPTIMAL HYPER-MINIMIZATION ⋮ The tractability frontier for NFA minimization ⋮ HYPER-MINIMIZATION FOR DETERMINISTIC TREE AUTOMATA ⋮ UNWEIGHTED AND WEIGHTED HYPER-MINIMIZATION ⋮ Minimal and Hyper-Minimal Biautomata ⋮ Better Hyper-minimization ⋮ FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS ⋮ Closure properties of hyper-minimized automata ⋮ Hyper-optimization for deterministic tree automata ⋮ More on Minimizing Finite Automata with Errors — Nondeterministic Machines
Cites Work
- Unnamed Item
- 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
- Hyper-minimisation Made Efficient
- HYPER-MINIMIZATION IN O(n2)
- Hopcroft’s Algorithm and Cyclic Automata
- Hyper-minimizing minimized deterministic finite state automata
- Hyper-Minimization in O(n 2)
- An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
- 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 \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
