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

https://hal.inria.fr/hal-00916615
Contributor : Blaise Genest <>
Submitted on : Tuesday, December 10, 2013 - 2:52:56 PM
Last modification on : Tuesday, June 15, 2021 - 4:27:28 PM
Long-term archiving on: : Tuesday, March 11, 2014 - 10:15:38 AM

File

GGMW13.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

607

Files downloads

585