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)

Producción científica: Conference contribution › revisión exhaustiva

13 Citas (Scopus)

Resumen

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.

Idioma original	English
Título de la publicación alojada	Proceedings of the IEEE Conference on Decision and Control
Páginas	85-91
Número de páginas	7
DOI	https://doi.org/10.1109/CDC.1991.261261
Estado	Published - ene 1992
Evento	Proceedings of the 30th IEEE Conference on Decision and Control Part 1 (of 3) - Brighton, Engl Duración: dic 11 1991 → dic 13 1991

Serie de la publicación

Nombre	Proceedings of the IEEE Conference on Decision and Control
ISSN (versión impresa)	0191-2216

Conference

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

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Acceder al documento

10.1109/CDC.1991.261261

Otros archivos y enlaces

Citar esto

@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. En 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

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

Resumen

Serie de la publicación

Conference

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto