On the complexity of supervisory control design in the RW framework

The time complexity of supervisory control design for a general class of pr oblems is studied, It is shown to be very unlikely that a polynomial-time a lgorithm can be found when either 1) the plant is composed of m components running concurrently or 2) the set of legal behaviors is given by the inter section of n legal specifications. That is to say, in general, there is no way to avoid constructing a state space which has size exponential in m + n , It is suggested that, rather than discouraging future work in the field, this result should point researchers to more fruitful directions, namely, s tudying special cases of the problem, where certain structural properties p ossessed by the plant or specification lend themselves to more efficient al gorithms for designing supervisory controls. As no background on the subjec t of computational complexity is assumed, we have tried to explain all the borrowed material in basic terms, so that this paper may serve as a tutoria l for a system engineer not familiar with the subject.