TUMTECHNISCHE UNIVERSITÄT MÜNCHENINSTITUT FÜR INFORMATIK

TechnischerTechnische Universität MünchenInstitut für InformatikBericht

Ernst W. Mayr and Jeremias Weihmann

TUM-I1514

Complexity Results for Fork-Free PetriNets

Complexity Results for Fork-Free Petri Nets

Ernst W. Mayr∗ Jeremias Weihmann∗

January 26, 2015

Abstract

We investigate fork-free Petri nets (�-PNs), which are those Petri nets for which eachtransition has at most one output place, connected by an arc with arbitrary multiplicity. Weshow that, for each reachable marking, there is a canonical �ring sequence with nice propertiesleading to the marking. The existence of such sequences enables us to apply a mathematicalframework for Petri nets which provides upper bounds for many classical problems. Usingthis framework and known lower bounds we show that the (zero-)reachability, boundedness,and covering problems of �-PNs are PSPACE-complete. For the liveness problem of �-PNswe obtain membership in PSPACE. Last, we show that the containment and equivalenceproblems of �-PNs are PSPACE-hard and decidable in exponential space.

1 Introduction

Fork-free Petri nets (�-PNs) are Petri nets, whose transitions have at most one outgoing arc (witharbitrary multiplicity). From the perspective of modeling, �-PNs could be used to represent sys-tems where di�erent entities are transformed into many copies of the same end product. Thisclass has already been considered by Holt and Commoner [2]. Lien [4] investigated terminationproperties of backward-concurrent-free Petri nets, a closely related subclass, where each transitionhas exactly one outgoing arc.Teruel and Silva [10, 11, 12] published a series of papers on equalcon�ict systems, a natural generalization of free-choice Petri nets containing the class of �-PNs.Amer-Yahia et al. [1] presented approaches based on techniques of linear algebra to reason aboutproperties of �-PNs among other things. Morita and Watanabe [8] showed that the RecLFS prob-lem of weighted state machines (WSMs), a subclass of �-PNs where each transition additionallyhas at most one incoming arc, is NP-hard, even if restricted to WSMs with exactly two di�erentarc multiplicities (the RecLFS problem asks, given a Petri net and a Parikh vector, if the Parikhvector is enabled in the Petri net). Taoka and Watanabe [9] investigated RecLFS for a subclass ofWSMs with cactus structure. However, no improved upper bounds or even completeness-results forclassical problems like RecLFS, reachability, boundedness, covering, containment or equivalencehave been found so far. In this paper, we �ll this gap.

We now describe our main tools. In [5], we showed (among other things) that the problemsabove are PSPACE-hard for WSMs, and therefore also for �-PNs in general (we also refer tothe journal version [7]). Furthermore, in Mayr and Weihmann [6], we provided a mathematicalframework which can be used to obtain upper bounds for these problems if the Petri nets ofthe class under consideration allow for certain (canonical) �ring sequences leading to reachablemarkings. In the same paper, they applied the framework to conservative Petri nets to obtainPSPACE-completeness for some of the problems above. This framework can also be used toobtain such results for join-free Petri nets (jf-PNs) which are those Petri nets for which eachtransition has at most one input place, connected with an arc with arbitrary multiplicity (i. e.,they are the inverse nets of �-PNs). Before the framework existed, we showed in [5], using similarideas, that the RecLFS, (zero-) reachability, boundedness, and covering problems of jf-PNs are

∗Institut für Informatik, Technische Universität München, D-85748 Garching, Germany,{mayr,weihmann}@in.tum.de

1

PSPACE-complete, and that the containment and equivalence problems are PSPACE-hard anddecidable in doubly exponential space.

Usually, showing that the prerequisites of the framework are satis�ed is the di�cult part whenusing it to obtain upper bounds for computational problems of some class of interest. Accord-ingly, the major part of this paper is dedicated to showing that �-PNs indeed have canonical �ringsequences which are suited to apply the framework. It will turn out that our observation madein [5] that jf-PNs have such �ring sequences is an important building block in our constructionof canonical �ring sequences for �-PNs. The results we obtain are PSPACE-completeness forthe (zero-)reachability, boundedness, and covering problems, PSPACE-membership for the live-ness problem, and PSPACE-hardness and EXPSPACE-membership for the containment andequivalence problems.

This paper is organized as follows. In Section 2, we introduce concepts and notation thatare used in later sections. In Section 3, we list the lower bounds of our problems of interest andobservations about jf-PNs which we will use for our construction of canonical �ring sequences in�-PNs, both borrowed from [5]. In Section 4, we present the framework, which is borrowed from[6]. In Section 5, we discuss and describe, on a high level, our approach and the constructions ofthe following section (involving results for jf-PNs and the framework). In Section 6, we constructthe canonical �ring sequences of �-PNs. In Section 7, we present the complexity results obtainedby combining the known lower bounds with the upper bounds found by applying the framework.In Section 8, we conclude the paper with a short summary and outlook.

2 Preliminaries

2.1 Basic Notation and Encoding Scheme

Throughout this paper, we use the following notation to avoid confusion between elements ofvectors or sequences and indexed elements of a set. We use v[i] in the few occasions we need torefer to the i-th element of a vector or a sequence v. The notation vi is reserved for indexedelements of a set (e. g., p1, p2, . . .). The set of all integers, all nonnegative integers, and all positiveintegers are denoted by Z, N, and N>0, respectively, while [a, b] := {a, a + 1, . . . , b} $ Z, and[k] = [1, k] $ N>0. For two vectors u, v ∈ Zk, we write u ≥ v if u[i] ≥ v[i] for all i ∈ [k], andu > v if u ≥ v and u[i] > v[i] for some i ∈ [k]. The maximum and minimum components of uare denoted by max(u) := maxi∈[k] u[i] and min(u) := mini∈[k] u[i], respectively, where we de�nemax(u) := min(u) := 0 if the dimension of the vector u is 0. Furthermore, let ld denote thefunction with ld(x) := log2(x) if x > 0, and ld(x) := 0 otherwise. (Using this variation of themaximum and minimum functions, and of the logarithm lets us avoid special cases with Petri nets

without places.) For two functions f , g : X → R, we write f(a)P≤ g(a) if there is a polynomial p

such that f(x) ≤ p(g(x)) for all x ∈ X. Note thatP≤ is transitive.

Throughout this paper we use a succinct encoding scheme. Every number is encoded in binaryrepresentation. A vector of Nk is encoded as a k-tuple. A tuple is encoded as a tuple of theencodings of the particular components. For an object x, size(x) denotes the encoding size of xunder this encoding scheme. The input size of a problem instance is the total size of the encodingsof all entities that are declared as being �given� in the respective problem statement.

2.2 Petri Nets

A Petri net N = (P ,T ,F ) is a directed bipartite graph whose nodes consist of the places in P ,transitions in T (T ∩P = ∅), and whose arcs and their multiplicity are given by the �ow functionF : (P ×T )∪ (T ×P )→ N. Throughout this paper, n, m, and W will always refer to the numberof places, transitions, and the largest arc multiplicity of the Petri net under consideration, resp.Usually, we assume an arbitrary but �xed order on P and T , respectively. With respect to thisordering of P , we can consider an n-dimensional vector v as a function of P , and, abusing notation,

