A NOTE ON DECIDING THE CONTROLLABILITY OF A LANGUAGE-K WITH RESPECT TO A LANGUAGE-L

If G is a plant automaton and K subset-or-equal-to L(G) is a prefix-closed language there exists a supervisor THETA that is complete with respect to G such that L(THETA/G) = K and L(G) = K if and only if K is controllable with respect to the plant language L(G) (cf. [15]). The language K is said to controllable with respect to L(G) if and only if i) K subset-or-equal-to L, and ii) KSIGMA(u) and L(G) subset-or-equal-to SIGMA, where SIGMA = SIGMA(u) or SIGMA(c) and SIGMA(u) and SIGMA(c) = empty set. The issue of deciding the controllability of K with respect to L(G) has been well studied in the context of finite-state automata [13]. Attempts at studying the above problem in a broader context [1], [17] have all concluded that it is undecidable. In this note, we show that if L(G) and K are represented as free-labeled Petri nets (cf. [12, ch. 6]) then the controllability of K with respect to L(G) is decidable. This result is a direct consequence of the decidability of the Petri net reachability problem [8], [11]. In effect, we have identified a modeling framework capable of finitely representing a class of infinite state systems and controllability is decidable within this framework.