On partial observability in discrete event control with pushdown systems

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 ⊆ L_M(G), is there a supervisor φ such that L_M(φ=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.