Supervisory control of Timed State Tree Structures

It is well known that the nonblocking supervisory control problem is NP-hard, subject in particular to state space explosion that is exponential in the number of system components. The problem of state explosion is more challenging in Timed DES than in untimed DES. In this paper we propose to manage complexity by organizing the system as a Timed State Tree Structure (TSTS). Based on TSTS we present an efficient recursive algorithm that can perform nonblocking supervisory control design (in reasonable time and memory) for systems of state size 10¹² and higher.