Symmetric Strategy Improvement

DOI10.1007/978-3-662-47666-6_31zbMath1440.91005arXiv1501.06484OpenAlexW1495265525MaRDI QIDQ3449491

Ashutosh Trivedi, Sven Schewe, Thomas Varghese

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.06484

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05)

Related Items (8)

Symmetric Strategy Improvement ⋮ Unnamed Item ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A delayed promotion policy for parity games

Uses Software

• PGSolver

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Results on the propositional \(\mu\)-calculus
• A combinatorial strongly subexponential strategy improvement algorithm 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
• A subexponential randomized algorithm for the simple stochastic game problem
• A superpolynomial lower bound for strategy iteration based on snare memorization
• A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
• Non-oblivious Strategy Improvement
• An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms
• A Deterministic Subexponential Algorithm for Solving Parity Games
• Symmetric Strategy Improvement
• Alternating-time temporal logic
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Exponential Lower Bounds for Policy Iteration
• 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
• Alternating tree automata, parity games, and modal \(\mu\)-calculus

This page was built for publication: Symmetric Strategy Improvement