Simple stochastic games with almost-sure energy-parity objectives are in NP and conp

DOI10.1007/978-3-030-71995-1_22OpenAlexW3140150357MaRDI QIDQ2233425

Richard Mayr, Sven Schewe, Dominik Wojtczak, Patrick Totzke

Publication date: 18 October 2021

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

zbMATH Keywords

parity gamesenergy gamessimple stochastic games

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (3)

Submixing and shift-invariant stochastic games ⋮ Unnamed Item ⋮ Simple stochastic games with almost-sure energy-parity objectives are in NP and conp

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}\)
• Fun with fireWire: A comparative study of formal verification methods applied to the IEEE 1394 root contention protocol
• Undecidable problems for probabilistic automata of fixed dimension
• Energy parity games
• Approximating the termination value of one-counter MDPs and stochastic games
• Optimizing the expected mean payoff in energy Markov decision processes
• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• The complexity of multi-mean-payoff and multi-energy games
• Qualitative Analysis of VASS-Induced MDPs
• Solving Parity Games on Integer Vectors
• One-Counter Stochastic Games
• Energy and Mean-Payoff Parity Markov Decision Processes
• Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time
• Alternating-time temporal logic
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Exponential Lower Bounds for Policy Iteration
• Energy Parity Games
• Supervisory Control of a Class of Discrete Event Processes
• The determinacy of Blackwell games
• Zero-reachability in probabilistic multi-counter automata
• Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• Computer Science Logic
• Markov Decision Processes with Multiple Long-run Average Objectives
• Perfect-Information Stochastic Mean-Payoff Parity Games
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• Decisive Markov Chains
• Automata, Languages and Programming
• Generalized Parity Games
• Stochastic Games
• Alternating tree automata, parity games, and modal \(\mu\)-calculus

This page was built for publication: Simple stochastic games with almost-sure energy-parity objectives are in NP and conp