=Paper=
{{Paper
|id=None
|storemode=property
|title=On Minimality and Equivalence of Petri Nets
|pdfUrl=https://ceur-ws.org/Vol-928/0382.pdf
|volume=Vol-928
|dblpUrl=https://dblp.org/rec/conf/csp/WaglerW12
}}
==On Minimality and Equivalence of Petri Nets==
https://ceur-ws.org/Vol-928/0382.pdf
On Minimality and Equivalence of Petri Nets
?
Annegret K. Wagler, Jan-Thierry Wegener
Université Blaise Pascal (Clermont-Ferrand II)
Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes
BP 10125, 63173 Aubière Cedex, France
Annegret.WAGLER@univ-bpclermont.fr wegener@isima.fr
Abstract. The context of this work is the reconstruction of Petri net
models for biological systems from experimental data. Such methods
aim at generating all network alternatives tting the given data. To keep
the solution set small while guaranteeing its completeness, the idea is
to generate only Petri nets being minimal in the sense that all other
networks tting the data contain the reconstructed ones.
In this paper, we consider Petri nets with extensions in two directions:
priority relations among the transitions of a network in order to allow the
modelization of deterministic systems, and control-arcs in order to rep-
resent catalytic or inhibitory dependencies. We de ne a containment re-
lation for Petri nets taking both concepts, priority relations and control-
arcs, into account. We discuss the consequences for extended Petri nets
diering in their sets of control-arcs and priority relations, and the im-
pact of our results towards the reconstruction of such Petri nets.
1 Introduction
The aim of systems biology is to analyze and understand dierent phenomena as,
e.g., responses of cells to environmental changes, host-pathogen interactions, or
eects of gene defects. To gain the required insight into the underlying biological
systems, experiments are performed and the resulting experimental data have
to be interpreted in terms of models that re ect the observed phenomena.
Depending on the biological aim and the type and quality of the available
data, dierent types of mathematical models are used and corresponding meth-
ods for their reconstruction have been developed, see for instance [9, 12, 13].
Here we focus on Petri nets, a framework which turned out to coherently
model both static interactions in terms of networks and the dynamic processes
in terms of state changes [1, 2, 10, 15, 17]. In fact, a network (P, T, A, w) re ects
the involved components by places p ∈ P and their interactions by transitions
t ∈ T , linked by weighted directed arcs. Each place p ∈ P can be marked with
|P |
an integral number of tokens de ning a system state x ∈ Z+ , and the studied
dynamic processes are represented by sequences of state changes, performed by
switching or ring enabled transitions (see Section 1.1).
?
The work of the second author was supported by the Labex IMobS3 and the FEDER
(Fonds européenne de développement régional).
To obtain models of this type, we developed in [5, 6, 14, 21] an exact combina-
torial approach to reconstruct Petri nets from experimental data in an exclusively
data-driven manner.
0
Our approach takes as input a set P of places and discrete time-series data X
0 1
given by sequences (x , x , . . . , x
m
) of experimentally observed system states1 .
The goal is to determine all Petri nets (P, T, A, w) that are able to reproduce
the data, i.e., where T contains enough transitions to perform for each x
j
∈ X0
the experimentally observed state change to x
j+1
∈ X 0 . This leads to the notion
of Petri nets being conformal with the data X 0 ; our approach guarantees to
generate all of them being minimal in the sense that no super uous transitions
occur in any network, see Section 1.2.
This combinatorial approach has been extended in two directions [3, 14].
On the one hand, we introduced in [14, 19, 20, 22] the concept of priority
relations among the transitions of a network in order to allow the modelization
of deterministic systems. This means that for states where at least two transitions
are enabled, the decision between the dierent alternatives is not taken randomly,
but a speci c transition is selected according to additional activation rules . For
2
this purpose, priorities between the transitions of the network can be used (see
0
Section 1.1 for more details). This leads to the notion of X -deterministic Petri
0
nets, which show a prescribed behavior on an experimentally observed subset X
of states: the reconstructed Petri nets (P, T, A, w) do not only contain enough
j+1 j
transitions to reach the experimentally observed successors x from x , but
j
exactly this transition will be selected among all enabled ones in x which is
j+1
necessary to reach x (see Section 1.2).
On the other hand, we adapted the approach from [6] for reconstructing
standard Petri nets in another direction, namely to also include control-arcs in
order to represent catalytic or inhibitory dependencies [3, 4]. Here, an enabled
transition t ∈ T coupled with a read arc (resp. an inhibitory arc) to a place
p ∈ P can switch only if a token (resp. no token) is present in p (see Section 1.1
for more details). This leads to the reconstruction of extended Petri nets which
are catalytically conformal with given data.
To keep the solution set small while guaranteeing its completeness, the idea is
to generate only Petri nets being minimal in the sense that all other networks
tting the data contain the reconstructed ones. For that, it is required to carefully
de ne a notion of minimality taking both concepts, priority relations and control-
arcs, into account. The di culty hereby is that priority relations and control-arcs
are concurrent concepts to prevent enabled transitions from switching.
1
Any continuous experimental time-series data need to be discretized in a pre-
processing step. As a consequence of this, reconstructing Petri nets, which show
exactly the same behavior as a system of ordinary dierential equations cannot be
expected in general.
2
In contrast to the normally used stochastic simulation, the aim of this approach is to
force the reconstructed Petri net to show the observed behavior of the experiments
in a simulation.
The contribution of this paper is to de ne a containment relation for Petri
nets and to discuss the consequences for extended Petri nets diering in their
sets of control-arcs and priority relations (Section 2). Finally, we discuss the
0
impact of our results towards the reconstruction of minimal X -deterministic
extended Petri nets (Section 3).
1.1 Petri Nets
A Petri net P = (P, T, A, w) is a weighted directed bipartite graph with two
kinds of nodes, places and transitions. The places p ∈ P represent the system
components (e.g. proteins, enzymes, genes, receptors or their conformational
states) and the transitions t ∈ T stand for their interactions (e.g., chemical
reactions, activations or causal dependencies). The arcs in A ⊂ (P ×T )∪(T ×P )
link places and transitions, and the arc weights w : A → N re ect stoichiometric
coe cients of the reactions.
Each place p ∈ P can be marked with an integral number xp of tokens, and
|P |
any marking de nes a state x ∈ N of the system. In biological systems, all
components can be considered to be bounded, as the value xp of any state refers
to the concentration of the studied component p ∈ P , which can only increase
up to a certain maximum cap(p). This leads to a capacitated Petri net (P, cap),
i.e., a Petri net P = (P, T, A, w) together with a capacity function cap : P → N,
|P |
whose set of potential states is X := {x ∈ N | xp ≤ cap(p)}.
An extended Petri net P = (P, T, (AS ∪ AR ∪ AI ), w) is a Petri net which has,
besides the standard-arcs in AS , two additional sets of special arcs (so-called
3 A
control-arcs): the set of read-arcs R ⊂ P × T and the set of inhibitor-arcs
AI ⊂ P × T . The set of all control-arcs, i.e., the set AR ∪ AI , is denoted by AC .
A transition t ∈ T is enabled in a state x ∈ X of a capacitated and extended
Petri net if all the following conditions are satis ed:
(i) xp ≥ w(p, t) for all p with (p, t) ∈ AS ,
(ii) xp + w(t, p) ≤ cap(p) for all p with (t, p) ∈ AS ,
(iii) xp ≥ w(p, t) for all p with (p, t) ∈ AR ,
(iv) xp < w(p, t) for all p with (p, t) ∈ AI .
If a transition is not enabled, we say it is disabled. In the case that condition
(iii) (resp. (iv)) does not hold, we say that t is disabled due to a read-arc (resp.
disabled due to an inhibitor-arc ).
When a transition t is enabled in a state x it can switch, leading to a successor
0 t
state x ∈ X (denoted by x →− x0 ) whose marking is obtained by
xp − w(p, t), for all p with (p, t) ∈ AS ,
0
xp := xp + w(t, p), for all p with (t, p) ∈ AS ,
xp , otherwise.
3
A read-arc (p, t) ∈ AR , also called test-arc, can be simulated in a standard Petri
net by two standard-arcs; namely by the arcs (p, t) ∈ AS and (t, p) ∈ AS , where
w(p, t) = w(t, p).
In general there can be more than one transition enabled in a state x ∈ X , and
the decision which transition switches is typically taken non-deterministically
(and the dynamic behavior is analyzed in terms of reachability, starting from
a certain initial state). This is not appropriate for biological system showing a
deterministic behavior where, e.g., a certain stimulation always results in the
same response. In this case, additional activation rules are required in order to
j j+1
force the switch from a state x to a speci c successor state x . For this pur-
pose, priorities between the transitions of the network can be used to determine
which of the enabled transitions has to be taken. Note that these priorities typ-
ically re ect the rate of the corresponding reactions where the fastest reaction
has highest priority. In Marwan et al. [14] it is proposed to model such priorities
with the help of partial orders on the set T of transitions of the network P . Here,
a partial order O on T is a relation ≤ between pairs of elements of T respecting
• re exivity (i.e., t ≤ t holds for all t ∈ T ),
• transitivity (i.e., from t ≤ t0 and t0 ≤ t00 follows t ≤ t00 for all t, t0 , t00 ∈ T ),
• anti-symmetry (i.e., t ≤ t0 and t0 ≤ t implies t = t0 ).
We call (P, O) an (extended) Petri net with priorities, if P = (P, T, A, w) is an
(extended) Petri net and O a priority relation on T .
Note that priorities can prevent enabled transitions from switching: for a state
x ∈ X , let T (x) := {t ∈ T | t is enabled in x}, then only a transition t ∈ T (x)
is allowed to switch or can switch if there is no other transition t ∈ T (x) with
0
(t < t0 ) ∈ O. The set of all transitions that are allowed to switch in x is denoted
by
TP,O (x) := {t ∈ T (x) | there is no t0 ∈ T (x) with (t < t0 ) ∈ O}.
In this paper we consider capacitated extended Petri nets with priorities
(P, cap, O): extended Petri nets P = (P, T, A, w) with a capacity function cap :
P → N on their places and a partial order O ⊂ T × T on their transitions.
1.2 Reconstructing Petri Nets from Experimental Data
Our main goal is to reconstruct Petri nets from experimental time-series data.
We rst brie y describe the input, the main idea, and the generated output of
the reconstruction approach.
First, a set of components P (later represented by the set of places) is chosen
which is expected to be crucial for the studied phenomenon. For each of them,
a capacity cap(p) is given so that all system states are represented by vectors
|P |
from X = {x ∈ N , xp ≤ cap(p)}.
To perform an experiment, the system is stimulated in a state (by external
stimuli like the change of nutrient concentrations or the exposition to some
1
pathogens) to generate an initial state x ∈ X . Then the system's response to the
stimulation is observed and the resulting state changes are measured at certain
1 k
) of states xi ∈ X re ecting the
time points. This yields a sequence (x , . . . , x
1
time-dependent response of the system to the stimulation, denoted by X (x ) =
(x1 , . . . , xk ). Typically, several experiments starting from dierent initial states
in a set Ini ⊆ X are necessary to describe the whole phenomenon, and we obtain
experimental time-series data of the form X 0 = {X (x1 ) | x1 ∈ Ini}, see Example
1 or Example 2 for illustration and [6, 7, 21] for more details.
0
Thus, the experimental setting is given by (P, cap, X ), and the task is to nd
all networks P = (P, T, AS , w) with P as set of places which are appropriate to
0
explain the experimentally observed behavior reported in X .
In the best case, two consecutively measured states x , x
j j+1
∈ X 0 are also
j+1 j
consecutive system states, i.e., x can be obtained from x by switching a
single transition in T . This is, however, in general not the case (and depends on
0 j+1
the chosen time points to measure the states in X ), but x is obtained from
j
x by a switching sequence of some length, where the intermediate states are
0
not reported in X .
P tting the experimental data, this can be interpreted as
In a network
follows. With P , an incidence matrix M ∈ Z|P |×|T | is associated, where each
row corresponds to a place p ∈ P of the network, and each column M·t to the
update vector of a transition t ∈ T :
−w(p, t) if (p, t) ∈ AS ,
Mpt := +w(t, p) if (t, p) ∈ AS ,
0 otherwise.
j+1 j
Reaching x from x by a switching sequence using the transitions from a
0
subset T ⊆ T , is equivalent to obtain the state vector xj+1 from xj by adding
0
the corresponding columns M·t of M for all t ∈ T :
X
xj + M·t = xj+1 .
t∈T 0
Hence, to t the experimental data, it is required to include enough transitions
to perform all experimentally observed switching sequences. More formally, a
network P = (P, T, AS , w) with incidence matrix M ∈ Z|P |×|T | is conformal
0 1 j j+1
with X if, for each x ∈ Ini and any two consecutive states x , x ∈ X (x1 ),
the linear equation system
xj+1 − xj = M λ
|T |
has an integral solution λ ∈ N such that λ is the incidence vector of a sequence
(t , ..., t ) of transition switches, i.e., there are states xj = y 1 , y 2 , ..., y k+1 =
1 k
xj+1 with y l + M·tl = y l+1 for 1 ≤ l ≤ k .
This leads to the following problem (Network Reconstruction Problem): Given
0
the experimental setting (P, cap, X ), generate all the networks P = (P, T, AS , w)
0
being conformal with X .
For details on the reconstruction approach to solve this problem, we refer
to [6, 21]. Note that all returned solution alternatives P = (P, T, AS , w) have
the same set of places P (as part of the input), but dier in the transition
sets T and the corresponding weighted arcs (obtained from all possible com-
binations of dierent switching sequences between two consecutively measured
j
states x , x
j+1
∈ X 0 ). To keep the solution set small while guaranteeing its com-
pleteness, the idea is to generate only Petri nets being minimal in the sense
that removing any transition from T yields a network which cannot explain the
experimental observations anymore.
This approach works only to reconstruct standard Petri nets. To re ne the
dynamic behavior of the reconstructed networks, two dierent extensions have
been considered which both impose further conditions for an enabled transition:
priority relations on the transitions to force a deterministic behavior and control-
arcs to represent catalytic or inhibitory dependencies.
We next brie y explain the corresponding extensions of the reconstruction
approach from [14, 18] and [6]. Note that both approaches take the already re-
constructed standard networks P = (P, T, AS , w) and add either a partial order
O ⊂ T × T on their transitions or a set of control-arcs AR ∪ AI .
To determine a suitable partial order for a network P = (P, T, AS , w) being
0
conformal with X ,
• consider, for any two consecutively measured states xj , xj+1 ∈ X 0 , the for P
j 1 2 k+1
selected sequence of intermediate states x = y , y , . . . , y = xj+1 and
i
• impose priority relations that force, in all those states y , this transition to
i+1
have highest priority which is required to reach y .
For any such priority relation O , we obtain a (capacitated) Petri net with prior-
ities (P, cap, O) which is X
0
-deterministic, as it shows a prescribed behavior on
0
the experimentally observed subset X of states.
To reconstruct extended Petri nets, where enzymatic reactions and inhibi-
tions are represented with the help of control-arcs,
• analyze the mass or signal ow experimentally observed in X 0 in dependency
of potential catalytically acting components,
• generate and evaluate a resulting logical formula, and
• insert the corresponding control-arcs in the studied reconstructed network
P = (P, T, AS , w).
This leads to the reconstruction of (capacitated) extended Petri nets which are
catalytically conformal with the given data.
The nal goal for the reconstruction is the combination of the two latter
0
methods to a global reconstruction approach producing all X -deterministic ex-
0
tended Petri nets tting the given data X . To keep the solution set small while
guaranteeing its completeness, the idea is again to generate only Petri nets be-
ing minimal in the sense that all other networks tting the data contain the
reconstructed ones.
While minimality could be easily related to set inclusion of the transition sets
of two standard Petri nets, the di culty for extended Petri nets with priorities
is that priority relations and control-arcs are concurrent concepts to prevent
enabled transitions from switching. Therefore, it is required to carefully de ne
a notion of minimality taking both concepts, priority relations and control-arcs,
into account, which will be the subject of the next section.
2 Classi cation of X 0 -Deterministic Extended Petri Nets
In this section, we consider capacitated extended Petri nets with priority rela-
0
tions, generated by a reconstruction approach from experimental data X and,
0
therefore, all being X -deterministic conformal networks. Formalizing a mini-
mality concept for such Petri nets can be done by de ning suitable equivalence
classes, and selecting a minimal one as representative of each equivalence class.
Hence, we rst have to de ne an appropriate equivalence relation as well as an
inclusion relation for the studied Petri nets, in order to classify the minimal
elements w.r.t. inclusion within the equivalence classes.
In the literature there are several concepts for the equivalence of Petri nets,
two often used ones are marking equivalence (see, e.g., [8]) and bisimulation
equivalence (see, e.g., [11, 16]).
Marking equivalence is de ned in terms of reachability in a Petri net P =
(P, T, A, w). A sequence of transitions t1 . . . tk in T is called a feasible switching
sequence for a state x0 ∈ X in P , if tj ∈ T (xj−1 ) for all 1 ≤ j ≤ k. A marking
xk is reachable from an initial marking x0 , if there exists a feasible switching
sequence from x to x . Two Petri nets are marking equivalent, if they have the
0 k
same set of reachable markings, starting from the same initial marking.
Two Petri nets are bisimilar if every feasible transition sequence in one Petri
net is a feasible transition sequence in the other Petri net and vice versa.
The two concepts of marking and bisimulation equivalence are not suitable
0
for our purpose, as we need to compare two X -deterministic conformal networks
1 0
starting from all initial states x ∈ Ini ⊆ X (and not just from one initial mark-
1 1 k
ing), but only on the states reported in X (x ) = (x , . . . , x ) (and not on all
1 k
intermediate system states between x and any reachable state x ). We, there-
fore propose to consider for any two consecutively measured states x , x
j j+1
∈ X0
j+1 j
only that x is reachable from x in terms of a feasible transition sequence.
De nition 1. Two X 0 -deterministic extended Petri nets (P, cap, O), (P̂, cap, Ô)
are X 0 -equivalent if both P and P̂ have the same incidence matrix.
One can easily verify that this is indeed an equivalence relation. Note that all
X 0 -deterministic extended Petri nets in the same equivalence class have not only
the same set of places (and therefore the same set X of potential states), but
also the sets of transitions, the sets of standard-arcs and their weights are equal.
We next de ne for such Petri nets an inclusion relation, obtained from strength-
ening the concept of bisimulation equivalence. For that, we call a sequence of
transitions t
1
. . . tk O-feasible for a state x0 of (P, cap, O) if tj ∈ TP,O (xj−1 ) for
all 1 ≤ j ≤ k .
De nition 2. Consider two X 0 -equivalent extended Petri nets (P, cap, O) and
(P̂, cap, Ô). We say P is included in P̂ , denoted by P ⊆ P̂ , if and only if for
all states x ∈ X , every Ô-feasible switching sequence for x in P̂ is a O-feasible
switching sequence for x in P .
In order to state the de nition of minimal, we need the following notions.
0
For an X -deterministic extended Petri net ((P, T, AS ∪ AC , w), cap, O)),
• a control-arc (p, t) ∈ AC is necessary, if ((P, T, AS ∪(AC \{(p, t)}), w), cap, O)
0
is not conformal to X ;
• a priority (t < t ) ∈ O is necessary, if O \ {(t < t0 )} is not a partial order or
0
(P, cap, O \ {(t < t0 )}) is not X 0 -deterministic;
• a priority (t < t0 ) ∈ O is strictly necessary, if (P, cap, O \ {(t < t0 )}) is not
X 0 -deterministic.
unnecessary.
If a priority is not (strictly) necessary, we call this element (strictly)
De nition 3. Among all X 0 -equivalent extended Petri nets, P is minimal i P
does neither have unnecessary elements nor is included in another Petri net P̂
being X 0 -equivalent to P .
0 0
Based on this inclusion relation for X -equivalent Petri nets we compare X -
deterministic extended Petri nets. Firstly, we provide a general statement on the
0
inclusion of X -deterministic extended Petri nets.
Lemma 1. Let (P, cap, O) and (P̂, cap, Ô) be two X 0 -equivalent Petri nets.
Then P ⊆ P̂ holds i for all states x ∈ X we have TP̂,Ô (x) ⊆ TP,O (x).
0
In order to classify X -deterministic extended Petri nets for inclusion, we
consider (P, cap, O) and (P̂, cap, Ô) with P = (P, T, AS ∪ AC , w) and P̂ =
(P, T, AS ∪ ÂC , ŵ), respectively, and distinguish the following cases:
• O ⊂ Ô and AC = ÂC ;
• O = Ô and AC ⊂ ÂC ;
• O ⊂ Ô and AC ⊂ ÂC ;
• Ô ⊂ O and AC ⊂ ÂC .
In other words, our aim is to determine, when we can safely remove a priority
0
or a control-arc to get a smaller X -deterministic extended Petri net.
Lemma 2. Let (P, cap, O) and (P̂, cap, Ô) be two X 0 -equivalent Petri nets with
O ⊂ Ô and AC = ÂC . Then P ⊆ P̂ holds.
0
One could be tempted to ask for the converse, i.e., if for two X -equivalent
Petri nets (P, cap, O) and (P̂, cap, Ô) with O = Ô and AC ⊂ ÂC , the inclusion
P ⊆ P̂ follows. However, it turns out to be not true in general, as the following
counter example demonstrates.
Example 1. Consider the two extended Petri nets (P, 1, O) and (P̂, 1, Ô) shown
0
on the left and the right side of Figure 1, respectively. Both Petri nets are X1 -
0
equivalent for X1 given by
(1 0 0 0 0) → (0 0 0 1 0),
(1 1 1 0 0) → (1 1 0 0 1) → (0 1 0 1 1), (1)
(0 1 1 0 0) → (0 1 0 0 1)
and satisfy O = Ô and AC ⊂ ÂC . However, the behavior of both nets diers
1
in a state x := (1 0 1 0 0) (indicated as marking in Figure 1), since we have
TP,O (x1 ) = {t2 } and TP̂ ,Ô (x1 ) = {t1 }. Thus, neither P ⊆ P̂ nor P̂ ⊆ P holds.
D E D E
t1 t2 t1 t2
A B C A B C
t1 < t2 t1 < t2
Fig. 1. Two X10 -equivalent Petri nets, (P, 1, O) on the left side and (P̂, 1, Ô) on
the right side, which satisfy O = Ô and AC ⊂ ÂC , but are not comparable.
0
Also in the case, where we have O ⊂ Ô and AC ⊂ ÂC , for two X -equivalent
Petri nets (P, cap, O) and (P̂, cap, Ô), neither P ⊆ P̂ nor P̂ ⊆ P follows in
general. This is demonstrated in the next example.
Example 2. Consider the two extended Petri nets (P, 1, O) and (P̂, 1, Ô) shown
0
on the left and the right side of Figure 2, respectively. Both Petri nets are X2 -
0
equivalent for X2 given by
(1 1 0 0 0 0) → (1 0 0 0 1 0) → (0 0 0 1 1 0),
(2)
(1 0 1 0 1 0) → (1 0 0 0 1 1) → (0 0 0 1 1 1)
2
and satisfy O ⊂ Ô and AC ⊂ ÂC . However, their behavior diers in state x :=
(1 0 1 0 0 0) (indicated as marking in Figure 2); since we have TP,O (x ) = {t3 } 2
2 1
but TP̂,Ô (x ) = {t }. Thus, neither P ⊆ P̂ nor P̂ ⊆ P holds.
D E F D E F
t1 t2 t3 t1 t2 t3
A B C A B C
t2 < t3 , t1 < t3 t1 < t2 , t2 < t3 , t1 < t3
Fig. 2. Two X20 -equivalent Petri nets (P, 1, O) on the left side and (P̂, 1, Ô) on
the right side, which satisfy O ⊂ Ô and AC ⊂ ÂC , but are not comparable.
The next case, which we consider in more detail is Ô ⊂ O and AC ⊂ ÂC .
We provide a necessary and a su cient condition for P ⊆ P̂ in Theorem 1 and
Theorem 2, respectively.
Theorem 1. Let (P, cap, O) and (P̂, cap, Ô) be two X 0 -equivalent Petri nets
with Ô ⊂ O and AC ⊂ ÂC .
If we have P ⊂ P̂ then for all (t < t0 ) ∈ O \ Ô, where (t < t0 ) is strictly
necessary, t and t0 are not both enabled in any state in P̂ .
Theorem 2. Let (P, cap, O) and (P̂, cap, Ô) be two X 0 -equivalent Petri nets
and let Ô ⊂ O and AC ⊂ ÂC . Furthermore, let every control-arc in ÂC be
necessary.
If for all (t < t0 ) ∈ O \ Ô the following properties hold:
(i) t and t0 are not both enabled in any state in P̂ ,
(ii) there does not exist a transition t00 with (t00 < t) ∈ Ô,
(iii) (t < t0 ) is strictly necessary in P ,
then P ⊂ P̂ follows.
Remark 1. Note that conditions (ii) and (iii) in Theorem 2 are indeed neces-
sary, as there exist counter examples, where the claimed inclusion does not hold
anymore, if one of the conditions (ii) or (iii) is dropped.
Remark 2. Finally, note that the presented concepts and approaches work for
Petri nets with arbitrary capacities. For the examples, we only consider the
binary case to keep the set of potential states small for the required calculations.
3 Conclusion
In this work, we address the problem of reconstructing capacitated extended
0
Petri nets with priorities from experimental time-series data X . Already in the
case of reconstructing standard Petri nets [6], standard Petri nets with priorities
[13] or extended Petri nets without priorities [4], there is typically no unique Petri
net being conformal with the given data, but a large set of solution alternatives.
0
We expect that reconstructing X -deterministic extended Petri nets results in
even larger solution sets. To keep the solution set small, while still guaranteeing
completeness, the idea is to generate only Petri nets being minimal in the sense
that all other nets tting the data contain the reconstructed ones.
While minimality can be easily related to set inclusion of the transition sets of
standard Petri nets, the di culty for extended Petri nets with priorities is that
priority relations and control-arcs are concurrent concepts to prevent enabled
transitions from switching.
Our contribution is to de ne a notion of minimality taking both concepts into
0
account. For that, we de ne when two X -deterministic extended Petri nets are
0
equivalent (X -equivalence), and provide an inclusion relation for such networks,
0
which allows to determine minimal elements in a class of X -equivalent Petri nets.
0
Furthermore, we address the question to classify X -equivalent Petri nets for
their inclusion. It turns out that
• the case O ⊂ Ô and AC = ÂC implies P ⊆ P̂ (Lemma 2),
• there exists a necessary and a su cient condition (Theorem 1 and Theorem
2, respectively) to conclude from Ô ⊂ O and AC ⊂ ÂC that P ⊂ P̂ holds,
• whereas Petri nets with O = Ô and AC ⊂ ÂC or O ⊂ Ô and AC ⊂ ÂC are
incomparable in general (see Example 1 and Example 2, respectively).
Our further goal is to identify some additional properties for capacitated
extended Petri nets with priorities, so that also for the latter two cases some
su cient conditions for their inclusion can be imposed.
Moreover, note that the rst case with O ⊂ Ô and AC = ÂC obviously
provides a test for inclusion, which can be easily performed.
Also the two conditions from Theorem 1 and Theorem 2 for the case Ô ⊂ O
and AC ⊂ ÂC can be veri ed e ciently, since the tests whether there is a state,
0
where two transitions t, t are both enabled, as well as that there is no other
00 00
transition t with (t < t) can be done in polynomial time by [19].
0
Hence, here we provided conditions, which imply an inclusion of two X -
equivalent Petri Nets, that can indeed be applied practically to reduce the solu-
tion set of the studied reconstruction approach.
References
1. M. Chen and W. Hofestädt. A Petri net application of metabolic processes. J.
Syst. Anal. Modell. Simul., 16:113122, 1994.
2. M. Chen and W. Hofestädt. Quantitative Petri net model fo gene regulated
metabolic networks in the cell. In Silico Biology, 3:347365, 2003.
3. M. Durzinsky, W. Marwan, and A. Wagler. Reconstruction of extended petri nets
from time-series data by using logical control functions. Journal of Mathematical
Biology, 2012.
4. M. Durzinsky, W. Marwan, and K. A. Wagler. Reconstruction of extended petri
nets from time-series data by using logical control functions. Journal of Mathe-
matical Biology, 2011. DOI: 10.1007/s00285-012-0511-3.
5. M. Durzinsky, A. Wagler, and R. Weismantel. A combinatorial approach to recon-
struct petri nets from experimental data. In Computational Methods in Systems
Biology, volume 5307, pages 328346, 2008.
6. M. Durzinsky, A. Wagler, and R. Weismantel. An algorithmic framework for net-
work reconstruction. Journal of Theoretical Computer Science, 412(26):28002815,
2011.
7. M. Durzinsky, K. A. Wagler, and R. Weismantel. A combinatorial approach to
reconstruct petri nets from experimental data. In M. Heiner and A.M. Uhrmacher,
editors, CSMB, volume 5307 of Lecture Notes in Computer Science, pages 328346,
2008.
8. J. Esparza and M. Nielsen. Decidability Issues for Petri Nets - a Survey. Bulletin
of the European Association for Theoretical Computer Science, 52:245262, 1994.
9. Boris N. Kholodenko, Anatoly Kiyatkin, Frank J. Bruggeman, Eduardo Sontag,
Hans V. Westerho, and Jan B. Hoek. Untangling the wires: A strategy to trace
functional interactions in signaling and gene networks. Proceedings of the National
Academy of Sciences, 99(20):1284112846, October 2002.
10. I. Koch and M. Heiner. Petri nets. In B. H. Junker and F. Schreiber, editors,
Biological Network Analysis, Wiley Book Series on Bioinformatics, pages 139179,
2007.
11. M. Kot and Z. Sawa. Bisimulation equivalence of a bpp and a nite-state system can
be decided in polynomial time. Electron. Notes Theor. Comput. Sci., 138(3):4960,
December 2005.
12. R. Krishna and S. Guo. A partial granger causality approach to explode causal
networks derived from multi-parameter data. Computational Methods in Systems
Biology, 5307:927, 2008.
13. R. Laubenbacher and B. Stigler. A computational algebra approach to reverse
engineering of gene regulatory networks. Journal of Theoretical Biology, 229:523
537, 2005.
14. W. Marwan, A. Wagler, and R. Weismantel. A mathematical approach to solve
the network reconstruction problem. Math. Methods of Operations Research,
67(1):117132, 2008.
15. W. Marwan, A. Wagler, and R. Weismantel. Petri nets as a framework for the re-
construction and analysis of signal transduction pathways and regulatory networks.
Natural Computing, 10:639654, 2011.
16. D. Park. Concurrency and automata on in nite sequences. In Proceedings of the
5th GI-Conference on Theoretical Computer Science, pages 167183, London, UK,
UK, 1981. Springer-Verlag.
17. J. W. Pinney, R. D. Westhead, and G. A. McConkey. Petri net representations in
systems biology. Biochem. Soc. Tarns., 31:15131515, 2003.
18. L. M. Torres and K. A. Wagler. Model reconstruction for discrete deterministic
systems. Electronic Notes in Discrete Mathematics, 36:175182, 2010.
19. L. M. Torres and K. A. Wagler. Encoding the dynamics of deterministic systems.
Math. Methods of Operations Research, 73:281300, 2011.
20. L. M. Torres, K. A. Wagler, and R. Weismantel. Modelling the dynamic behavior
of deterministic biological systems (extended abstract). Proc. of ALIO/EURO
Workshop on Appl. Comb. Opt., 2008. ISBN 978-950-29-1116-8.
21. K. A. Wagler. Prediction of network structure, volume 16 of Computational Biology,
pages 309338. Springer London, 2010.
22. K. A. Wagler and R. Weismantel. The combinatorics of modeling and analyzing
biological systems. Natural Computing, 10:655681, 2011.