On partial observability in discrete event control with pushdown systems

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


Consider an event alphabet ∑. The Supervisory Control Theory of Ramadge and Wonham asks the question, given a plant model G, with language L M(G) ⊆ ∑* and another language K ⊆ LM(G), is there a supervisor φ such that LM(φ=G) = K. This question is complicated when the output of G is partially masked by M, which sends some events to the empty string ε. This leads to the notion of the observability of K with respect to L and the mask M. We have K is observable with respect to L and M if for all s, t ∈ K̄ if sσ ∈ K̄ and M(s) = M(t) and tσ ∈ L̄, then tσ ∈ K̄. The property of observability can be related to a much stronger property normality, which is easily decidable when G has a finite number of states and K is also generated by a finite state machine. 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 non-finite memory. In this paper, we show the following: there is a property we call Property P that is (i) independent of Normality (Property N), (ii) implies observability, (iii) is decidable when K is accepted by a deterministic pushdown machine and G is a finite state machine and (iv) is preserved under union and hence there is a supremal sublanguage for which Property P holds for any K.

Original languageEnglish (US)
Title of host publicationProceedings of the 2010 American Control Conference, ACC 2010
PublisherIEEE Computer Society
Number of pages4
ISBN (Print)9781424474264
StatePublished - Jan 1 2010

Publication series

NameProceedings of the 2010 American Control Conference, ACC 2010

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering


Dive into the research topics of 'On partial observability in discrete event control with pushdown systems'. Together they form a unique fingerprint.

Cite this