Distributed Synthesis for Regular and Contextfree Specifications

We adress the controller synthesis problem for distributed systems with regular and deterministic contextfree specifications. Our main result is a complete characterization of the decidable architectures for local specifications. This extends existing results on local specifications in two directions. First, we consider arbitrary, not necessarily acyclic, architectures and second, we allow deterministic contextfree specifications. Moreover, we show that as soon as one considers global deterministic contextfree specifications, even very simple architectures are undecidable.