TY - JOUR
T1 - A note on deciding controllability in pushdown systems
AU - Griffin, Christopher
N1 - Funding Information:
Manuscript received October 29, 2004; revised May 11, 2005 and August 25, 2005. Recommended by A. Giua. The research presented in this note was supported by the Defense Advanced Research Projects Agency under Grant DAAD19-01-1-0504. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and do not necessarily reflect the view of the sponsoring agencies.
PY - 2006/2
Y1 - 2006/2
N2 - Consider an event alphabet ∑. The supervisory control theory of Ramadge and Wonham asks the question, given a plant model G, with language LM (G) ⊆ ∑* and another language K ⊆ LM (G), is there a supervisor φ such that LM (φ/(G) = K. Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of with respect to LM (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 the controllability property was decidable for K. The class of languages generated by pushdown automata properly includes the regular languages. They are accepted by finite state machines coupled with pushdown stack memory. This makes them interesting candidates as supervisory languages, since the supervisor will have nonfinite memory. In this note, we show the following: i) If S is a specification given by a deterministic pushdown automaton and L is generated by a finite state machine, then there is an algorithm to decide whether K = S ∩ L is controllable with respect to L. ii) It is undecidable for an arbitrary specification S generated by a nondeterministic pushdown automaton and plant language L generated by a finite state machine whether K= S ∩ L is controllable with respect to L.
AB - Consider an event alphabet ∑. The supervisory control theory of Ramadge and Wonham asks the question, given a plant model G, with language LM (G) ⊆ ∑* and another language K ⊆ LM (G), is there a supervisor φ such that LM (φ/(G) = K. Ramadge and Wonham showed that a necessary condition for this to be true is the so-called controllability of with respect to LM (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 the controllability property was decidable for K. The class of languages generated by pushdown automata properly includes the regular languages. They are accepted by finite state machines coupled with pushdown stack memory. This makes them interesting candidates as supervisory languages, since the supervisor will have nonfinite memory. In this note, we show the following: i) If S is a specification given by a deterministic pushdown automaton and L is generated by a finite state machine, then there is an algorithm to decide whether K = S ∩ L is controllable with respect to L. ii) It is undecidable for an arbitrary specification S generated by a nondeterministic pushdown automaton and plant language L generated by a finite state machine whether K= S ∩ L is controllable with respect to L.
UR - http://www.scopus.com/inward/record.url?scp=33244479694&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33244479694&partnerID=8YFLogxK
U2 - 10.1109/TAC.2005.863513
DO - 10.1109/TAC.2005.863513
M3 - Article
AN - SCOPUS:33244479694
SN - 0018-9286
VL - 51
SP - 334
EP - 337
JO - IEEE Transactions on Automatic Control
JF - IEEE Transactions on Automatic Control
IS - 2
ER -