The Reachability Problem for Petri Nets is Not Primitive Recursive
Jérôme Leroux
Abstract
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.
Topics & Concepts
ReachabilityPetri netReachability problemUpper and lower boundsLift (data mining)Computer scienceDimension (graph theory)Process architectureStochastic Petri netMathematicsDiscrete mathematicsTheoretical computer scienceCombinatoricsAlgorithmMathematical analysisData miningFormal Methods in Verificationsemigroups and automata theoryPetri Nets in System Modeling