Universal algorithms for parity games and nested fixpoints

DOI10.1007/978-3-031-22337-2_12zbMath1528.68404arXiv2001.04333OpenAlexW4312611483MaRDI QIDQ6113979

Rémi Morvan, Marcin Jurdziński, K. S. Thejaswini

Publication date: 10 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.04333

zbMATH Keywords

parity gamesfixpoint equationssymbolic algorithmsquasi-polynomial algorithmuniversal treesattractor decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Games involving graphs (91A43)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Symbolic model checking: \(10^{20}\) states and beyond
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• Fast and simple nested fixpoints
• Quasipolynomial computation of nested fixpoints
• Optimal satisfiability checking for arithmetic \(\mu\)-calculi
• Practical synthesis of reactive systems from LTL specifications via parity games
• Lattice-theoretic progress measures and coalgebraic model checking
• Qualitative concurrent parity games
• A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
• Recursive algorithm for parity games requires exponential time
• The mu-calculus and Model Checking
• Exponential Lower Bounds for Policy Iteration
• Deciding parity games in quasipolynomial time
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• A modal μ perspective on solving parity games in quasi-polynomial time
• Quasipolynomial Set-Based Symbolic Algorithms for Parity Games
• Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
• Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

This page was built for publication: Universal algorithms for parity games and nested fixpoints