The Reachability Problem for Petri Nets is Not Primitive Recursive

2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021)（2021）

引用 66|浏览65

暂无评分

摘要

We present a way to lift up the Tower complexity lower bound of the reachability problem for Petri nets to match the Ackermannian upper bound closing a long standing open problem. We also prove that the reachability problem in dimension 17 is not elementary.

查看译文

关键词

Petri nets, reachability, complexity, fast growing functions

AI 理解论文

溯源树

样例

生成溯源树，研究论文发展脉络

Chat Paper

正在生成论文摘要