Deciding the winner in parity games is in UP-UP
From MaRDI portal
Publication:293426
Recommendations
Cites work
- Alternating automata with start formulas
- 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
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3990873 (Why is no real title available?)
- On model checking for the -calculus and its fragments
- Positional strategies for mean payoff games
- Self-witnessing polynomial-time complexity and prime factorization
- The complexity of mean payoff games on graphs
- The complexity of stochastic games
Cited in
(only showing first 100 items - show all)- Mu-calculus path checking
- Parity game reductions
- A convex programming-based algorithm for mean payoff stochastic games with perfect information
- Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
- Solving parity games via priority promotion
- A delayed promotion policy for parity games
- Is your model checker on time? On the complexity of model checking for timed modal logics
- Improving parity games in practice
- Robust worst cases for parity games algorithms
- Abstract tropical linear programming
- Infinite-duration poorman-bidding games
- Automated temporal equilibrium analysis: verification and synthesis of multi-player games
- Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
- Computational complexity, Newton polytopes, and Schubert polynomials
- Looking at mean-payoff and total-payoff through windows
- On the universal and existential fragments of the \(\mu\)-calculus
- Average-energy games
- Fixpoint logics over hierarchical structures
- A superpolynomial lower bound for strategy iteration based on snare memorization
- A note on the approximation of mean-payoff games
- Mean-payoff games with partial observation
- Solving parity games using an automata-based algorithm
- Template-based unbounded time verification of affine hybrid automata
- Two local strategy iteration schemes for parity game solving
- Parameterized Algorithms for Parity Games
- Recursive algorithm for parity games requires exponential time
- The mu-calculus and Model Checking
- Graph Games and Reactive Synthesis
- From Parity and Payoff Games to Linear Programming
- Measuring Permissivity in Finite Games
- Exponential examples of solving parity games
- scientific article; zbMATH DE number 7445162 (Why is no real title available?)
- scientific article; zbMATH DE number 7447732 (Why is no real title available?)
- Solving parity games in big steps
- The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
- A CSP-Based Approach for Solving Parity Game
- Value Iteration
- The Descriptive Complexity of Parity Games
- Infinite Runs in Weighted Timed Automata with Energy Constraints
- Solving μ-Calculus Parity Games by Symbolic Planning
- Solving parity games in practice
- On canonical forms for zero-sum stochastic mean payoff games
- Alternating traps in Muller and parity games
- A survey of stochastic -regular games
- Solving parity games by a reduction to SAT
- The complexity of all-switches strategy improvement
- Computational tameness of classical non-causal models
- Incentive Stackelberg mean-payoff games
- Equilibria, fixed points, and complexity classes
- ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
- Achieving new upper bounds for the hypergraph duality problem through logic
- On solving mean payoff games using pivoting algorithms
- The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
- Permissive strategies: from parity games to safety games
- Model Checking Games
- _1 and the modal -calculus
- Obligation Blackwell games and p-automata
- Polynomial-time under-approximation of winning regions in parity games
- Average-energy games
- Partial solvers for parity games: effective polynomial-time composition
- A delayed promotion policy for parity games
- Window parity games: an alternative approach toward parity games with time bounds
- A parity game tale of two counters
- Simple fixpoint iteration to solve parity games
- scientific article; zbMATH DE number 7455738 (Why is no real title available?)
- A recursive approach to solving parity games in quasipolynomial time
- Games where you can play optimally with arena-independent finite memory
- Deciding Parity Games in Quasi-polynomial Time
- scientific article; zbMATH DE number 7533361 (Why is no real title available?)
- scientific article; zbMATH DE number 7559480 (Why is no real title available?)
- Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
- Register games
- Life is random, time is not: Markov decision processes with window objectives
- Solving mean-payoff games via quasi dominions
- Reactive synthesis without regret
- Parity games with weights
- Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
- Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games
- Faster algorithms for mean-payoff games
- Three notes on the complexity of model checking fixpoint logic with chop
- More Precise Partition Abstractions
- Model Checking for Action Abstraction
- The Complexity of Nash Equilibria in Infinite Multiplayer Games
- Solving Parity Games in Big Steps
- Life is random, time is not: Markov decision processes with window objectives
- On model checking for the -calculus and its fragments
- Improved complexity analysis of quasi-polynomial algorithms solving parity games
- The stochastic arrival problem
- Complexity through translations for modal logic with recursion
- Solving mean-payoff games via quasi dominions
- A matrix-based approach to parity games
- Guessing winning policies in LTL synthesis by semantic learning
- From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
- Complexity results for modal logic with recursion via translations and tableaux
- Priority promotion with Parysian flair
- Stochastic window mean-payoff games
- Parity games on temporal graphs
- Checking history-determinism is NP-hard for parity automata
- A quasi-polynomial black-box algorithm for fixed point evaluation
- An objective improvement approach to solving discounted payoff games
This page was built for publication: Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293426)