2

write v(p) for the entry of v corresponding to place p. Analogously, we write v(t) in context of anm-dimensional vector v and a transition t.

A marking µ of N is a vector in Nn. A pair (N ,µ0) such that µ0 is a marking of N is calleda marked Petri net, and µ0 is called its initial marking. We will omit the term �marked� if thepresence of a certain initial marking is clear from the context. The inverse net of N is obtainedby inverting the direction of all arcs in N while keeping their multiplicities.

For a node x ∈ P ∪ T , •x := {y | F (y,x) > 0} (x• := {y | F (x, y) > 0}) is the preset (postset,resp.) of x. A Petri net is a join-free Petri net (jf-PN) if |•t| ≤ 1 for all transitions t, a fork-freePetri net (�-PN) if |t•| ≤ 1 for all transitions t, and a weighted state machine (WSM) if it isa jf-PN and an �-PN at the same time. For jf-PNs, we abuse notation by identifying •t by itsunique element (if this set is not empty). The transition t is enabled at µ or enabled in (N ,µ) ifµ(p) ≥ F (p, t) for all p ∈ P . If t is enabled at µ, then it can be �red. By doing so, t produces themarking µ′ = µ+ ∆(t), where ∆(t)(p) = (F (t, p)−F (p, t)) is the displacement of t at place p, and

we write µt−→ µ′.

Let σ ∈ T ∗ be a transition sequence. The length of σ is denoted by |σ|, and •σ =⋃i∈[|σ|]

•σ[i]denotes its preset. We de�ne σ[i..j] := σ[i] · · ·σ[j], σ[..i] := σ[1..i], and σ[i..] := σ[i]σ[i+1] · · · . We

write µσ−→ µ′ if µ

σ[1]−−→ µ′′σ[2..]−−−→ µ′ for some marking µ′′. We then say that σ is enabled at µ, and

leads from µ to µ′, For the empty sequence ε, we de�ne µε−→ µ. If σ is enabled in (N ,µ0), then

we call σ a �ring sequence.A marking µ is called reachable if µ0

σ−→ µ for some σ. The reachability set R(P) of a Petrinet P consists of all markings reachable in P. We say that a marking µ can be covered if there isa reachable marking µ′ ≥ µ. A Petri net P is called bounded if R(P) is �nite. A Petri net P iscalled live if, for each transition t of P and each marking µ ∈ R(P), there is a transition sequenceenabled at µ that contains t.

The displacement of σ is de�ned by ∆(σ) :=∑i∈[|σ|] ∆(σ[i]). A Parikh vector Φ (also known

as �ring count vector) is simply an element of Nm. The Parikh map Ψ : T ∗ → Nm maps eachtransition sequence σ to its Parikh image Ψ(σ) where Ψ(σ)(t) = k for a transition t if t appearsexactly k times in σ. The displacement of Φ is de�ned by ∆(Φ) := ∆(σ) for some σ with Ψ(σ) = Φ.Abusing notation, we write t ∈ Φ if Φ(t) > 0, and t ∈ σ if t ∈ Ψ(σ). The special Parikh vectorΨ�rst(σ) is a 0-1-vector such that, for all transitions t, Ψ�rst(σ)(t) = 1 if and only if t ∈ σ and•t′ 6= •t for all transitions t′ ∈ σ in front of the �rst occurrence of t in σ. For transition sequences σand ϕ, the sequence that is obtained from σ by deleting the �rst min{Ψ(σ)(t),Ψ(ϕ)(t)} occurrencesof every transition t, is denoted by σ .− ϕ.

A Parikh vector or a transition sequence with nonnegative displacement at all places is calledloop since, if it can be �red at least once at some marking, the loop can immediately be �redagain at the resulting marking. A loop with positive displacement at some place p is a positiveloop (for p). A Parikh vector/transition sequence with nonpositive displacement at all places isa nonpositive loop. A nonpositive loop with negative displacement at some place p is a negativeloop (for p). A loop with displacement 0 at all places is a zero-loop.

A Petri net is encoded as an enumeration of places p1, . . . , pn and transitions t1, . . . , tm followedby an enumeration of the arcs with their respective arc multiplicities.

In this paper, we consider the following classical computational problems for classes C of Petrinets.

• RecLFS: Given a PN P ∈ C and a Parikh vector Φ, is Φ enabled in P?

• Reachability: Given a PN P ∈ C and a marking µ, is µ reachable in P?

• Zero-reachability: Given a PN P ∈ C, is the empty marking reachable in P?

• Covering: Given a PN P ∈ C and a marking µ, is µ coverable in P?

• Boundedness: Given a PN P ∈ C, is P bounded?

• Liveness: Given a PN P ∈ C, is P live?

3

• Containment: Given two PNs P, P ′ ∈ C, is R(P) ⊆ R(P ′)?

• Equivalence: Given two PNs P, P ′ ∈ C, is R(P) = R(P ′)?

3 Observations about Join-Free Petri Nets

In this section, we collect observations about jf-PNs which are needed later in Section 6. Theseare borrowed from [5]. We remark that we slightly changed the formulation of some lemmatacompared to [5] to account for special cases like the net without places. For stronger versions ofsome of these statements we refer to the journal version [7] (which is to appear). A similar remarkalso applies to Section 4.

Lemma 3.1 ([5], Theorem 1). The RecLFS problem of general Petri nets is PSPACE-complete,even if restricted to WSMs.

Lemma 3.2 ([5], Lemma 2). Let σ be a �ring sequence of a jf-PN (N ,µ0). If a transitiont ∈ Ψ�rst(σ[i+1..]) is enabled at µ0 + ∆(σ[..i]), then σ[..i] · t · (σ[i+1..]

.− t) is a �ring sequence.

Lemma 3.3 ([5], Lemma 3). Let (P ,T ,F ) be a jf-PN, σ a transition sequence, and µ, µ′ markingswith µ+ ∆(σ) = µ′ and µ(p), µ′(p) ≥W for all p ∈ •σ. Then, there is a permutation of σ enabledat µ (and leading to µ′).

Lemma 3.4 ([5], Lemma 5). Let N = (P ,T ,F ) be a Petri net. Then, there is a �nite setH(N) = {Φ1, . . . ,Φk} $ Nm of loops of N such that each loop of H(N) consists of at most(1 + (n + m)W )n+m transitions, and such that, for each loop Φ of N , there are a1, . . . , ak ∈ Nwith Φ = a1Φ1 + . . .+ akΦk.

Lemma 3.5 ([5], Lemma 6). There is a constant c ∈ N>0 such that, for each jf-PN P =(P ,T ,F ,µ0) with n > 0 and each reachable marking µ of P, there are k ≤ n · max(µ) andtransition sequences ξ, ξ̄, α1, . . ., αk+1, τ1, . . ., τk with the following properties, where u =(nmW + max(µ0) + 1)cn(n+m):

(a) ξ = α1 · τ1 ·α2 · τ2 · · · τk ·αk+1 is a �ring sequence of length at most (k+ 1)u leading from µ0

