Büchi Automata Can Have Smaller Quotients

DOI10.1007/978-3-642-22012-8_20zbMath1333.68159OpenAlexW1696271966MaRDI QIDQ3012925

Lorenzo Clemente

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

Mathematics Subject Classification ID

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

Related Items

Parity game reductions, Simulation relations and applications in formal methods, Minimization of Visibly Pushdown Automata Using Partial Max-SAT, Büchi Automata Can Have Smaller Quotients

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