Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
From MaRDI portal
Publication:293426
DOI10.1016/S0020-0190(98)00150-1zbMath1338.68109OpenAlexW2142133061MaRDI QIDQ293426
Publication date: 9 June 2016
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001501?np=y
Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (98)
Equilibria for games with combined qualitative and quantitative objectives ⋮ On the universal and existential fragments of the \(\mu\)-calculus ⋮ Permissive strategies: from parity games to safety games ⋮ Template-Based Unbounded Time Verification of Affine Hybrid Automata ⋮ The mu-calculus and Model Checking ⋮ Graph Games and Reactive Synthesis ⋮ $\aleph_1$ and the modal $\mu$-calculus ⋮ TWO LOCAL STRATEGY ITERATION SCHEMES FOR PARITY GAME SOLVING ⋮ Mean-payoff games with partial observation ⋮ From Parity and Payoff Games to Linear Programming ⋮ Measuring Permissivity in Finite Games ⋮ Exponential examples of solving parity games ⋮ Computational tameness of classical non-causal models ⋮ Solving parity games in big steps ⋮ The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete ⋮ Parity game reductions ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Incentive Stackelberg Mean-Payoff Games ⋮ On canonical forms for zero-sum stochastic mean payoff games ⋮ Unnamed Item ⋮ Average-energy games ⋮ Alternating traps in Muller and parity games ⋮ Robust worst cases for parity games algorithms ⋮ Parameterized Algorithms for Parity Games ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Abstract tropical linear programming ⋮ Infinite-duration poorman-bidding games ⋮ A CSP-Based Approach for Solving Parity Game ⋮ A survey of stochastic \(\omega \)-regular games ⋮ Solving parity games by a reduction to SAT ⋮ Continuous Positional Payoffs ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Unnamed Item ⋮ The stochastic arrival problem ⋮ Value Iteration ⋮ Fixpoint logics over hierarchical structures ⋮ Solving mean-payoff games via quasi dominions ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP ⋮ Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games ⋮ Unnamed Item ⋮ 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 ⋮ Equilibria, fixed points, and complexity classes ⋮ A superpolynomial lower bound for strategy iteration based on snare memorization ⋮ A note on the approximation of mean-payoff games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Descriptive Complexity of Parity Games ⋮ Infinite Runs in Weighted Timed Automata with Energy Constraints ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Simple stochastic games with almost-sure energy-parity objectives are in NP and conp ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Solving parity games via priority promotion ⋮ Reactive synthesis without regret ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games ⋮ Model Checking Games ⋮ New deterministic algorithms for solving parity games ⋮ Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games ⋮ Reduction of stochastic parity to stochastic mean-payoff games ⋮ Faster algorithms for mean-payoff games ⋮ On model checking for the \(\mu\)-calculus and its fragments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Mean-payoff games and propositional proofs ⋮ Unnamed Item ⋮ Three notes on the complexity of model checking fixpoint logic with chop ⋮ A delayed promotion policy for parity games ⋮ On Solving Mean Payoff Games Using Pivoting Algorithms ⋮ More Precise Partition Abstractions ⋮ Model Checking for Action Abstraction ⋮ Solving μ-Calculus Parity Games by Symbolic Planning ⋮ The Complexity of Nash Equilibria in Infinite Multiplayer Games ⋮ Solving Parity Games in Big Steps ⋮ Improving parity games in practice ⋮ Unnamed Item ⋮ Computational complexity, Newton polytopes, and Schubert polynomials ⋮ OBLIGATION BLACKWELL GAMES AND P-AUTOMATA ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Polynomial-Time Under-Approximation of Winning Regions in Parity Games ⋮ Solving Parity Games Using an Automata-Based Algorithm ⋮ Solving Parity Games in Practice ⋮ Unnamed Item ⋮ Recursive algorithm for parity games requires exponential time ⋮ Mu-calculus path checking ⋮ Is your model checker on time? On the complexity of model checking for timed modal logics ⋮ Looking at mean-payoff and total-payoff through windows
Cites Work
- Unnamed Item
- Unnamed Item
- Alternating automata with start formulas
- Positional strategies for mean payoff games
- The complexity of stochastic games
- Self-witnessing polynomial-time complexity and prime factorization
- The complexity of mean payoff games on graphs
- Computer aided verification. 8th international conference, CAV '96, New Brunswick, NJ, USA, July 31 -- August 3, 1996. Proceedings
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- On model checking for the \(\mu\)-calculus and its fragments
This page was built for publication: Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