to µ,

(b) ξ̄ = α1 · α2 · · ·αk+1 is a �ring sequence of length at most u, and

(c) each τi, i ∈ [k], is a positive loop of length at most u enabled at some marking µ∗ withmax(µ∗) ≤ u and µ∗ ≤ µ0 + ∆(α1 · α2 · · ·αi).

Lemma 3.6 ([5], Theorems 2 and 3). The zero-reachability, the reachability, the boundedness,and the covering problems of jf-PNs are PSPACE-complete, even if restricted to WSMs.

Lemma 3.7 ([5], Theorem 4). The containment and the equivalence problems of jf-PNs arePSPACE-hard, even if restricted to WSMs, and decidable in doubly exponential space.

4 The Mathematical Framework

In this section, we describe the mathematical framework which we use to obtain complexity resultsfor �-PNs in Section 7. The central motives of this framework are canonical �ring sequences ξleading to reachable markings which result from inserting short loops τ1, . . ., τk into short backbonesequences ξ̄. It will turn out in Section 6 that, for �-PNs, the backbones and loops have at mostexponential length and all loops can be inserted at the same position at the backbone, which,using this framework, immediately implies the complexity results in Section 7. The framework isborrowed from [6].

4

De�nition 4.1 (f -g-canonical class of Petri nets). A class C of Petri nets is f -g-canonical for twomonotonically increasing functions f , g : N4 → N if, for each P = (P ,T ,F ,µ0) ∈ C with n > 0 andeach marking µ reachable in P, there are some k ∈ [0,n(max(µ) + uW )] and transition sequencesξ, ξ̄, α1, . . ., αk+1, τ1, . . ., τk with the following properties, where u = f(n,m,W , max(µ0)):

(a) ξ = α1 · τ1 · α2 · τ2 · · ·αk · τk · αk+1 is a �ring sequence of length at most (k + 1)u leadingfrom µ0 to µ,

(b) ξ̄ = α1 · α2 · · ·αk+1 is a �ring sequence of length at most u,

(c) at most g(n,m,W , max(µ0)) elements of {α1, . . . ,αk+1} are nonempty sequences, and

(d) each τi, i ∈ [k], is a positive loop of length at most u, enabled at some marking µ∗ withmax(µ∗) ≤ u and µ∗ ≤ µ0 + ∆(α1 · α2 · · ·αi).

An f -g-canonical class is

• structurally f -g-canonical if, for each (N ,µ0) ∈ C and each marking µ of N , the Petri net(N ,µ) is also in C, and

• simple if it can be determined in polynomial space if a given Petri net P belongs to C, andif f and g are computable functions.

We remark that these canonical �ring sequence leading to a reachable markings µ are not nec-essarily unique since there might be are other sequences satisfying the properties of De�nition 4.1,and usually there are. However, we can assume w. l. o. g. that we always refer to unique sequenceswhen considering the canonical �ring sequence, for instance by considering the lexicographicallysmallest sequence satisfying this de�nition.

For classes of Petri nets satisfying this de�nition, several complexity results are known. Byshowing that a class is (structurally and simple) f -g-canonical, we obtain complexity results forproblems involving this class for free.

Lemma 4.2 ([6], Theorem 2). Let C be a simple f -g-canonical class of Petri nets. Then, thereachability, and the covering problems are decidable in space polynomial in

size(P) + size(µ) + n ld f(n,m,W , max(µ0)) + r,

and the boundedness problem is decidable in space polynomial in

size(P) + n ld f(n,m,W , max(µ0)) + r,

where r is the space needed to compute f(n,m,W , max(µ0)).

Lemma 4.3 ([6], Theorem 4). Let C be a simple structurally f -g-canonical class of Petri nets.Then, the liveness problem of C is decidable in space polynomial in

size(P) + n ld(f(n,m,W , max(µ0) + f(n,m,W , max(µ0))W )) + r,

where r is the space needed to compute

f(n,m,W , max(µ0) + f(n,m,W , max(µ0))W ).

Lemma 4.4 ([6], Theorem 5). Let C be a simple structurally f -g-canonical class of Petri nets.Then, for some polynomial p, the equivalence and containment problems of C are decidable in space

p((K + 2u1K)u2n · 2p(s+n ld(u3)) + r),

where

• s is the encoding size of the input,

5

• n is the total number of places of both nets,

• m is the total number of transitions,

• W is the maximum of all arc multiplicities of both nets,

• K is the largest number of tokens appearing at some place at the initial markings,

• u1 = f(n,m,W ,K), u2 = g(n,m,W ,K), u3 = f(n,m,W ,K + 2u1W ), and

• r is the time needed to compute u1, u2, and u3.

5 High Level Description

In the following, a sequence is called long if its length is at least exponential in the input size(where a non-speci�ed exponential function separates between long and short).

A su�cient argument. Our goal is to show that the class of �-PNs is f -2-canonical for anexponentially bounded function f and the constant function 2. Let µ be a marking reachable inan �-PN P, and σ be some �ring sequence with µ0

σ−→ µ. If µ has not substantially more tokensthan µ0, then we can use Lemma 3.5 (applied to the inverse net of P with µ as its initial marking)to argue that there is a short �ring sequence leading from µ0 to µ. This means that we are already�nished for such a marking µ (in fact, the procedure that is described below also takes this caseinto consideration).

More interesting is the case where there is place p which contains substantially more tokensat µ compared to µ0. Here, Lemma 3.5 cannot successfully be applied. Its application wouldpossibly yield a long sequence ξ since the encoding size of µ (which is part of the input for theapplication of the lemma) is substantially larger than the size of the original input instance. Thismeans, another approach must be found.

Consider a sub-procedure that takes a �ring sequence σ with a big displacement as describedabove, leading from µ0 to µ, and �nds sequences α, τ , and β with the following properties.

(i) α · τ · β is a �ring sequence leading to µ,

(ii) α · β is a �ring sequence,

(iii) τ is a short positive loop.

Furthermore, we demand that applying the sub-procedure to σ and then iteratively to theresidual sequences α · β until α · β has a small displacement yields short loops τ1, . . ., τk with theproperty that

(iv) for each i ∈ [k], the sequence α · τi is a �ring sequence.

Note that if α or β are long, then, as discussed previously, we can use Lemma 3.5 to �nd shortsequences α′ and β′ with respectively same displacements as α and β such that α′ · β′ is a �ringsequence.

The complete procedure of our interest consists of this iterative application of the sub-proceduredescribed above, and of replacing of α and β by Parikh-equivalent sequences. Let α′, τ1, · · · , τk,β′ denote the sequences produced by this procedure.

If we had such a procedure, then this would immediately imply that the class of �-PNs isf -2-canonical for some exponential function f . The reason is that we can simply consider eachreachable marking µ, then take some �ring sequence σ leading to µ, and apply the procedure toobtain ξ = α′ · τ1 · · · τk · β′. Here, the short sequences α′ and β′ are identi�ed with the sequencesα1 and αk+1 of De�nition 4.1, and α2, . . ., αk are empty sequences.

