The reachability problem for Petri nets is the task to decide, for a given Petri net N and a marking m, whether m can be reached from the initial con guration of N by ring a valid sequence of transitions. In this paper, we show that the reachability problem for acyclic join-free Petri nets is NP-complete.
The concept of Petri nets goes back to Carl Adam Petri [
Petri net analysis deals, for example, with the task to deduce behavioral
properties of the model like reachability, liveness or deadlock, and is subject of
a dedicated annual contest [
In this paper, we deal with a special instance of a central algorithmic problem of Petri net analysis: The reachability problem for Petri nets is the task to decide, for a given Petri net N and a marking m, whether m is reachable from the initial con guration of N by ring a sequence of transitions of N .
In theoretical computer science, this problem has been investigated for many
years from both the computability and the complexity point of view: while the
decidability status of the problem has been open for a long time, it was
nally shown in [
However, from the complexity point of view, better results can be obtained for
structural restricted Petri nets: for example, the complexity of the reachability
problem boils down to PSPACE-complete for 1-safe Petri nets; the problem is
NP-complete for acyclic Petri nets [
Free-choice Petri nets de ne one of the most important sub-classes of Petri
nets. The reachability problem generally remains EXPSPACE-hard for these
nets, but becomes PSPACE-complete for 1-safe free-choice Petri nets, and it is
NP-complete for live 1-safe free-choice Petri nets [
Join-free Petri nets build a particular yet useful subclass of Petri nets and
allow every transition to have at most one input place [
The paper is structured as follows: The next Section 2 provides basic de nitions and supports them with some examples. After that, Section 3 provides the announced hardness result. Finally, Section 4 brie y closes the paper. 2
In this section, we introduce relevant basic notions around Petri nets and show some examples.
De nition 1 (Petri Nets). A Petri net, also Petri net, N = (P; T; f; m0) consists of nite and disjoint sets of places P and transitions T , a (total) ow f : ((P T ) [ (T P )) ! N and an initial marking m0 : P ! N. De nition 2 (Preset, postset). The nodes of a Petri net N = (P; T; f; m0) are P [ T . The preset of a node x is de ned by x = fy j f (y; x) > 0g, the postset of x is de ned by x = fy j f (x; y) > 0g. Notice that x \ x is not necessarily empty. For a transition t, the pre-places are all places in t; the post-places are all places in t . Pre-transitions and post-transitions for a place are de ned analogously. Subclasses of Petri nets. Within the class of Petri nets, we can determine various subclasses, which di er in their ow relation structure: A Petri net N = (P; T; f; m0) is called acyclic if its underlying directed graph G = (V; E) with vertices V = P [ T and edges E = f(x; y) j x; y 2 V; f (x; y) > 0g has no directed circuits. Moreover, N is join-free, if every transition t has at most one pre-place, that is, j tj 1. If the co-domain of the ow f is restricted to f0; 1g, then N is called plain. Furthermore, N is free-choice, if it is plain and, additionally, if it holds for two arbitrary distinct transitions t and t0 2 T : t \ t0 6= ; ) t = t0. This means that if two transitions share one pre-place, then they share all pre-places. Notice that a plain join-free Petri net is free-choice by triviality, since in this case there is no transition with several pre-places.
Figure 1 shows the net N that is obviously acyclic and join-free and freechoice as well.
De nition 3 (Transition Rule). Let N = (P; T; f; m0) be a Petri net. Transition t is enabled in marking m if 8p : m(p) f (p; t). Firing a Transition t leads from marking m to marking m0 if t is enabled in m and 8p : m0(p) = m(p) f (p; t) + f (t; p), denoted as m !t m0.
De nition 4 (Firing Sequence, Reachability Set). Let N = (P; T; f; m0) be a Petri net and m; m0 some (not necessarily distinct) markings of N . We say a sequence (of transitions) = ! 2 T can re at m and its ring leads to m0, denoted by m ! m0 if and only if either = " and m = m0 or = !a, where !m020 !aT ma0n.dWae 2calTl ,RaSn(dNt)he=refmis ja9ma2rkTing: mm000 o!f Nmgsutchhe trheaatchmabi!!lityms0e0ta(nodf N ), which contains all of N 's reachable markings.
De nition 5 (Set of transitions of a sequence). Let N = (P; T; f; m0) be a Petri net and let 2 T . We de ne the set S of transitions of inductively as follows: If = ", then S = ; and, otherwise, if = !a with ! 2 T and a 2 T , then S = fag [ S!.
Using the transition rule, a Petri net induces a labeled transition system, called the reachability graph. De nition 6 (Labeled Transition System, Reachability Graph). A (deterministic) transition system T S = [S; s0; R; A] is a directed labeled graph with the set of nodes S (called states), an initial state s0 2 S, and a transition relation R S A S with some set of actions A. The reachability graph of a Petri net N is a transition system, where the set of states is RS(N ), m0 serves as the initial state and (m; t; m0) 2 R i m !t m0.
In this paper, we consider the following instance of the reachability problem:
Input: A tuple (N; m) where N = (P; T; f; m0) is an acyclic and join-free
Petri net and m is a marking of N .
Question: Does there exist a ring sequence 2 T such that m0 ! m?
Example 1. Let N be the given net in Figure 1 with the initial marking m0 = (1; 0; 0; 0) whereas, with a little abuse of de nition, the tuple is an abbreviation of m0(pH0 ) = 1; m0(pH1 ) = m0(pH2 ) = m0(pH3 ) = 0. In m0, only t0 is activated. Firing t0 leads to marking m1 = (0; 1; 1; 0). The marking m2 = (0; 0; 0; 2) is reachable, because the ring sequence t0t1t2 leads us from m0 to m2. On the contrary, marking m3 = (1; 0; 0; 1) is not reachable, as for producing tokens on pH3 , we need to consume the token from pH0 rst to activate the transition t1 and t2. 3
The following theorem provides the main result of this paper: Theorem 1. Reachability for Acyclic Join-free Petri Nets is NPcomplete.
The remainder of this paper is dedicated to the proof of Theorem 1: First
of all, by a result of [
Consequently, in order to complete the proof of Theorem 1, it remains to
show that Reachability for Acyclic Join-free Petri Nets is NP-hard.
The proof of the NP-hardness is based on a polynomial-time reduction of the
following particular Sat-problem, which is known to be NP-complete from [
Input: A pair (V; F ) consisting of a set V of boolean variables and a set F = fC0; : : : ; Cn 1g consisting of 3-variable-clauses, such that Ci = fXi0 ; Xi1 ; Xi2 g V and i0 < i1 < i2 for all i 2 f0; : : : ; n 1g. Every variable X 2 V appears in exactly three di erent clauses.
Question: Does there exist a one-in-three model for (V; F ), i.e. a set S V such that jS \ Cij = 1 for all i 2 f0; : : : ; n 1g? Example 2. The instance (V; F ) of CM 1 in 3 3Sat with set of variables V = fX0; X1; : : : ; X5g and set of 3-variable-clauses F = fC0; C1; : : : ; C5g, where { C0 = fX0; X1; X2g { C1 = fX0; X1; X3g { C2 = fX0; X1; X5g { C3 = fX2; X3; X4g { C4 = fX2; X4; X5g { C5 = fX3; X4; X5g allows a positive decision, since S = fX0; X4g is a one-in-three model for (V; F ).
Notice that the number of variables and the number of clauses are equal for any arbitrary instance of CM 1 in 3 3Sat. This concludes from the problem de nition of CM 1 in 3 3Sat, as every variable occurs exactly in three di erent clauses and each clause consists of three di erent variables.
In the remainder of this paper, unless explicitly stated otherwise, let (V; F ) be an arbitrary but xed input of CM 1 in 3 3Sat, where V = fX0; X1; : : : ; Xn 1g and F = fC0; C1; : : : ; Cn 1g such that Ci = fXi0 ; Xi1 ; Xi2 g and i0 < i1 < i2 for all i 2 f0; : : : ; n 1g.
Our reduction uses the following simple yet crucial fact: Fact 1. If S
V is a one-in-three model for F , then jSj = n3 . ewxeachtalvyeththreaet djFisjti=nc3tjcSlja.uTsehsisa nimd,pmlieosrejSovje=r, jn3S \Cij = 1 for all i 2 f0; : : : ; n .
The reduction. In order to prove the hardness part of Theorem 1, we translate the instance (V; F ) into an input (N; m) of Reachability for Acyclic Join-free Petri Nets such that there is a one-in-three model for (V; F ) if and only if m is reachable from the initial marking of N .
For the Petri net N , we introduce the following components: { for every i 2 f0; : : : ; n 1g, the place pCi that represents the clause Ci and is initially marked by one token: m0(pCi ) = 1; { for every i 2 f0; : : : ; n 1g, the initially empty place pXi : m(pXi ) = 0; { for every i 2 f0; : : : ; n 1g, three transitions t0Xi ; t1Xi and t2Xi that represent the three occurrences of the variable Xi in the clauses of F : if C`0 ; C`1 ; C`2 with `0 < `1 < `2 2 f0; : : : ; n 1g are exactly the clauses that contain Xi, then, for all j 2 f0; 1; 2g, it is pC`j the unique pre-place of the transition tjXi , where f (pC`j ; tjXi ) = 1; moreover, for all j 2 f0; 1; 2g, the place pXi is the only post-place of tjXi , where f (tjXi ; pXi ) = 1; { for every i 2 f0; : : : ; n 1g, three other helper-transitions t0Hi ; t1Hi ; t2Hi and two helper-places pHi and qHi , such that f (t0Hi ; pHi ) = 1 and f (t0Hi ; pXi ) = 1, f (pHi ; t1Hi ) = 1 and f (t1Hi ; qHi ) = 1 and f (t1Hi ; pXi ) = 1, f (qHi ; t2Hi ) = 1 and f (t2Hi ; pXi ) = 1, m(pHi ) = m(qHi ) = 0.
The reduction yields the Petri net N = (P; T; f; m0) with places and transitions as follows: Lemma 1. If there is a one-in-three model for F , then m is a reachable marking of N . Proof. Recall that any one-in-three model for F has exactly n3 elements by Fact 1. Let i0; : : : ; i n3 1 2 f0; : : : ; n 1g be n3 pairwise distinct indices, such that S = fXi0 ; : : : ; Xi n3 1 g is a one-in-three model for F , that is, for all i 2 f0; : : : ; n 1g, it holds S \ Ci = fXi` g for some ` 2 f0; : : : ; n3 1g. Moreover, let j0; : : : ; j 23n 1 2 f0; : : : ; n 1g be the 23n pairwise distinct indices such that fXj0 ; : : : ; Xj 23n 1 g = V n S. We now show, that the marking m is reachable from the marking m0 of N by a ring sequence, which can be derived from S. Initially, only the clause places pC0 ; : : : ; pCn 1 are marked with one token each. Therefore, for every ` 2 f0; : : : ; n3 1g, the transitions t0Xi` ; t1Xi` ; t2Xi` , which represent the occurrences of the variable Xi` in the clauses of F , are all activated. Since S is a one-in-three model, for all j; ` 2 f0; : : : ; n3 1g and all h; k 2 f0; 1; 2g, the following is true: if (j; h) 6= (`; k), then tXihj \ tXik` = ;. Hence, the following sequence can re at m0 (and results in the marking m1, de ned below): 1 = t0Xi0 tXi0 tXi0 tXi1 tXi1 tXi1 : : : t0Xi n3 1 tXi n3 1 tXi n3 1
1 2 0 1 2 1 2 |m1(p{Xzi0 )=3} |m1(p{Xzi1 )=3} | } m1(pXi{n3z 1 )=3 For all ` 2 f0; : : : ; n3 1g and all j 2 f0; 1; 2g, ring tjXi` consumes the only token from its unique pre-place and produces exactly one token on its unique post-place pXi` . Consequently, ring the transition sequence 1 leads from m0 to the marking m1, such that m1(pXi` ) = 3 for all ` 2 f0; : : : ; n3 1g and m1(p) = 0 for all other places p 2 P n fpXi0 ; : : : ; pXi n 1 g.
3 In order to obtain m, we extend 1 by the sequence 2 = t0Hj0 t1Hj0 t2Hj0 t0Hj1 t1Hj1 t2Hj1 : : : t0Hj 23n 1 t1Hj 23n 1 t2Hj 23n 1 | m(pX{jz0 )=3 } | m(pX{jz1 )=3 } | } m(pXj {23nz 1 )=3 It is easy to see, that 2 can be red at m1, since t0Hj` does not have a pre-place foofrthaell s`ub2sefq0u;e: n::c;e 2t3n0Hj` t11Hgj.` Mt2Hojr`eodvoeers, nfoortheivnegryels`e2thfa0n; :t:o: ;p2u3nt thr1ege, ttohkeensrionng pXj` : t0Hj` puts a token on pHj` and a token on pXj` ; after that t1Hj` consumes the token from pHj` and puts a token on qHj` and another one on pXj` ; nally, 2 tHj` consumes the token from qHj` and puts a third token on pXj` . In particular, m0
1 !2 m, which proves the lemma.
Conversely, by the following lemma, if (N; m) is a yes-instance, then (V; F ) is a yes-instance as well: Lemma 2. Let 2 T and let i 2 f0; : : : ; n
be a ring sequence of N that leads to the marking m 1g be arbitrary but xed. 1. If t0Hi 2 S , then tjXi 62 S for all j 2 f0; 1; 2g. 2. If there is j 2 f0; 1; 2g such that tjXi 2 S , then t0Xi ; t1Xi ; t2Xi 2 S . 3. The set S = fXi j t0Xi ; t1Xi ; t2Xi 2 S g de nes a one-in-three model for F . Proof. (1): The transition t0Hi puts a token on pHi and a token on pXi . Since pmu(tpsHai )to=ke0naonndqpHHiian=dofnt1HpiXgi, awnedhaasvweetlhl.aStitn1Hcie 2m(SqH.i S)i=mi0laarnlyd, tqrHainsi=tiofnt2Hti1Hgi, the transition t2Hi occurs in . Finally, since the ring of t2Hi puts a token on pXi , and pXi = ;, and m(pXi ) = 3, we have that pXi \ S = ft0Hi ; t1Hi ; t2Hi g. This implies the claim.
(2): Since tjXi 2 S , by (1), we have that t0Hi 62 S , which certainly implies t1Hi 62 and t2Hi 62 . Hence, by m(pXi ) = 3, we have that every of the transitions t0Xi ; t1Xi and t2Xi has put a token on pXi , which implies the claim. (3): Recall that the i-th clause is given by Ci = fXi0 ; Xi1 ; Xi2 g. Since k m(pCi ) = 0, there are j 2 f0; 1; 2g and k 2 f0; 1; 2g, such that tXij 2 S . By (2), this implies t0Xij ; t1Xij ; t2Xij 2 S and thus Xij 2 Ci \ S. In particular, we have that S \ Ci 6= ;.
S. BIfyjCdie\nSitjion2o,fthSe,nththiseriemaprleiedsist0Xtiinjc;tt1Xj;ij`; 2t2Xfij0;21;S2g sauncdh tt0Xhia`t; tX1Xiij`;; Xt2Xi`i`22CS\ and, by the construction of N , this implies jpCi \S j 2 as well. This is a contradiction, since m0(pCi ) = 1 and pCi = ; and f (pCi ; t) = 1 for all t 2 pCi . Consequently, jCi \ Sj = 1.
Finally, by the arbitrariness of i, we have that jCi \ Sj = 1 for all i 2 f0; : : : ; n 1g, which proves the claim.
Since the reduction is obviously polynomial and Reachability for Acyclic Join-free Petri Nets belongs to NP, by Lemma 1 and Lemma 2, we have proven Theorem 1. 4
In this paper, we show that the well-known reachability problem of Petri nets is NP-complete for the class of acyclic join-free Petri nets, which are also freechoice. The hardness-proof bases on the reduction of a particular SAT-problem. The membership in NP heavily bases on the fact that the nets addressed are acyclic. Hence, it remains future work to determine the complexity of the reachability problem for join-free Petri nets that may contain cycles.
Acknowledgements. We would like to thank the anonymous reviewers for their detailed comments and valuable suggestions. In particular, we thank the reviewer for the hint that improved the original reduction, which provided an acyclic join-free Petri net with general arc weights, instead of the current plain net.