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

Speaker(s)

Anca Muscholl

Affiliation

LaBRI, Bordeaux

Date

April 18, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

Asynchronous games over tree architectures

Seminar

Seminar Automata Theory

---

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.

---