More on Minimizing Finite Automata with Errors — Nondeterministic Machines

DOI10.1142/S0129054117500150zbMath1371.68151OpenAlexW2615308287MaRDI QIDQ5268394

Markus Holzer, Sebastian Jakobi

Publication date: 20 June 2017

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

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

zbMATH Keywords

computational complexitynondeterministic finite automataalmost-equivalence\(E\)-equivalenceminimal finite automata

Mathematics Subject Classification ID

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

Cites Work

• The parallel complexity of finite-state automata problems
• Intersection and union of regular languages and state complexity
• On the equivalence, containment, and covering problems for the regular and context-free languages
• An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton
• Relationships between nondeterministic and deterministic tape complexities
• HYPER-MINIMIZATION IN O(n²)
• Computational Parallels between the Regular and Context-Free Languages
• Minimal NFA Problems are Hard
• FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS

This page was built for publication: More on Minimizing Finite Automata with Errors — Nondeterministic Machines