Minimal and Hyper-Minimal Biautomata

DOI10.1142/S0129054116400050zbMath1338.68148OpenAlexW3022901100MaRDI QIDQ5890813

Markus Holzer, Sebastian Jakobi

Publication date: 23 June 2016

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

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

zbMATH Keywords

computational complexityminimization problemalmost-equivalencebiautomatahyper-minimality

Mathematics Subject Classification ID

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

Cites Work

• Descriptional and computational complexity of finite automata -- a survey
• The method of forced enumeration for nondeterministic automata
• The parallel complexity of finite-state automata problems
• Space-bounded reducibility among combinatorial problems
• On the complexity of the parity argument and other inefficient proofs of existence
• An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
• Nondeterministic Space is Closed under Complementation
• New problems complete for nondeterministic log space
• FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
• Derivatives of Regular Expressions