Recent Results on Computational Issues in Supervisory Control

We present and discuss the implications of recent results by several researchers on computational issues in supervisory control of discrete event systems. The first issue discussed is the boundary between decidability and undecidability in centralized and decentralized control problems for systems modeled by finite-state automata and subject to regular language specifications. The second issue discussed is the PSPACE-completeness of a large class of verification and control problems for decentralized and modular systems modeled by sets of interacting finite-state automata coupled by parallel composition. The state space explosion inherent to modular systems and the possible time-space tradeoff that arises for computations on these systems are discussed.