SOME COMPLEXITY RESULTS ON TRANSITION-SYSTEMS AND ELEMENTARY NET SYSTEMS

There is a strong relationship between transition systems and elementa ry net systems. We consider the problem of finding an elementary net s ystem corresponding to a given transition system, where the correspond ence is defined as an isomorphism between a transition system and the state transition diagram of an EN system. The problem is decomposed in to two related problems, and we show that these problems are NP-comple te. However, this result does not mean that the original problem is NP -complete. The problem to construct a labeled EN system corresponding to a given transition system is also considered.