On the Existence of Finite State Supervisors for Arbitrary Supervisory Control Problems

Given two prefix closed languages K, L ⊆ Σ*, where K ⊆ ⊆ L represents the desired closed-loop behavior and L is the open-loop behavior, there exists a finite-state supervisor that enforces K in the closed loop if and only if there is a regular, prefix-closed language M ⊆ ⊆ Σ*such that: 1) M Σ_u⊓ L ⊆ ⊆ M, and 2) M ⊓ L = K (cf. [9] for an equivalent definition). In this paper, we_show that this is equivalent to: 1) the controllability of sup{P ⊆ ⊆ K ∪ L | pr(P) = P} with respect to Σ*, and 2) the regularity of sup{P ⊆ ⊆ K ∪ | pr(P) = P}, where L = Σ*— L and pr(•) is the set of prefixes of strings in the language argument. We use this property to investigate the issue of deciding the existence of a finite-state supervisor for different representations. We also present some properties of the language sup{P ⊆ ⊆ K ∪ L | pr(P) = P}, along with implications to the synthesis of solutions to the supervisory control problem with the fewest states.