From equivalence to almost-equivalence, and beyond-minimizing automata with errors (extended abstract)

DOI10.1007/978-3-642-31653-1_18MaRDI QIDQ3167495zbMATH OpenOpenAlexFDO

Authors Markus Holzer, Sebastian Jakobi

Publication date 2 November 2012

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31653-1_18

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS
• More on Minimizing Finite Automata with Errors — Nondeterministic Machines
• On minimising automata with errors
• Hyper-Minimization in O(n 2)
• Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete

Cited in

(7)

• Hyper-optimization for deterministic tree automata
• More on Minimizing Finite Automata with Errors — Nondeterministic Machines
• Boundary sets of regular and context-free languages
• Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete
• On minimising automata with errors
• scientific article; zbMATH DE number 7439745 (Why is no real title available?)
• FROM EQUIVALENCE TO ALMOST-EQUIVALENCE, AND BEYOND: MINIMIZING AUTOMATA WITH ERRORS

This page was built for publication: From equivalence to almost-equivalence, and beyond-minimizing automata with errors (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167495)