<p>Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does <em>not</em> terminate from a marking $M_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $M_0 \rightarrow^* M \rightarrow^\sigma M'$, $|\sigma| &gt; 0$ and $M' \geq M$. By <a href="https://doi.org/10.1016/0304-3975(78)90036-1" rel="noreferrer">[Rac78]</a>, if such a firing sequence exists, then there is one of length doubly exponential. Thus, it can be guessed non deterministically, which shows that the problem is in EXPSPACE. By [Lip76], the problem is EXPSPACE-hard and hence EXPSPACE-complete. See, e.g., Section 3.2.4 of these <a href="https://www7.in.tum.de/um/courses/petri/SS2018/PNSkript.pdf" rel="noreferrer">lecture notes</a> for a presentation of Lipton's reduction.</p>

<p>[Rac78] Charles Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6:223–231, 1978.</p>

<p>[Lip76] Richard J. Lipton. The reachability problem requires exponential space. Technical report 63, Department of Computer Science, Yale University, 1976.</p>

CC BY-SA 4.0
2018-05-05T11:10:49.277Z
2018-05-05T11:10:49.277Z
Michael Blondin
<p>Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example consists in running the net until either all configurations have been reached or a repeating one is found. Is there any clever way to solve the problem? What is the lower bound complexity?</p>

CC BY-SA 3.0
2018-04-28T00:44:05.920Z
Section 7 of https://www7.in.tum.de/um/bibdb/esparza/course.pdf (rule of thumb 6) suggests that it's probably EXPSPACE-hard.
Alex Meiburg
<lower-bounds><decidability><complexity><petri-nets>
Petri net termination
Alberto
# Petri net termination

(Asked by: username_0 on 2018-04-27)

Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example consists in running the net until either all configurations have been reached or a repeating one is found. Is there any clever way to solve the problem? What is the lower bound complexity?

**Tags:** lower-bounds, decidability, complexity, petri-nets
> **Comments:**
> **username_1**: Section 7 of https://www7.in.tum.de/um/bibdb/esparza/course.pdf (rule of thumb 6) suggests that it's probably EXPSPACE-hard.  

---

## 1 answers

### Answer by username_2 on 2018-05-05. Score: 6

Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does *not* terminate from a marking $M\_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $M\_0 \rightarrow^\* M \rightarrow^\sigma M'$, $|\sigma| > 0$ and $M' \geq M$. By [[Rac78]](https://doi.org/10.1016/0304-3975(78)90036-1), if such a firing sequence exists, then there is one of length doubly exponential. Thus, it can be guessed non deterministically, which shows that the problem is in EXPSPACE. By [Lip76], the problem is EXPSPACE-hard and hence EXPSPACE-complete. See, e.g., Section 3.2.4 of these [lecture notes](https://www7.in.tum.de/um/courses/petri/SS2018/PNSkript.pdf) for a presentation of Lipton's reduction.

[Rac78] Charles Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6:223–231, 1978.

[Lip76] Richard J. Lipton. The reachability problem requires exponential space. Technical report 63, Department of Computer Science, Yale University, 1976.


---

