Asynchronous games over tree architectures

Prelegent(ci)

Anca Muscholl

Afiliacja

LaBRI, Bordeaux

Termin

18 kwietnia 2012 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with B. Genest, H. Gimbert and I. Walukiewicz

Seminarium

Seminarium „Teoria automatów”

---

The control problem starts with a plant and asks to restrict its
 controllable actions in such a way that a given specification is
 met. The synthesis problem can be seen as a special case of the
 control problem. 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, where
 every process can communicate with its parent, its children, and
 with the environment. 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.

---