CREMMI - Modélisation mathématique et informatique
Disciplines :
Computer science Mathematics
Author, co-author :
Bouyer, Patricia
Markey, Nicolas
Larsen, Kim G.
Laursen, Simon
Randour, Mickaël ; Université de Mons > Faculté des Sciences > Service de Mathématiques effectives ; Université de Mons > Faculté des Sciences > Informatique théorique
Language :
English
Title :
Average-energy games
Publication date :
01 March 2018
Journal title :
Acta Informatica
ISSN :
0001-5903
Publisher :
Springer, Allemagne
Volume :
55
Issue :
2
Pages :
91-127
Peer reviewed :
Peer Reviewed verified by ORBi
Research unit :
S820 - Mathématiques effectives
Research institute :
R150 - Institut de Recherche sur les Systèmes Complexes
Aminof, B., Rubin, S.: First cycle games. In: Proceedings of SR, EPTCS 146, pp. 83–90 (2014)
Björklund, H., Sandberg, S., Vorobyov, S.: Memoryless determinacy of parity and mean payoff games: a simple proof. Theor. Comput. Sci. 310(1–3), 365–378 (2004)
Bloem, R., Chatterjee, K., Henzinger, T.A., Jobstmann, B.: Better quality in synthesis through quantitative objectives. In: Proceedings of CAV, LNCS 5643, pp 140–156. Springer, Berlin (2009)
Bohy, A., Bruyère, V., Filiot, E., Raskin, J.-F.: Synthesis from LTL specifications with mean-payoff objectives. In: Proceedings of of TACAS, LNCS 7795, pp. 169–184. Springer, Berlin (2013)
Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: Markov decision processes and stochastic games with total effective payoff. In: Proceedings of STACS, LIPIcs 30, pp. 103–115. Schloss Dagstuhl—LZI (2015)
Bouyer, P., Fahrenberg, U., Larsen, K.G., Markey, N., Srba, J.: Infinite runs in weighted timed automata with energy constraints. In: Proceedings of FORMATS, LNCS 5215, pp. 33–47. Springer, Berlin (2008)
Bouyer, P., Markey, N., Randour, M., Larsen, K.G., Laursen, S.: Average-energy games. In: Proceedings of GandALF, EPTCS 193, pp. 1–15 (2015)
Brázdil, T., Klaška, D., Kučera, A., Novotný, P.: Minimizing running costs in consumption systems. In: Proceedings of CAV, LNCS 8559, pp. 457–472. Springer, Berlin (2014)
Cassez, F., Jensen, J.J., Larsen, K.G., Raskin, J.-F., Reynier, P.-A.: Automatic synthesis of robust and optimal controllers—an industrial case study. In: Proceedings of HSCC, LNCS 5469, pp. 90–104. Springer, Berlin (2009)
Chakrabarti, A., de Alfaro, L., Henzinger, T.A., Stoelinga, M.: Resource interfaces. In: Proceedings of EMSOFT, LNCS 2855, pp. 117–133. Springer, Berlin (2003)
Chatterjee, K., Doyen, L.: Energy parity games. In: Proceedings of ICALP, LNCS 6199, pp. 599–610. Springer, Berlin (2010)
Chatterjee, K., Velner, Y.: Mean-payoff pushdown games. In: Proceedings of LICS, pp. 195–204. IEEE (2012)
Chatterjee, K., Prabhu, V.S.: Quantitative timed simulation functions and refinement metrics for real-time systems. In: Proceedings of HSCC, pp. 273–282. ACM (2013)
Chatterjee, K., Randour, M., Raskin, J.-F.: Strategy synthesis for multi-dimensional quantitative objectives. Acta Inf. 51(3–4), 129–163 (2014)
Chatterjee, K., Doyen, L., Randour, M., Raskin, J.-F.: Looking at mean-payoff and total-payoff through windows. Inf. Comput. 242, 25–52 (2015)
Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8(2), 109–113 (1979)
Fearnley, J., Jurdziński, M.: Reachability in two-clock timed automata is PSPACE-complete. In: Proceedings of ICALP, LNCS 7966, pp. 212–223. Springer, Berlin (2013)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gawlitza, T., Seidl, H.: Games through nested fixpoints. In: Proceedings of CAV, LNCS 5643, pp. 291–305. Springer, Berlin (2009)
Gimbert, H., Zielonka, W.: When can you play positionnaly? In: Proceedings of MFCS, LNCS 3153, pp. 686–697. Springer, Berlin (2004)
Gimbert, H., Zielonka, W.: Games where you can play optimally without any memory. In: Proceedings of CONCUR, LNCS 3653, pp. 428–442. Springer, Berlin (2005)
Grädel, E., Thomas, W., Wilke, T. (eds.): Automata, Logics, and Infinite Games: A Guide to Current Research, LNCS 2500. Springer, Berlin (2002)
Juhl, L., Larsen, K.G., Raskin, J.-F.: Optimal bounds for multiweighted and parametrised energy games. In: Theories of Programming and Formal Methods, LNCS 8051, pp. 244–255. Springer, Berlin (2013)
Jurdziński, M.: Deciding the winner in parity games is in UP ∩ co-UP. Inf. Process. Lett. 68(3), 119–124 (1998)
Jurdziński, M., Sproston, J., Laroussinie, F.: Model checking probabilistic timed automata with one or two clocks. Logical Methods Comput. Sci. 4(3), 1–28 (2008)
Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23(3), 309–311 (1978)
Kopczynski, E.: Half-positional determinacy of infinite games. In: Proceedings of ICALP, LNCS 4052, pp. 336–347. Springer, Berlin (2006)
Lafourcade, P., Lugiez, D., Treinen, R.: Intruder deduction for AC-like equational theories with homomorphisms. Research Report LSV-04-16, Laboratoire Spécification et Vérification, ENS Cachan, France (2004)
Lafourcade, P., Lugiez, D., Treinen, R.: Intruder deduction for AC-like equational theories with homomorphisms. In: Proceedings of RTA, LNCS 3467, pp. 308–322. Springer, Berlin (2005)
Larsen, K.G., Laursen, S., Zimmermann, M.: Limit your consumption! Finding bounds in average-energy games. In: Proceedings of QAPL, EPTCS (2016)
Randour, M.: Automated synthesis of reliable and efficient systems through game theory: a case study. In: Proceedings of the European Conference on Complex Systems 2012, Springer Proceedings in Complexity XVII, pp. 731–738. Springer, Berlin (2013)
Randour, M.: Synthesis in Multi-Criteria Quantitative Games. Ph.D. Thesis, Université de Mons, Belgium (2014)
Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997)
Thuijsman, F., Vrieze, O.J.: The bad match; a total reward stochastic game. OR Spektrum 9(2), 93–99 (1987)
Velner, Y., Chatterjee, K., Doyen, L., Henzinger, T.A., Rabinovich, A.M., Raskin, J.-F.: The complexity of multi-mean-payoff and multi-energy games. Inf. Comput. 241, 177–196 (2015)
Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1–2), 343–359 (1996)
