A modal perspective on solving parity games in quasi-polynomial time

DOI10.1145/3209108.3209115MaRDI QIDQ5145340zbMATH OpenOpenAlexFDO

Authors Karoliina Lehtinen

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3209108.3209115

zbMATH Keywords

algorithmic complexitydescriptive complexitymodal \(\mu\) calculusparity games

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43)

Recommendations

• Deciding parity games in quasipolynomial time
• A brief excursion to parity games
• scientific article; zbMATH DE number 1500523
• Succinct progress measures for solving parity games
• Solving Parity Games in Big Steps

Cited in

(39)

• A brief excursion to parity games
• Improving parity games in practice
• Quasipolynomial computation of nested fixpoints
• Finite-state strategies in delay games
• Robust worst cases for parity games algorithms
• Synthesizing optimally resilient controllers
• Solving parity games in big steps
• Solving μ-Calculus Parity Games by Symbolic Planning
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• Deciding parity games in quasipolynomial time
• A recursive approach to solving parity games in quasipolynomial time
• The Theory of Universal Graphs for Infinite Duration Games
• Deciding Parity Games in Quasi-polynomial Time
• scientific article; zbMATH DE number 7533361 (Why is no real title available?)
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• scientific article; zbMATH DE number 7559481 (Why is no real title available?)
• On the Way to Alternating Weak Automata
• A faster deterministic exponential time algorithm for energy games and mean payoff games
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• Register games
• Succinct progress measures for solving parity games
• Quasipolynomial set-based symbolic algorithms for parity games
• Parity games with weights
• Universal trees grow inside separating automata: quasi-polynomial lower bounds for parity games
• Solving Parity Games in Big Steps
• Alternating weak automata from universal trees
• Good for games automata: from nondeterminism to alternation
• Reachability games and parity games
• Universal algorithms for parity games and nested fixpoints
• Improved complexity analysis of quasi-polynomial algorithms solving parity games
• Complexity results for modal logic with recursion via translations and tableaux
• Priority promotion with Parysian flair
• Systems of fixpoint equations: abstraction, games, up-to techniques and local algorithms
• A quasi-polynomial black-box algorithm for fixed point evaluation
• The Strahler number of a parity game
• Beyond value iteration for parity games: strategy iteration with universal trees
• Exponential time algorithms for deciding regular games
• Deciding regular games: a playground for exponential time algorithms
• A direct reduction from stochastic parity games to simple stochastic games

This page was built for publication: A modal \(\mu\) perspective on solving parity games in quasi-polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145340)