The sub-procedure is described in Lemma 6.1, although as a variation for jf-PNs because ofreasons of technical and intuitive nature, which we explain later. The procedure is described inCorollary 6.3. The result that the class of �-PNs is f -2-canonical can be found in Lemma 6.4.

6

A �rst idea for the sub-procedure and why it does not work. Let σ again denote a �ringsequence from µ0 to µ. We would like to argue that then σ contains a loop τ as a contiguoussubsequence of σ such that the sequence which results from removing τ from σ is still a �ringsequence. Indeed, if the number of tokens at p is doubly exponentially larger at µ compared toµ0, then arguments involving the coverability tree (see Karp and Miller [3]) show that σ containsa positive loop τ such that σ = α · τ · β. However, it's not necessarily the case that α · β is still�rable because it may be that τ is necessary for β to be �red, i. e., property (ii) is not necessarilysatis�ed. Property (iii) is also not necessarily satis�es since this argument only provides a doublyexponential upper bound for the length of τ . Also, the upper bound on the length of σ (doublyexponential) and the prerequisites for this argument (doubly exponential di�erence in the tokennumbers) are rather weak. We need stronger bounds on these entities if we want to use ourframework to obtain the desired upper bounds for the decision problems of our interest.

A better idea. We now describe a better approach on a very high level, that is, we addressonly the most important ideas without explaining the many technical details. Furthermore, thisapproach here is simpli�ed compared to the actual one in the following chapters, and is thereforenot feasible with respect to certain details. Hence, the reader is encouraged to only take the ideas,and not to try to understand every detail at this point.

Observe that if there is a place p such that µ(p) > µ0(p), then σ must contain a transitionthat increases the number of tokens at p. We want to argue that if µ(p)− µ0(p) is big, then thereare enough such transitions within σ such that we can combine some of these together with a fewother transitions, which balance out the decrease of tokens at places other than p, and obtain aloop τ . In other words, by permuting σ, we obtain α, τ , and β such that α · τ · β is an enabledpermutation of σ, and τ is a positive loop which increases the number of tokens at p.

The process of creating τ consists of iteratively choosing transitions from σ that either increasethe number of tokens at p (because we want to have a positive loop for p) or increase the numberof tokens at a place for which the current sequence τ decreases the number of tokens (because thedisplacement at each place must be nonnegative). When we pick a transition for τ , we want to doit in such a way that at each point α · τ · β is enabled.

To this end, we observe that if α leads to some marking µ′ then we can choose the most righttransition within α that puts tokens to a place p with µ′(p) ≥W , and push it to the last positionin α. The resulting sequence is still enabled. In such a manner, we can let τ grow in the backwarddirection, i. e., we �rst choose its last transition by pushing it to the end, then the second-lasttransition by pushing it in front of the last transition, etc.

However, instead of the original �-PN P, we consider its inverse net P ′, which is a jf-PN, anddescribe a procedure where we let a negative loop grow in the forward direction. The reason whywe do this with an jf-PN instead of an �-PN is that this permutation procedure consists of manysteps where we must ensure at each point that the permutation of the original sequence is also a�ring sequence. This is easier for jf-PNs in an intuitive sense since we must only ensure that theunique input place of a transition under consideration contains enough tokens. By reversing thewhole sequence later (which then is a �ring sequence in P), we obtain a positive loop.

To create τ , the main idea is the following: We start with an initial marking µ0 and a �ringsequence σ of P ′, leading to an end marking µσ, where there is a place p

∗ such that µ0(p∗)−µσ(p∗)is big. We let a pre�x α′ grow by iteratively picking transitions in an appropriate way from theshrinking su�x β (which is initialized by β ← σ). Let ν denote the marking reached by the currentpre�x α′. (Since α′ changes during the procedure, ν also changes.)

The way we pick the next transition is as follows: We �rst de�ne appropriate small intervalsfor each place p 6= p∗ such that the interval for p contains µ0(p). Here we assume that the initialmarking at places p 6= p∗ is not much larger than µσ in order to make the intervals small. (In thisdescription, we leave out a technical preprocessing step which yields an alternative initial markingwith this property, which is then considered instead of the real initial marking.) These intervalsare de�ned in such a way that the permutation procedure can never push ν(p) below the lowerboundary of the interval of p. The upper boundary for each place p 6= p∗ is at least µσ(p) in order

7

to make sure that we can pick a transition consuming tokens from p whenever its token numberis above the upper boundary.

Each time ν(p) leaves the interval of p by crossing the upper boundary, we extend α′ bychoosing a transition which consumes tokens from p in order to push the number of tokens backinto the interval. It could be the case that the transitions chosen in this manner will at some pointconstitute a positive loop since it can happen that they push tokens back and forth between bigplaces and increase their total number of tokens. However, this is no issue at all since eventuallythe number of tokens will necessarily enter the interval again because the end marking at p issmaller than the the upper boundary of p. If, however, the token numbers at all places p 6= p∗ arewithin the respective intervals, we choose a transition that consumes tokens from p∗.

The important observation is that the number of di�erent sub markings, restricted to the placesp 6= p∗, where all token numbers are in their intervals, is small since the intervals are small. Thatmeans that the number of times we observe a new smallest marking w. r. t. the number of tokensat p∗ where all token numbers at places p 6= p∗ are in their intervals, is also small. At some point,we repeat such a sub marking. The sequence τ between the �rst and the next time we observe thissub marking is then a negative loop for p∗, and a zero-loop for all p 6= p∗, i. e., we can �nd α and anegative loop τ such that α′ = α · τ . In particular, the negative loop τ has a small displacement.The sequence α · τ · β is enabled since we always extend α′ by transitions that consume tokensfrom places where the number of tokens is large (i. e., above the appropriately de�ned interval).Hence, (i) is satis�ed.

Furthermore, since the loop τ only decreases the number of tokens at a place which has a largenumber of tokens, we can argue that the sequence α · β is enabled at µ0 −∆(τ) (in other words,the inverse of α · β is enabled in the original �-PN P). Hence, (ii) is satis�ed.

We still must argue that (iii) and (iv) are satis�ed. In fact, this requires a more carefullyprocedure. In particular, we must preprocess σ in a certain way to obtain a subsequence whichonly uses places that are not too small. This subsequence is then processed. Let µ′ denote themarking reached by this subsequence. Without going into detail, the main idea is that µ′ is largeenough such that, in the original �-PN P, µ′ enables each positive loop that is the inverse of somenegative loop τi created by the permutation procedure. Therefore, (iv) is satis�ed.

Actually, (iii) is not necessarily satis�ed. The displacement of τ might be small but the lengthof the sequence itself is unbounded. To solve this problem, we can extract a short sequence fromτ that is also a negative loop for p∗ and a zero-loop for all other places. Here, we also left outmany details in the procedure that ensure that we can �nd such a short negative loop, and thatthis negative loop is compatible with (i)�(iv). All these details are discussed later.

6 Canonical Firing Sequences in Fork-Free Petri Nets

In this section, we show that the class of �-PNs is f -2-canonical for some function f which isexponentially bounded in the size of the input net. In particular, we show that each markingreachable in an �-PN has a canonical �ring sequence with the properties of De�nition 4.1

