From Parity and Payoff Games to Linear Programming
From MaRDI portal
Publication:3182965
DOI10.1007/978-3-642-03816-7_57zbMath1250.68131OpenAlexW1551906639MaRDI QIDQ3182965
Publication date: 16 October 2009
Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_57
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) 2-person games (91A05) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items
Tropicalizing the Simplex Algorithm ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Incentive Stackelberg Mean-Payoff Games ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Abstract tropical linear programming ⋮ A note on the approximation of mean-payoff games ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions ⋮ Faster algorithms for mean-payoff games
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- A new polynomial-time algorithm for linear programming
- Results on the propositional \(\mu\)-calculus
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- Positional strategies for mean payoff games
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- The complexity of mean payoff games on graphs
- An improved algorithm for the evaluation of fixpoint expressions
- Mathematical problems for the next century
- On the \(\epsilon\)-perturbation method for avoiding degeneracy
- A subexponential randomized algorithm for the simple stochastic game problem
- A randomized polynomial-time simplex algorithm for linear programming
- On the average number of steps of the simplex method of linear programming
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Alternating-time temporal logic
- Cyclic games and an algorithm to find minimax cycle means in directed graphs
- An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
- Smoothed analysis of algorithms
- Synthesis of Asynchronous Systems
- Satisfiability and Finite Model Property for the Alternating-Time μ-Calculus
- From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata
- DAG-Width and Parity Games
- Solving Parity Games in Big Steps
- Computer Aided Verification
- On model checking for the \(\mu\)-calculus and its fragments
- Alternating tree automata, parity games, and modal \(\mu\)-calculus
