PSPACE-completeness of Modular Supervisory Control Problems*
dc.contributor.author | Rohloff, Kurt | en_US |
dc.contributor.author | Lafortune, Stéphane | en_US |
dc.date.accessioned | 2006-09-11T15:39:41Z | |
dc.date.available | 2006-09-11T15:39:41Z | |
dc.date.issued | 2005-06 | en_US |
dc.identifier.citation | Rohloff, Kurt; Lafortune, Stéphane; (2005). "PSPACE-completeness of Modular Supervisory Control Problems*." Discrete Event Dynamic Systems 15(2): 145-167. <http://hdl.handle.net/2027.42/45090> | en_US |
dc.identifier.issn | 0924-6703 | en_US |
dc.identifier.issn | 1573-7594 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/45090 | |
dc.description.abstract | In this paper we investigate computational issues associated with the supervision of concurrent processes modeled as modular discrete-event systems. Here, modular discrete-event systems are sets of deterministic finite-state automata whose interaction is modeled by the parallel composition operation. Even with such a simple model process model, we show that in general many problems related to the supervision of these systems are PSPACE-complete. This shows that although there may be space-efficient methods for avoiding the state-explosion problem inherent to concurrent processes, there are most likely no time-efficient solutions that would aid in the study of such “large-scale” systems. We show our results using a reduction from a special class of automata intersection problem introduced here where behavior is assumed to be prefix-closed. We find that deciding if there exists a supervisor for a modular system to achieve a global specification is PSPACE-complete. We also show many verification problems for system supervision are PSPACE-complete, even for prefix-closed cases. Supervisor admissibility and online supervision operations are also discussed. | en_US |
dc.format.extent | 179246 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Kluwer Academic Publishers; Springer Science + Business Media, Inc. | en_US |
dc.subject.other | Mathematics | en_US |
dc.subject.other | Systems Theory, Control | en_US |
dc.subject.other | Convex and Discrete Geometry | en_US |
dc.subject.other | Manufacturing, Machines, Tools | en_US |
dc.subject.other | Electronic and Computer Engineering | en_US |
dc.subject.other | Operation Research/Decision Theory | en_US |
dc.subject.other | Modular Systems | en_US |
dc.subject.other | Supervisory Control | en_US |
dc.subject.other | Verification | en_US |
dc.subject.other | Computational Complexity | en_US |
dc.title | PSPACE-completeness of Modular Supervisory Control Problems* | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Industrial and Operations Engineering | en_US |
dc.subject.hlbsecondlevel | Mechanical Engineering | en_US |
dc.subject.hlbtoplevel | Engineering | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, The University of Michigan, 1301 Beal Ave., Ann Arbor, MI, 48109-2122, USA | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, The University of Michigan, 1301 Beal Ave., Ann Arbor, MI, 48109-2122, USA | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/45090/1/10626_2004_Article_6210.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/s10626-004-6210-5 | en_US |
dc.identifier.source | Discrete Event Dynamic Systems | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.