On a high level, we achieve this by providing a procedure that takes some sequence σ leadingto a reachable marking µ, and construct from this sequence the sequence ξ. (More precisely, bydoing so we show that a sequence satisfying De�nition 4.1 for µ exists.) This procedure permutesthe given sequence and replaces parts of it with short displacement-equivalent sequences.

The stepping stone for the construction is a procedure that, given a �ring sequence of a jf-PN(satisfying some conditions), permutes it in such a way that we obtain a �ring sequence which,among other things, has a su�x which is a negative loop and satis�es some other useful properties.As already explained in the previous chapter, the reason why we consider jf-PNs instead of �-PNsis because it is intuitively easier to verify in case of a jf-PN that a some transition is enabled atsome marking since each transition only depends on a single place. Furthermore, by consideringjf-PNs, we can immediately use many known results for this class of Petri nets.

Lemma 6.1. Let (P ,T ,F ,µ0) be a jf-PN, and σ a �ring sequence leading to some marking µσsuch that µσ(p) ≥ W for all p ∈ •σ, and µ0(p∗) ≥ µσ(p∗) + (δ + 3) ·W for some place p∗ ∈ •σ,

8

where δ = (max(µσ) + W + 1)n−1. Then, there are transition sequences α, τ and a markingµ∗ ∈ {0,W}n such that

(a) α · τ is a permutation of σ with µ0α·τ−−→ µσ,

(b) (µ0 + ∆(τ))α−→ µσ,

(c) τ is a negative loop with ∆(τ)(p∗) ∈ [−(nmW + 1)n+m, −1] and ∆(τ)(p) = 0 for all p 6= p∗,

(d) |τ | ≤ (nmW + 1)n+m, and

(e) (µ∗ −∆(τ))τ−→ µ∗, where µ∗(p) = W if µσ(p) ≥W , and µ∗(p) = 0 otherwise.

Proof. In the following, we will construct transition sequences α′, τ ′ satisfying (a) and (b) (replaceα and τ by α′ and τ ′ there) as well as the property

(c') ∆(τ)(p∗) ∈ [−δ ·W , − 1] and ∆(τ)(p) = 0 for all p ∈ P \ {p∗}.

Property (c' ) is weaker than (c) in the sense that (c) implies (c' ) but not the other way round.We can later nevertheless use α′ and τ ′ to de�ne the sequences α and τ of interest which satisfy theproperties of the lemma. To �nd α′ and τ ′, we use a procedure which, by permuting and splittingσ in an appropriate way, creates a number of intermediate sequences which are then recombinedto α′ and τ ′.

Our �rst step to this end consists of �nding transition sequences α0, ϕ0, . . ., ϕδ and markingsν0, . . ., νδ such that, for appropriately de�ned integral levels `0 > . . . > `δ+1, the followingproperties are satis�ed for all i ∈ [0, δ]:

(i) ν0ϕ0···ϕi−−−−→ νi,

(ii) νi(p) ∈ [0, max(µσ) +W ] for all p ∈ P \ {p∗}, and

(iii) νi(p∗) ∈ [`i+1 + 1, `i].

Moreover, these transition sequences shall be de�ned in such a way that we can use them later toconstruct α′ and τ ′.

The important property about these sequences is that, for each p 6= p∗, the number of tokensat p is trapped in the interval [0, max(µσ)+W ] at each marking νi, and that the number of tokensat p∗ is strictly monotonically decreasing by a small amount when proceeding from νi to νi+1.This means that some sub-marking restricted to the places p 6= p∗ must repeat at some point (i. e.,νi(p) = νj(p) for some i and j and all p 6= p∗), and hence we have found a negative loop (withdisplacement νj − νi). The general idea how we �nd these markings and sequences is illustratedin Figure 1.

The role of the marking ν0 is to serve as an alternative initial marking. This marking is thestarting point for constructing the sequences above. The important property of ν0 is that, for eachplace p 6= p∗, the absolute value of the di�erence between ν0(p) and µσ(p) is small (remember thatwe want to trap p 6= p∗ in the interval [0, max(µσ) +W ]).

We �rst show how to construct ν0. We initialize α0 ← ε as the empty sequence and ψ ← σ.As long as there is a t ∈ Ψ�rst(ψ) such that •t 6= p∗ and (µ0 + ∆(α0))(•t) > µσ(•t) + W , we setα0 ← α0 · t and ψ ← ψ .− t. (Note that this means that we extend α0 by �ring t at markingµ0 + ∆(α0).) We stop, when no such t exists (any more). After that, we de�ne ν0 := µ0 + ∆(α0)and ϕ0 := ε. (The sequence ϕ0 is a dummy sequence to avoid a special case when constructing

the remaining sequences ϕi, i > 0.) By Lemma 3.2, we observe µ0α0−→ ν0

ψ−→ µσ.We remark that, in the procedure above, there may be di�erent possibilities to choose t ∈

Ψ�rst(ψ). Depending on which of them we choose, the resulting sequences may be di�erent. If wewant to make them unique, we could de�ne an ordering of the transitions and then choose thesmallest possible transition w. r. t. this ordering. However, to show the lemma, it is not importantwhich transition we choose. This remark also applies at various occasions later when we permutesequences using similar schemes.

9

µ0

ν 0ν 1

ν i1

ν i1+1

ν i2

α0

ϕ1

ϕ2···ϕ

iϕi 1+1

ϕi 1+2···ϕ

i 2

0

max

(µσ)

max

(µσ)

+W` 0 ` 1 ` 2 ` i

1

` i1+1

` i1+2

` i2

` i2+1

p1p2p3p∗

p1p2p3p∗

p1p2p3p∗

p1p2p3p∗

p1p2p3p∗

p1p2p3p∗

Figure

1:Thesequencesgeneratedin

thefollow

ingconsist

oftransitionsoftheoriginalsequenceσsuch

thateach

occurrence

ofatransitionofσ

isusedatmost

once

inthesesequences.

Startingfromµ0,wegenerateα0whichleadsto

amarkingν 0

such

thatν 0

(p)≤

max(µσ)(p)

+W

forall

p∈P\{p∗ },and

∆(α

0)(p∗ )≥

0.From

there,wede�nelevels` i,i∈

[0,δ

+1],andgenerate

sequencesϕi,i∈

[δ],such

that,when

encounteringthe

respective

correspondingmarkingsν i,therespectivenumber

oftokensateach

placep∈P\{p∗ }

isstilltrapped

within

theinterval

[0,

max(µσ)+W

],andsuch

thatthenumber

oftokensatp∗isstrictly

decreasing,whereν i

(p∗ )∈

[`i+

1+

1,`i].Byconstructingasu�cientnumber

ofthesesequences

andmarkings,we�ndi 1<i 2such

thatν i

1(p

)=ν i

2(p

)forallp∈P\{p∗ }.Thesequenceϕi 1+1···ϕ

i 2=

:τ′′isthen

anegativeloopforp∗ .

Permuting

τ′′in

anappropriateway

yieldsthenegative

loopτ′ .

10

Next, we de�ne the levels `0, . . ., `δ+1 by `i := ν0(p∗)− i ·W , i ∈ [0, δ+1]. Note that properties(i)�(iii) are satis�ed for i = 0.

We proceed by recursively de�ning the remaining transition sequences and markings. For alli ∈ [δ], let ϕi and νi be recursively de�ned by ϕi := getSubSeq(i) and νi := ν0 + ∆(ϕ0 · · ·ϕi).Furthermore, we de�ne σrest := σ .− (α0 · ϕ0 · · ·ϕδ). The function getSubSeq basically does the

Function getSubSeq(iteration i)

ϕ← empty sequenceψrest ← ψ .− (ϕ0 · · ·ϕi−1)while ∃t ∈ Ψ�rst(ψrest) : [(p∗ = •t and (νi−1 + ∆(ϕ))(p∗) > `i) or(∃p ∈ P \ {p∗} : p = •t and (νi−1 + ∆(ϕ))(p) > µσ(p) +W )] do

ϕ← ϕ · tψrest ← ψrest

.− treturn ϕ

following: Starting from the marking νi−1, it creates a sequence ϕi by iteratively choosing tran-sitions from the sequence containing the remaining transitions (which is ψ .− (ϕ0 · · ·ϕi−1) at thebeginning of the function). At each step, it either chooses a transition that consumes tokens fromp∗ provided p∗ has too many tokens (i. e., the token number is larger than level `i) or chooses atransition that consumes tokens from some place p 6= p∗ provided p has too many tokens (i. e., thetoken number is larger than µσ(p) +W ). Note that it is always possible to �nd such a transitionsince, otherwise, the remaining sequence would not lead to µσ.

Lemma 3.2 immediately implies that α0 · ϕ0 · · ·ϕδ · σrest is a �ring sequence which ensuresproperty (i) for all i ∈ [δ]. Using induction on i ∈ [0, δ], it is not hard to show properties (ii)�(iii)for the remaining sequences and markings: Let i ∈ [δ], and assume that (ii)�(iii) hold for step i−1.Property (ii) and νi(p

∗) ≤ `i of (iii) directly follow from the de�nition of Function getSubSeq.Furthermore, νi−1(p∗) ≥ `i + 1 holds by the induction hypothesis. Subsequently, one iteration ofthe while-loop of Function getSubSeq cannot decrease the number of tokens at p∗ below `i+1 + 1,which implies νi+1(p∗) ≥ `i+1 + 1. Thus, (iii) holds.

We continue the proof by de�ning α′ and τ ′. By (ii), there are at most δ di�erent projectionsof the δ + 1 markings νi, i ∈ [0, δ], onto the places p ∈ P \ {p∗}. Hence, there are i1, i2 ∈ [0, δ],i1 < i2, such that νi1(p) = νi2(p) for all p ∈ P \ {p∗}. Let α1 := ϕ0 · · ·ϕi1 , τ ′′ := ϕi1+1 · · ·ϕi2 ,α2 := ϕi2+1 · · ·ϕδ · σrest, α0, 1 := α0 ·α1, α1, 2 := α1 ·α2, and α

′ := α0 ·α1 ·α2, see (a) of Figure 2.(In this illustration, certain sequences are indicated to be enabled at certain markings. Thisfollows from the de�nition of the sequences and from our observations made above, in particularproperty (i).)

Property (iii) ensures ∆(τ ′′)(p∗) ∈ [−(i2 − i1 + 1)W , − 1], and therefore that τ ′′ satis�es (c' )(where τ of (c' ) is identi�ed with τ ′′). This together with the assumption of this lemma implies(ν0 + ∆(α1, 2))(p) ≥ µσ(p) ≥ W for all p ∈ •τ ′′. Therefore, we can apply Lemma 3.3 to themarkings ν0 + ∆(α1, 2) (which is none other than µ0 + ∆(α′)), µσ, and the sequence τ ′′ to obtaina permutation τ ′ of τ ′′ which is enabled at µ0 + ∆(α′). Note that also τ ′ satis�es (c' ) (where τof (c' ) is identi�ed with τ ′). Next we observe that α2 is enabled at νi1 since α2 is enabled at νi2and νi1 ≥ ν2 holds. Consequently, α′ · τ ′ is a permutation of σ enabled at µ0, and (a) follows, see(b) of Figure 2.

