Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P

• Autorzy: Chaloupka J.
• Języki publikacji: EN

Abstrakty

EN

We consider a two-player infinite game with zero-reachability objectives played on a 2-dimensional vector addition system with states (VASS), the states of which are divided between the two players. Brázdil, Jančar, and Kučera (2010) have shown that for k > 0, deciding the winner in a game on k-dimensional VASS is in (k − 1)-EXPTIME. In this paper, we show that, for k = 2, the problem is in P, and thus improve the EXPTIME upper bound.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 1
• Strony: 15--42
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Chaloupka J.

• Faculty of Informatics, Masaryk University, Botanick´a 68a, 60200 Brno, Czech Republic

Bibliografia

• [1] P. Bouyer, U. Fahrenberg, K. G. Larsen, N. Markey, and J. Srba. Infinite runs in weighted timed automata with energy constraints. In Proc. Formal Modeling and Analysis of Timed Systems, pages 33–47. Springer, 2008. [2] T. Brázdil, P. Jančar, and A. Kučera. Reachability games on extended vector addition systems with states. In Proc. International Colloquium on Automata, Languages and Programming, LNCS. Springer, 2010.
• [3] L. Brim, J. Chaloupka, L. Doyen, R. Gentilini, and J.F. Raskin. Faster algorithms for mean-payoff games. Formal Methods in System Design, 38(2):97–118, 2011.
• [4] A. Chakrabarti, L. de Alfaro, T. Henzinger, and M. Stoelinga. Resource interfaces. In Proc. Embedded Software, volume 2855 of LNCS, pages 117–133. Springer, 2003.
• [5] J. E. Hopcroft and J.-J. Pansiot. On the reachablility problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135–159, 1979.
• [6] P. Jančar. Undecidability of bisimilarity for petri nets and related problems. Theoretical Computer Science, 148:281–301, 1995.
• [7] P. Jančar. Decidability of bisimilarity for one-counter processes. Information and Computation , 158:1–17, 2000.
• [8] W. Reisig. Petri Nets – An Introduction . Springer, 1985