The Reachability Problem for Petri Nets is Not Primitive Recursive

Jérôme Leroux

doi:10.1109/focs52979.2021.00121

FOCS2021Top-tier venue

The Reachability Problem for Petri Nets is Not Primitive Recursive

Jérôme Leroux

arXiv DOI Publisher

2021Year

62Citations

27Top-tier citations

Abstract

We provide an Ackermannian complexity lower bound for the reachability problem for checking programs, a model equivalent to Petri nets. Moreover in fixed dimension 2d + 4, we show that the problem is F d -hard. As a direct corollary, the reachability problem in dimension 10 is not elementary.