To show (b) for α′, it's only necessary to consider α0, 1 since we already know that νi2α2−→

µσ. Moreover, it's su�cient to verify that, for all j ∈ [0, |α0, 1| − 1] and p ∈ P , (µ0 + ∆(τ ′) +∆((α0, 1)[..j]))(p) ≥ min{W , (µ0 + ∆((α0, 1)[..j]))(p)} holds since this implies that the marking(µ0 + ∆(τ ′) + ∆((α0, 1)[..j])) enables the next transition (α0, 1)[j+1]. Since, by (c' ), τ ′ does notchange the number of tokens at some place other than p∗, this su�cient condition remains to beshown for p∗, which we do now.

We �rst consider α0. Since µ0(p∗) + ∆(τ ′)(p∗) ≥ W and p∗ /∈ •α0, we �nd (µ0 + ∆(τ ′) +∆((α0)[..j]))(p

∗) ≥W for all j ∈ [0, |α0| − 1].

11

Next, we consider α1 = ϕ1 · · ·ϕi1 . By (iii), we �nd

νi(p∗) ≥ `i+1 + 1 > `i1 = `i1+1 +W = ν0(p∗)− (i1 + 1) ·W +W

≥ µ0(p∗)− (i1 + 1) ·W +W ≥ µσ(p∗) + (δ + 3) ·W − (i1 + 1) ·W +W

= µσ(p∗) + (δ − i1 + 1) ·W + 2W ≥ (δ − i1 + 1) ·W + 3W

for all i ∈ [0, i1 − 1] (remember for this sequence of inequalities the prerequisite µσ(p∗) ≥W ). Byproperty (iii) and the de�nition of Function getSubSeq, we observe ∆((ϕi)[..j])(p

∗) ≥ −2W for alli ∈ [0, δ], j ∈ [0, |ϕi|]. Thus, (νi + ∆((ϕi+1)[..j]))(p

∗) ≥ (δ − i1 + 1) ·W +W for all i ∈ [0, i1 − 1]and j ∈ [0, |ϕi+1|]. Adding the displacement of τ ′ yields (νi + ∆(τ ′) + ∆((ϕi+1)[..j]))(p

∗) ≥−(i2 − i1 + 1)W + (δ − i1 + 1) ·W +W ≥W for all i ∈ [0, i1 − 1] and j ∈ [0, |ϕi+1|]. This implies(ν0 + ∆(τ ′) + ∆((α1)[..j]))(p

∗) ≥ W for all j ∈ [0, |α1| − 1]. In total, (b) follows for α′, see (c) ofFigure 2.

So far, we have shown that α′ and τ ′ satisfy (a), (b), and (c' ), but not necessarily (c). Wenow de�ne sequences α and τ satisfying (a)�(c). The following observations are illustrated in

µ0 ν0 νi1 νi2 νδ µσα0 α1 = ϕ0 · · ·ϕi1 τ ′′ = ϕi1+1 · · ·ϕi2 ϕi2+1 · · ·ϕδ σrest

(a)

νi2 µσα2 = ϕi2+1 · · ·ϕδ · σrest

µ0 µ0 + ∆(α′) µσα′ = α0 · α1 · α2 τ ′

(b)

µ0 + ∆(τ ′) µσα′ = α0 · α1 · α2

(c)

µσ −∆(τi)∀i ∈ [q] : µστi

(d)

µσ −∆(α) = µ0 + ∆(τj) µσα = α0 · α1 · α2 · τ1 · · · τj−1 · τj+1 · · · τq

µ0 µ0 + ∆(α) µσα = α0 · α1 · α2 · τ1 · · · τj−1 · τj+1 · · · τq τ = τj

Figure 2: Observations for di�erent steps of Lemma 6.1

12

(d) of Figure 2. We apply Lemma 3.4 to the inverse net of P and Ψ(τ ′), and obtain nonpositiveloops Φ1, . . ., Φq with min(Φi) ≥ −(1 + (n + m)W )n+m ≥ −(nmW + 1)c(n+m) for all i ∈ `and some constant c ∈ N>0, and Ψ(τ ′) =

