Concurrent Games on VASS with Inhibition
| Autor: | Serge Haddad, Nathalie Sznajder, Béatrice Bérard, Mathieu Sassolas |
|---|---|
| Přispěvatelé: | Modélisation et Vérification (MoVe), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Spécification et Vérification [Cachan] (LSV), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS), Modeling and Exploitation of Interaction and Concurrency (MEXICO), École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Cachan (ENS Cachan)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Koutny, Maciej, Ulidowski, Irek |
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Counter machine
Theoretical computer science Informatique générale Semantics (computer science) Computer science Théorie de la décision et des jeux Distributed computing [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] 0102 computer and information sciences 02 engineering and technology Extension (predicate logic) DUAL (cognitive architecture) 01 natural sciences Undecidable problem Decidability 010201 computation theory & mathematics Reachability 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing |
| Zdroj: | 23rd International Conference on Concurrency Theory (CONCUR'12) 23rd International Conference on Concurrency Theory (CONCUR'12), Sep 2012, Newcastle upon Tyne, United Kingdom. pp.39-52, ⟨10.1007/978-3-642-32940-1_5⟩ Lecture Notes in Computer Science ISBN: 9783642329395 CONCUR Proceedings of the 23rd International Conference on Concurrency Theory (CONCUR'12) |
| DOI: | 10.1007/978-3-642-32940-1_5⟩ |
| Popis: | We propose to study concurrent games on a new extension of Vector Addition Systems with States, where inhibition conditions are added for modeling purposes. Games are a well-suited framework to solve control problems, and concurrent semantics reflect realistic situationswhere the environment can always produce a move before the controller, although it is never required to do so. This is in contrast with previous works, which focused mainly on turn-based semantics. Moreover, we consider asymmetric games, where environment and controller do not have the same capabilities, although they both have restricted power. In this setting, we investigate reachability and safety objectives, which are not dual to each other anymore, and we prove that (i) reachability games are undecidable for finite targets, (ii) they are 2-EXPTIME-complete forupward-closed targets and (iii) safety games are co-NP-complete for finite, upward-closed and semi-linear targets. Moreover, for the decidable cases, we build a finite representation of the corresponding controllers. Supported by ERC Starting Grant n°279499 "inVEST" Supported by project CoChaT Supported by project ImpRo (ANR-2010-BLAN-0317) info:eu-repo/semantics/published Supported by the European Union Seventh Framework Programme [FP7/2007-2013] under grant agreement 257462 HYCON2 NOE |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|