The Complexity of the Finite Containment Problem for Petri Nets
Ernst W Mayr, Albert R. Meyer · Journal of the ACM · 1981
If the reachability set of a Petri net or vector addmon system is fimte, it can be effectively constructed.Furthermore, this finiteness is decidable The complexity of dectsion procedures for the containment and equality problem of f'lmte reachabihty sets rs investigated, and it is shown by reducing a bounded version of Hilbert's Tenth Problem to the finite containment problem that these two problems are extremely hard--that, in fact, the complexity of each decision procedure exceeds any primitive recursive functmn mfimtely often The funte containment and equality problems are thus the first uncontrived decidable problems which are not primitive recursive KEY WORDS AND PHRASES.incluston problem, reachabihty set, Petn net, pdmmve recurs~ve complexity