\input zb-basic
\input zb-ioport
\iteman{io-port 05898957}
\itemau{Brim, L.; Chaloupka, J.; Doyen, L.; Gentilini, R.; Raskin, J.F.}
\itemti{Faster algorithms for mean-payoff games.}
\itemso{Form. Methods Syst. Des. 38, No. 2, 97-118 (2011).}
\itemab
Summary: In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time.
\itemrv{~}
\itemcc{}
\itemut{quantitative models; (quantitative) model checking; embedded systems; synthesis of controllers; quantitative games; mean-payoff objectives; energy constraints; algorithms \& complexity upper bounds}
\itemli{doi:10.1007/s10703-010-0105-x}
\end