Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata

DOI10.1137/S0097539703420675zbMath1079.68050OpenAlexW1964680921MaRDI QIDQ5317190

Kousha Etessami, Thomas Wilke, Rebecca A. Schuller

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703420675

zbMATH Keywords

parity gamesBüchi automatastate space reductionfair simulation relations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Good-for-MDPs Automata for Probabilistic Analysis and Reinforcement Learning ⋮ Consistent Consequence for Boolean Equation Systems ⋮ Graph Games and Reactive Synthesis ⋮ Computing Stuttering Simulations ⋮ Parity game reductions ⋮ Memory Reduction for Strategies in Infinite Games ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Simulation relations and applications in formal methods ⋮ Mechanizing the Powerset Construction for Restricted Classes of ω-Automata ⋮ New Optimizations and Heuristics for Determinization of Büchi Automata ⋮ Minimization of Visibly Pushdown Automata Using Partial Max-SAT ⋮ Büchi Automata Can Have Smaller Quotients ⋮ Optimizing Winning Strategies in Regular Infinite Games ⋮ Quantitative simulations by matrices ⋮ Categorical Büchi and parity conditions via alternating fixed points of functors ⋮ Advanced Ramsey-Based Büchi Automata Inclusion Testing ⋮ Game-theoretic simulation checking tool ⋮ Efficient on-the-fly Algorithm for Checking Alternating Timed Simulation ⋮ \( \omega \)-automata