Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
15--42
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
autor
- 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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-4d36b8a5-d2fc-4b4d-a362-7de0a4950736