Complexity of Verifying Nonblockingness in Modular Supervisory Control
arXiv:1703.050119 citationsh-index: 16
Originality Synthesis-oriented
AI Analysis
Provides foundational complexity bounds for a core verification problem in modular supervisory control, relevant to control theorists and engineers.
The paper proves new complexity results for verifying nonblockingness in modular supervisory control of discrete event systems, showing the problem is PSPACE-complete.
Complexity analysis becomes a common task in supervisory control. However, many results of interest are spread across different topics. The aim of this paper is to bring several interesting results from complexity theory and to illustrate their relevance to supervisory control by proving new nontrivial results concerning nonblockingness in modular supervisory control of discrete event systems modeled by finite automata.