FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS

DOI10.1142/S0129054113400327zbMath1293.68169OpenAlexW2057653105MaRDI QIDQ5495421

Sebastian Jakobi, Markus Holzer

Publication date: 4 August 2014

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054113400327

zbMATH Keywords

computational complexityalmost-equivalenceminimal finite automata

Mathematics Subject Classification ID

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

Related Items (4)

More on Deterministic and Nondeterministic Finite Cover Automata ⋮ Minimal and Hyper-Minimal Biautomata ⋮ More on Minimizing Finite Automata with Errors — Nondeterministic Machines ⋮ More on deterministic and nondeterministic finite cover automata

Cites Work

• The complexity of computing the permanent
• The method of forced enumeration for nondeterministic automata
• The parallel complexity of finite-state automata problems
• A very hard log-space counting class
• Space-bounded reducibility among combinatorial problems
• An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
• Polynomial Space Counting Problems
• OPTIMAL HYPER-MINIMIZATION
• HYPER-MINIMIZATION IN O(n²)
• Nondeterministic Space is Closed under Complementation
• The Complexity of Enumeration and Reliability Problems
• New problems complete for nondeterministic log space

This page was built for publication: FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS