Faster algorithms for mean-payoff parity games

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

Authors: Krishnendu Chatterjee, Alexander Svozil, Monika R. Henzinger 

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 (14)

• Stability in graphs and games
• On promptness in parity games
• Fine-grained complexity lower bounds for problems in computer aided verification
• Improved set-based symbolic algorithms for parity games
• The cost of exactness in quantitative reachability
• Perfect-information stochastic mean-payoff parity games
• On satisficing in quantitative games
• Faster algorithms for mean-payoff games
• Faster algorithms for extensive-form game solving via improved smoothing functions
• New algorithms for combinations of objectives using separating automata
• Solving mean-payoff games via quasi dominions
• Improved Rounding for Parallel Repeated Unique Games
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• Improved algorithms for parity and Streett objectives

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)