Title :
On the complexity of forbidden state problems for controlled marked graphs
Author :
Krogh, Bruce H. ; Magott, Jan ; Holloway, Lawrence E.
Author_Institution :
Dept. of Electr. & Comput. Eng., Carnegie-Mellon Univ., Pittsburgh, PA, USA
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
Keywords :
Petri nets; automata theory; computational complexity; decidability; discrete time systems; NP-complete; asynchronous concurrent cyclic automata; automata-based models; computational complexity; computationally tractable mutual exclusion problems; controlled Petri nets; controlled marked graphs; decidability; discrete event systems; forbidden state problems; polynomial complexity; shared events; solvability; Automata; Automatic control; Computational complexity; Concurrent computing; Control system synthesis; Control systems; Discrete event systems; Petri nets; Polynomials; Power system modeling; Robots;
Conference_Titel :
Decision and Control, 1991., Proceedings of the 30th IEEE Conference on
Conference_Location :
Brighton
Print_ISBN :
0-7803-0450-0
DOI :
10.1109/CDC.1991.261261
