The Complexity of the Finite Containment Problem for Petri Nets

Ernst W. Mayr, Albert R. Meyer

Research output: Contribution to journalArticlepeer-review

75 Scopus citations


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.

Original languageEnglish
Pages (from-to)561-576
Number of pages16
JournalJournal of the ACM
Issue number3
StatePublished - 1 Jul 1981
Externally publishedYes


  • Petn net
  • incluston proble
  • pdmmve recursive complexity
  • reachabihty set


Dive into the research topics of 'The Complexity of the Finite Containment Problem for Petri Nets'. Together they form a unique fingerprint.

Cite this