Supervisor Existence For Modular Discrete-Event Systems

This paper examines decision problems involving supervisors for modular systems. We investigate the problem of deciding if there exists a supervisor that can augment a modular system to satisfy a modular global specification. Our system and specification modules are ``discrete-event systems'' modeled as finite-state automata. The parallel composition operation is used to model the interaction between the various modules. A supervisor for a discrete-event system observes events as they occur in the system and enforces a control action by disabling some controllable events. We find that these types of problems are generally PSPACE-complete for a large class of systems and specifications.