On the control of discrete-event dynamical systems

We study a class of problems related to the supervisory control of a discrete-event system (DES), as formulated by Wonham and we focus on the computational effort required for their solution. While the problem of supervisory control of a perefetcly observed DES may be easily solved by dynamic programming, the problem becomes intractable (in the sense of complexity theory) when a supervisor with a minimal number of states is sought. Furthermore, supervisory control is an intractable problem, in general, when imperfectly observed systems are considered. Finally, some negative results are obtained for the control of interconnected systems consisting of a large number of subsystems.