Deciding Parity Games in Quasi-polynomial Time
From MaRDI portal
Publication:5073521
DOI10.1137/17M1145288OpenAlexW2999201158WikidataQ126343112 ScholiaQ126343112MaRDI QIDQ5073521
Bakhadyr Khoussainov, Sanjay Jain, Wei Li, Cristian S. Calude, Frank Stephan
Publication date: 3 May 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1145288
Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70)
Related Items (2)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Solving parity games in big steps
- Fundamentals of parameterized complexity
- Alternating traps in Muller and parity games
- The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
- Finite model theory and its applications.
- The isomorphism relation between tree-automatic structures
- Strong computational lower bounds via parameterized complexity
- Graph operations on parity games and polynomial-time algorithms
- Number of quantifiers is better than number of tape cells
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- Fast and simple nested fixpoints
- An improved algorithm for the evaluation of fixpoint expressions
- Fixed-point logics and solitaire games
- Pushdown processes: Games and model-checking
- Memoryless determinacy of parity and mean payoff games: a simple proof
- Strategy synthesis for multi-dimensional quantitative objectives
- The complexity of multi-mean-payoff and multi-energy games
- Dicing on the Streett
- Parametrized complexity theory.
- Solving Parity Games Using an Automata-Based Algorithm
- Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
- Parameterized Algorithms for Parity Games
- Explicit Muller Games are PTIME
- From Parity and Payoff Games to Linear Programming
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Exponential Determinization for ω‐Automata with a Strong Fairness Acceptance Condition
- The Isomorphism Problem for ω-Automatic Trees
- Solving Parity Games in Practice
- On the menbership problem for functional and multivalued dependencies in relational databases
- Alternation
- Bisimulation, modal logic and model checking games
- The Complexity of Decision Versus Search
- On the synthesis of strategies in infinite games
- Permissive strategies: from parity games to safety games
- Deciding parity games in quasipolynomial time
- A modal μ perspective on solving parity games in quasi-polynomial time
- A hierarchy of tree-automatic structures
- From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
- Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
- Solving Parity Games in Big Steps
- Mathematical Foundations of Computer Science 2005
- The complexity of theorem-proving procedures
- Generalized Parity Games
- Perspectives of System Informatics
- Automata theory and its applications
- On model checking for the \(\mu\)-calculus and its fragments
- Alternating tree automata, parity games, and modal \(\mu\)-calculus
This page was built for publication: Deciding Parity Games in Quasi-polynomial Time
