Alternating Vector Addition Systems with States

Jean-Baptiste Courtois 1 Sylvain Schmitz 1, 2, *
* Auteur correspondant
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : Alternating vector addition systems are obtained by equipping vector addition systems with states (VASS) with 'fork' rules, and provide a natural setting for infinite-arena games played over a VASS. Initially introduced in the study of propositional linear logic, they have more recently gathered attention in the guise of multi-dimensional energy games for quantitative verification and synthesis. We show that establishing who is the winner in such a game with a state reachability objective is 2-ExpTime-complete. As a further application, we show that the same complexity result applies to the problem of whether a VASS is simulated by a finite-state system.
Type de document :
Communication dans un congrès
Csuhaj-Varjú, Erzsébet; Dietzfelbinger, Martin; Ésik, Zoltán. 39th International Symposium on Mathematical Foundations of Computer Science, Aug 2014, Budapest, Bulgaria. Springer, 8634, pp.220--231, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-44522-8_19〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00980878
Contributeur : Sylvain Schmitz <>
Soumis le : lundi 30 juin 2014 - 11:46:38
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mardi 11 avril 2017 - 09:23:36

Fichier

article.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Baptiste Courtois, Sylvain Schmitz. Alternating Vector Addition Systems with States. Csuhaj-Varjú, Erzsébet; Dietzfelbinger, Martin; Ésik, Zoltán. 39th International Symposium on Mathematical Foundations of Computer Science, Aug 2014, Budapest, Bulgaria. Springer, 8634, pp.220--231, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-44522-8_19〉. 〈hal-00980878v2〉

Partager

Métriques

Consultations de la notice

499

Téléchargements de fichiers

232