ON A WEAKER NOTION OF CONTROLLABILITY OF A LANGUAGE-K WITH RESPECT TOA LANGUAGE-L

A prefix-closed language K subset-or-equal-to SIGMA is said to be con trollable with respect to another prefix-closed language L subset-or-e qual-to SIGMA if and only if i) K subset-or-equal-to L, and ii) KSIGM A(u) and L subset-or-equal-to K, where SIGMA = SIGMA(u) or SIGMA(c) an d SIGMA(u) and SIGMA(c) = empty set (cf. [6]). In this note, we consid er a weaker notion of controllability where it is not required that K subset-or-equal-to L. If L is the prefix-closed language generated by a plant automaton G, then essentially there exists a supervisor THETA that is complete with respect to G such that L(THETA\G) = K and L if a nd only if K is weakly controllable with respect to L (cf. [6, proposi tion 5.1]). For an arbitrary modeling formalism we show that the inclu sion problem is reducible to the problem of deciding the weaker notion of controllability. Therefore, removing the requirement that K subset -or-equal-to L from the original definition of controllability does no t help the situation from a decidability viewpoint. This observation i s then used to identify modeling formalisms that are not viable for su pervisory control of the untimed behaviors of discrete event dynamic s ystems.