## Abstract

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 language | English |
---|---|

Pages (from-to) | 561-576 |

Number of pages | 16 |

Journal | Journal of the ACM |

Volume | 28 |

Issue number | 3 |

DOIs | |

State | Published - 1 Jul 1981 |

Externally published | Yes |

## Keywords

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