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

DOI10.1007/978-3-642-31653-1_18zbMATH Open1370.68175OpenAlexW12503799MaRDI QIDQ3167495FDOQ3167495

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

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

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)

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
• Title not available (Why is that?)
• 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)