On The Complexity of Counter Reachability Games

• Autorzy: Reichert J.

Identyfikatory

DOI

10.3233/FI-2016-1320

• Języki publikacji: EN

Abstrakty

EN

Counter reachability games are played by two players on a graph with labelled edges. Each move consists of picking an edge from the current location and adding its label to a counter vector. The objective is to reach a given counter value in a given location. We distinguish three semantics for counter reachability games, according to what happens when a counter value would become negative: the edge is either disabled, or enabled but the counter value becomes zero, or enabled. We consider the problem of determining the winner in counter reachability games and show that, in most cases, it has the same complexity under all semantics. This constrasts with the one-player case, for which the decision problem is decidable without any elementary upper bound under the first semantics, whereas it is NP-complete under the third one. Surprisingly, under one semantics, the complexity in dimension one depends on whether the objective value is zero or any other integer.

Słowa kluczowe

EN

computational complexity; game theory; semantic web; NP-complete problems; decision making; problem solving

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 143, nr 3/4
• Strony: 415--436
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Reichert J.

• LSV, ENS Cachan 61, avenue du Président Wilson, France

Bibliografia

• [1] Karp RM, Miller RE. Parallel Program Schemata. The Journal of Computer and System Sciences. 1969;3(2):147–195. doi:10.1016/S0022-0000(69)80011-5.
• [2] Bouyer P, Fahrenberg U, Larsen KG, Markey N, Srba J. Infinite Runs in Weighted Timed Automata with Energy Constraints. In: Proceedings of the 6th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS); 2008. p. 33–47. doi:10.1007/978-3-540-85778-5 4.
• [3] Fahrenberg U, Juhl L, Larsen KG, Srba J. Energy Games in Multiweighted Automata. In: Proceedings of the 8th International Colloquium on Theoretical Aspects of Computing (ICTAC); 2011. p. 95–115. doi:10.1007/978-3-642-23283-1 9.
• [4] Kosaraju SR. Decidability of Reachability in Vector Addition Systems (PreliminaryVersion). In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing. STOC ’82. New York, NY, USA: ACM; 1982. p. 267–281. doi:10.1145/800070.802201.
• [5] Haase C, Halfon S. Integer Vector Addition Systems. CoRR. 2014;abs/1406.2590. doi:10.1007/978-3-319-11439-2 9.
• [6] Brázdil T, Jancar P, Kucera A. Reachability Games on Extended Vector Addition Systems with States. In: Proceedings of the 37th International Colloquiumon Automata, Languages and Programming (ICALP) – Part II; 2010. p. 478–489. doi:10.1007/978-3-642-14162-1 40.
• [7] Jurdzinski M, Laroussinie F, Sproston J. Model Checking Probabilistic Timed Automata with One or Two Clocks. In: Proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS); 2007. p. 170–184. doi:10.2168/LMCS-4(3:11)2008.
• [8] Arul A, Reichert J. The Complexity of Robot Games on the Integer Line. In: Proceedings of the 11th Workshop on Quantitative Aspects of Programming Languages and Systems (QAPL). vol. 117 of EPTCS; 2013. p. 132–146. doi:10.4204/EPTCS.117.9.
• [9] Papadimitriou CH, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall; 1982.
• [10] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms (3. ed.). MIT Press; 2009.
• [11] Hunter P. Reachability in succinct one-counter games. ArXiv e-prints. 2014 jul;.