∑qi=1 Φi. By property (c' ) and by the fact that

(µσ −∆(Φi))(p) ≥ µσ(p) ≥ W holds for all p ∈ •σ ⊇ •τi and i ∈ [q], we can apply Lemma 3.3 to

�nd nonpositive loops τ1, . . ., τq with Ψ(τi) = Φi and µσ −∆(τi)τi−→ µσ for all i ∈ [q] such that,

for some j ∈ [q], τj =: τ is a negative loop satisfying (c) and (d). Correspondingly, we de�neα := α′ ·τ1 · · · τj−1 ·τj+1 · · · τq. Note that α ·τ is a �ring sequence since α′ is enabled at µσ−∆(α′)(i. e., property (b)) and each τi, i ∈ [q], is a nonpositive loop enabled at µσ −∆(τi). Hence, α andτ satisfy (a)�(e).

We obtain the following canonical �ring sequence by �rst permuting a given �ring sequenceappropriately, and then iteratively applying Lemma 6.1 as well as Lemma 3.5. Since the mostcharacteristic property of this canonical sequence is that almost all transitions are contained inshort negative loops, we call it negative canonical sequence.

Lemma 6.2. There is a constant c ∈ N>0 such that, for each jf-PN P = (N ,µ0) with n > 0 andeach marking µ reachable in P, there are k ∈ [0,n ·max(µ0)], transition sequences α, β, τ1, . . .,τk, and a marking µ∗ ∈ {0,W}n such that

(a) α · τ1 · · · τk · β is a �ring sequence leading from µ0 to µ,

(b) α · β is enabled at (µ−∆(α · β)) with |α · β| ≤ (nmW + max(µ) + 1)cn2(n+m),

(c) µ0 + ∆(α · τ1 · · · τk) ≥ µ∗, and

(d) each τi, i ∈ [k], is a negative loop with

(i) ∆(τi)(p∗) ∈ [−(nmW + 1)(n+m), − 1] for some place p∗ and

∆(τi)(p) = 0 for all p 6= p∗,

(ii) |τi| ≤ (nmW + 1)(n+m), and

(iii) (µ∗ −∆(τi))τi−→ µ∗.

Proof. We assume m, W > 0 since the lemma trivially holds otherwise. Let µ be a reachablemarking, and ρ be a �ring sequence leading to µ.

We want to show the lemma by repeatedly applying Lemma 6.1. However, this lemma requiresthat the sequence σ which we are applying the lemma to satis�es µσ(p) ≥ W for all p ∈ •σ.Therefore, we extract such a sequence from ρ as follows.

First, we initialize σ ← ε and ρrest ← ρ. As long as there is a transition t ∈ Ψ�rst(ρrest) with(µ0 + ∆(σ))(•t) ≥ 2W , we set σ ← σ · t and ρrest ← ρrest

.− t. At the end of this procedure, wede�ne µσ := µ0 + ∆(σ). It is easy to see that σ has the desired property.

Now, we iteratively apply Lemma 6.1 as long as possible, using (P ,T ,F ,µ0 + ∆(τ1 · · · τi−1)),αi−1, and µσ in the i-th iteration, where τi and αi (with α0 = σ) denote the sequences resultingfrom the i-th application of the lemma. Let ` ≤ n · max(µ0) denote the number of applicationsof Lemma 6.1, and µ∗ the marking de�ned in Lemma 6.1. We remark that α` is the �residual�sequence which remains of σ after we have extracted the negative loops τ1, . . ., τ`. We �rst observethat, by Lemma 6.1, the negative loops τi, i ∈ [`], satisfy property (d).

Next, we �nd (µσ−∆(α`))α`−→ µσ ≥ µ∗. Furthermore, max(µσ) ≤ max(µ)+2W holds. To see

this, assume max(µσ) > max(µ) + 2W for the sake of contradiction. Then, there is a transitiont ∈ Ψ�rst(ρrest) with (µ0 + ∆(σ))(•t) ≥ 2W which, by the construction of σ, cannot be the case.By this, we �nd

max(µσ −∆(α`)) ≤ max(µσ) + (δ + 3) ·W≤ max(µσ) + ((max(µσ) +W + 1)n−1 + 3) ·W≤ (max(µ) + 2W )an

13

for some constant a ∈ N>0. We apply Lemma 3.5 to the markings (µσ−∆(α`)) and µσ, and obtain

a transition sequence α (i. e., sequence ξ of Lemma 3.5) with (µσ −∆(α`)) = (µσ −∆(α))α−→ µσ.

The sequence α is not necessarily a permutation of α` but has the same displacement. In particular,

we have µ0α−→ (µ0+∆(α))

τ1···τ`−−−−→ µσ ≥ µ∗, meaning that (c) is satis�ed. Let c denote the constantof Lemma 3.5 (the constant c of the Lemma we are proving at the moment is somewhat largerthan the constant c of Lemma 3.5). Furthermore, let u and k be the numbers of this particularapplication of Lemma 3.5. Using the bounds given above, we �nd

|α| ≤ (k + 1)u ≤(

max(µσ) + (nmW + max(µσ −∆(α`)) + 1)cn(n+m))2

≤(

(max(µ) + 2W ) + (nmW + (max(µ) + 2W )an + 1)cn(n+m))2

≤ (nmW + max(µ) + 1)dn2(n+m)

for some constant d ∈ N>0. Last, we apply Lemma 3.5 to the markings µσ and µ, yielding a

transition sequence β (i. e., sequence ξ of Lemma 3.5) with µσβ−→ µ. Let u and k denote the

numbers of this particular application of Lemma 3.5. Then, we observe

|β| ≤ (k + 1)u ≤(

max(µ) + (nmW + max(µσ) + 1)cn(n+m))2

≤(

max(µ) + (nmW + max(µ) + 2W + 1)cn(n+m))2

≤ (nmW + max(µ) + 1)dn(n+m)

for some constant d ∈ N>0. The observations above imply (µσ − ∆(α))α−→ µσ

β−→ µ as well as

µ0α−→ (µ0+∆(α))

