Note on deciding the controllability of a language K with respect to a language L

Research output: Contribution to journalArticlepeer-review

Abstract

If G is a plant automaton and K ⊃ L(G) is a prefix-closed language there exists a supervisor Θ that is complete with respect to G such that L(Θ|G) = K intersect L(G) = K if and only if K is controllable with respect to the plant language L(G) (ef.). The language K is said to controllable with respect to L(G) if and only if i) K ⊃ L, and ii) KΣu intersect L(G) ⊃ K, where Σ = Σu union Σc and Σu intersect Σc = O. The issue of deciding the controllability of K with respect to L(G) has been well studied in the context of finite-state automata. Attempts at studying the above problem in a broader context 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.) 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. 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.

Original languageEnglish (US)
Pages (from-to)658-662
Number of pages5
JournalIEEE Transactions on Automatic Control
Volume38
Issue number4
DOIs
StatePublished - Apr 1993
Externally publishedYes

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Note on deciding the controllability of a language K with respect to a language L'. Together they form a unique fingerprint.

Cite this