Asynchronous Games over Tree Architectures - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Asynchronous Games over Tree Architectures

Résumé

We consider the distributed control problem in the setting of Zielonka asynchronous automata. Such automata are compositions of finite processes communicating via shared actions and evolving asynchronously. Most importantly, processes participating in a shared action can exchange complete information about their causal past. This gives more power to controllers, and avoids simple pathological undecidable cases as in the setting of Pnueli and Rosner. We show the decidability of the control problem for Zielonka automata over acyclic communication architectures. We provide also a matching lower bound, which is l-fold exponential, l being the height of the architecture tree.
Fichier principal
Vignette du fichier
GGMW13.pdf (763.41 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00916615 , version 1 (10-12-2013)

Identifiants

Citer

Blaise Genest, Hugo Gimbert, Anca Muscholl, Igor Walukiewicz. Asynchronous Games over Tree Architectures. ICALP - 40th International Colloquium on Automata, Languages, and Programming- 2013, Jul 2013, RIGA, Latvia. pp.275-286, ⟨10.1007/978-3-642-39212-2_26⟩. ⟨hal-00916615⟩
196 Consultations
103 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More