Towards decentralized synthesis: Decomposable sublanguage and Joint Observability Problems

This note studies two closely related decision problems from the area of decentralized synthesis. The first problem is about deciding the existence of a non-empty decomposable sublanguage of a regular language, called Decomposable Sublanguage Problem; the second is Joint Observability Problem, which is known in the literature. We provide characterizations of the decidability of both decision problems. Then, we study the undecidability of related problems such as Distributed Supervisory Control Problem and Parametrized Control Synthesis Problem. To address these undecidability results, we also propose a couple of heuristics that can provide solutions to the two studied problems, but also to more general problems from control or trace theory.