On the complexity of forbidden state problems for controlled marked graphs

Bruce H. Krogh; Jan Magott; Lawrence E. Holloway

doi:10.1109/CDC.1991.261261

On the complexity of forbidden state problems for controlled marked graphs

Bruce H. Krogh, Jan Magott, Lawrence E. Holloway

Institute for Sustainable Manufacturing (ISM)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

13 Scopus citations

Abstract

The authors discuss the computational complexity of forbidden state problems for discrete event systems modeled by controlled Petri nets (CPNs). They prove polynomial complexity of decidability and solvability for a class of forbidden state problems when the CPN model is a controlled marked graph (CMG). The results for CPNs are compared with results obtained for forbidden state problems using automata-based models. In particular, it is shown that CMGs can model a class of computationally tractable mutual exclusion problems for asynchronous, concurrent cyclic automata with shared events which were shown by C. H. Golaszewski and P. J. Ramadge (1988) to be NP-complete for the general case.

Original language	English
Title of host publication	Proceedings of the IEEE Conference on Decision and Control
Pages	85-91
Number of pages	7
DOIs	https://doi.org/10.1109/CDC.1991.261261
State	Published - Jan 1992
Event	Proceedings of the 30th IEEE Conference on Decision and Control Part 1 (of 3) - Brighton, Engl Duration: Dec 11 1991 → Dec 13 1991

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0191-2216

Conference

Conference	Proceedings of the 30th IEEE Conference on Decision and Control Part 1 (of 3)
City	Brighton, Engl
Period	12/11/91 → 12/13/91

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Access to Document

10.1109/CDC.1991.261261

Cite this

@inproceedings{eb5d8f7f21244585a11f68f090bfd953,

title = "On the complexity of forbidden state problems for controlled marked graphs",

abstract = "The authors discuss the computational complexity of forbidden state problems for discrete event systems modeled by controlled Petri nets (CPNs). They prove polynomial complexity of decidability and solvability for a class of forbidden state problems when the CPN model is a controlled marked graph (CMG). The results for CPNs are compared with results obtained for forbidden state problems using automata-based models. In particular, it is shown that CMGs can model a class of computationally tractable mutual exclusion problems for asynchronous, concurrent cyclic automata with shared events which were shown by C. H. Golaszewski and P. J. Ramadge (1988) to be NP-complete for the general case.",

author = "Krogh, {Bruce H.} and Jan Magott and Holloway, {Lawrence E.}",

year = "1992",

month = jan,

doi = "10.1109/CDC.1991.261261",

language = "English",

isbn = "0780304500",

series = "Proceedings of the IEEE Conference on Decision and Control",

pages = "85--91",

booktitle = "Proceedings of the IEEE Conference on Decision and Control",

note = "Proceedings of the 30th IEEE Conference on Decision and Control Part 1 (of 3) ; Conference date: 11-12-1991 Through 13-12-1991",

}

Krogh, BH, Magott, J & Holloway, LE 1992, On the complexity of forbidden state problems for controlled marked graphs. in Proceedings of the IEEE Conference on Decision and Control. Proceedings of the IEEE Conference on Decision and Control, pp. 85-91, Proceedings of the 30th IEEE Conference on Decision and Control Part 1 (of 3), Brighton, Engl, 12/11/91. https://doi.org/10.1109/CDC.1991.261261

On the complexity of forbidden state problems for controlled marked graphs. / Krogh, Bruce H.; Magott, Jan; Holloway, Lawrence E.
Proceedings of the IEEE Conference on Decision and Control. 1992. p. 85-91 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the complexity of forbidden state problems for controlled marked graphs

AU - Krogh, Bruce H.

AU - Magott, Jan

AU - Holloway, Lawrence E.

PY - 1992/1

Y1 - 1992/1

N2 - The authors discuss the computational complexity of forbidden state problems for discrete event systems modeled by controlled Petri nets (CPNs). They prove polynomial complexity of decidability and solvability for a class of forbidden state problems when the CPN model is a controlled marked graph (CMG). The results for CPNs are compared with results obtained for forbidden state problems using automata-based models. In particular, it is shown that CMGs can model a class of computationally tractable mutual exclusion problems for asynchronous, concurrent cyclic automata with shared events which were shown by C. H. Golaszewski and P. J. Ramadge (1988) to be NP-complete for the general case.

AB - The authors discuss the computational complexity of forbidden state problems for discrete event systems modeled by controlled Petri nets (CPNs). They prove polynomial complexity of decidability and solvability for a class of forbidden state problems when the CPN model is a controlled marked graph (CMG). The results for CPNs are compared with results obtained for forbidden state problems using automata-based models. In particular, it is shown that CMGs can model a class of computationally tractable mutual exclusion problems for asynchronous, concurrent cyclic automata with shared events which were shown by C. H. Golaszewski and P. J. Ramadge (1988) to be NP-complete for the general case.

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

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

U2 - 10.1109/CDC.1991.261261

DO - 10.1109/CDC.1991.261261

M3 - Conference contribution

AN - SCOPUS:0026716884

SN - 0780304500

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 85

EP - 91

BT - Proceedings of the IEEE Conference on Decision and Control

T2 - Proceedings of the 30th IEEE Conference on Decision and Control Part 1 (of 3)

Y2 - 11 December 1991 through 13 December 1991

ER -

On the complexity of forbidden state problems for controlled marked graphs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this