Petri Nets with time restrictions

Louchka Popova-Zeugmann

Humboldt-Universität zu Berlin FB-16 Informatik PF 1297, O-1086 Berlin e-mail: popova@informatik.hu-berlin.de

Abstract:A new kind of time dependent Petri net is defined in this paper: time intervals are associated with each place; there it is no force to fire at any time. Basic properties of the new kind of net are studied here. A discrete way to compute the reachability graph is shown. Comparision with the classical Petri nets in relating to liveness and boundedness is done.

A Petri net is a graphic and nevertheless exact structure to formal model of a system with asynchronous components. The major use of Petri nets is the modelling of systems of ivents in wich it is possible for same events to occur concurently.

The base of all kinds of Petri nets is the classical Petri net, defined by C.A.Petri. In the last 10 years there was arised a great variety of Petri nets for actual modelling of different special systems: stochastic Petri net - for modelling of stochastic dependent concurent systems; olour Petri net - for short modeling; time dependent Petri net - for modelling of time dependend concurent systems etc.

The time is in lots of systems an important component and cannot be dropped, especially in technical systems. The time can be described in different ways by assosiating time restrictions with transitions, places, tokens, with or without force to fire etc. Some of the time dependent Petri nets can be simulated by classical Petri nets, some other cannot be simulated by them (cp. [5], [6], [10],p.107, [11], p.97). However it is usefull to modell time systems by time dependent Petri nets because:

- it is easy to describe the time here

- it is easier to analyse the system

- the evaluation of the results of the analyse is easier.

In this paper we consider a new type of time dependent Petri net, namely Petri net with time restricted places: when a token arives to a place it cannot be used for firing at once, but it has to wait for a time (different at the different places) until it becomes matur to fire. Now, during an interval (different at the different places) the token can be activ, e.g. it can be used to enable transitions, only during the given interval. After this interval the token loses its ability to be activ and waits again until it can be used for firing. During the whole time there is no force to fire.

Similar considerations are studed, for example, in [2], [3]. The difference to our model is: after the interval the tokens may not be used for firing. Essential disadvantage of [2] is, that here is not shown any method for studing the behaviour of the net. An algorithm for analysing the net is described in [3] and it is implemented, too (cp. [12]).

Well studied time dependent Petri net are the Time Petri net, defined by Merlin (cp. [1],[4],[5],[6], etc.) and the Timed Petri net, defined by Ramchandani (cp. [7],[9], etc.).

In the first section we give a short explanation of what Petri nets are. In section 2 Petri nets with time restricted places are defined and some basic properties are shown. Reachability graph for these nets are defined in a discrete way in section 3. Some comperisons with classical Petri nets are done here. In the last section we discuss some possibilities to study the behaviour of the net without computation of the (whole) rachability graph.

1.Notations and basic definitions

N denotes the set of natural numbers, N^{+} is N \ { 0 }. Q_{o} is the set of nonnegative rational numbers. A^{∗} is the language of all words over the alphabetA, including the empty word e. Let f be a mapping where f : B ⟶ C × D with f(b) = (c, d). By l(f(b))we denote c and by r(f(b)) we denote d.

In the following we will define the Petri net and some closely related notations. A detailed characterization of these nets is explained e.g. in [8] and [11].

Definition 1.1.: The structure N = (P, T, F, V, m_{o}) is called Petri net (PN), iff

(1) P, T, F are finite sets with

P ∩ T = ∅

P ∪ T ≠ ∅

F ⊆ (P × T) ∪ (T × P) and

dom(F) ∪ cod(F) = P ∪ T (net)

(2) V : F ⟶ N^{+} (weidht of the arcs)

(3) m_{o} : P ⟶N (initial marking)

Definition 1.2.: The mapping m : P N is called a marking of N. Definition 1.3.: Let t ∈ T be a transition in a Petri net N. T induce

the markings t^{−} und t^{+}, defined as follows:

