Hierarchy of persistency with respect to the length of action’s disability Kamila Barylska1? and Edward Ochmański1,2 {khama,edoch}@mat.umk.pl 1 Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland 2 Institute of Computer Science, Polish Academy of Sciences, Jana Kazimierza 5, 01-248 Warszawa, Poland Abstract. The notion of persistency, based on the rule "no action can disable another one" is one of the classical notions in concurrency theory. We recall two ways of generalization of this notion: the first is "no action can kill another one" and the second "no action can kill another en- abled one". Afterwards we present an infinite hierarchy of computations in which one action disables another one for no longer than a speci- fied number of steps (e/l-k-persistency). We prove that if an action is disabled, and not killed, by another one, it can not be postponed indef- initely. Finally we deal with decision problems about e/l-k persistency. We show that this kind of persistency is decidable with respect to steps, markings and nets. Keywords: Petri nets, concurrency, persistency, decision problems 1 Introduction The notion of persistency is one of the most frequently discussed issues in the Petri net theory - [4,7,8,11,12] and many others. It is being studied not only in terms of theoretical properties, and also as a useful tool for designing and analyz- ing software environments [3]. In software engineering, persistency is a desirable property and many systems may not work properly without it. We say that an action of a processing system is persistent if, whenever it becomes enabled, it remains enabled until executed. A system is said to be persistent if all its actions are persistent. This classical notion is introduced by Karp/Miller [10]. Also interesting, with practical applications, is the notion of weak persistency introduced and investigated in [16,15,9]. In section 3, we bring to mind two generalizations of the classical notion (defined in [2]): l/l persistency and e/l-persistency. An action is said to be l/l-persistent if it remains live until executed, and is e/l-persistent if, whenever it is enabled, it cannot be killed by ? The study is cofounded by the European Union from resources of the European Social Fund.Project PO KL "Information technologies: Research and their interdisciplinary applications", Agreement UDA-POKL.04.01.01-00-051/10-00. 126 PNSE’12 – Petri Nets and Software Engineering another action. For uniformity, we name the traditional persistency notion e/e- persistency. Next, we recall that those kinds of persistency are decidable in the class place/transition nets. In section 4, we extend the hierarchy mentioned above with an infinite hi- erarchy of e/l-persistent steps. A step M aM 0 is said to be e/l-k-persistent for some k ∈ N if the execution of an action a pushes the execution of any other enabled action away for at most k steps. We prove that if an action is disabled by another one, it can not be postponed indefinitely. We show that if a p/t-net is e/l-persistent, then it is e/l-k-persistent for some k ∈ N (Theorem 3) and such a k can be effectively found (Theorem 9). We also point, that the above-cited result does not hold for nets which do not have the monotonicity property (for example for inhibitor nets). Afterwards, we investigate the set of markings in which two actions are en- abled simultaneously, and also the set of reachable markings with that feature. We show that the minimum of the latter is finite and effectively determined. We also prove that if some action pushes the enabledness of another one away for more than k steps, then it also needs to happen in some minimal reachable marking enabling these two actions. Finally, we show that e/l-k-persistency is decidable with respect to steps (Theorem 1), markings (Theorem 2) and nets (Theorem 7). The concluding section contains some questions and plans for further inves- tigations. 2 Basic Notions 2.1 Denotations The set of non-negative integers is denoted by N. Given a set X, the cardinality (number of elements) of X is denoted by |X|, the powerset (set of all subsets) by 2X , the cardinality of the powerset is 2|X| . Multisets over X are members of NX , i.e. functions from X into N. 2.2 Petri Nets and Their Computations The definitions concerning Petri nets are mostly based on [5]. Definition 1 (Nets). Net is a triple N = (P, T, F ), where: – P and T are finite disjoint sets, of places and transitions, respectively; – F ⊆ P × T ∪ T × P is a relation, called the flow relation. For all a ∈ T we denote: • a = {p ∈ P | (p, a) ∈ F } - the set of entries to a a• = {p ∈ P | (a, p) ∈ F } - the set of exits from a K. A. Barylska, E. Ochmański: Hierarchy of persistency 127 Petri nets admit a natural graphical representation. Nodes represent places and transitions, arcs represent the flow relation. Places are indicated by circles, and transitions by boxes. The set of all finite strings of transitions is denoted by T ∗ , the length of w ∈ T ∗ is denoted by |w|, number of occurrences of a transition a in a string w is denoted by |w|a , two strings u, v ∈ T ∗ such that (∀a ∈ T ) |u|a = |v|a are said to be Parikh equivalent. Definition 2 (Place/Transition Nets). Place/transition net (shortly, p/t- net) is a quadruple S = (P, T, F, M0 ), where: – N = (P, T, F ) is a net, as defined above; – M0 ∈ NP is a multiset of places, named the initial marking; it is marked by tokens inside the circles, capacity of places in unlimited. Multisets of places are named markings. In the context of p/t-nets, they are mostly represented by nonnegative integer vectors of dimension |P |, assuming that P is strictly ordered. The natural generalizations, for vectors, of arithmetic operations + and −, as well as the partial oder 6, all defined componentwise, are well known and their formal definitions are omitted. In this context, by • a(a• ) we understand a vector of dimension |P | which has 1 in every coordinate corresponding to a place that is an entry to (an exit from, respectively) a and 0 in other coordinates. A transition a ∈ T is enabled in a marking M whenever • a ≤ M (all its entries are marked). If a is enabled in M , then it can be executed, but the execution is not forced. The execution of a transition a changes the current marking M to the new marking M 0 = (M −• a) + a• (tokens are removed from entries, then put to exits). The execution of an action a in a marking M we call a (sequential) step. We shall denote M a for the predicate "a is enabled in M " and M aM 0 for the predicate "a is enabled in M and M 0 is the resulting marking". This notions and predicates we extend, in a natural way, to strings of tran- sitions: M εM for any marking M , and M vaM 00 (v ∈ T ∗ , a ∈ T ) iff M vM 0 and M 0 aM 00 . If M wM 0 , for some w ∈ T ∗ , then M 0 is said to be reachable from M ; the set of all markings reachable from M is denoted by [M i . Given a p/t-net S = (P, T, F, M0 ), the set [M0 i of markings reachable from the initial marking M0 is called the reachability set of S, and markings in [M0 i are said to be reachable in S. A transition a ∈ T is said to be live in a marking M if there is a string u ∈ T ∗ such that ua is enabled in M . A transition a ∈ T that is not live in a marking M is said to be dead in a marking M . If M aM 0 and a transition b 6= a is enabled (live) in M and not enabled (not live) in M 0 , then we say that (the execution of) a disables (kills) b. 128 PNSE’12 – Petri Nets and Software Engineering Definition 3 (Inhibitor nets ). Inhibitor net is a quintuple S = (P, T, F, I, M0 ), where: – (P, T, F, M0 ) is a p/t-net, as defined above; – I ⊆ P × T is the set of inhibitor arcs (depicted by edges ended with a small empty circle). Sets of entries and exits are denoted by • a and a• , as in p/t- nets; the set of inhibitor entries to a is denoted by ◦ a = {p ∈ P | (p, a) ∈ I}. A transition a ∈ T (of an inhibitor net) is enabled in a marking M when- ever •a ≤ M (all its entries are marked) and (∀p ∈ ◦ a) M (p) = 0 - all in- hibitor entries to a are empty. The execution of a leads to the resulting marking M 0 = (M −• a) + a• . The following well-known fact follows easily from Definitions 1 and 2. Fact 1 (Diamond and big diamond properties) Any place/transition net possesses the following property: Big Diamond Property: If M uM 0 & M vM 00 & u ≈ v (Parikh equivalence), then M 0 = M 00 . Its special case with |u| = |v| = 2 is called the Diamond Property: If M abM 0 & M baM 00 , then M 0 = M 00 . Definition 4 (ω-extension). Let Ω = N ∪ {ω}, where ω is a new symbol (de- noted infinity). We extend, in a natural way, arithmetic operations: ω + n = ω, ω − n = ω, and the order: (∀n ∈ N) n < ω. The set of k-dimensional vectors over Ω we shall denote by Ω k , and its elements we shall call ω-vectors. Operations +, − and the order ≤ in Ω k are componentwise. For X ⊆ Ω k , we denote by Min(X) the set of all minimal (wrt ≤) members of X, and by Max(X) the set of all maximal (wrt ≤) members of X. Let v, v 0 ∈ Ω k be ω-vectors such that v ≤ v 0 , then we say that v 0 covers v ( v is covered by v 0 ) . Let us recall the well known important fact known as the Dickson’s Lemma. Lemma 1 ([6]). Any subset of incomparable elements of Ω k is finite. Definition 5. We say that a Petri net S = (P, T, F, M0 ) has the monotonicity property if and only if (∀w ∈ T ∗ )(∀M, M 0 ∈ N|P | ) M w ∧ M ≤ M 0 ⇒ M 0 w. Fact 2 P/t-nets have the monotonicity property. Proof. Obvious, since in p/t-nets the tokens of M 0 −M can be regarded as frozen (disactive) tokens. Fact 3 Inhibitor nets do not have the monotonicity property. Proof. Let us look at the example of Fig. 1. It can be easily seen that M1 < M10 . M1 a holds but M10 a doesn’t hold. Remark: In the paper we will use the notions of reachability graph (tree) and coverability graph (tree). We assume that the notions are known to the reader. Their definitions can be found in any monograph or survey about Petri nets (see [5,13] or arbitrary else). K. A. Barylska, E. Ochmański: Hierarchy of persistency 129 Fig. 1. Non-monotonic inhibitor net 3 Three Kinds of Persistency The notion of persistency is one of the classical notions in concurrency theory. The notion is recalled in [2] (named in the sequel e/e-persistency). Some of its generalizations: l/l-persistency and e/l-persistency are also introduced there. Let us sketch the notions informally. The classical e/e-persistency means "no action can disable another one", the l/l-persistency means "no action can kill another one" and the e/l-persistency means "no action can kill another enabled one". Let us go on to formal definitions. Definition 6 (Three kinds of persistency). Let S = (P, T, F, M0 ) be a place/transition net. If (∀M ∈ [M0 i) (∀a, b ∈ T ) – M a ∧ M b ∧ a 6= b ⇒ M ab, then S is said to be e/e-persistent; – M a ∧ (∃u)M ub ∧ a 6= b ⇒ (∃v)M avb, then S is said to be l/l-persistent; – M a ∧ M b ∧ a 6= b ⇒ (∃v)M avb, then S is said to be e/l-persistent. The classes of e/e-persistent (l/l-persistent, e/l-persistent) p/t-nets will be de- noted by Pe/e , Pl/l and Pe/l , respectively. It is shown in [2] that the following decision problems are decidable: Instance: A p/t net (N, M0 ) Questions: EE Net Persistency Problem: Is the net S e/e-persistent? LL Net Persistency Problem: Is the net S l/l-persistent? EL Net Persistency Problem: Is the net S e/l-persistent? 4 Hierarchy of e/l-persistency In the previous section we defined three kinds of persistency. Now, we extend the hierarchy mentioned above with an infinite hierarchy of e/l-persistent steps. 130 PNSE’12 – Petri Nets and Software Engineering Definition 7 (E/l-persistent steps - an infinite hierarchy). Let S = (P, T, F, M0 ) be a p/t-net, let M be a marking. W call a step M aM 0 : – e/l-0-persistent iff it is e/e-persistent (the execution of an action a does not disable any other action); – e/l-1-persistent iff (∀b ∈ T, b 6= a) M b ⇒ [M ab ∨ (∃c ∈ T )M acb] (the execution of an action a pushes the execution of any other enabled action away for at most 1 step); – e/l-2-persistent iff (∀b ∈ T, b 6= a) M b ⇒ (∃w ∈ T ∗ )[|w| ≤ 2 ∧ M awb] (the execution of an action a pushes the execution of any other enabled action away for at most 2 steps); ... – e/l-k-persistent for some k ∈ N iff (∀b ∈ T, b 6= a) M b ⇒ (∃w ∈ T ∗ )[|w| ≤ k∧ M awb] (the execution of an action a pushes the execution of any other en- abled action away for at most k steps); ... – e/l-∞-persistent iff (∀b ∈ T, b 6= a) M b ⇒ (∃w ∈ T ∗ ) M awb (the execution of an action a pushes the execution of any other enabled action away). Remark: Note that e/l-∞-persistent steps are exactly e/l-persistent steps. Directly from Definition 7 we get the Fact 4 Let S = (P, T, F, M0 ) be a p/t-net, let M be a marking. If the step M aM 0 is e/l-k-persistent for some k ∈ N, then it is also e/l-i-persistent for every i ≥ k. Definition 8. Let S = (P, T, F, M0 ) be a p/t-net, M be a marking and k ∈ N. Marking M is e/l-k-persistent iff for every action a ∈ T that is enabled in M the step M a is e/l-k-persistent. P/t-net S = (N, M0 ) is e/l-k-persistent iff every marking reachable in S is e/l-k-persistent. We denote the class of e/l-k-persistent p/t-nets by Pe/l−k . The direct conclusion from Fact 4 and Definition 8 is as follows: Fact 5 Let S = (P, T, F, M0 ) be a p/t-net, M be a marking, and k ∈ N. If the marking M is e/l-k-persistent, then it is also e/l-i-persistent for every i ≥ k. If the net S is e/l-k-persistent, then it is also e/l-i-persistent for every i ≥ k. Now we can formulate the problem: EL-k Step Persistency Problem Instance: P/t-net S, marking M , action a ∈ T enabled in M . Question:Is the step M a e/l-k-persistent? Theorem 1. The EL-k Step Persistency Problem is decidable (for any k ∈ N). K. A. Barylska, E. Ochmański: Hierarchy of persistency 131 Proof. An algorithm of checking if a step M a is e/l-k-persistent (for some k ∈ N) for a given net S = (N, M0 ): Let us build the part of the depth of k+1 (we call it the (k+1)-component) of the reachability tree of (N, M 0 ), where M 0 is a marking obtained from M by execution of a. The step M a is e/l-k-persistent if for every action b ∈ T , such that a 6= b and b is enabled in M , there is a path in the (k+1)-component of the reachability tree of (N, M 0 ) containing an arc labeled by b. Let us introduce another problem: EL-k Marking Persistency Problem Instance:P/t-net S = (N, M0 ), marking M . Question:Is the marking M e/l-k-persistent? Theorem 2. The EL-k Marking Persistency Problem is decidable (for any k ∈ N). Proof. For every action a ∈ T that is enabled in a marking M , we check if a step M a is e/l-k-persistent (for some k ∈ N) for a given net S = (N, M0 ), using the algorithm of Theorem 1. Let us recall the well-known fact, that follows from the Dickson’s Lemma 1. Fact 6 Every infinite sequence of markings contains an infinite increasing (not necessarily strictly) subsequence of markings. Recall also that p/t-nets have the monotonicity property - Fact 2. Let us define the notion of k-enabledness. Definition 9 (k-enabledness). Let S = (P, T, F, M0 ) be a p/t-net, let M be a marking. For k ∈ N we say that the action a ∈ T is k-enabled in the marking M if and only if ∃w ∈ T ∗ , such that |w| ≤ k ∧ M wa. Now, we can show: Lemma 2. Let S be a p/t-net. For an arbitrary a ∈ T there exists a natural number ka ∈ N, such that in every marking M the transition a is ka -enabled or it is dead. Proof. Suppose that the lemma does not hold for some action a ∈ T . It means that for each k ∈ N there is a marking M such that M is not k-enabled but not dead. This means that M is k0 -enabled for some k0 > k. Thus, there exists an infinite sets of markings M1 , M2 , . . . and integers k1 < k2 < . . ., such that the action a is live in each marking Mi and it is not ki -enabled in Mi for all i = 1, 2, . . .. Let us choose (by Fact 6) an infinite increasing sequence of markings Mi1 ≤ Mi2 ≤ . . .. Since the action a is live in Mi1 , it is k-enabled in Mi1 , for some k ∈ N. As the strictly increasing sequence k1 < k2 < . . . is infinite, k < kij for some j. By the monotonicity property (Fact 2), the action a is k-enabled, hence kij -enabled in the marking Mij . Contradiction. 132 PNSE’12 – Petri Nets and Software Engineering Remark: Note that the proof of Lemma 2 is purely existential, it does not present any algorithm for finding k. Now, we are ready to formulate the main theorem of the chapter: Theorem 3. If a p/t-net is e/l-persistent, then it is e/l-k-persistent for some k ∈ N. In words: Whenever an action is disabled by another one, it is pushed away for not more than k-steps. Proof. If the net is e/l-persistent, then no action kills another enabled one. From the Lemma 2 we know, that if an action a ∈ T is not dead then it is ka -enabled. Let us take K = max{ka |a ∈ T }, for the numbers ka from the Lemma 2. One can see that every action in the net that is not dead, is K-enabled. Thus, the execution of any action may postpone the execution of an action a for at most K steps. So we have the implication: if a p/t-net is e/l-persistent, then it is e/l-K-persistent, for K defined above. Fig. 2. A p/t-net that is e/l-3 persistent but not e/l-2 persistent Example 1. Let us look at the example of Fig. 2. The only possible situation for temporary disabling an action by another one is the execution of a that disables b. And then b could be enabled again after the execution of the sequence cde, so after 3 steps. Hence, the net is e/l-3-persistent, and obviously not e/l-2- persistent. The following example shows that Theorem 3 does not hold for nets without the monotonicity property. Example 2. Let us look at the example of Fig. 3. We can see an inhibitor net and its computation such that for every k ∈ N one can push an action away for a distance greater than k steps. This net is life, hence it is e/l-persistent, but it is not e/l-k-persistent for any k ∈ N. In the infinite computation acbcdaecbcddaeecbcdddaeeecb . . . the first a pushes b away for 1 step, the second - for 2 steps and every k-th a - for k steps. K. A. Barylska, E. Ochmański: Hierarchy of persistency 133 Fig. 3. An inhibitor net and its infinite computation 4.1 EL-k Net Persistency Problem In the previous section, we established that an action can not postpone another action indefinitely (Theorem 3). We proved, that if a p/t-net is e/l-persistent, then it is e/l-k-persistent for some k ∈ N. We showed that such a k exists but we did not present any algorithm for finding this k. In view of the statements above, let us consider the following problem: EL-k Net Persistency Problem Instance:P/t-net S = (N, M0 ), k ∈ N. Question:Is the net S e/l-k-persistent? To solve this problem we must prove a set of auxiliary facts. From this moment, let S = (N, M0 ) be an arbitrary p/t-net. Let us define the following set of markings: Ea,b = {M ∈ N|P | | M a ∧ M b}- the set of markings enabling actions a and b simultaneously. Let us define minEa,b ∈ N|P | , the minimum marking enabling actions a and b simultaneously: if (• a[i] = 1 ∨ • b[i] = 1) then minEa,b [i] := 1 else minEa,b [i] := 0 (for i = {1, . . . , |P |}). Note that minEa,b = minEa,b + N|P | . Let us formulate an auxiliary problem: Mutual Enabledness Reachability Problem Instance:P/t-net S = (N, M0 ), actions a, b ∈ T . Question:Is there a marking M such that M ∈ Ea,b and M ∈ [M0 i ? (Is there a reachable marking M such that actions a and b are both enabled in M ?) Theorem 4. The Mutual Enabledness Reachability Problem is decidable. 134 PNSE’12 – Petri Nets and Software Engineering Proof. Let M = minEa,b . We build a coverability graph for the p/t-net S. We check whether in the graph exists a vertex corresponding to an ω-marking M 0 such that M 0 covers M . If so, then actions a and b are simultaneously enabled in some reachable marking of the net S. Otherwise, those transitions are never enabled at the same time. Let Min[M0 i be a set of minimal (wrt ≤) reachable markings of the net S. As members of Min[M0 i are incomparable, the set Min[M0 i is finite, by Lemma 1. Le us denote by REa,b the set of all reachable markings of the net S enabling actions a and b simultaneously: REa,b = {M ∈ [M0 i | M a ∧ M b} = Ea,b ∩ [M0 i. Let Min(REa,b ) be a set of all minimal reachable markings of the net S en- abling action a and b simultaneously. Let us recall the Set Reachability Problem. Set Reachability Problem Instance:P/t-net S = (N, M0 ) and a set X ⊆ N|P | . Question:Is there a marking M ∈ X, reachable in S? Theorem 5. If X ⊆ Nk is a rational convex set, then the X-Reachability Prob- lem is decidable in the class of p/t-nets. Proof. In [2]. Proposition 1. The set Min(REa,b ) can be effectively constructed. Proof. Sketch of the proof: We put into work the theory of residue sets of Valk/Jantzen [14]. By Valk’s/Jantzen’s Theory, to show that the set of minimal elements of the set REa,b is effectively computable, it is enough S to demonstrate that the set REa,b ↑ has the property RES (where REa,b ↑= {x ↑| x ∈ REa,b } and x ↑= {z ∈ N|P | | x ≤ z}). We show it using decidability Theorem 5). Example 3. The set of all minimal reachable markings of the net depicted in Fig.4 enabling action a and b simultaneously, is Min(REa,b ) = {[1, 1, 1], [2, 0, 1]}. Proposition 2. If there exists a marking M ∈ REa,b such that the execution of an action a in M pushes the execution of an action b away for more than k steps (for some k ∈ N), then there exists some minimal marking M 0 ∈ Min(REa,b ) such that the execution of an action a in M 0 pushes the execution of an action b away for more than k steps, too. K. A. Barylska, E. Ochmański: Hierarchy of persistency 135 Fig. 4. A p/t-net. Proof. Let M be a marking, such that the execution of an action a in M pushes the execution of an action b away for more than k steps (for some k ∈ N). Let M 0 ∈ Min(REa,b ) such that M 0 ≤ M . Such a marking has to exist. Suppose that there is a string w ∈ T ∗ , |w| ≤ k such that M 0 awb. Then obviously also M awb (from the monotonicity property - Fact 2). We obtain a contradiction. Hence, the execution of an action a in M 0 postpones the execution of b for more than k steps. Now, we are ready to introduce the following problem: EL-k Transition Persistency Problem Instance:P/t-net S = (N, M0 ), ordered pair (a, b) ∈ T × T, b 6= a, k ∈ N. Question:Is there a reachable marking M ∈ [M0 i such that M a ∧ M b ∧ ¬[(∃w ∈ T ∗ )|w| ≤ k ∧ M awb]? (Does a postpone b for more than k steps?) Theorem 6. The EL-k Transition Persistency Problem is decidable. Proof. We introduce an algorithm of deciding if an action a pushes the execution of an action b away for more than k steps in some reachable marking M . 1. We check whether any markings from the set Ea,b is reachable. (a) If not, we answer NO. (b) Otherwise: i. We build the set Min(REa,b ). ii. For all markings M1 ∈ Min(REa,b ): M2 := M1 a. We build a part of the depth of k+1 (the (k+1)-component) of the reachability tree of (N, M2 ). If the piece has an edge labeled by b, we answer NO. Otherwise we answer YES. And now the proof of decidability of the EL-k Net Persistency Problem is ready. 136 PNSE’12 – Petri Nets and Software Engineering Theorem 7. The EL-k Net Persistency Problem is decidable (for any k ∈ N). Proof. S is e/l-k-persistent iff the algorithm solving EL-k Transition Persistency Problem answers NO for all ordered pairs (a, b) ∈ T × T , a 6= b. Finally, let us bring to mind decision another problems defined in [2]: Transitions Persistency Problems Instance:P/t-net S = (N, M0 ), and transitions a, b ∈ T, a 6= b. Questions (informally): EE-Persistency Problem: Does a disable an enabled b? LL-Persistency Problem: Does a kill a live b? EL-Persistency Problem: Does a kill an enabled b? From [2] we know that the problems are decidable. Theorem 8. For a given p/t net S = (N, M0 ) and a pair of transitions a, b ∈ T one can calculate a minimum number ka,b ∈ N such that a postpones an enabled b for at most ka,b steps (if such a number exists). Proof. We ask whether a kills an enabled b (EL-Persistency Problem). If YES then ka,b does not exist (a kills b) else: We compute a set Min(REa,b ). We build the reachability tree as long as from every M ∈ Min(REa,b ) a path leads to a vertex M 0 (it can be an empty path) such M 0 b. The maximum length of such paths is the desired number ka,b . Theorem 9. If a p/t-net S = (N, M0 ) is e/l-persistent, then it is e/l-k-persistent for some k ∈ N and such a k can be effectively computed. Proof. For every pair (a, b) of transitions we find ka,b defined above. The number we are looking for is k = max(ka,b : a, b ∈ T ). 5 Questions for Further Work It is shown in [1] that if we change the firing rule in the following way: only e/e-persistent computations are permitted, then we get a new class of nets (we call them nonviolence nets) which are computationally equivalent to Turing ma- chines. We plan to investigate net classes, with firing rules changed (only e/l-k- persistent computations are allowed) and answer the question: Question 1: What is the computational power of nets created this way? We investigated p/t-nets because they are easy to examine (mainly due to their convenient properties such as the monotonicity property). We would like to study the hierarchy of e/l-k-persistency in more difficult extensions of p/t-nets. K. A. Barylska, E. Ochmański: Hierarchy of persistency 137 6 Acknowledgments The authors are very grateful to the anonymous referees, for their very sound remarks and suggestions. References 1. Kamila Barylska, Lukasz Mikulski, and Edward Ochmanski. On persistent reacha- bility in petri nets. In Susanna Donatelli, Jetty Kleijn, Ricardo Jorge Machado, and João M. Fernandes, editors, ACSD/Petri Nets Workshops, volume 827 of CEUR Workshop Proceedings, pages 373–384. CEUR-WS.org, 2010. 2. Kamila Barylska and Edward Ochmanski. Levels of persistency in place/transition nets. Fundam. Inform, 93(1-3):33–43, 2009. 3. E. Best and J. Esparza. Model checking of persistent Petri nets. Lecture Notes in Computer Science, 626:35–??, 1992. 4. Eike Best and Philippe Darondeau. Decomposition theorems for bounded persis- tent petri nets. In Kees M. van Hee and Rüdiger Valk, editors, Petri Nets, volume 5062 of Lecture Notes in Computer Science, pages 33–51. Springer, 2008. 5. Jorg Desel and Wolfgang Reisig. Place or transition petri nets. In Wolfgang Reisig and Grzegorz Rozenberg, editors, Lectures on Petri Nets, Vol. I: Basic Models, Advances in Petri Nets, volume 1491 (Volume I) of Lecture Notes in Computer Science (LNCS), pages 122–173. Springer-Verlag (New York), Dagstuhl, Germany, September 1996, revised paper 1998. 6. Leonard E. Dickson. Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Amer. J. Math., 35:413–422, 1913. 7. Jan Grabowski. The decidability of persistence for vector addition systems. Infor- mation Processing Letters, 11(1):20–23, 29 August 1980. 8. M. Hack. Decidability questions for petri nets. Technical Report TR-161, MIT Lab. for Comp. Sci., June 1976. 9. Hiraishi and Ichikawa. On structural conditions for weak persistency and semilin- earity of petri nets. TCS: Theoretical Computer Science, 93, 1992. 10. R. Karp and R. Miller. Parallel program schemata. Journal of Computer and System Sciences, 3:147–195, 1969. 11. Landweber and Robertson. Properties of conflict-free and persistent petri nets. JACM: Journal of the ACM, 25, 1978. 12. Ernst W. Mayr. Persistence of vector replacement systems is decidable. Acta Informatica, 15:309–318, 1981. 13. P. Starke. Petri-Netze (in German). VEB Deutscher Verlag der Wissenschaften, East Berlin, GDR, 1980. 14. Valk and Jantzen. The residue of vector sets with applications to decidability problems in petri nets. ACTAINF: Acta Informatica, 21, 1985. 15. Yamasaki. Normal petri nets. TCS: Theoretical Computer Science, 31, 1984. 16. Hideki Yamasaki. On weak persistency of Petri nets. Information Processing Letters, 13(3):94–97, 13 December 1981.