On a Weaker Notion of Controllability of a Language K with respect to a Language L

Research output: Contribution to journalArticlepeer-review


A prefix-closed language K ⊆ Σ is said to be controllable with respect to another prefix-closed language L ⊆ Σ if and only if i) K ⊆ L, and ii) KΣu ∩ L [formula omitted] K, where [formula omitted] and [formula omitted] (cf. [6]). In this note, we consider a weaker notion of controllability where it is not required that K [formula omitted] L. If L is the prefix-closed language generated by a plant automaton G, then essentially there exists a supervisor [formula omitted] that is complete with respect to G such that [formula omitted]G) = K [formula omitted] L if and only if K is weakly controllable with respect to L (cf. [6, proposition 5.1]). For an arbitrary modeling formalism we show that the inclusion problem is reducible to the problem of deciding the weaker notion of controllability. Therefore, removing the requirement that K [formula omitted]L from the original definition of controllability does not help the situation from a decidability viewpoint. This observation is then used to identify modeling formalisms that are not viable for supervisory control of the untimed behaviors of discrete event dynamic systems.

Original languageEnglish (US)
Pages (from-to)1446-1447
Number of pages2
JournalIEEE Transactions on Automatic Control
Issue number9
StatePublished - Sep 1993
Externally publishedYes

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On a Weaker Notion of Controllability of a Language K with respect to a Language L'. Together they form a unique fingerprint.

Cite this