Büchi Automata Can Have Smaller Quotients
From MaRDI portal
Publication:3012925
DOI10.1007/978-3-642-22012-8_20zbMath1333.68159MaRDI QIDQ3012925
Publication date: 7 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22012-8_20
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Simulation relations and applications in formal methods, Parity game reductions, Büchi Automata Can Have Smaller Quotients, Minimization of Visibly Pushdown Automata Using Partial Max-SAT
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simulation relations for alternating Büchi automata
- Fair simulation
- Forward and backward simulations. I. Untimed Systems
- Minimizing nfa's and regular expressions
- Beyond Hyper-Minimisation--Minimising DBAs and DPAs is NP-Complete
- Büchi Automata Can Have Smaller Quotients
- Weak alternating automata are not that weak
- Multipebble Simulations for Alternating Automata
- Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
- Minimizing Generalized Büchi Automata