Faster algorithms for mean-payoff parity games

DOI10.4230/LIPICS.MFCS.2017.39MaRDI QIDQ5111253zbMATH OpenFDO

Authors Krishnendu Chatterjee, Alexander Svozil, Monika R. Henzinger

Publication date 26 May 2020

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

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)

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

Cites work

• scientific article; zbMATH DE number 4124989 (Why is no real title available?)
• Better Quality in Synthesis through Quantitative Objectives
• Energy and Mean-Payoff Parity Markov Decision Processes
• Energy parity games
• Faster algorithms for mean-payoff games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Measuring Permissiveness in Parity Games: Mean-Payoff Parity Games Revisited
• Perfect-information stochastic mean-payoff parity games
• Positional strategies for mean payoff games
• Solving Sequential Conditions by Finite-State Strategies
• Supervisory Control of a Class of Discrete Event Processes
• Synthesizing robust systems

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)