Deciding parity games in quasipolynomial time
From MaRDI portal
Publication:4977976
DOI10.1145/3055399.3055409zbMath1369.68234OpenAlexW2586521831MaRDI QIDQ4977976
Bakhadyr Khoussainov, Wei Li, Sanjay Jain, Frank Stephan, Cristian S. Calude
Publication date: 17 August 2017
Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3055399.3055409
Related Items (66)
Hyperplane separation technique for multidimensional mean-payoff games ⋮ The Theory of Universal Graphs for Infinite Duration Games ⋮ Cooking Your Own Parity Game Preorders Through Matching Plays ⋮ $\aleph_1$ and the modal $\mu$-calculus ⋮ Unnamed Item ⋮ Linear temporal logic -- from infinite to finite horizon ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Width of Non-deterministic Automata ⋮ Finite-state strategies in delay games ⋮ Robust worst cases for parity games algorithms ⋮ Approximating the minimal lookahead needed to win infinite games ⋮ Robust, expressive, and quantitative linear temporal logics: pick any two for free ⋮ A computation model with automatic functions and relations as primitive operations ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Abstract tropical linear programming ⋮ Infinite-duration poorman-bidding games ⋮ Reachability games and parity games ⋮ A survey on satisfiability checking for the \(\mu \)-calculus through tree automata ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Adaptive strategies for rLTL games ⋮ On the complexity of rational verification ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Church synthesis on register automata over linearly ordered data domains ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Justifications and a reconstruction of parity game solving algorithms ⋮ Token Games and History-Deterministic Quantitative-Automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Automated temporal equilibrium analysis: verification and synthesis of multi-player games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Synthesis of Data Word Transducers ⋮ Combinations of Qualitative Winning for Stochastic Parity Games ⋮ Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems ⋮ Solving parity games via priority promotion ⋮ Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions ⋮ New deterministic algorithms for solving parity games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A delayed promotion policy for parity games ⋮ Improving parity games in practice ⋮ Quasipolynomial computation of nested fixpoints ⋮ Unnamed Item ⋮ Synthesizing Optimally Resilient Controllers ⋮ Synthesizing optimally resilient controllers ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Büchi Good-for-Games Automata Are Efficiently Recognizable ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ On the Way to Alternating Weak Automata ⋮ The GKK algorithm is the fastest over simple mean-payoff games ⋮ Bounded game-theoretic semantics for modal mu-calculus ⋮ Timed games with bounded window parity objectives
This page was built for publication: Deciding parity games in quasipolynomial time
