2012
A note on controllability of deterministic context-free systems
MASOPUST, TomášBasic information
Original name
A note on controllability of deterministic context-free systems
Authors
Edition
Automatica, Elsevier, 2012, 0005-1098
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Czech Republic
Confidentiality degree
is not subject to a state or trade secret
Impact factor
Impact factor: 2.919
Organization unit
Faculty of Informatics
UT WoS
000307688200057
Keywords in English
Discrete-event systems; Controllability; Deterministic Context-Free Systems; Decidability.
Tags
International impact, Reviewed
Changed: 10/11/2012 11:54, doc. RNDr. Tomáš Masopust, Ph.D., DSc.
Abstract
In the original language
In this paper, we prove that the most important concept of supervisory control of discrete-event systems, the controllability property, is undecidable for two deterministic context-free languages K and L, where L is prefix-closed, even though K is a subset of L. If K is not a subset of L, the undecidability follows from the work by Sreenivas. However, the case where K is a subset of L does not follow from that work because it is decidable whether K and L are equivalent as shown by Senizergues. Thus, our result completes this study. The problem is also mentioned as open in the PhD thesis by Griffin, who extended the supervisory control framework so that the specification language is modelled as a deterministic context-free language (compared to the classical approach where the specification is regular) and the plant language is regular. This approach is of interest because it brings an opportunity for more concise representations of the specification (as discussed, e.g., in the work by Geffert et al.) and, therefore, in some sense it treats the most interesting problem of the current supervisory control theory, the state-space explosion problem.