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
embedded systemsenergy constraintsquantitative models(quantitative) model checkingalgorithms \& complexity upper boundsmean-payoff objectivesquantitative gamessynthesis of controllers
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)
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