Deciding parity games in quasipolynomial time
From MaRDI portal
Publication:4977976
DOI10.1145/3055399.3055409zbMATH Open1369.68234OpenAlexW2586521831MaRDI QIDQ4977976FDOQ4977976
Authors: Sanjay Jain, Bakhadyr Khoussainov, Wei Li, Cristian S. Calude, Frank Stephan 
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
Recommendations
Cited In (85)
- Title not available (Why is that?)
- Improving parity games in practice
- Deciding Parity Games in Quasi-polynomial Time
- Title not available (Why is that?)
- Title not available (Why is that?)
- An Accelerated Algorithm for 3-Color Parity Games with an Application to Timed Games
- Bounded game-theoretic semantics for modal mu-calculus
- Width of Non-deterministic Automata
- Parity to Safety in Polynomial Time for Pushdown and Collapsible Pushdown Systems
- On the complexity of rational verification
- Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
- Timed games with bounded window parity objectives
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Theory of Universal Graphs for Infinite Duration Games
- Solving parity games via priority promotion
- Title not available (Why is that?)
- Abstract tropical linear programming
- Approximation schemes for stochastic mean payoff games with perfect information and few random positions
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Hyperplane separation technique for multidimensional mean-payoff games
- Title not available (Why is that?)
- Title not available (Why is that?)
- New deterministic algorithms for solving parity games
- Title not available (Why is that?)
- Automated temporal equilibrium analysis: verification and synthesis of multi-player games
- Title not available (Why is that?)
- A cure for stuttering parity games
- Büchi Good-for-Games Automata Are Efficiently Recognizable
- Linear temporal logic -- from infinite to finite horizon
- A delayed promotion policy for parity games
- Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
- Title not available (Why is that?)
- Time and Parallelizability Results for Parity Games with Bounded Tree and DAG Width
- Reachability games and parity games
- Quasipolynomial computation of nested fixpoints
- Approximating the minimal lookahead needed to win infinite games
- Title not available (Why is that?)
- Title not available (Why is that?)
- A computation model with automatic functions and relations as primitive operations
- Robust, expressive, and quantitative linear temporal logics: pick any two for free
- Synthesis of Data Word Transducers
- Title not available (Why is that?)
- Cooking Your Own Parity Game Preorders Through Matching Plays
- A convex programming-based algorithm for mean payoff stochastic games with perfect information
- Title not available (Why is that?)
- Finite-state strategies in delay games
- Robust worst cases for parity games algorithms
- Justifications and a reconstruction of parity game solving algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Infinite-duration poorman-bidding games
- Synthesizing optimally resilient controllers
- On the Way to Alternating Weak Automata
- Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints
- $\aleph_1$ and the modal $\mu$-calculus
- Universal algorithms for parity games and nested fixpoints
- The GKK algorithm is the fastest over simple mean-payoff games
- Synthesizing Optimally Resilient Controllers
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
- On Nash-solvability of \(n\)-person graphical games under Markov and a-priori realizations
- Improved complexity analysis of quasi-polynomial algorithms solving parity games
- Church synthesis on register automata over linearly ordered data domains
- Combinations of Qualitative Winning for Stochastic Parity Games
- Complexity results for modal logic with recursion via translations and tableaux
- Operations on fixpoint equation systems
- Token Games and History-Deterministic Quantitative-Automata
- Priority promotion with Parysian flair
- Parity games on temporal graphs
- Symbolic solution of Emerson-Lei games for reactive synthesis
- Synthesis with privacy against an observer
- Systems of fixpoint equations: abstraction, games, up-to techniques and local algorithms
- New algorithms for combinations of objectives using separating automata
- On the size of disjunctive formulas in the \(\mu\)-calculus
- Size measures and alphabetic equivalence in the \(\mu \)-calculus
- Perspective games
- A survey on satisfiability checking for the \(\mu \)-calculus through tree automata
- On-the-fly solving for symbolic parity games
- Proof systems for the modal \(\mu \)-calculus obtained by determinizing automata
- Adaptive strategies for rLTL games
This page was built for publication: Deciding parity games in quasipolynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977976)
