Undecidable problems of decentralized observation and control on regular languages☆
References (22)
- et al.
A survey of computational complexity results in systems and control
Automatica
(2000) - et al.
Decentralized supervisory control of discrete-event systems
Inform. Sci.
(1988) Transductions and Context-Free Languages
(1979)- et al.
Supervisory control of discrete-event processes with partial observations
IEEE Trans. Automat. Control
(1988) - et al.
Coordinated decentralized protocols for failure diagnosis of discrete event systems
- et al.
Computers and Intractability: A Guide to the Theory of NP-Completeness
(1979) - et al.
Centralized and decentralized supervisory control of nondeterministic systems under partial observation
SIAM J. Control Optim.
(1997) - et al.
Synthesizing distributed systems
- et al.
Effective control synthesis for DES under partial observations
- et al.
A normality theorem for decentralized control of discrete event systems
IEEE Trans. Automat. Control
(1994)
Distributed controller synthesis for local specifications
Cited by (77)
Decentralized architectures for supervisory control of discrete event systems
2022, Encyclopedia of Electrical and Electronic Power Engineering: Volumes 1-3The Science of Software and System Design
2018, undefinedOn the history of diagnosability and opacity in discrete event systems
2018, Annual Reviews in ControlCitation Excerpt :His work was an important source of inspiration for the doctoral research of Rami Debouk at Michigan, which led to Debouk et al. (2000). At around the same time, Stavros Tripakis, working with Sengupta at UC Berkeley, proved the first undecidability results for a version of decentralized diagnosis where communication delays are not bounded (Tripakis, 2004). In order to improve upon the decentralized solution in Debouk et al. (2000) (referred to as Protocol “3” therein) and at the same time avoid the undecidability that arises in the framework of Tripakis (2004), researchers subsequently investigated various decentralized architectures with either a coordinator (as in the protocols called Protocols “1 and 2” in Debouk et al., 2000), or by enhancing the local diagnostic modules to perform “conditional decisions” or use “inference mechanisms” or set-intersection refinements, as in the approaches initially developed in Wang, Yoo, and Lafortune (2007) and Kumar and Takai (2009), which themselves were followed by several extensions, and the subsequently developed “intersection-based” schemes in Panteli and Hadjicostis (2013) and Keroglou and Hadjicostis (2015b).
Decentralized observability of discrete event systems with synchronizations
2017, AutomaticaCitation Excerpt :In this setting, although the basic notion of local observability given by Tripakis is still fundamental, two major extensions are needed. In fact the observability property defined in Tripakis (2004b) makes two rather restrictive assumptions. Combining the two extensions above, we introduce the notion of q-sync observability.
From Diagnosability to Opacity: A Brief History of Diagnosability or Lack Thereof
2017, IFAC-PapersOnLine
- ☆
This work has been supported in part by European IST projects “Next TTA” under project No. IST-2001-32111 and “RISE” under project No. IST-2001-38117, and by CNRS STIC project “CORTOS”.