Beyond Hyper-Minimisation--Minimising DBAs and DPAs is NP-Complete
From MaRDI portal
Publication:2908870
DOI10.4230/LIPIcs.FSTTCS.2010.400zbMath1245.68096OpenAlexW1534702427MaRDI QIDQ2908870
Publication date: 29 August 2012
Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_95de.html
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (20)
Learning infinite-word automata with loop-index queries ⋮ Good-for-MDPs Automata for Probabilistic Analysis and Reinforcement Learning ⋮ Automata Theory and Model Checking ⋮ Linear temporal logic -- from infinite to finite horizon ⋮ Certifying DFA bounds for recognition and separation ⋮ Multi-Valued Reasoning about Reactive Systems ⋮ On Minimization and Learning of Deterministic ω-Automata in the Presence of Don’t Care Words ⋮ Simulation relations and applications in formal methods ⋮ Minimization of automata for liveness languages ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Certifying inexpressibility ⋮ Büchi Automata Can Have Smaller Quotients ⋮ Regular \(\omega\)-languages with an informative right congruence ⋮ Computing All ℓ-Cover Automata Fast ⋮ Unnamed Item ⋮ Sensing as a Complexity Measure ⋮ Minimizing GFG Transition-Based Automata ⋮ \( \omega \)-automata ⋮ Hyper-optimization for deterministic tree automata
This page was built for publication: Beyond Hyper-Minimisation--Minimising DBAs and DPAs is NP-Complete
