LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Asynchronous Games over Tree Architectures
- Date
- Tuesday, June 26 2012 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Anca Muscholl (LaBRI, Université Bordeaux-1)
We consider the control problem for Zielonka asynchronous automata. This is a distributed synthesis problem since Zielonka automata is an asynchronous parallel composition of finite processes communicating via rendez-vous. The most important aspect of this model is that the processes participating in a rendez-vous can exchange complete information about their causal past. It is an intriguing open problem whether the control problem is decidable in this setting. We show decidability of the control problem for Zielonka automata over an acyclic communication architecture. The complexity of our algorithm is l-fold exponential with l being the height of the tree representing the architecture. We show that this complexity is tight.
This is joint work with B. Genest, H. Gimbert and I. Walukiewicz.