Faster algorithms for mean-payoff parity games

DOI10.4230/LIPICS.MFCS.2017.39zbMATH Open1441.91015arXiv1706.06139MaRDI QIDQ5111253FDOQ5111253

Monika R. Henzinger, Krishnendu Chatterjee, Alexander Svozil

Publication date: 26 May 2020

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

Recommendations

• Perfect-information stochastic mean-payoff parity games
• Faster algorithms for mean-payoff games
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• Improved set-based symbolic algorithms for parity games
• Qualitative analysis of concurrent mean-payoff games

zbMATH Keywords

graph gamesBüchi gamesmean-payoff parity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Applications of game theory (91A80) Games involving graphs (91A43)

Cites Work

• Supervisory Control of a Class of Discrete Event Processes
• Positional strategies for mean payoff games
• Synthesizing robust systems
• Better Quality in Synthesis through Quantitative Objectives
• Title not available (Why is that?)
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Solving Sequential Conditions by Finite-State Strategies
• Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited
• Faster algorithms for mean-payoff games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Perfect-Information Stochastic Mean-Payoff Parity Games
• Energy Parity Games
• Energy and Mean-Payoff Parity Markov Decision Processes

Cited In (3)

• Fine-grained complexity lower bounds for problems in computer aided verification
• Faster algorithms for extensive-form game solving via improved smoothing functions
• Improved Rounding for Parallel Repeated Unique Games

This page was built for publication: Faster algorithms for mean-payoff parity games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111253)