×

zbMATH — the first resource for mathematics

Fixed-dimensional energy games are in pseudo-polynomial time. (English) Zbl 1440.68122
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part II. Berlin: Springer. Lect. Notes Comput. Sci. 9135, 260-272 (2015).
Summary: We generalise the hyperplane separation technique [K. Chatterjee and Y. Velner, Lect. Notes Comput. Sci. 8052, 500–515 (2013; Zbl 1371.68106)] from multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the latter whose running time is exponential only in the dimension, but not in the number of vertices of the game graph. This answers an open question whether energy games with arbitrary initial credit can be solved in pseudo-polynomial time for fixed dimensions 3 or larger [J. Chaloupka, Fundam. Inform. 123, No. 1, 15–42 (2013; Zbl 1281.68160)]. It also improves the complexity of solving multi-dimensional energy games with given initial credit from non-elementary [T. Brázdil et al., Lect. Notes Comput. Sci. 6199, 478–489 (2010; Zbl 1288.68179)] to 2EXPTIME, thus establishing their 2EXPTIME-completeness.
For the entire collection see [Zbl 1316.68013].

MSC:
68Q25 Analysis of algorithms and problem complexity
91A80 Applications of game theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdulla, P.A., Atig, M.F., Hofman, P., Mayr, R., Kumar, K.N., Totzke, P.: Infinite-state energy games. In: CSL-LICS 2014. ACM (2014) · Zbl 1401.68139
[2] Abdulla, P.A., Mayr, R., Sangnier, A., Sproston, J.: Solving parity games on integer vectors. In: D’Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013 - Concurrency Theory. LNCS, vol. 8052, pp. 106-120. Springer, Heidelberg (2013) · Zbl 1390.68452 · doi:10.1007/978-3-642-40184-8_9
[3] Brázdil, T., Chatterjee, K., Kučera, A., Novotný, P.: Efficient controller synthesis for consumption games with multiple resource types. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 23-38. Springer, Heidelberg (2012) · Zbl 06070736 · doi:10.1007/978-3-642-31424-7_8
[4] Brázdil, T., Jančar, P., Kučera, A.: Reachability games on extended vector addition systems with states. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 478-489. Springer, Heidelberg (2010) · Zbl 1288.68179 · doi:10.1007/978-3-642-14162-1_40
[5] Chaloupka, J.: Z-reachability problem for games on 2-dimensional vector addition systems with states is in P. Fund. Inform. 123(1), 15-42 (2013) · Zbl 1281.68160
[6] Chatterjee, K., Doyen, L., Henzinger, T.A., Raskin, J.F.: Generalized mean-payoff and energy games. In: FSTTCS 2010. LIPIcs, vol. 8, pp. 505-516. LZI (2010) · Zbl 1245.68090
[7] Chatterjee, K., Randour, M., Raskin, J.F.: Strategy synthesis for multi-dimensional quantitative objectives. Acta Inf. 51(3-4), 129-163 (2014) · Zbl 1360.68208 · doi:10.1007/s00236-013-0182-6
[8] Chatterjee, K., Velner, Y.: Hyperplane separation technique for multidimensional mean-payoff games. In: D’Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013 - Concurrency Theory. LNCS, vol. 8052, pp. 500-515. Springer, Heidelberg (2013) · Zbl 1371.68106 · doi:10.1007/978-3-642-40184-8_35
[9] Courtois, J.-B., Schmitz, S.: Alternating vector addition systems with states. In: Csuhaj-Varjú, E., Dietzfelbinger, M., Ésik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 220-231. Springer, Heidelberg (2014) · Zbl 1425.68290
[10] Fahrenberg, U., Juhl, L., Larsen, K.G., Srba, J.: Energy games in multiweighted automata. In: Cerone, A., Pihlajasaari, P. (eds.) ICTAC 2011. LNCS, vol. 6916, pp. 95-115. Springer, Heidelberg (2011) · Zbl 1350.68168 · doi:10.1007/978-3-642-23283-1_9
[11] Juhl, L., Guldstrand Larsen, K., Raskin, J.-F.: Optimal bounds for multiweighted and parametrised energy games. In: Liu, Z., Woodcock, J., Zhu, H. (eds.) Theories of Programming and Formal Methods. LNCS, vol. 8051, pp. 244-255. Springer, Heidelberg (2013) · Zbl 1390.68399 · doi:10.1007/978-3-642-39698-4_15
[12] Rackoff, C.: The covering and boundedness problems for vector addition systems. Theor. Comput. Sci. 6(2), 223-231 (1978) · Zbl 0368.68054 · doi:10.1016/0304-3975(78)90036-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.