On the complexity of forbidden state problems for controlled marked graphs
Bruce H. Krogh, Jan Magott, L.E. Holloway · 2002
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.>