t^{−} = \{ \begin{matrix}V (p, t) ,iff & (p, t) ∈ F \\ 0 ,iff & (p, t) ∉ F \end{matrix}

t^{+} = \{ \begin{matrix}V (t, p) ,iff & (t, p) ∈ F \\ 0 ,iff & (t, p) ∉ F \end{matrix}

Definition 1.4.: Let N be a Petri net, t ∈ T and m be a marking. The transition t is enabled (may fire) bym iff t^{−} ≤ m.

Definition 1.5.: Let N be a Petri net, m a marking in N and t be an enabled transition by m. m′ is called the follower marking of m iff m′ = m + △t ( = t^{+} - t^{−} ).

2.Petri nets with time restrictions at the places

In the following we will model the time by nonnegative rational numbers. Definition 2.1.: The structur ZN = (P, T, F, V, m_{o}, I) is called Pe-

tri net with time restrictions at the places (PN-tP), iff (1) (P, T, F, V, m_{o}) is a Petri net (2)I : P ⟶ Q_{o} × Q_{o} with l(I(p)) ≤ r(I(p)).

The different tokens can arive to a place at any times and following we have to count the age of every one token, i.e. we need a clock for every one token:

Definition 2.2.: Let ZN = (P, T, F, V, m_{o}, I) be a PN-tP, p ∈ P and J : P ⟶ (Q ∪{♯})^{∗} with

J(p) := \{ \begin{matrix}♯ ,iff & m(p) = 0 \\ α_{1}α_{2}...α_{m(p)} ,iff & m(p) > 0 \end{matrix} .

α_{j} is the age of the j^{th} token at the place p.

To each place we have associated so many clocks as tokens are there. A special clock is the ”empty” clock, which always shows to ♯ (i.e. at this place there are not any tokens). At each time we can add a new clock (if a new token arives to the place) or eliminate a token clock (if a token is used for firing). Formal description of these facts are the definition 2.5 and 2.6.

For the time being we define the notation ”canonical initial state” of the token clocks. As such one state we take the state where all the clocks (exept ♯) show to 0. Of course, a net can start at an other ”initial state” of the token clocks ( at least one token clock shows to a positive time).The choice of the initial state is very important for the behaviour of the net (cp. remark 3.1.).

Definition 2.3.: Let ZN be a PN-tP. J_{o} is called canonical initial state of the token clocks of ZN, iff

J_{o}(p) := \{ \begin{matrix}♯ ,falls & m_{o}(p) = 0 \\ 0^{m(p)} ,falls & m_{o}(p) > 0 \end{matrix} .

Obviously, it is true: m(p) = ln(J(p)) for every place p ∈ P. Further, it is easy to see that the total behaviour of a PN-tP cannot be described by the markings only. The token clocks connect markings and time. We will show, the notion ”token clocks” is enough to describe the behaviour of these nets. In the follow we will use the notion ”state”, too: a state z denotes the pair (m, J).

And now the firing rules for a PN-tP:

Definition 2.4.: Let ZN = (P, T, F, V, m_{o}, I) be a PN-tP, z = (m, J) be a state and t ∈ T.t is ready to fire in the state z, iff

(1) t^{−} ≤ m ( t is enabled by m )

(2) ∀p(p ∈ F t ⟶ ∀ν(ν ∈ { 1,2,...,t^{−}(p)} ⟶ l(I(p)) < J^{ν}(p) ≤ r(I(p)), iff l(I(p)) < r(I(p)) and l(I(p)) = J_{ν}(p), else )

where ν = 1, ..., t^{−}(p), and J(p) = J^{1}(p)J^{2}(p)...J^{m(p)}(p) and J^{1}(p) ≥ J^{2}(p) ≥ ...J^{m(p)}(p). Remark 2.1.: The firing intervals are half-open intervals

(l(I(p)), r(I(p))], iff l(I(p)) < r(I(p)), resp.[ l(I(p)) , r(I(p)) ], iff l(I(p)) = r(I(p))

Definition 2.5.: Let ZN = (P, T, F, V, m_{o}, I) be a PN-tP. The state z = (m, J) changes into the state z′ = (m′, J′) by the firing of the transition t (notation: z ⟶^{t} z′), iff

(0) t is ready to fire in z

(1) m′ = m + △t.

J′^{ν}(p) := \{ \begin{matrix}J^{ν+t^{−}(p)}(p) & ,iff m(p) > 0 ∧m′ > 0 ∧ 1 ≤ ν ≤ m(p) − t^{−}(p) \\ ♯ & ,iff m′(p) = 0 \\ 0 & ,else \end{matrix}

and ν = 1, ..., m′(p).

Example 2.1.:

Let p ∈ P  m(p) =3 and J(p) =7;3;1  and t^{−}=2  and t^{+}=4 be. Than it holds: m′(p) =5 and J′(p) =1;0;0;0;0. .

Definition 2.6.: Let ZN = (P, T, F, V, m_{o}, I) be a PN-tP. The state z = (m, J) changes into the states z′ = (m′, J′) by the time duration τ ∈ Q_{o} (notation: z ⟶^{τ} z′),iff

(1) m′ = m

(2) J′^{ν}(p) := \{ \begin{matrix}(J^{ν}(p) + τ)m̂od(r(I(p)) & ,iff m(p)> 0 \\ ♯ & ,else \end{matrix} .

ν = 1, ..., m′(p), where

a m̂od b := \{ \begin{matrix}a mod b & ,iff a ≠ 0 or a = b = 0 \\ b & ,iff a mod b = 0 and b ≠0 \end{matrix} .

Example 2.2.:

Let p ∈ P be a place with l(I(p)) = 2, r(I(p)) = 4, m(p) = 2 and J(p) = 2.5; 1. Than it is:

[figure: 4; 0; 1; 2; 3; age of the 2^{th} token; age of the 1^{th} token; firing interval]

Figer 1

Sufficient for the study the behaviour of all PN-tP is the study the behaviour of PN-tP with I : P ⟶ N × N only (cp. [5],[6]).

Theorem 2.1.: Let ZN = (P, T, F, V, m_{o}, I) be a PN-tP and t an enable transition in ZN, i.e. there exists a sequence σ=(τ_{o}t_{1}τ_{1}...t_{n}τ_{n}), t_{i} ∈ T, τ ∈ Q_{o} and z_{o} ⟶^{σ} z ⟶^{t} in ZN. Then there exists a sequence

σ̂= (τ̂_{o}t_{1}τ̂_{1}...t_{n}τ̂_{n}), τ̂_{i} ∈ N and z_{o} ⟶^{σ̂}⟶^{t} in ZN.

For the proof see the proof idea of the theorem 3.1.

We can show some more: It is possible to find the times τ̂_{i} in the same cycle of [0,r(I)] as τ_{i} belong (i.e. | τ_{i} − τ̂_{i} |≤ r(I(p)) for every input place p of the transition t_{i+1} ). However, this proof is complicate and rather extensive. Analogously to this proof is the proof in [5], p.233-237.

3.Reachability graph and net behaviour

Let ZN be a PN-tP. The smallest set of states Z_{ZN}(z_{o}) which involves the state z_{o} and is closed under the operations ”change of states” by firing a transition or by time duration.

Definition 3.1.: The graph EG_{ZN}(z_{o}) is called a reachability graph of PN-tP ZN, iff its nodes are the integer-states from Z_{ZN}(z_{o}) and its arcs are defined by the triples (z, τ, z′) resp. (z, τ, z′), where z ⟶^{t} z′ resp.bzw.

z ⟶^{τ} z′.

Example 3.1.:

ZN_{1}:

[figure: P_{2}; [2,2]; P_{1}; (3,4]; P_{3}; (3,4]; t_{1}; t_{2}; Figer 2]

The integer-states in ZN_{1} are:

z_{o}=((1,1,0), ( \begin{matrix}0 \\ 0 \\ ♯ \end{matrix} )), z_{1}=((1,1,0), ( \begin{matrix}2 \\ 2 \\ ♯ \end{matrix} )), z_{2}=((1,0,1), ( \begin{matrix}2 \\ ♯ \\ 0 \end{matrix} )), z_{3}=((1,0,1), ( \begin{matrix}3 \\ ♯ \\ 1 \end{matrix} )),

z_{4}=((1,0,1), ( \begin{matrix}4 \\ ♯ \\ 2 \end{matrix} )), z_{5}=((1,0,1), ( \begin{matrix}1 \\ ♯ \\ 3 \end{matrix} )), z_{6}=((1,0,1), ( \begin{matrix}2 \\ ♯ \\ 4 \end{matrix} )), z_{7}=((1,1,0), ( \begin{matrix}4 \\ 2 \\ ♯ \end{matrix} )),

z_{8}=((1,0,1), ( \begin{matrix}0 \\ ♯ \\ 0 \end{matrix} )), z_{9}=((1,0,1), ( \begin{matrix}3 \\ ♯ \\ 3 \end{matrix} )), z_{10}=((1,0,1), ( \begin{matrix}4 \\ ♯ \\ 4 \end{matrix} )), and

[figure: EG_{ZN}(z_{o}):; z_{5}; z_{0}; z_{10}; z_{9}; z_{4}; z_{6}; z_{1}; z_{7}; z_{8}; z_{3}; z_{2}; t_{2}; 1; 2; 3; 2; t_{1}; t_{1}; 1; 1; 1; 1; 1; Figer 3]

In the following we will compare a PN-tP ZN = (P, T, F, V, m_{o}, I) with the classical Petri net N = (P, T, F, V, m_{o}). Analogously to the classical Petri net we can define the notions ” liveness” and ”boundedness” for the PN-tP. In general, there is no relation between liveness in N and in ZN (cp. Example 3.1.). The behaviour of the both nets relating to the boundedness is the same, if the initial state of the PN-tP is the canonical one.

Let ZN an N be a pair of PN-tP and classical PN. We will see, that every enable sequence of transitions in N can be fired in ZN, too:

Theorem 3.1.: Let ZN = (P, T, F, V, m_{0}, I) be a PN-tP and N = (P, T, F, V, m_{0}) be a classical PN. When the sequence σ=(t_{1}...t_{n}) can fire in N, so there exists a sequence σ̂=(τ_{o}t_{1}τ_{1}...τ_{n}t_{n}) in ZN and

z_{o} ⟶^{τ_{o}} zo^{′} ⟶^{t_{1}} z_{1} ⟶^{τ_{1}} ... ⟶^{t_{n}} z_{n} ⟶^{τ_{n}}zn^{′}

and J′ _{i}^{ν}(p) := \{ \begin{matrix}♯ & , falls m′(p) = 0 \\ r(I(p)) & , sonst \end{matrix} .

ν = 1, ..., mi^{′}(p)

i=1,...,n.

Proof: By induction on n. Idea: Always to wait until all token clocks show r(I) for each token.

Corollar 3.1.:

(1) When a PN-tP ZN is live, so the classical PN is live, too. The reverse is in general not true.

(2) A PN-tP ZN is bounded if and only if the classical PN N is bounded ((z_{o} is the canonical initial states)

Remark 3.1.: When the initial state is not the canonical one, than the assertion of Corollar 3.1. (2) does not holt. E.g. we consider the PN-tP ZN_{1} with a initial state z_{o} = (m_{o}, ( \begin{matrix}3 \\ 0 \\ ♯ \end{matrix} )). ZN_{1} is dead.

4. Discussion

The analyse, suggested in section 3 can take much place and time. Otherwise in many cases it can be sufficient just to consider such paths of the reachability graph, which lead to a dead state or to a cycle (in the reachability graph). Here the theory of stubborn sets, defined and stadied for classical PN by Valmari, offers good possibilities (cp. [13]).

An other way to reduce the reachability graph is to define classes of states. But in that case the use of a single state is more difficult. Even if a PN-tP is bounded the decidability of the liveness and of the reachability of an arbitrary state can take a lot of time.

From the corollar 3.1. it is easiely to conclude that in a PN-tP we cannot test whether an unbounded place is marked or not. But a simulation of this kind of time dependent Petri nets with classical Petri nets is not to expect.

References

1.Diaz,M.; Bertomieu, B.: Modeling and Verification of Time Dependent Systems Using Time Petri Nets. In: IEEE Trans. on Software Eng.,vol. 17, No.3, 1991,259-273

2. Ghezzi, C.; Mandrioli, D.; Morasca, S.; Pezze, M.: A general way to put time in Petri nets. In Proceeding of the Software Engineering Conference,1989.

3. Hanisch, H.-M.: Petri-Netz-Modelle zur operativen Steuerung in verfahrenstechnischen Systemen. Im Tagungsband der Fachtagung ”Entwurf komplexer Automatisierungssysteme”, 5.-6.Mai, 1992, Braunschweig.

4. Merlin, P.: A Study of the Recoverability ofommunication Protocols. Ph. D. Thesis, Computer Science Dept., University of California, Irvine, 1974.

5. Popova, L.: On Time Petri Nets. In: J. Inform. Process. Cybern. EIK 27(1991) 4, 227-244.

6. Popova-Z., L.: Zeit-Petri-Netze. Dissertation, Humboldt-Universität, Berlin, 1989.

7. Ramchandani, C.: Analysis of Asynchronous concurrent Systems by Timed Petri Nets. Project MAC-TR 120, MIT, Febr.1974

8. Reisig, W.: Petri-Netze. Springer, 1982.

9. Sifakis,J.: Performance Evolution of Systems Using Nets. In: Net Theory and Applications; (LNCS); Springer, 1980; pp.307-319.

10. Starke, P.: Petri-Netze: Grundlagen, Anwendungen, Theorie. Berlin, 1980.

11. Starke, P.: Analyse von Petri-Netz-Modellen. Stuttgart: Teubner, 1990.

12. Starke, P.: ATNA-Arc Timed Net Analyser. In: Petri Net Newsletter 37, Dec. 1990, 27-33.

13. Valmari, A.: Compositional State Space Generation. In Proceedings of the II^{th} International Conference on Application and Theory of Petri Nets, June 1990.