A primitive recursive algorithm for the general Petri net reachability problem
Zakaria Bouziane · 2002
E. Mayr and R. Kosaraju (1981) proved the decidability of the general Petri net reachability problem. However their algorithms are non primitive recursive. Since then the primitive recursiveness of this problem was stated as an open problem. In this paper we give a double exponential space algorithm for the general Petri net reachability problem.