τ1···τk−−−−→ µσβ−→ µ. This together with the bounds on |α| and |β| ensures properties

(a) and (b).

By reversing negative canonical �ring sequences of jf-PNs, we obtain positive canonical �ringsequences of �-PNs.

Corollary 6.3. There is a constant c ∈ N>0 such that, for each �-PN P = (N ,µ0) with n > 0and each marking µ reachable in P, there are k ∈ [0,n · max(µ)], transition sequences α, β, τ1,. . ., τk, and a marking µ∗ ∈ {0,W}n such that

(a) α · τ1 · · · τk · β is a �ring sequence leading from µ0 to µ,

(b) α · β is enabled at µ0 with |α · β| ≤ (nmW + max(µ0) + 1)cn2(n+m),

(c) µ0 + ∆(α) ≥ µ∗, and

(d) each τi, i ∈ [k], is a positive loop with

(i) ∆(τi)(p∗) ∈ [1, (nmW + 1)c(n+m)] for some place p∗ and ∆(τi)(p) = 0 for all p 6= p∗,

(ii) |τi| ≤ (nmW + 1)c(n+m), and

(iii) τi is enabled at µ∗.

Proof. Lemma 6.2 implies the corollary by considering the inverse net of P, as well as µ as theinitial marking and µ0 as the end marking.

Lemma 6.4. There is a constant c ∈ N>0 such that the class of �-PNs is simple structurallyf -g-canonical, where f(n,m,W ,K) = (nmW +K + 1)cn

2(n+m) and g(n,m,W ,K) = 2.

Proof. This follows immediately from Corollary 6.3.

14

7 Complexity Results

Our observations of the previous section allows us to apply the framework to obtain the followingcomplexity results.

Theorem 7.1. The RecLFS, (zero-)reachability, boundedness, and covering problems of �-PNs arePSPACE-complete, even if restricted to WSMs. The liveness problem of �-PNs is in PSPACE.

Proof. PSPACE-completeness for the RecLFS problem is immediately implied by Lemma 3.1(for an Petri net P = (P ,T ,F ,µ0) and Parikh vector Φ consider the inverse net of P with µ0 +∆(Φ) as initial marking). The lower bound for the (zero-)reachability, boundedness, and coveringproblems are provided by Lemma 3.6. By Lemma 6.4, the class of �-PNs is simple structurally f -f -canonical for the function f given in the lemma, where f(n,m,W ,K) = (nmW +K+ 1)cn

2(n+m).By Lemma 4.2, the (zero-)reachability, and covering problems of �-PNs are decidable in space

polynomial in size(P) + size(µ) + n ld f(n,m,W , max(µ0)) + rP≤ size(P) + size(µ). Similarly, the

boundedness problem is decidable in space polynomial in size(P) + n ld f(n,m,W , max(µ0)) +

rP≤ size(P). By Lemma 4.3, the liveness problem of �-PNs is decidable in space polynomial in

size(P) + n ld(f(n,m,W , max(µ0) + f(n,m,W , max(µ0))W )) + rP≤ size(P).

Theorem 7.2. The containment and the equivalence problems of �-PNs are decidable in expo-nential space and are PSPACE-hard, even if restricted to WSMs.

Proof. PSPACE-hardness follows from Lemma 3.7. Let s denote the encoding size of the input.Then, by Lemma 4.4 and Lemma 6.4, there are polynomials p, p′ such that the equivalence and

containment problems are decidable in space polynomial in (K + 2u1K)u2n · 2p(s+n ld(u3)) + rP≤

(K + 2f(n,m,W ,K)K)2n · 2p(s+n ld f(n,m,W ,K+2f(n,m,W ,K)W ))P≤ 2p

′(s).

8 Conclusion

We investigated fork-free Petri nets, a natural class of Petri nets. Using results for join-free Petrinets, we showed that reachable markings in �-PNs can be reached by �ring sequences with niceproperties. This enabled us to apply a mathematical framework for Petri nets, which providedupper bounds for many classical computational problems. We showed that the (zero-)reachability,boundedness, and covering problems are PSPACE-complete, that the liveness problem is inPSPACE, and that the containment and equivalence problems are PSPACE-hard and decidablein exponential space. Clearly, for the latter three problems, the respective lower and upper boundsdo not match. Further research is needed to �ll this gap. Moreover, it would be interesting to knowif there are other classes for which completeness-results for the classical problems investigated inthis paper are unknown and for which the framework of [6] can be applied.

References

1. C. Amer-Yahia, N. Zerhouni, A. E. Moudni, and M. Ferney. Some subclasses of Petri nets andthe analysis of their structural properties: a new approach. IEEE Transactions on Systems,Man and Cybernetics, Part A: Systems and Humans, 29(2):164�172, 1999.

2. A. W. Holt and F. Commoner. Events and conditions. In Record of the Project MAC Confer-ence on Concurrent Systems and Parallel Computation, pages 3�52. ACM, New York, 1970.

3. R. M. Karp and R. E. Miller. Parallel program schemata. Journal of Computer and SystemSciences, 3(2):147�195, 1969.

15

4. Y. E. Lien. Termination properties of generalized Petri nets. SIAM Journal on Computing, 5(2):251�265, 1976.

5. E. W. Mayr and J. Weihmann. Completeness results for generalized communication-free Petrinets with arbitrary edge multiplicities. In Proceedings of the 7th International Workshop onReachability Problems, volume 8169 of Lecture Notes in Computer Science, pages 209�221.Springer, 2013.

6. E. W. Mayr and J. Weihmann. A framework for classical Petri net problems: ConservativePetri nets as an application. In Proceedings of the 35th International Conference on Applicationand Theory of Petri Nets (ICATPN'14), volume 8489 of Lecture Notes in Computer Science,pages 314�333. Springer, 2014.

7. E. W. Mayr and J. Weihmann. Completeness results for generalized communication-free Petrinets with arbitrary arc multiplicities. Fundamenta Informaticae, 2015. To appear.

8. K. Morita and T. Watanabe. The legal �ring sequence problem of Petri nets with state machinestructure. In Proceedings of the 1996 IEEE International Symposium on Circuits and Systems(ISCAS'96), volume 3, pages 64�67, 1996.

9. S. Taoka and T. Watanabe. A linear time algorithm solving the legal �ring sequence problemfor a class of edge-weighted cactuses. In Proceedings of the 1999 IEEE International Conferenceon Systems, Man, and Cybernetics (SMC'99), volume 3, pages 893�898, 1999.

10. E. Teruel and M. Silva. Liveness and home states in equal con�ict systems. In Proceedingsof the 14th International Conference on Application and Theory of Petri Nets (ICATPN'93),volume 691 of Lecture Notes in Computer Science, pages 415�432. Springer, 1993.

11. E. Teruel and M. Silva. Well-formedness of equal con�ict systems. In Proceedings of the 15thInternational Conference on Application and Theory of Petri Nets (ICATPN'94), volume 815of Lecture Notes in Computer Science, pages 491�510. Springer, 1994.

12. E. Teruel and M. Silva. Structure theory of equal con�ict systems. Theoretical ComputerScience, 153:271�300, 1996.

16