Faster algorithms for mean-payoff games

DOI10.1007/s10703-010-0105-xzbMath1213.68430OpenAlexW2065595179MaRDI QIDQ537946

Laurent Doyen, Jean-François Raskin, J. Chaloupka, Luboš Brim, Raffaella Gentilini

Publication date: 23 May 2011

Published in: Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10703-010-0105-x

zbMATH Keywords

embedded systemsenergy constraintsquantitative models(quantitative) model checkingalgorithms \& complexity upper boundsmean-payoff objectivesquantitative gamessynthesis of controllers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10)

Related Items (44)

Hyperplane separation technique for multidimensional mean-payoff games ⋮ The Theory of Universal Graphs for Infinite Duration Games ⋮ Looking at mean payoff through foggy windows ⋮ Graph Games and Reactive Synthesis ⋮ Protocol scheduling ⋮ USING STRATEGY IMPROVEMENT TO STAY ALIVE ⋮ Incentive Stackelberg Mean-Payoff Games ⋮ The Complexity of Infinitely Repeated Alternating Move Games ⋮ Instantaneous reaction-time in dynamic consistency checking of conditional simple temporal networks ⋮ Safraless LTL synthesis considering maximal realizability ⋮ Average-energy games ⋮ Unnamed Item ⋮ Automated competitive analysis of real-time scheduling with graph games ⋮ Enforcing opacity by insertion functions under multiple energy constraints ⋮ Solving mean-payoff games via quasi dominions ⋮ Checking dynamic consistency of conditional hyper temporal networks via mean payoff games. Hardness and (pseudo) singly-exponential time algorithm ⋮ Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A note on the approximation of mean-payoff games ⋮ Bounding Average-Energy Games ⋮ Down the Borel hierarchy: solving Muller games via safety games ⋮ Polynomial-time algorithms for energy games with special weight structures ⋮ Fixpoint theory -- upside down ⋮ Reactive synthesis without regret ⋮ Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games ⋮ Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games ⋮ Energy parity games ⋮ Unnamed Item ⋮ A general approach for optimizing dynamic sensor activation for discrete event systems ⋮ Quantitative reductions and vertex-ranked infinite games ⋮ On Solving Mean Payoff Games Using Pivoting Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Supervisor synthesis and throughput optimization of partially-controllable manufacturing systems ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ The GKK algorithm is the fastest over simple mean-payoff games ⋮ The complexity of multi-mean-payoff and multi-energy games ⋮ Qualitative analysis of concurrent mean-payoff games ⋮ Looking at mean-payoff and total-payoff through windows

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Cyclical games with prohibitions
• Results on the propositional \(\mu\)-calculus
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Positional strategies for mean payoff games
• The complexity of mean payoff games on graphs
• Mean Cost Cyclical Games
• Faster Algorithm for Mean-Payoff Games
• From Parity and Payoff Games to Linear Programming
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Infinite Runs in Weighted Timed Automata with Energy Constraints

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