Asynchronous Games over Tree Architectures

Abstract : 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.
Type de document :
Communication dans un congrès
Fomin, Fedor V. and Freivalds, Rūsiņš and Kwiatkowska, Marta and Peleg, David. ICALP - 40th International Colloquium on Automata, Languages, and Programming- 2013, Jul 2013, RIGA, Latvia. Springer, 7966, pp.275-286, 2013, LNCS. 〈10.1007/978-3-642-39212-2_26〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00916615
Contributeur : Blaise Genest <>
Soumis le : mardi 10 décembre 2013 - 14:52:56
Dernière modification le : mercredi 16 mai 2018 - 11:24:06
Document(s) archivé(s) le : mardi 11 mars 2014 - 10:15:38

Fichier

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

Identifiants

Citation

Blaise Genest, Hugo Gimbert, Anca Muscholl, Igor Walukiewicz. Asynchronous Games over Tree Architectures. Fomin, Fedor V. and Freivalds, Rūsiņš and Kwiatkowska, Marta and Peleg, David. ICALP - 40th International Colloquium on Automata, Languages, and Programming- 2013, Jul 2013, RIGA, Latvia. Springer, 7966, pp.275-286, 2013, LNCS. 〈10.1007/978-3-642-39212-2_26〉. 〈hal-00916615〉

Partager

Métriques

Consultations de la notice

341

Téléchargements de fichiers

80