Succinct progress measures for solving parity games

MaRDI QIDQ5144638zbMATH OpenFDO

Authors Marcin Jurdziński, Ranko Lazić

Publication date 19 January 2021

Full work available at URL https://arxiv.org/abs/1702.05051, http://dl.acm.org/citation.cfm?id=3330027

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1500523
• A brief excursion to parity games
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• Deciding parity games in quasipolynomial time
• Universal trees grow inside separating automata: quasi-polynomial lower bounds for parity games

Cited in

(48)

• A brief excursion to parity games
• Solving parity games via priority promotion
• Improving parity games in practice
• Quasipolynomial computation of nested fixpoints
• Bounded game-theoretic semantics for modal mu-calculus
• Finite-state strategies in delay games
• Robust worst cases for parity games algorithms
• Synthesizing optimally resilient controllers
• Winning Regions of Pushdown Parity Games: A Saturation Method
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• Finite-state strategies in delay games
• A comparison of BDD-based parity game solvers
• scientific article; zbMATH DE number 1500523 (Why is no real title available?)
• The complexity of all-switches strategy improvement
• Parity to safety in polynomial time for pushdown and collapsible pushdown systems
• Improvement in small progress measures
• A parity game tale of two counters
• Simple fixpoint iteration to solve parity games
• 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
• A modal \(\mu\) perspective on solving parity games in quasi-polynomial time
• Solving mean-payoff games via quasi dominions
• Quasipolynomial set-based symbolic algorithms for parity games
• Universal trees grow inside separating automata: quasi-polynomial lower bounds for parity games
• Combinations of Qualitative Winning for Stochastic Parity Games
• Alternating weak automata from universal trees
• Universal algorithms for parity games and nested fixpoints
• Improved complexity analysis of quasi-polynomial algorithms solving parity games
• On-the-fly solving for symbolic parity games
• Complexity results for modal logic with recursion via translations and tableaux
• A quasi-polynomial black-box algorithm for fixed point evaluation
• On the complexity of multi-pushdown games
• The Strahler number of a parity game
• The worst-case complexity of symmetric strategy improvement
• Lookahead games and efficient determinisation of history-deterministic Büchi automata
• Beyond value iteration for parity games: strategy iteration with universal trees
• Real equation systems with alternating fixed-points
• Deciding regular games: a playground for exponential time algorithms
• A direct reduction from stochastic parity games to simple stochastic games
• Improving parity game solvers with justifications

This page was built for publication: Succinct progress measures for solving parity games

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