The Reachability Problem for Petri Nets is Not Primitive Recursive

Jérôme Leroux

doi:10.1109/focs52979.2021.00121

FOCS2021顶会

The Reachability Problem for Petri Nets is Not Primitive Recursive

Jérôme Leroux

arXiv DOI 出版方

2021年份

62被引次数

27顶会引用

摘要

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.