IEEE Transactions on Automatic Control, Vol.53, No.3, 826-829, 2008
A note on the properties of the supremal controllable sublanguage in pushdown systems
Consider an event alphabet Sigma. The supervisory control theory of Ramadge and Wonham asks the question: given a plant model G with language L-M (G) subset of Sigma* and another language K subset of L-M (G), is there a supervisor phi such that L-M (phi/G) = K? Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of K with respect to L-M (G). They showed that when G is a finite-state automaton and K is a regular language (also generated by a finite state automaton), then there is a regular supremal controllable sub-language sup(c) (K) subset of K that is effectively constructable from generators of K and G. In this paper, we show: 1) there is an algorithm to compute the supremal controllable sublanguage of a prefix closed K accepted by a deterministic pushdown automaton (DPDA) when the plant language is also prefix closed and accepted by a finite state automaton and 2) in this case, we show that this supremal controllable sublanguage is also accepted by a DPDA.