Towards decentralized synthesis: Decomposable sublanguage and Joint Observability Problems

Liyong Lin, Alin Stefanescu, Rong Su, Weilin Wang, Ahmad Reza Shehabinia

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)


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.

Original languageEnglish
Title of host publication2014 American Control Conference, ACC 2014
Subtitle of host publicationPortland, Oregon, USA. 4-6 June 2014
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages6
ISBN (Electronic)9781479932733
ISBN (Print)9781479932726, 9781479932757
Publication statusPublished - 2014
Externally publishedYes
EventAmerican Control Conference 2014 - Portland, United States of America
Duration: 4 Jun 20146 Jun 2014


ConferenceAmerican Control Conference 2014
Abbreviated titleACC 2014
CountryUnited States of America


  • decentralized observation
  • decidability
  • decomposability
  • discrete-event systems
  • trace theory

Cite this