Supervisor existence for modular discrete-event systems

Kurt R. Rohloff; Stephane Lafortune

doi:10.1016/S1474-6670(17)34669-4

Supervisor existence for modular discrete-event systems

Kurt R. Rohloff, Stephane Lafortune

Research output: Contribution to journal › Conference article › peer-review

5 Scopus citations

Abstract

This paper examines decision problems involving existence conditions for supervisors of modular systems. We investigate the problem of deciding if there exists a supervisor that can augment a modular system to satisfy a given modular global specification. Our system and specification modules are "discrete-event systems" modeled as finite-state automata. The parallel composition operation is used to model the interaction between the various modules. A supervisor for a discrete-event system observes events as they occur in the system and enforces a control action by disabling some controllable events. We find that these types of problems are generally PSPACE-complete for a large class of systems and specifications.

Original language	English (US)
Pages (from-to)	205-210
Number of pages	6
Journal	IFAC Proceedings Volumes (IFAC-PapersOnline)
Volume	36
Issue number	18
DOIs	https://doi.org/10.1016/S1474-6670(17)34669-4
State	Published - 2003
Externally published	Yes
Event	2nd IFAC Conference on Control Systems Design, CSD 2003 - Bratislava, Slovakia Duration: Sep 7 2003 → Sep 10 2003

All Science Journal Classification (ASJC) codes

Control and Systems Engineering

Keywords

Computational Complexity
Discrete Event Systems
Modular and Concurrent Systems
Regular Languages
Specification and Verification
Supervision and Control

Access to Document

10.1016/S1474-6670(17)34669-4

Cite this

@article{c8d673b99fb6466ab48c6b14303f1084,

title = "Supervisor existence for modular discrete-event systems",

abstract = "This paper examines decision problems involving existence conditions for supervisors of modular systems. We investigate the problem of deciding if there exists a supervisor that can augment a modular system to satisfy a given modular global specification. Our system and specification modules are {"}discrete-event systems{"} modeled as finite-state automata. The parallel composition operation is used to model the interaction between the various modules. A supervisor for a discrete-event system observes events as they occur in the system and enforces a control action by disabling some controllable events. We find that these types of problems are generally PSPACE-complete for a large class of systems and specifications.",

keywords = "Computational Complexity, Discrete Event Systems, Modular and Concurrent Systems, Regular Languages, Specification and Verification, Supervision and Control",

author = "Rohloff, {Kurt R.} and Stephane Lafortune",

note = "Publisher Copyright: {\textcopyright} 2003 IFAC.; 2nd IFAC Conference on Control Systems Design, CSD 2003 ; Conference date: 07-09-2003 Through 10-09-2003",

year = "2003",

doi = "10.1016/S1474-6670(17)34669-4",

language = "English (US)",

volume = "36",

pages = "205--210",

journal = "IFAC Proceedings Volumes (IFAC-PapersOnline)",

issn = "1474-6670",

publisher = "IFAC Secretariat",

number = "18",

}

TY - JOUR

T1 - Supervisor existence for modular discrete-event systems

AU - Rohloff, Kurt R.

AU - Lafortune, Stephane

PY - 2003

Y1 - 2003

N2 - This paper examines decision problems involving existence conditions for supervisors of modular systems. We investigate the problem of deciding if there exists a supervisor that can augment a modular system to satisfy a given modular global specification. Our system and specification modules are "discrete-event systems" modeled as finite-state automata. The parallel composition operation is used to model the interaction between the various modules. A supervisor for a discrete-event system observes events as they occur in the system and enforces a control action by disabling some controllable events. We find that these types of problems are generally PSPACE-complete for a large class of systems and specifications.

AB - This paper examines decision problems involving existence conditions for supervisors of modular systems. We investigate the problem of deciding if there exists a supervisor that can augment a modular system to satisfy a given modular global specification. Our system and specification modules are "discrete-event systems" modeled as finite-state automata. The parallel composition operation is used to model the interaction between the various modules. A supervisor for a discrete-event system observes events as they occur in the system and enforces a control action by disabling some controllable events. We find that these types of problems are generally PSPACE-complete for a large class of systems and specifications.

KW - Computational Complexity

KW - Discrete Event Systems

KW - Modular and Concurrent Systems

KW - Regular Languages

KW - Specification and Verification

KW - Supervision and Control

UR - http://www.scopus.com/inward/record.url?scp=1542282396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1542282396&partnerID=8YFLogxK

U2 - 10.1016/S1474-6670(17)34669-4

DO - 10.1016/S1474-6670(17)34669-4

M3 - Conference article

AN - SCOPUS:1542282396

SN - 1474-6670

VL - 36

SP - 205

EP - 210

JO - IFAC Proceedings Volumes (IFAC-PapersOnline)

JF - IFAC Proceedings Volumes (IFAC-PapersOnline)

IS - 18

T2 - 2nd IFAC Conference on Control Systems Design, CSD 2003

Y2 - 7 September 2003 through 10 September 2003

ER -

Supervisor existence for modular discrete-event systems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this