Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Blaise Genest Connect in order to contact the contributor
Submitted on : Tuesday, December 10, 2013 - 2:52:56 PM
Last modification on : Saturday, June 25, 2022 - 7:41:18 PM
Long-term archiving on: : Tuesday, March 11, 2014 - 10:15:38 AM


Files produced by the author(s)



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⟩



Record views


Files downloads