In this paper we consider Interval-Timed Petri nets (ITPN), an extension of Timed Petri nets in which the discrete time delays of transitions are allowed to vary within fixed intervals including possible zero durations. These nets will be analyzed for the first time under some maximal step semantics with auto-concurrency. This matches well with the reality of time critical systems which could be modeled and analyzed with our model. We introduce in particular the notion of global firing step which regroups all what happens inbetween two time ticks. Full algebraic representations of the semantics are proposed. We introduce time-dependent state equations for a sequence of global firing steps of ITPNs which are analogous to the state equation for a firing sequence in standard Petri nets and we prove its correctness using linear algebra. Our result delivers a necessary condition for reachability which is also a sufficient condition for non-reachability of an arbitrary marking in an ITPN.
Petri nets (PN) as proposed initially by Carl Adam Petri [4] are applied to design models of systems considering only causal relations in it and not temporal ones. Of course there is a huge field of applications in which time does not really matter. In real systems, however, the time is mostly indispensable and therefore it cannot be ignored. Thus a certain number of time-dependent Petri net classes had been proposed in the meanwhile, cf.([3], [9], [5], [2], [11], [1], [6]). Moreover, it is well known that the majority of these classes are more expressive then the classic model: Almost all time-dependent Petri net classes are Turing-powerful, while the power of classic Petri nets is less than that of Turing-machines.
In this paper we are dealing with Interval-Timed Petri nets (ITPN), which are an extension of Timed Petri nets (TPN), introduced by Ramhandani in [9] and extensively studied by Sifakis [10]. TPNs are classic PNs where each transition is associated with a natural number which describes its firing duration. TPNs, as well as their extensions like ITPNs, are Turing-powerful (cf. Popova [6]).
In ITPNs the firing duration of a transition is also given by a natural number but this duration is not fixed. It may vary within an interval which is associated with the transition. The apparition of a transition is thus divided in two events, the startfire and the endfire event. Inbetween them tick events may happen, corresponding to the passing (or elapsing) of one time unit of some global clock [1].
When transitions are enabled they must start firing. This is the reason why we consider as firing modus for ITPNs the firing in maximal steps. Two different step semantics are possible: with or without auto-concurrency. In this article, we consider ITPNs with auto-concurrency. This means that when a transition becomes enabled, irrespective of whether or not an instance of it is firing already, a new instance must immediately start firing. The firing duration of each new instance is choosen in a non-deterministic way and is a natural number, describing how many tick events may occur before the endfiring event. This number belongs to the interval associated with the transition. Contrary to previous work, zero firing durations are allowed in this article.
A configuration in a PN is described by a marking. Because of the explicit presence of time a marking alone cannot completely represent the configuration of a time-dependent Petri net however. For this reason we use the notion of “state" which includes both the marking and the corresponding temporal informations. The first aim of the paper is to introduce the maximal step semantics for the ITPNs formally: a firing step sequence in an ITPN consists of alternating so called Globalsteps (multisets of startfire and endfire events) and tick events. And we will prove some semantical properties.
The second aim of this paper is to provide a sufficient condition for nonreachability of states in ITPNs similar to the sufficient condition for non-reachability of markings for classic Petri nets. To illustrate this purpose, let us consider first the problem in a classic Petri net N , starting with a firing sequence σ of N . After the firing of such a sequence a certain marking M of N is reached. We can compute this marking using the following well known equation:
M = M0 + C · ψσ
(
Let us consider the PN N1 with M0 = (
Furthermore, it is evident that the marking M 0 = (
Let us now consider the Interval-Timed Petri net D1 arising from the PN N1 by adding time durations to each transition – the firing of each transition should take exactly one time unit, thus [1, 1] is the duration interval associated to t1 and t2. As both transitions are firable from the initial state, after startfiring both transitions in one step, the empty marking M is reached. After one tick event, both transitions need to endfire in one step, and the initial state is reached again. Thus it is easy to see that in this ITPN D1 the marking M 0 is not reachable. This simple example shows that reachability and non-reachability in an IntervalTimed Petri net are essentially unrelated to reachability and non-reachability in its untimed skeleton. Our aim is to prove with the help of a time-dependent state equation that for instance, it is impossible to reach M 0 in D1.
Of course, the time-dependent state equations we are establishling in this
paper are much more complex than (
The paper is organized as follows: First formal definitions of ITPNs and their maximal step semantics are given in Section 2, and some semantical equivalence is proved. Then original algebraic representations and calculus of these semantics are proposed in Section 3. Some of them are adaptations of definitions known for the algebraic presentation of a firing step sequence for TPN [8], or ITPN without zero duration and without auto-concurrency [7], and others are entirely new here. Within this frame intermediate algebraic properties are first established in Section 4, leading then to the state equations. Full proofs of all results are included in the paper. 2
This section will define the objects treated in this article.
As usual, N denotes the set of all natural numbers including zero, N+ is that without zero. A matrix A is a (m × n) - matrix when A has m rows and n columns. The denotation A = aij i=1···m for a matrix A means that A is a j=1···n (m × n) - matrix and aij is the element of A in the (i)−th row and in the j−th column. Furthermore, A.j = (a.j ) denotes the j-th column of the matrix A and Ai. = (ai.) denotes the i-th row. The (d × d) - matrix Od denotes the (d × d) zero-matrix (all its elements are zero), the (d × d) - matrix Ed is the (d × d) identity matrix. 2.1
A (marked) Petri net (PN) is a quadruple N = (P, T, v, M0), where P (the set of places) and T (the set of transitions) are finite and disjoint sets and v : (P × T ) ∪ (T × P ) −→ N defines the arcs with their weights and M0 : P −→ N fixes the initial p-marking. In general, a p-marking M : P −→ N is presented by a vector of dimension |P |. As usual, t is called enabled in a p-marking M if for all p ∈ P, v(p, t) ≤ M (p).
Let N be a PN and D : T −→ N × N be a function. Then, a pair Z = (N , D) is called an Interval-Timed Petri net (ITPN) where N is its skeleton and D its duration function including zero duration. Thus, D defines an interval for each transition. within which its firing duration can vary.
The bounds sfd(t) and lfd(t) with D(t) = sfd(t), lfd(t) are called the shortest firing duration for t and the longest firing duration for t, respectively. Furthermore, each δi ∈ D(ti)∩N can be the actual duration of transition ti firing. The bounds are allowed to be zero, i.e. the firing can be considered to take no time. An ITPN behaves similarly to a PN with regards to maximal step semantics. In this article auto-concurrency is not only allowed, but forced. Thus a maximal step will be a multiset of events which appears at the same moment. Formally, a multiset U of events E is a total function U : E −→ N, where U (ei) defines the number of occurrences of the event ei in the multiset U . We can write U in the extended set notation U = {eU(e) | e ∈ E and U (e) 6= 0} and we denote by ] the operator of multisets union.
Let t be a transitions sequence of length n, t = t1t2 · · · tn. The transitions sequence t is called an undesired cycle if, for all i 6 n, sf d(ti) = 0 and for all p, P v(ti, p) − v(p, ti) > 0. Thus undesired cycles have firing duration zero 16i6n and could be infinitely repeated without time elapsing.
An ITPN is well formed if it has no undesired cycles. In order to avoid infinite steps only well formed nets are considered in this paper.
Note that a token will reach the post-set of a transition ti only after the time corresponding to the actual duration of this transition has elapsed. The exact value of the actual duration δi is unknown at the beginning of the firing of ti. The transition may stop firing after an arbitrary number δi ∈ D(ti) of time ticks has elapsed.
As usual in time-dependent PNs, states in ITPNs are pairs S = (M, h) of mappings, M being the p -marking and h codes the clocks of the transitions. In [7] h was defined as clock-vector, whereas now, in the context of auto-concurrency, h needs to be a matrix of dimension (|T | × d). Thus the clock-matrix h has |T | rows (i.e. the number of transitions in the skeleton Z) and d = max(lf d(ti)) + 1 ti∈T columns. The value hi,j+1 represents the number of active transitions ti with age j (i.e. fired since j time ticks), where j ∈ D(ti). Please, note that we need to use ‘j+1" because the first column of the matrix has number 1 and not number 0. The initial state S(0) = (M (0), h(0)) of Z is given by the initial marking M (0) = M0 of Z and the zero-clock-matrix h(0) where hi(,0j) = 0 for all i, j. The ITPN Zo which is used as a running example is shown in Fig.2. [1,3] t2 2 Now, the behavior of ITPNs will be defined. For the transition rule of an ITPN we distinguish three types of events, namely – Startfire events: A startfire event, denoted as [ti, must occur immediately (even n times) if ti becomes enabled in the skeleton (resp. if n transitions ti become enabled at the same time). For each occurrence of [ti the input tokens of ti are removed from their preplaces, the clock associated with ti will count this occurrence by incrementing the number hi,1 and ti will be called active. – Endfire events: An endfire event, denoted as tii, must occur (even n times) if the clock associated with ti is expiring, i.e. hi,j+1 = n 6= 0 and j = lf d(ti). The event tii may occur (at most qi times) if P hi,j+1 = qi > 1. sfd(ti)6j<lfd(ti) For each of the endfire events tii which occurs the corresponding hi,j+1 is decremented and the output tokens are delivered at the postplaces of ti. There is not only some choice, if some active transitions which need not to endfire may endfire. But once the number of these may endfire events is fixed (for instance q ≤ qi times transition ti), there is a choice to take these q events totally nondeterministically or to take deterministically those q which are the oldest among the qi active ones. – Tick events: A tick event, denoted as X, is enabled iff there is no firing event which must either start firing or stop firing. Upon occurring, a tick event increments the clocks for all active transitions. Hence the tick events are global. More precisely the incrementation is realised with a right shift of the clock-matrix and by setting the first column to zero.
The initial state is considered to be the first after-tick state. The whole set of such states is defined by induction in the sequel. An ITPN can change from one after-tick state into another one by the occurrence of the so-called Globalstep, which due to zero duration and auto concurrency extends the definition of firing triple known from [7]. A Globalstep consists of several parts, first a multiset of endfire events (called Endstep), then an iterative union of two multisets Maxstep and EndstepZero, (called Iteratedstep). A Maxstep is a maximal step of startfire events and an EndstepZero is a multiset of endfire events of transitions with zero firing duration. The iteration stops when no further Maxstep is possible. Note that it always stops as only wellformed ITPNs are considered. The Globalstep is followed by one tick event for time elapsing.
During the execution of the ITPN Globalsteps and single tick events alternate
in the following way. Let S(
1) An Endstep (for end-firing-step ), denoted by G(
Thus Endstep G(i1) = T1 ] T20 where T20 ⊆ T2 , T1 = {tini i | i ∈ [1, |T |], hi(,1j)+1 = ni 6= 0, j = lf d(ti)} and T2 = {tiqi i | i ∈ [1, |T |], qi = P hi(,1j)+1 }.
sfd(ti)6j<lfd(ti)
Without loss of generality, we can choose for each i to put in T20 the oldest active transitions ti ∈ T2, as shown later in Theorem 3.
G(
M (
G(
X ti∈G(i1) P hi(,1j)0 > 0 j0>j
P
j0>j+1
hi(,1j)0 = q and 0 < q < hi(,1j)
and ehi(,1j) :=
0
hi(,1j) − q
hi(,1j)
if G(
i
if G(
i otherwise.
The state S˜(
2) An Iteratedstep is the iterative union of two multisets, the first one being a Maxstep. The second one contains only Endfiring events of transitions with zero duration, we denote that as EndstepZero.
We start by setting k := 0 and
Mf(1,k) = Mf(
If there are several enabled Mai=x1steps, the choice will be arbitrary solved. The iterative union is stopped if the calculated k + 1-th Maxstep is empty (Gm(1,k+1) = ∅,i.e. a fixpoint is reached). This implies that no further transitions can fire in this step, which always arrives because of the wellformedness of the net. The value of k is stocked in kmax (kmax := k).
b) An EndstepZero, denoted by Gz(1,k+1), is a multiset of endfire events of just activated transitions, which must or may end their firing immediately. Precisely, EndstepZero contains only transitions started in the same step of iteration and whose shortest firing duration is equal to zero; all of them whose longest firing duration is equal to zero too must end their firing; among the others an arbitrary number of transitions may end their firing. Thus EndstepZero is defined as i ∈ [1, |T |] and sf d(ti) = 0 andh ni = Gm(1,k+1)([ti) ni 6 Gm(1,k+1)([ti) i or lf d(ti) 6= 0 and
lf d(ti) = 0 and .
A state S˜(1,k+1) is calculated after the k-th iteration such that for each p ∈ P it holds that: M (1,k+1)(p) = Mf(1,k)(p)− f X Gm(1,k+1)([ti) · v(p, ti) + X Gz(1,k+1)(tii) · v(ti, p) and ( h˜i(,1j,k) + Gm(1,k+ti1∈)T([ti) − Gz(1,k+1)(tii) ti∈T h˜i(,1j,k+1) := h˜i(,1j,k) where for all l > 0, the Endstep G(l), Iteratedstep G(l) and states S(l) = i I (M (l), h(l)), S0(l) = (M 0(l), h0(l)) and S˜(l) = (Mf(l), h˜(l)) verify the above conditions. In particular each S(l) has the same marking, i.e. the same first column in the time marking as S0(l−1).
The following lemma states that the definition of S0(
M 0(l) = Mf(l) − iP|=T1| G(Il)([ti) · v(p, ti) + iP|=T1| G(Il)(tii) · v(ti, p) (h˜i(,lj) + [G(Il)([ti) − G(Il)(tii)] if j = 1 h˜i(,lj) otherwise. and 2
M 0(l) = M (l,kmax)
(
i=1 and after kmax iterations we obtain
|T |
(=5) Mf(l,kmax−1) − X Gm(l,kmax)([ti) · v(p, ti) +
|T |
X Gz(l,kmax)(tii) · v(ti, p)
i=1
M 0(l)
=
(
M (l,0)
f
−
kmax |T | kmax |T |
X X Gm(l,k)([ti) · v(p, ti) + X X Gz(l,k)(tii) · v(ti, p)
k=1 i=1
|T |
(
h˜i(,lj,kmax−1) + [G(ml,kmax)([ti) − G(zl,kmax)(tii)]
h0(l) = h˜(l,kmax)
(
=
(
The set of all after-tick states and intermediate states forms the set of reachable states of Z. The reachability graph start with the initial state s0 and has all these states as nodes and the concerned Endsteps, Iteratedsteps or ticks X as arc inscriptions. Each after-tick state has as many successor nodes as the number of subsets of the set of endfiring events which may occur in the state. Each of these nodes has as many successor nodes as Iteratedsteps. Thus the reachability graph grows very quickly. To avoid the construction of such an enormous reachability graph the consideration of the state equation to decide unreachability will be a good alternative. 2.3
We could have defined firing step sequences of an ITPN as in (
Two firing step sequences σ and σ0 are called similar, denoted by σ0 ∼ σ if both start at the same state and in all states S(l) and S0(l) the marking (i.e. their first column) is the same, and the Globalsteps are the same. Thus, in similar firing step sequences only the clock matrices may differ, which signifies that transitions of different ages could have endfired.
The following sentence establishes that w.l.o.g., we can always use as may endfire events the oldest active transitions (as chosen in Definition 1 of Subsection 2.2. above).
Note that in both cases, transitions whose actual durations are the upper bound of their respective time interval (δi = lf d(ti)) must endfire. For the others active transitions (i.e. those which may endfire) we have the choice to choose which transitions do so. Choosing to endfire the oldest active transitions make the choice deterministic. reached, too.
E xample 2 Let be S(
0 0 0 0
M (
0 0 0 0 Note that in this state, there are eight active transitions t2 whose time interval is [1, 3].
From the clock matrix h(
σ0 where always the oldest active transitions are endfired,
Proof. Let σ be a sequence of n > 1 global steps where may endfire events are
chosen arbitrarily among the active transitions independently of their ages. As
defined in (
. . . S(n−1) G−(in→−1) S˜(n−1) G−(In→−1) S0(n−1) −X→ S(n) and ∀i 6 n, S(i) = (M (i), h(i)) , where M (i) is a marking and h(i) its associated clock matrix. We want to prove, by induction on n, that we can obtain another sequence σ0 which has the same global steps as σ but different states, by endfiring the oldest active transitions first.
Base : n = 1. For the first global step σ = S(0) −G→(i0) S˜(0) −G→(I0) S0(0) −X→ S(
The first endfiring multi-set is empty and the age does not play any role. Thus S˜o(0) = S˜(0).
The iterated step contains only endfiring events of zero ages, thus we can use the same multiset of firing
S0o(0) = S0(0). After the tick event So(
Induction step: Let σ be a firing step sequence of size (n + 1) with arbitrary aged endfiring events.
Thus, the prefix of σ of size n is the following firing step sequence
σ0 = S(0) −G→(i0) S˜(0) −G→(I0) S0(0) −X→ S(
Now let us prove that there exist σo of size (n + 1) with σo ∼ σ, such that the oldest active transitions endfire.
By hypothesis, we have σo0, such σo0 ∼ σ0 and σo0 ends with state So(n), such that the states S(n) and So(n) have the same markings but may have different clock matrices. In σo0 only the oldest active transitions have endfired.
We need to prolongate σo0 by the same (n+1)-th global step (Gi(n), GI (n), X). Thus, we have to show the existence of fitting h˜o(n), h0o(n) and h0(n+1) such that So(n) = (M (n), ho(n)) G−(i→n) S˜o(n) = (Mf(n), h˜o(n)) G−(I→n) So0(n) = (M 0(n), h0o(n)) X −→ So(n+1) = (M (n+1), ho(n+1)).
We have first to show that we can endfire zi active transitions by choosing the oldest ones. Clearly, as the same global steps appeared in σ0 and σo0, the same number of active transitions appears in the two states S(n) and So(n), i.e., for all i, it holds that
X i>1d+1 i>1
Because all preceding global steps are the same for the two sequences, we have precisely the same number of transitions too young to be endfired, i.e., for all i,
P hi(,nj) = P h(oni),j . Thus, there are also the same number of active j6sfd(ti) j6sfd(ti) transitions which must or may endfire in S(n) and So(n).
By consequence, we can take exactly the same endfiring multiset G(n) as in σ, i by choosing the oldest active instance of transitions.
The state S˜o(n) = (Mf(n), h˜o(n)), as defined in (
Now the same iterated step GI (n) can appear in both states leading to S0 (n) =
o
(M 0(n), h0o(n)), as defined in (
Finally, by the tick event we obtain So(n+1) = (M (n+1), ho(n+1)), as defined in
(
Thus, the firing step sequence σo is successfully completed. We can conclude that σo ∼ σ.
d+1 X ho i,j (n) and zi 6 i>1 d+1
X hi(,nj).
hi(,nj) = 3
As already quoted, the relationship between a firing step sequence σ and a reachable p-marking M in an ordinary PN with initial p-marking M0 and a incidence matrix C can be described formally by the following linear equation, where ψσ is the Parikh vector of σ: M = M0 + C · ψσ. A Parikh vector of a word α defined over the finite set, here of transitions T = {t1 · · · tn} is a vector of dimension n and the i-th component is the number of appearance of ti in the word α. Our goal is to obtain a similar result for ITPNs, i.e. to give an algebraic description, precisely, a linear equation, for each firing step sequence, now of Globalsteps as defined above, in an arbitrary ITPN which takes into account the time, too. Meanwhile state equations had been introduced for TPN with fixed duration [8] and for ITPN without auto-concurrency and without zero duration [7], where the semantics had been formulated in a more algebraic way. We will present in the following the formal definitions of the notions we need later for the different proofs. Some of them are adaptations of definitions known for the algebraic presentation of a firing step sequence for TPN, or ITPN without zero duration and without auto-concurrency [8,7] and others are entirely new here. 3.1
In this subsection we introduce a more detailed view of the p-markings in an arbitrary ITPN with respect to the time. This view makes it possible to obtain a time-dependent state equation for a firing step sequence and it delivers a sufficient condition for the non-reachability of p-markings (timeless) as well as of time markings in such a net.
First, to calculate the effect of Endstep Gi we introduce a new (|T |×d) matrix, denoted by Gi which is the matrix representation of the Endstep multiset, fixing which events have to endfire, by taking the oldest ones.
G(
i G(i1i,)j := hi(,1j)
q
0
if G(
i j0>j
if G(
i j0>j
The proof is an immediate consequence of the above definition (
Second, in order to describe the relation between tokens and time
algebraically, we use a generalization of the p-marking, called time marking, cf. [8].
A time marking is a (|P | × (d + 1))- matrix. The number of rows is equal to the
number of places and the number of columns, d + 1, equals the maximum of all
longest durations in the considered ITPN, plus 2. They are numbered from 1
to d + 1. Each column can be considered to be a p-marking. The first column
represents the number of visible tokens in each place, i.e. the actual p-marking
M . The other columns represent tokens which are on their way to the places:
column number two for those arriving immediately, column number three for those
arriving in one time unit (one tick later), the column number four for those
arriving in two time units (after two ticks), and so on. We may observe, that only
a finite number of time markings can be associated with a given p-marking M.
(
A time state s is now defined as a pair (m, h), where m is a time marking and h is a clock-matrix. The initial time marking m(0) is defined as
m.(
The initial time state s(0) is the pair (m(0), h(0)) considered now to be the first after-tick time state.
E xample 5 Consider the ITPN Zo with d = 4 and m(0) = ( 80 00 00 00 00 ) . initial time marking allows many possible Globalsteps such as, e.g., 1. (G(0) = ∅, G(0) = {[t28});
i I 2. (G(i0) = ∅, G(I0) = {[t26, [t3} U{t3i} U{[t4}= {[t26, [t3, [t4, t3i}); 3. (G(i0) = ∅, G(I0) = {[t22, [t33} U{t3i3} U{[t1} U{t1i} U{[t2}
= {[t23, [t33, [t1, t3i3, t1i}).
The choice of one Globalsteps among those above is arbitrary. We will consider later the third one appearing.
Let s(
(13) mei(,1j) :=
|T |
mi(,1j) − kP>1 G(i1k),j0 · v(tk, pi)
if j > 1 and
j0 = lf d(tk) − j + 3
and h˜i(,1j) := hi(,1j) − G(i1i,)j (by Lemma 4). It is clear that mei(
I
in Lemma 1. For each transition tk ∈ G(
I j = lf d(tk) + 2, but tk does not influence the others columns. Hence, it holds that m0i(,j1) :=
j=1l6fdk(6tk|T)+| 2 mei(,1j) + mei(,1j) − |PT| G(I1)([tk) · v(pi, tk) + |PT| k>1 k>1
P hG(I1)([tk) − G(I1)(tki)i · v(tk, pi)
G(I1)(tki) · v(tk, pi) if j = 1 if j > 1 .
(14)
The clock matrix h0(
c) Now one tick has to occur s0(
As G(0) = O, it holds that h˜(0) = h(0) = O. As GI (0)([t3) − GI (0)(t3i) = 3 it
i
follows that
h0(
Analogously to states, we call reachable time states all after-tick and intermediate time states reached during the execution of arbitrary firing step sequences. at place pi immediately when the startfire event [tk appears, and ci(,kr) shows the number of tokens that will arrive at place pi when the endfire event tki appears after at most (r − 2) time units.
E xample 7 The time incidence matrix of Zo from Fig.2 is as follows: C = Obviously the time incidence matrix takes into account the longest firing duration lf d(ti) for each transition ti.
The appearance of tiin in some G(l) at a certain state s(l) = (m(l), h(l)) tells us i that there are at least n active transitions. The matrix G(l) associated to the i end-step tells us which ones are going to endfire.
For subsequent computation we need to update the matrix C with respect to G(l). This is achieved by matrix C(l) obtained from C where for each submatrix i C((il)) the first column represents the tokens consumed by the transitions to endfire and the j-th column represents the tokens arriving to the corresponding places after j − 2 ticks at least.
Therefore, concerning G(l) in the state s(l) = (m(l), h(l)), we define the matrix i C(l) :=
C((1l)), C((2l)), . . . , C((|lT) |) (d + 1))-matrix with as follows. Each C((kl)) = ci,r (l,k) i=1···|P | is a (|P |× r=1···d ci(,lr,k) := −v(pi, tk) · Gi(tk) if r = 1 .
v(tk, pi) · Gik,r0 f r > 1 and r0 = lf d(tk) − r + 3 E xample 8 In the ITPN Zo let us consider the endfiring step s(l) =
G(l) 0 0 0 0 (m(l), h(l)) −→i s˜(l) = ( m˜(l), h˜(l)) with m(l) = ( 00 00 140 80 00 ), h(l) = 00 04 01 00 0 0 4 0 0 0 0 0 G(il) = {t2i4, t4i3}. Then its associated matrix is G(il) = 000 030 310 000 .
The time incidence matrix C(l) arises from the matrix C as follows: C(l) = ( 00 00 00 00 00 −04 00 20 60 00 00 00 00 00 00 −03 00 36 00 00 ). (16) and Our goal now is to introduce a sparse matrix U which allows us to calculate C(l) from C, such that C(l) = C · U (l) for its submatrix U (l). Let us consider tki 6∈ G(l) and tii ∈ G(l).
i i We define the square matrix U (l) with (d + 1) · |T | rows and (d + 1) · |T | columns O stands for a block of zeros, Ai(l) is a t1 tk ti tn (d+1×d+1) matrix obtained from Ed+1 t1 A(1l) O Od+1 O Od+1 O Od+1 (cbb1uyy)r:rGMe(inul)cl(ettsipiiloy)fiwnegnhditchfirhienigfirssttehvceeonlnutummntbioeifr ionEf dto+hc1e- O...... . ....... . O...... O...... O...... O...... O...... . [(cce02oon,)llduud-S]mmsutannepspemofroGfsulelE(ilodlt)wdii.np+sgl1:ietbdhyebyt(hlfGed(i((lil),tfji)dfo(−trij)ea++ch23))j--tt∈hh tttikn OOO......dddOO+++111 ......OOOOO A(klOO)......=ddOO++O11d+1 ....OOO.O. OOA......ddi(OO++l)11 .OOOO. . OOA......dd(nOO++l)11 E xample 9 In Zo from Fig. 2 we consider the same end-step G(l) = {t2i4, t4i3} with G(l) = 000 030 010 000 . We obtain the corresponding matrices A(2l), Ai(4l) and U (l): i 0 0 3 0
4 0 0 0 0 ! A(2l) = 00 00 00 00 00 , A(4l) = 0 0 0 0 0 0 0 1 3 0 30 00 00 00 00 ! OO55 AO(25l) OO55 OO55 0 0 0 0 0 , U (l) = O5 O5 O5 O5 . 0 0 3 0 0 0 0 0 0 0 O5 O5 O5 A(4l)
It is evident that matrix U (l) makes it possible to calculate C(l) because the values of each submatrix C((kl)) of C(l) verify with respect to the endfire events tki
C((kl)) = (
C(k) · A((lk)) C(k) · Od+1 if tki ∈ G(l)
i .
otherwise.
The |P | × (d + 1) · |T | -matrix C(l) = C · U (l) is called time incidence matrix with actual durations for the end-step G(l).
i
In the following calculi (just below and later) we need some matrices, all of them are sparse square (d + 1 × d + 1) matrices: Besides the already introduced identity matrix Ed+1 and zero-matrix Od+1, we define here the matrices Ld+1 = (lij ), Wd+1 = (wij ) and the progress matrix Rd+1 = (rij ) by setting lij := 1if i ≥ 2
and i = j , wij := 0otherwise 1 if i ≥ 2
and j = 1 , ri,j := 0 otherwise.
1if (i = j = 1) or (i = j + 1) . 0otherwise For simplicity we write R instead of Rd+1 if d + 1 is clear from the context. E xample 10 For the running example Zo from Fig.1 with d + 1 = 5 these square matrices are
L5= 0 0 0 0 0 ! 0 1 0 0 0 0 0 1 0 0 , W5= 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 ! 1 0 0 0 0 1 0 0 0 0 , R5= 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 ! 1 0 0 0 0 0 1 0 0 0 . 0 0 1 0 0 0 0 0 1 0
Now, let us observe the utility of these matrices. If we multiply an arbitrary (l × d +1)- matrix A by Ld+1 we obtain a (l × (d +1))- matrix B = A· Ld+1 whose first column is the l - dimensional zero-vector and the rest of its columns are the same as in the matrix A. If we multiply A by Wd+1 we obtain a (l × (d + 1))matrix B0 = A · W whose first column is the sum of all but the first columns of A and all the other columns are zero-vectors. Finally, if we multiply A by Rd+1 we obtain a (l × (d + 1))- matrix B00 = A · W whose i-th column is the (i + 1)-th column of A, except the first one and the last one. Thus the multiplication by R insures a shift. The first column of B00 is the sum of the first and second columns of A and the last one is a zero-vector.
Now, for each Endstep G(l) = {tin1i1 i, . . . , tinρiρ i} and Iteratedstep
iqiρ G(l) = {[tin1i1 , tiq1i1 i, . . . , [tinκiρ , tiρ i}, with qs 6 ns forall s ∈ [1 · · · ρ]. we define a
I matrix B(l), called the bag matrix of G(l) as well as the matrices Bm(l) and Bz(l) i i called the bag matrices of G(Il), all being (d + 1 · |T | × (d + 1)) matrices, by setting Bi((l)1) Bm(l()1) Bz((l)1) B(l) Bi(l) = Bi((li)...|(T2)|) , Bm(l) = BBm(lm(()...l|()T2)|) and Bz(l) = BBz((lz(...)|(lT)2)|) where
B(l) :=
i(s) Bm(l()s) :=
Ld+1 0 · Ed+1 if s ∈ {i1, . . . , iρ} , otherwise.
G(Il)([ts) · Ed+1 if s ∈ {i1, . . . , iκ} , 0 · Ed+1 otherwise. (17) Bz(l()s) := G(Il)(tsi) · Ld+1 if s ∈ {i1, . . . , iκ}
0 · Ed+1 otherwise.
Remark 1 In the bag matrices for Endsteps B(l) and Bz(l), the first column is i obviously a zero vector. (18) E xample 11 The Iteratedstep G(l) = {[t62, [t3, [t1, t3i} of the net Z0 from Fig.1 1·E5 I 0·L5 yields Bm(l) = 61··EE55 and Bz(l) = 01··LL55 . 2 0·E5 0·L5 Finally, we consider two ((d + 1) · |T | × (d + 1))-matrices K(l) and B(l) which i I help us to describe algebraically the effect of respectively an Endstep and an Iteratedstep.
We will prove that the following terms describe exactly this change. − C(l) · Bi(l) + C(l) · Bi(l) · Rd = −
C · U (l) B(l) + | C{(zl) } i | C{(zl) } C · U (l) B(l) · i · Rd = C and − U (l)B(l) + U (l) · Bi(l) · Rd i
= C · Ki(l) | :={Kz(l) }
i C · Bm(l) − C · Bz(l) + C · Bz(l) · Rd = C ( Bm(l) − Bz(l) + Bz(l) · Rd) = C · BI(l).
| }
:={BzI(l)
In this section we derive a state equation for an arbitrary ITPN that is analogous
to the state equation (
We consider in the firing step sequence given in (
s(l) −−G−(il→) s˜(l) −−G−(Il→) s0(l) −−X−→ s(l+1).
The following two remarks are easy to prove. . (19) (20) (21) Remark 2 For all k ≥ d it holds that Rk =: (fi,j) i=1···d with j=1···d fi,j = 1 if i= 1 0 otherwise .
Remark 3 Let be W (l) := Bi(l) · Rd. Then the matrix W (l) has the following structure:
W((1l)) W (l) = W((2l)) ...
W((|lT) |) Lemma 12 Let us consider the (|P | × d + 1) - matrix Q(l) := C(l) · Bi(l). Then its elements qi,j have the following values:
0 if j = 1 qi(,lj) = |T |
P Gik,j0 · v(tk, pi) if 1 < j 6 d + 1 and j0 = lf d(tk) − j + 3 k=1 . and
W((sl)) :=
Wd if ts ∈ G l
i .
Od otherwise.
Proof. We compute the elements qi(,lj).
Case 1: j = 1. Then qi(,l1) =
Case 2: |T | (d+1) c(l,r) P P i,k · b(kl,,1r) = 0. r=1 k=1 qi(,lj) = C(l) · Bi(l) i,j = | ={z0} 1 < j 6 d + 1. Then |T | P C((kl)) · B(l) k=1 i(k) i,j
C(l) · Bi(l) i,1 =
P|T| C((kl)) · B(l) k=1 i(k) i,1
= = |PT| dP+1 ci(,lk,r) · b(kl,,jr) r=1 k=1 |T | = P r=1 ci(,lj,r) · 1
|T | = P G (16) k=1 ik, lfd(tk)−j+3 · v(tk, pi).
We will first establish linear equations for the time markings around a firing step.
T heorem 13 Let Z be an ITPN, and let the time states s(l) = (m(l), h(l)), s˜(l) = (m(l)h˜(l)), s0(l) = (m0(l), h0(l)) and s(l+1) = (m(l+1), h(l+1)) be defined as e in (21). Then the time markings fulfil m(l) = m(l) + C · Ki(l) e m0(l) = me(l) + C · BI(l) m(l+1) = m0(l) · R (22) (23) (24)
In order to derive (22) we have to show that me(l) i,j = m(l) i,j + C · Ki(l) i,j for each i ∈ {1, · · · , |P |} and j ∈ {1, · · · , d + 1}.
Case 1: j = 1. According to the definition of time markings ( 13) it holds that
|T | d = X X k=1 r=1
G(ilk),r · v(tk, pi) .
|T | d k=1 rP=1 G(ilk),r · v(tk, pi) = C · Ki(l) i,1. It holds
P C · K(l) − C · U (l) · Bi(l) i,1 + C · U (l) · Bi(l) · Rd . − C · U (l) · Bi(l) i,1. As the first column of the − C(l) · Bi(l)
= − Q(l) Subsequently, we consider the second term we know that i,1 = 0. (cf. lemma 12) C · U (l) · Bi(l) · Rd i,1 . By remark 3 C · U (l) · Bi(l) · Rd−1 =
C(l) · W i,1
k=1 = (d+1)·|T | (l)
P ci,k · wk(l,)1 = r=1 k=1 |T | dP+1 c(l,r) P
|T | d i,k · wk(l,,1r) (16) k=1 rP=1 G(ilk),r · v(tk, pi).
= P Considering (25),(26) and (27) leads to the equation m(l) e i,1 = m(l) (25) (26) (27) i,1
+ (28) C · K(l) i
i,1 Case 2: , as desired.
j > 1.
According to the definition of time markings in (13) it holds that |T | mei(,lj) − mi(,lj) = − X G (l)
C · K(l)
= i i,j (19) − C · U (l) · Bi(l) + C · U (l) · Bi(l) · Rd
i,j ik, lfd(tk)−j+3 k=1 C · K(l) i i,j
|T | = − P G (l) k=1 · v(tk, pi). ik, lfd(tk)−j+3 · v(tk, pi). ik, lfd(tk)−j+3
· v(tk, pi). (cf. Lemma 12) = − Q(l) = − Q(l) = − |T | X G (l) i,j i,j = = − C(l) · Bi(l) + C(l) · Bi(l) · Rd
i,j − Q(l) + C(l) · W (l) i,j
(cf. Rem. 3 and Lemma 12) + C(l) · W (l)
(l)
+ 0 = qi,j
i,j
(cf. Rem. 3)
The profs of equations (23) and (24) can be done similarly.
2
Now we can deduce the main result, i.e., the equation for the sequence (
T heorem 14 Let Z be an ITPN, n ≥ 1 and σ a firing step sequence
consisting of n Globalsteps, alternating with ticks, leading to the time state s(n) =
(m(n), h(n)) as defined in (
We call Ψσ, which is a ((d + 1) · |T | × |P |) - matrix, the Parikh matrix and
equation (29) the state equation of the firing step sequence (
It is evident, that due to Theorems 13 and 14, we can analogously establish state equations for the other (intermediate) time markings, such as m0(n) and m(n), that appear in the firing step sequences. e
The last Theorem 14 provides a sufficient condition for the non-reachability
of a given time marking. Let us explain what it means to show that there does not
exist a sequence, nevertheless which length, such that after firing of the sequence
from the initial time state, the net is in a time state whose time marking is the
given one. For this reason, similar to the case for classic Petri nets, we have to
solve an system of equalities defined by the equation (29). Of course, this system
of equalities is much more difficult than that for the equation (
The number of variables in the state equation is around n · |T | · (d + 1)2/2 + 3 , in total. Additionally, there are some more additional "local" equalities/inequalities.
Finally, we have to prove that for no n the obtained system of equalities of the state equation has an integer solution. In that case the given time marking is not reachable. In the other case - if there is an integer solution for some particular n - then no assertion can be done about the reachability of the time marking. It could be possible that the solution represents only non realizable sequences with, for instance, intermediate states which would have negative values. 5
In this article we have studied the class of Interval-Timed Petri nets with discrete delays in their most complex version. Firstly, zero duration is allowed (i.e. zero is possible as a lower bound of the duration interval of a transition), which has as consequence that in between two time ticks a certain number of transitions may start and end and provoke the start and perhaps ending of others, and so on. We consider only well formed nets where this number is always finite, i.e. where there is no undesired cycle of transitions of zero duration.
Then we allow auto-concurrency in the firing of transitions. This means that in maximal steps several instances of the same transition may start at the same moment and could have independent durations. Our notion of Globalstep, which consists of all startfire and endfire events in between two time ticks, is original.
When in a state a subbag of concurrently active instances of the same transition should end we could choose to end the oldest ones between them or arbitrary ones. We prove that both ways are equivalent, leading to sequences composed of the same Globalsteps. This result allows us to choose once for all in this article to end always the oldest active transitions.
To obtain adequate formalizations, original algebraic structures have been proposed for all defined concepts.
In this complex algebraic context, our goal was to construct state equations for the considered net class. We proposed a series of results which lead to the main theorem, which establishes that each reachable time state fulfils a certain nontrivial state equation. The paper contains all proofs.
By contraposition we may conclude, that a time state is unreachable in the considered Interval-Timed Petri net when the system of equalities associated to its state equation has no solution.