=Paper=
{{Paper
|id=Vol-1373/paper1
|storemode=property
|title=The dynamics of deterministic systems - A survey
|pdfUrl=https://ceur-ws.org/Vol-1373/paper1.pdf
|volume=Vol-1373
|dblpUrl=https://dblp.org/rec/conf/apn/TorresW15
}}
==The dynamics of deterministic systems - A survey==
https://ceur-ws.org/Vol-1373/paper1.pdf
The dynamics of deterministic systems –
A survey
Luis M. Torres1 , Annegret K. Wagler2
luis.torres@epn.edu.ec, wagler@isima.fr
1
Centro de Modelizatión Matemática (ModeMat)
Escuela Politécnica Nacional, Quito, Ecuador
2
LIMOS (UMR 6158 CNRS)
University Blaise Pascal, Clermont-Ferrand, France
Abstract. We present a model for the dynamics of discrete determin-
istic systems, based on an extension of the Petri net framework. Our
model relies on the definition of a priority relation between conflicting
transitions, which is encoded in a compact manner by orienting the edges
of a transition conflict graph. The benefit is that this allows the use of a
successor oracle for the study of dynamic processes from a global point
of view, independent from a particular initial state and the (complete)
construction of the reachability graph. We provide a characterization,
in terms of a local consistency condition, of those deterministic systems
whose dynamic behavior can be encoded using our approach and con-
sider the problem of recognizing when an orientation of the transition
conflict graph is valid for this purpose . Finally, we address the prob-
lem of gaining the information that allows to provide an appropriate
priority relation gouverning the dynamic behavior of the studied system
and dicuss some further implications and generalizations of the studied
approach.
1 Introduction
Petri nets constitute a well-established framework for modeling complex dynamic
systems. Their broad application range includes the design of asynchronous hard-
ware circuits [31], the analysis of production and workflow systems [2], the anal-
ysis and control of batch processes [9], the design of distributed algorithms for
networks of agents [26], and the modeling and simulation of biological networks
[10,11,21], to cite only some prominent examples.
Petri nets also turned out to be a flexible modeling framework that has been
extended in various ways for dealing with different applications. For instance,
colored and high-level Petri nets have been widely used for protocol specification
in communication networks [5,14]. Stochastic Petri nets are used in cases where
uncertainty is attached to input data, to describe external noise generated by the
environment, as well as noise that might be intrinsic to a system [16,3]. Hybrid
Petri nets allow to model systems were both continuous and discrete processes
M Heiner, AK Wagler (Eds.): BioPPN 2015, a satellite event of PETRI NETS 2015,
CEUR Workshop Proceedings Vol. 1373, 2015.
2 LM Torres, AK Wagler
coexist [6], and the inclusion of additional features required for modeling certain
biological networks has led to the definition of Hybrid Functional Petri nets [22].
In this paper we consider another possible extension that aims at representing
systems whose dynamic behavior exhibits deterministic features.
More formally, a network G = (P, T, A, w) reflects the involved components
(like network elements, technical components, biological entities etc.) by places
p ∈ P and their interactions (like transformations, causal dependencies, chemical
reactions etc.) by transitions t ∈ T , linked by weighted directed arcs. Each place
p ∈ P can be marked with an integral number of tokens defining a system state
x ∈ ZP + , and dynamic processes are represented by sequences of state changes,
starting from an initial state x0 and performed by consecutively switching or
firing enabled transitions (see Section 2 for more details).
Usually, the dynamic behavior is the result of several conflicting as well as
concurrent ongoing dynamic processes. A Petri net is a pair (G, x0 ) consisting
of a network G together with an initial state x0 , and its state space X (x0 ) is
understood as the set of all further system states which can be reached from x0
by switching or firing sequences of transitions, see e.g. [25] for more information.
In this framework, describing the dynamics of a system might be done by model
animation, i.e., by simulating the flow of tokens inside the network as transitions
are switched [12]. Given a network G and an initial state x0 ∈ X , some central
problems that are usually studied in this context are:
– Reachability: Determine whether the system may eventually reach one of a
set of target states after a finite sequence of transition switches.
– Boundedness: Determine if there are sequences of transition switches that
lead to the accumulation of an unlimited number of tokens at some place of
the network.
– Existence of deadlocks: Determine whether the system can reach a state at
which no transitions are enabled.
– Liveness: Determine whether no sequence of transition switches can put the
system into a state where some transition is permanently disabled.
The problems mentioned above are in general hard from a computational com-
plexity point of view. For instance, reachability was proven to require exponential
space [15] and decidability of this problem could only be established some years
later [23,24].
Partial versus global point of view on a system. Dynamic processes can be en-
coded as directed paths in a state digraph G where nodes represent states and
there is a directed arc between two states x, x′ if x′ can be obtained from x by
switching a single transition. It is common practice to use the term reachability
or marking graph to refer to the subgraph G(x0 ) of G induced by the set X (x0 )
of nodes corresponding to those states that can be reached from the initial state
x0 of the network.
Considering G(x0 ) allows only a partial view on the studied system which is,
e.g., suitable for a technical system performing exactly one process. However,
already a failure of one or several components of such a system can change the
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 3
initial state, and a more global view is required to coherently model both the
normal and the mal function of the system, and to detect the faulty element(s)
by an according failure analysis.
Similarly, the study of biological systems by performing experiments can
be seen as putting the system in a particular initial state and observing the
evolution of the system in terms of resulting sequences of state changes. Due
to the intrinsic complexity of biological systems, the dynamic behavior of such
systems can rarely be understood by performing a single experiment. In general,
several experiments starting from different initial states are required and need
to be coherently interpreted in a single model.
To study dynamic systems and processes therein from a more global point
of view (independent from a particular initial state), we therefore suggest to
consider the state digraph G on the potential state space X of the system, i.e.,
on the set of all theoretically possible states.
Non-deterministic versus deterministic systems. While studying dynamic pro-
cesses, a particular situation occurs when so-called dynamic conflicts are present
at states, in which two transitions are enabled, but switching one disables the
other. In this case, model animation does not allow definite conclusions about
any system properties, as mentioned in [11]. The reason is that the occurrence
of dynamic conflicts is understood as alternative (branching) system behavior,
where a decision between these alternatives is taken non-deterministically.
However, there are examples of systems that show a deterministic behavior
despite the existence of dynamic conflicts. We call a dynamic system determinis-
tic if any state x ∈ X has a unique successor state succ(x). For technical systems,
a deterministic behavior is often crucial in order to guarantee the reliability of
the performed processes. In addition, also some biological systems are determin-
istic, as stimulating them in a certain way triggers always the same response (see
e.g. the light-induced sporulation of Physarum polycephalum plasmodia or the
phototaxis of halobacterial cells described in [18,17,19]). Petri nets, as originally
defined, can be used to model such systems only in some trivial cases.
A compact encoding for deterministic systems. Our aim is to overcome the
above mentioned difficulties by presenting a way to model deterministic sys-
tems from a global point of view (independent from a particular initial state),
and to predict the systems behavior for all possible system states (whithout gen-
erating explicitely the state digraph). For that, we define a successor function
succ : X → X which returns succ(x) for every x ∈ X . An explicit encoding of
succ, for instance pointwise, is about of the same size as the state digraph G, and
hence at least exponential in the size of G. Here we propose a more compact way
of representing the dynamics of a deterministic system, by encoding the global
dynamic behavior of the system through a local selection criterion that chooses
among all currently enabled transitions the one which switches to the successor
state succ(x).
In the next section, we formally provide all definitions and concepts needed
for Petri nets as models for deterministic systems. Our model relies on the defi-
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
4 LM Torres, AK Wagler
nition of a priority relation between conflicting transitions, which is encoded in a
compact manner by orienting the edges of a transition conflict graph. This is sub-
ject of Section 3, where the transition conflict graph is introduced together with
suitable orientations of its edges in order to impose priorities among transitions
as a selection criterion. This leads to a compact encoding of both a successor
and a predecessor oracle. We also provide a characterization of the deterministic
systems that can be encoded by our model. The issue of recognizing and charac-
terizing such suitable orientations of the transition conflict graph is addressed in
Section 4, while Section 5 is devoted to the problem of finding such orientations.
We finally summarize all proposed concepts and their benefits and discuss some
further implications and generalizations of the studied approach.
2 Petri nets with a deterministic behavior
In this section, we will formally provide all definitions and concepts needed for
Petri nets as models for systems with a deterministic behavior.
Recall that a network G = (P, T, A, w) is used to encode the structure of the
underlying system, where the set P of places represents the system’s components,
the set T of transitions stands for their interactions, and the weighted directed
arcs (p, t) or (t, p) ∈ A exclusively connect places and transitions. A network G =
(P, T, A, w) can also be represented by its incidence matrix M := (mpt ) ∈ ZP ×T
where each row corresponds to a place p ∈ P and each column to a transition
t ∈ T . We have
−wpt if p ∈ P − (t),
mpt := +wtp if p ∈ P + (t),
0 otherwise,
where P − (t) := {p ∈ P : (p, t) ∈ A} , denotes the set of pre-places of t ∈ T and
P + (t) := {p ∈ P : (t, p) ∈ A} the set of its post-places.
Some places B ⊆ P may have bounded capacities, which are given by the
positive integral vector u ∈ ZB+ . Each place p ∈ P can be marked with an integral
number xp of (at most up ) tokens, and any marking defines a state of the system
that can be represented as an integral nonnegative vector x ∈ ZP + . The potential
state space of
© a capacitated network (G,ªu) is the set of all theoretically possible
states X := x ∈ ZP + : xp ≤ up , ∀p ∈ B . It is at least exponential in |P | and is
finite if B = P holds.
Dynamic processes are described as sequences x1 , . . . , xk of consecutive sys-
tem states3 , where state xi+1 is obtained from xi by switching or firing a (single)
transition t ∈ T . Thereby, t consumes wpt tokens from each pre-place p ∈ P − (t)
and produces wtp new tokens on each post-place p ∈ P + (t). A transition t ∈ T is
enabled at a state x ∈ X if switching t yields a valid successor state x + M·t ∈ X ,
where M·t is the column of M associated with t, and disabled otherwise. Thus,
t ∈ T is enabled in x ∈ X if
3
Throughout this paper, we will use superindices to reference different states and
subindices to specify places. Thus, xip is the number of tokens assigned to place p at
state xi .
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 5
E1 xp − wpt ≥ 0 for all p ∈ P − (t) and
E2 xp + wtp ≤ up for all p ∈ P + (t) ∩ B.
Remark 1. An extended Petri net (P, T, (A ∪ AR ∪ AI ), w) is a Petri net which
has, besides the (standard) arcs in A, two additional sets of so-called control-
arcs: the set of read-arcs AR ⊂ P ×T and the set of inhibitor-arcs AI ⊂ P ×T . In
such a Petri net, switching of transitions is also controlled by read- and inhibitor-
arcs: a transition t ∈ T is enabled at x ∈ X if E1 and E2 are satisfied and it
additionally holds that
E3 xp ≥ wpt for all p with (p, t) ∈ AR , and
E4 xp < wtp for all p with (p, t) ∈ AI .
Note that also in an extended Petri net, switching of an enabled transition t at
x yields x + M·t as succesor state since control-arcs do not affect the marking.
In general, it is possible that more than one transition is enabled in a state
x ∈ X ; we denote by T (x) the set of all such transitions. Conversely,
X(t) := x ∈ X : xp ≥ wpt , ∀p ∈ P − (t); xp ≤ up − wtp , ∀p ∈ P + (t) ∩ B
© ª
denotes the set of states at which transition t is enabled.
Recall that the state digraph of a system is defined by G := (X , A) where
nodes represent potential states and a node x has an outgoing arc (x, x′ ) ∈ A
if and only if x′ = x + M·t for some t ∈ T (x), i.e., if x′ can be obtained from x
by switching a single transition. We call x ∈ X a branching state if there are at
least two transitions in T (x). The existence of a branching state implies either
an alternative or a concurrent behavior of the system.
An alternative behavior occurs when at least two transitions t, t′ ∈ T (x) are
in dynamic conflict, i.e., if they cannot switch simultaneously as for some place
p ∈ P , we have
xp − wpt − wpt′ < 0, or xp + wtp + wt′ p > up ,
thus, if x+M·t +M·t′ ∈/ X holds. While animating the model, either t or t′ has to
be selected at x. In the case of concurrency, on the contrary, no two transitions
from T (x) are in a dynamic conflict. All transitions in T (x) could be switched
simultaneously, resulting in the valid state
X
x′ = x + M·t ∈ X .
t∈T (x)
In this case, G contains paths for all possible interleaving sequences between x
and x′ , corresponding to all possible permutations of the transitions in T (x).
Petri nets are an adequate model for simulating the dynamic behavior of
deterministic systems, only if no branching states are present. Otherwise, a
mechanism has to be specified that allows to decide “which is the right path
to choose” in the state digraph. This includes in particular a way of resolving
dynamic conflicts.
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
6 LM Torres, AK Wagler
We call a Petri net deterministic if each state x ∈ X has a unique successor
succ(x) ∈ X . The dynamic behavior of a deterministic system can be specified
in the form of a successor-oracle which returns, for every state x ∈ X , the value
of succ(x). Our goal is to propose a compact implementation for this oracle.
Hereby, we restrict our attention to systems where the successor-oracle can be
expressed via a transition selection function trans : X → T , which assigns to
every state x ∈ X a unique transition trans(x) ∈ T (x) that must be switched
in order to reach state succ(x). Not all deterministic systems can be modeled in
this way, see the discussion in Section 6, and even if it is possible, an explicit
(i.e., pointwise) encoding of trans is extensive as it requires an amount of space
proportional to the size of the state digraph G, which, as pointed out in the
previous section, is at least exponential in the number of places of the network.
In [20], it was proposed to use priorities between the transitions of the net-
work as additional activation rules to determine which transition from T (x) has
to be selected as trans(x) in order to reach succ(x). Our contribution consists in
providing a compact scheme for encoding trans based on such priorities.
Remark 2. The priority relations proposed in [20] shall reflect the relative re-
action rates of the (chemical) reactions represented by the transitions of the
network with the idea that faster reactions have higher priorities and are taken.
On the model side, priorities can be seen as a discrete extreme case of firing rates
of transitions defined by probability distributions, where exactly one transition
in T (x) (namely, the highest-priority transition trans(x)) has probability 1, and
all other transitions in T (x) have probability 0.
As we show in the next section, if a deterministic system S = (G, u, succ)
satisfies a quite natural consistency condition, then there exists a digraph D :=
(T, A) on the set of transitions with the following properties:
– for every x ∈ X , the set T (x) induces a subgraph having a unique sink t(x)
– and t(x) = trans(x) is the required transition to switch from x to succ(x).
2
Observe that this graph has a size of O(|T | ), which is polynomial in the size of
G. Indeed, the arcs of D can be interpreted as priority relations between pairs
of transitions, with trans(x) being the transition with highest priority among all
transitions in T (x).
3 Encoding valid priority relations
As observed in the previous section, one key issue for modeling the dynamic
behavior of a deterministic system is the specification of a mechanism for the
(unambiguous) resolution of dynamic conflicts between enabled transitions.
Definition 1. Given a capacitated network G = (P, T, A, w) with u ∈ ZB + , its
transition conflict graph is an undirected graph K(G,u) = (T, E) having as nodes
the transitions from G, where two transitions t, t′ are joined by an edge if and
only if there exists at least one state where both are enabled, i.e.,
tt′ ∈ E ⇔ X(t) ∩ X(t′ ) 6= ∅.
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 7
As long as there is no risk of confusion, we will simply write K instead of
K(G,u) . It follows straightforwardly from this definition that, for every state
x ∈ X , the set T (x) of enabled transitions induces a clique in K, i.e., a set of
mutually adjacent nodes.
Remark 3. The converse is not necessarily true, as it is shown in [29]. How-
ever, as the sets X(t) are boxes, it is straightforward to prove that at least the
inclusionwise maximal cliques in K are associated with states of the system.
2
The transition conflict graph K can be constructed in O(|P | |T | ) time using
a straightforward algorithm to check for box intersections X(t)∩X(t′ ). The next
lemma from [29] provides a more efficient way of its computation.
Lemma 1. Consider a capacitated network (G, u), with G = (P, T, A, w), u ∈
′
ZB
+ and X(t) 6= ∅ ∀t ∈ T . Then t, t ∈ T are in conflict if and only if
wpt ≤ up − wt′ p ∀p ∈ P − (t) ∩ P + (t′ ) ∩ B and
wpt′ ≤ up − wtp ∀p ∈ P − (t′ ) ∩ P + (t) ∩ B holds.
Observe that, in the particular case where we have capacities u = 1l, it follows
as a corollary from the last lemma that two transitions t, t′ ∈ T are in conflict if
and only if
P − (t) ∩ P + (t′ ) ∩ B = ∅ and P − (t′ ) ∩ P + (t) ∩ B = ∅. (1)
The following example illustrates the previous results.
Example 1. Consider the capacitated network (G, 1l), with G = (P ∪ T, A, 1l),
from Figure 1(a). Checking the pre- and post-places for all transitions in T
yields:
ti P − (ti ) P + (ti )
t1 {2} {1}
t2 {2} {3}
t3 {2} {5}
t4 {5} {1, 4}
t5 {2, 5} {3}
According to (1), all pairs of transitions are in conflict, except (t3 , t4 ) and (t3 , t5 ),
and we obtain the transition conflict graph shown in Figure 1(b).
As stated in the introduction, our main purpose is to encode the dynamics of
a given deterministic system S = (G, u, trans) in a compact way, by introducing
enough priority relations among transitions, as to be able to determine trans(x)
for every x ∈ X . We have observed that the set of enabled transitions at each
state corresponds to a clique in the transition conflict graph K, and hence K is a
plausible candidate for a framework where these priorities could be embedded.
This idea motivates the following definition.
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
8 LM Torres, AK Wagler
1 t1 t3 t1 t3
2
4
t5 3 t2 t5 t2
t4 t4
5
(a) (b)
Fig. 1. (a) A capacitated network of a dynamic system, and (b) its transition conflict
graph. All place capacities and arc weights are assumed to be equal to one.
Definition 2. Let D(G,u) = (T, A) be a directed graph obtained by orienting the
edges of K(G,u) . D(G,u) is valid for the system S = (G, u, trans) if, for every state
x ∈ X with T (x) 6= ∅, the subgraph induced by the nodes from T (x) has a unique
sink, and this sink coincides with trans(x).
As for the unoriented transition conflict graph, we will write in the following
D instead of D(G,u) whenever there is no risk of confusion. Observe that the
existence of a valid orientation implicitly imposes a further requirement on the
nature of a dynamic system. Namely, if two states x, x∗ ∈ X have the same set
T (x) = T (x∗ ) of enabled transitions, then both induce the same subgraph of
D and, therefore, trans(x) = trans(x∗ ) must hold. Moreover, if a transition t is
enabled at two states x, x′ ∈ X and t is the highest-priority transition at x, then
either t is also the highest-priority transition at x′ or trans(x′ ) 6∈ T (x). The next
result from [29] shows that this condition is also sufficient for the existence of a
valid orientation.
Theorem 1. A system S = (G, u, trans) has a valid orientation if and only if the
following consistency condition holds for any pair of states x and x′ : if trans(x)
∈ T (x) ∩ T (x′ ) then either trans(x′ ) = trans(x) or trans(x′ ) ∈ T (x′ ) \ T (x).
As illustrated in Algorithm 1, a valid orientation completely encodes the
dynamic behavior of a deterministic system, since it can be used to obtain an
implicit implementation of the successor-oracle. Given a state x ∈ X , all we
need to do in order to find its successor is to determine the highest-priority
transition trans(x) at x. This can be accomplished by searching for the unique
sink in the subgraph of D induced by the set T (x) of enabled transitions. (If no
transitions are enabled at x, the algorithm just returns the same current state
x as successor.)
A predecessor of x is a state y ∈ X with succ(y) = x. For that, we must
have x = y + M·trans(y) . Since there are at most |T | candidates for the transition
trans(y), it follows that the set pred(x) of all possible predecessors of x has
cardinality not larger than |T | and can be constructed calling the successor
oracle at most |T | times, as shown in Algorithm 2. Here, first a set cand(x) of
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 9
Input: (G, u, D), x ∈ X
Output: succ(x)
3: Construct the set T (x) of enabled transitions
if T (x) = ∅ then
return x
6: end if
{Compute out-degree of transitions in the subgraph of D induced by T (x)}
for t ∈ T (x) do
9: δ − (t) := |{tt′ ∈ A : t′ ∈ T (x)}|
end for
{Return successor state}
12: t∗ ← t ∈ T (x) with δ − (t) = 0
return x + M·t∗
Algorithm 1: Implementing a successor-oracle by a valid orientation.
all candidate transitions t ∈ T fulfilling y := x − M·t ∈ X is computed, then the
condition t = trans(y) tested for each candidate by calling the successor oracle.
Input: (G, u, D), x ∈ X
Output: pred(x)
3: {Construct ˘set of transition candidates}
cand(x) ← t ∈ T : xp + wpt ≤ up , ∀p ∈ P − (t) ∩ B; xp − wtp ≥ 0, ∀p ∈ P + (t)
¯
{Call successor-oracle to construct sets of predecessors}
6: pred(x) ← ∅
for t ∈ cand(x) do
y ← x − M·t
9: if trans(y) = t then
pred(x) ← pred(x) ∪ {y}
end if
12: end for
{Return set of possible predecessors}
return pred(x)
Algorithm 2: An implementation for a predecessor-oracle.
Computing successors and sets of predecessors is a key operation within sim-
ulation algorithms to study the dynamic behavior of a system and in particular
to address the different questions described in the previous section. To the best
of our knowledge, currently no solution algorithm for these problems is known,
which does not rely on storing explicit descriptions of the state digraph or some
equivalent structure to compute succ(x) at every state x, which strongly limits
the size of the networks that can be considered, due to the high memory re-
quirements. Moreover, in certain application areas such as systems biology, the
explicit values of succ(x) can only be determined by carrying out expensive and
time-consuming wet lab experiments. Having, however, a valid orientation it is
possible to determine or predict succ(x) for each state x ∈ X .
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
10 LM Torres, AK Wagler
4 Recognizing and characterizing valid orientations
Another issue of interest concerns the recognition of valid orientations: Given a
capacitated network (G, u), and an orientation D of the edges in the transition
conflict graph, determine whether D induces a valid dynamic behavior on G,
in the sense that for every state x ∈ X , the corresponding clique in D has a
unique sink. Observe that a clique cannot have more than one sink, and that
every clique without a sink contains a directed cycle. Hence, if D is acyclic then
every clique of the graph has a unique sink, and we immediately obtain:
Observation 1 Every acyclic orientation of K is valid.
On the other hand, the next example shows that there are deterministic
systems for which the valid orientation encoding the dynamic behavior contains
directed cycles.
Example 2. Figure 2 depicts a network (G, 1l) with w = 1l together with a valid
orientation D of the transition conflict graph that contains a directed cycle C =
(t1 , t2 , t3 ). Table 1 lists all branching states of the system and the corresponding
sets of enabled transitions. It is straightforward to check that each of these sets
induces a clique in D with a unique sink t(x).
4
t1 t2 t1 t2
3
t3 t3
1 t4 2 t4
Fig. 2. A capacitated network and a valid orientation for its transition conflict graph
which contains a directed cycle C = (t1 , t2 , t3 ). All arc weights and capacities of the
places are assumed to be equal to one.
Table 1. All branching states of the system from Figure 2.
x1 x2 x3 x4 T (x) t(x)
1 1 0 0 {t1 , t2 } t2
0 1 1 0 {t2 , t3 } t3
1 0 1 0 {t1 , t3 } t1
1 1 1 0 {t1 , t2 , t3 , t4 } t4
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 11
The fact that one has to check, for each clique Q in K, if there is a corre-
sponding state x ∈ X with T (x) = Q makes the recognition of valid orientations
hard in general, as there might be up to 2|T | cliques. In the following we describe
a special class of orientations for which this recognition problem can be solved
efficiently.
In [29], it is shown that two different dynamic systems might share the same
transition conflict graph. This motivated the definition of the following equiva-
lence relation between capacitated networks
(G, u) ∼K (G′ , u′ ) ⇔ K(G,u) ∼
= K(G′ ,u′ ) ,
where ∼= stands for graph isomorphism. An orientation is strongly valid if it is
valid for all networks of some equivalence class of ∼K . Acyclic orientations are
one specific example of strongly valid orientations. In general, any orientation
where every clique has a unique sink is (trivially) strongly valid. Moreover, the
converse is also true, as it follows from a result in [29] that each equivalence class
contains a network with the property that every clique in K is associated to a
state. This fact makes strongly valid orientations easy to recognize.
Theorem 2. An orientation D of the transition conflict graph of a capacitated
network (G, u) is strongly valid if and only if it does not contain any directed
cycle of length 3.
In this context, one is tempted to wonder whether it is possible to gain more
insights on (strongly) valid orientations by exploring structural properties of K.
In [29], it is shown that for any undirected graph H, there is a network G having
H as its transition conflict graph. Thus, in general, neither K nor D can admit
particular graph-theoretical properties. Studying the problem however from a
hypergraph-theoretical point of view as done in [30], opens the possibility of
characterizing valid orientations further.
A hypergraph is a generalization of a graph in which it is possible to connect
any number of nodes. Formally, a hypergraph is a pair H = (V, E) where V is a
set of elements, called nodes or vertices, and E is a family of non-empty subsets of
V , called hyperedges. We further use two other combinatorial structures related
to hypergraphs. The dual H∗ of H is a hypergraph whose nodes and hyperedges
are interchanged, so that the nodes are given by all Ei ∈ E and there is one
hyperedge Vv = {Ej |v ∈ Ej } for each v ∈ V . The intersection graph G(H) of H
is a graph whose nodes represent the hyperedges of H, and two nodes are joined
by an edge if and only if the corresponding hyperedges intersect.
Recall that, by definition, for every state x ∈ X , the set T (x) of enabled
transitions induces a clique in K, whereas the converse is not necessarily true
(but at least the inclusion-wise maximal cliques in K are associated with states
of the system), see Remark 2.
The equivalence relation on X , where x ∼ x′ iff T (x) = T (x′ ), partitions
the state space into r ≤ 2|T | equivalence classes X1 , . . . , Xr of states that share
the same sets of enabled transitions. Let x̃i ∈ Xi with 1 ≤ i ≤ r be (arbitrarily
chosen) representative elements for each of these classes, and define the transition
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
12 LM Torres, AK Wagler
hypergraph HT = (T, ET ) of G to be the hypergraph © on the set T ofª transitions,
whose family ET of hyperedges is given by ET = T (x̃i ) : 1 ≤ i ≤ r . Thus, the
size of HT is exponential in the number of transitions of the network, but it is
always finite, as there are at most 2|T | different subsets of T .
© 1The state r
ª hypergraph of G is the dual hypergraph HX̃ of HT and has X̃ =
n x̃ , . . . , x̃ o set, where its family of hyperedges is determined by EX̃ =
as node
X(t) ∩ X̃ : t ∈ T . Directly from the definition of HX̃ we deduce:
Lemma 2. The intersection graph G(HX̃ ) of the state hypergraph HX̃ is exactly
the transition conflict graph K.
A hypergraph H = (V, E) has the Helly property if, for any family E ′ ⊆ E
of pairwise intersecting hyperedges, there exists a node v ∈ V contained in all
hyperedges from E ′ . A well-known result in hypergraph theory [4] states that H
has the Helly property if and only if the inclusion-wise maximal hyperedges of
its dual hypergraph H∗ are precisely the inclusion-wise maximal cliques of the
intersection graph G(H) of H [4]. This implies:
Lemma 3. HX̃ satisfies the Helly property.
A direct consequence from Lemma 3 and the preceding observations is ob-
tained in [30]:
Theorem 3. The inclusion-wise maximal hyperedges from ET are exactly the
inclusion-wise maximal cliques of K. Thus, for every inclusion-wise maximal
clique Q there is some state x̃i ∈ X̃ , 1 ≤ i ≤ r, satisfying T (x̃i ) = Q.
We next show that K has an interesting property, provided that HT and HX̃
belong to certain classes of hypergraphs. A cycle of length k in a hypergraph
H = (V, E) is a sequence (v1 , E1 , v2 , E2 , . . . , vk , Ek , vk+1 ) such that vi ∈ V for
all 1 ≤ i ≤ k + 1, Ei ∈ E for all 1 ≤ i ≤ k, Ei 6= Ej if i 6= j, vi , vi+1 ∈ Ei for all
1 ≤ i ≤ k, and vk+1 = v1 . Due to [1], a hypergraph H is acyclic if and only if
H is conformal (i.e., its dual H∗ has the Helly property) and for every cycle of
length at least 3 in H, some edge of H contains at least 3 nodes of the cycle. On
the other hand, a hypergraph H∗ = (V ∗ , E ∗ ) is called arboreal if there exists a
tree T ∗ on the node set V ∗ such that every hyperedge of H∗ induces a subtree in
T ∗ . Due to structural characterizations in [7,8,27], arboreal hypergraphs are dual
to acyclic hypergraphs and their intersection graphs are chordal, i.e. each cycle
having four or more nodes contains a chord: an edge joining two nodes that are
not adjacent in the cycle. Moreover, it can be shown that arboreal hypergraphs
have the Helly property.
Combining all these properties, the following result is obtained in [30].
Theorem 4. The following assertions are equivalent:
– HT is acyclic.
– HX̃ is arboreal.
– K is chordal.
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 13
Note that a chord (t, t′ ) within a directed cycle C in D induces a new directed
cycle with a smaller number of nodes, as C contains both a directed path from
t to t′ and a directed path from t′ to t. Hence, an orientation of a chordal graph
contains a directed cycle of length 3 if and only if it contains any directed cycle.
This observation was used in [30] to obtain a new characterization of acyclic
transition hypergraphs:
Theorem 5. The transition hypergraph HT is acyclic if and only if, for any
orientation D of K, the following two statements are equivalent:
1. D is strongly valid.
2. D is acyclic.
5 Finding valid orientations
In the previous sections, we addressed the problem of the existence of a valid ori-
entation and how to recognize and characterize such orientations. This motivates
a canonical further question, namely, once the existence of a valid orientation
has been confirmed for a deterministic system, can we also find it?
As pointed out in [28], infering a valid orientation of a transition conflict
graph shall be done by taking observations on dynamic processes in the under-
lying deterministic system into account. That is: Based on the knowledge of the
values of succ(x) at some states x ∈ X , we aim at finding a valid orientation
that encodes the global dynamic behavior of the system since succ(x) can be
determined with the help of this orientation for all states x ∈ X .
In the following we consider a deterministic system S = (G, u, trans) that
fulfills the consistency condition from Theorem 1 and hence trans can be encoded
as a valid orientation D of the transition conflict graph. Given as input the
capacitated network (G, u) and an oracle for returning the value of trans(x) at
any state x ∈ X , we want to determine D by calling the oracle as few times
as possible since in practice, a call to the oracle stands for the execution of a
(probably expensive and time-consuming) experiment.
We call a set X ′ ⊆ X of states a valid test set if the information about the
corresponding highest-priority transitions {trans(x) : x ∈ X ′ } suffices for infer-
ring the direction of all arcs in D. Consequently, we are interested in the following
problem, formulated in [28].
Definition 3 (Minimum Valid Test Set Problem (MVTP)). Given a de-
terministic system S together with an oracle for returning highest-priority tran-
sitions, find a valid test set of minimum cardinality.
The meaning of inferring an orientation deserves further explanation. Let
us denote by partial orientation a (mixed) graph D′ := (T, A′ , E′ ) obtained by
fixing the direction for some edges of K, with A′ being the set of the correspond-
ing oriented arcs, and E′ the set of the remaining unoriented edges. A partial
orientation is extendible if it is possible to choose directions for all unoriented
edges in such a way that a valid orientation is obtained. Given an extendible
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
14 LM Torres, AK Wagler
partial orientation D′ := (T, A′ , E′ ), a yet unoriented edge tt′ ∈ E′ is said to be
inferable as (t, t′ ) if the partial orientation D̂′ := (T, A′ ∪{(t′ , t)}, E′ \{tt′ }) is not
extendible. Moreover, D′ is sufficient for inferring a valid orientation D := (T, A)
if all edges in E′ are inferable as the corresponding arcs in A.
Example 3. Figure 3 illustrates these concepts. The partial orientation depicted
in (a) is not extendible, as choosing any direction for edge t2 t3 produces one
inclusionwise maximal clique without sink. In contrast, any direction chosen for
this edge in (b) leads to a valid orientation, so t2 t3 is not inferable in the second
example. A sufficient partial orientation is shown in (c): the two unoriented edges
t2 t3 and t3 t4 must be oriented as (t3 , t2 ) and (t3 , t4 ). Orienting any of them in
the opposite direction leads to a non-extendible partial orientation.
This shows that the optimal solution of MVTP may depend on the underlying
valid (complete) orientation D, and not on the transition conflict graph alone.
t3 t3 t3
t1 t4 t1 t4 t1 t4
t2 t2 t2
(a) (b) (c)
Fig. 3. Different types of partial orientations: (a) non-extendible; (b) extendible, but
non-sufficient; and (c) sufficient
In general, recognizing if a partial orientation is extendible, or if an unoriented
edge is inferable constitutes a difficult task, due to the lack of a characterization
of valid orientations from a graph theoretical point of view. In this section we
consider the particular case when D is acyclic. As mentioned earlier, acyclic
orientations are always (strongly) valid and the only strongly valid orientations
for deterministic dynamic systems with acyclic transition hypergraph HT (see
Theorem 5). Trivially, if D is acyclic then any partial orientation cannot contain
a directed cycle. On the other hand, in [28] it is proved the following:
Lemma 4. Any acyclic partial orientation is extendible.
Recall from Theorem 2 that an orientation is strongly valid if and only if
it does not contain a directed cycle of length three. Hence, for any extendible
partial orientation D′ := (T, A′ , E′ ), if (t, t′ ), (t′ , t′′ ) ∈ A′ and tt′′ ∈ E′ then tt′′ is
inferable as (t, t′′ ).
It follows from the previous lemma that an edge tt′ ∈ E′ in an acyclic partial
orientation D′ = (T, A′ , E′ ) can be inferred as (t, t′ ) if and only if the digraph
(T, A′ ) contains a directed path from t to t′ . As a consequence, D′ is sufficient if
for every tt′ ∈ E′ the digraph (T, A′ ) contains either a directed path from t to t′ ,
or a directed path from t′ to t. We say in this case that D′ has the path-property.
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 15
Conversely, given a (complete) orientation D = (T, A), an arc a := (t, t′ ) ∈ A
is called essential if the digraph (T, A \ {a}) does not contain a directed path
from t to t′ . Observe that the direction of a cannot be inferred in any partial
orientation extendible to D. Hence, any sufficient partial orientation must contain
all essential arcs from D. The next result from [28] shows that no further arcs
are required.
Theorem 6. Let D = (T, A) be a valid orientation and A∗ ⊆ A the set of
essential arcs. The partial orientation D∗ := (T, A∗ , E∗ ), where E∗ is the set of
edges from K corresponding to the arcs in A \ A∗ , is sufficient for inferring D.
Observe that the set A∗ is unique, and that it can be computed from D in
O(m2 ) time complexity, with m := |A|, for example by several runnings of a
breadth-first search algorithm to determine if each arc of A is essential or not.
Determining the direction of essential arcs is specially important for recon-
structing valid orientations. The following lemma from [28] implies that any valid
test set has cardinality larger than or equal to the number of essential arcs in D.
Lemma 5. For any state x ∈ X , knowledge of the highest-priority transition
from T (x) can be used to orient at most one essential arc.
As a consequence, the following result is obtained in [28].
Theorem 7. A valid test set X ′ ⊆ X is optimal for MVTP if and only if A(x)∩
A∗ 6= ∅ for every x ∈ X ′ , where A(x) := {(t, trans(x)) : t ∈ T (x), t 6= trans(x)}
is the set of arcs whose directions are revealed by testing the system at x.
Note that such an optimal valid test set can be easily determined if D is
known. However, in the setting of the MVTP it is not possible to devise a
“winning strategy” that guarantees that each A(x) contains an essential arc, as
the next example shows.
Example 4. Consider the conflict graph given in Figure 5(a). Observe that K
contains three cliques of size 3 (triangles) and seven edges, and that every edge is
contained in one triangle. It can be checked that for any edge e ∈ E, there exists a
valid orientation where e is not essential. Hence, any winning strategy for MVTP
must start by querying the oracle at a state x∗ ∈ X related to one of the cliques
of size 3. But for any of these cliques, there is a valid orientation where A(x∗ )
contains no essential arc. Indeed, if T (x∗ ) = {t1 , t2 , t3 } or T (x∗ ) = {t1 , t3 , t4 },
choose the orientation from Figure 5(c). Otherwise, if T (x∗ ) = {t1 , t4 , t5 }, choose
the orientation from Figure 5(b).
Even if it is not possible to devise a “winning strategy” that guarantees to
orient an essential arc with each oracle call in general, a valid orientation can
be obtained by Algorithm 3, provided that the underlying system has one state
associated with each clique of the transition conflict graph K = (T, E). Observe
that in this case the obtained orientation is strongly valid.
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
16 LM Torres, AK Wagler
t1 t1 t1
t5 t2 t5 t2 t5 t2
t4 t3 t4 t3 t4 t3
(a) (b) (c)
Fig. 4. A transition conflict graph (a) and two valid acyclic orientations (b)-(c). Es-
sential arcs are marked bold.
Input: K {transition conflict graph}
Q = {Q1 , . . . , Qk } {partition of the edges into cliques}
3: Output: D {strongly valid orientation}
for i ← 1, . . . , k do
while Qi contains more than one node do
6: determine x ∈ X with T (x) = Qi
call oracle and determine trans(x)
orient arcs {(t, trans(x)) : t ∈ T (x), t 6= trans(x)}
9: remove trans(x) from Qi
end while
end for
Algorithm 3: Inferring a strongly valid orientation.
Algorithm 3 takes as input a partition of the edges in E into a set of cliques
Q := {Q1 , . . . , Qk }. At each iteration of the outer loop, it processes a clique
Qi ∈ Q. At first, the oracle is called to orient all edges incident to the unique
sink node of Qi . Then this node is removed from Qi and the oracle is called
again on the remaining subclique. The procedure is repeated until Qi contains
only one node, which means that all its edges Phave been oriented. Since the inner
k
loop is executed |Qi | − 1 times, a total of i=1 |Qi | − k calls to the oracle are
required to find the valid orientation D. This quantity is strictly smaller than
m if |Qi | ≥ 3 holds for at least some Qi ∈ Q, since then there is at least one
iteration where two edges are oriented simultaneously, and no edge is oriented
more than once.
This indeed ensures:
Theorem 8. If the underlying system has one state associated with each clique
of the transition conflict graph, then Algorithm 3 computes a strongly valid ori-
entation.
6 Discussion
Petri nets constitute a well-established framework for modeling complex dynamic
systems. It is common practice to study dynamic processes in terms of directed
paths in the reachability or marking graph G(x0 ) starting from a designated
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 17
initial state x0 . Hereby, a particular situation occurs when dynamic conflicts are
present at states, in which two transitions are enabled, but switching one dis-
ables the other. In this case, model animation does not allow definite conclusions
about any system properties [11]. The reason is that the occurrence of dynamic
conflicts is understood as alternative (branching) system behavior, where a de-
cision between these alternatives is taken non-deterministically. Therefore, the
classical reachability analysis has the drawbacks that it
– explores the studied system only from a local point of view, starting from a
particular initial state x0 ;
– is only applicable for systems of a limited size since the reachability graph
G(x0 ) needs to be explicitly constructed, but grows exponentially in the size
of the network;
– cannot be used to study systems that exhibit a deterministic behavior.
Our aim was to overcome these difficulties by presenting a way to compactly
model deterministic systems from a global point of view (independent from a
particular initial state), and to predict the systems behavior for all possible
system states (whithout generating explicitly the state digraph). For that, we
have examined a new approach for encoding the dynamic behavior of certain
deterministic discrete systems that relies on extending the familiar framework
of Petri nets. Our encoding consists in a realization of the successor-oracle as a
valid orientation of the edges of the transition conflict graph K, together with
Algorithm 1. This encoding is compact in the sense that the amount of space
required for its storage is polynomial in the size of the network. Therefore, it is
well-suited for being integrated into simulation algorithms like [12] to study the
dynamics of large complex deterministic systems, and to address issues such as
reachability, boundedness, existence of deadlocks, and liveness, among others.
A possible interesting extension of our model concerns the study of dynamic
systems where the concurrent switch of various transitions can occur. Through-
out this paper we have assumed that a change from a state x ∈ X to its suc-
cessor state succ(x) can always be explained by the switch of a single transition
trans(x). However, there are deterministic systems where this does not hold, as
shown in the following example.
Example 5. Consider a deterministic system (G, 1l, succ) with network G as de-
picted in Figure 5 and w = 1l. It is straightforward to check that the system
has the four branching states x0 , . . . , x3 shown in the figure. The following ta-
ble lists the sets of enabled transitions at each of these states, as well as the
corresponding successor states specified by succ:
j branching state xj T (xj ) succ(xj )
0 (1, 1, 0, 0)T {t1 , t2 } (0, 0, 1, 1)T
T
1 (0, 1, 1, 0) {t2 , t3 } (0, 1, 0, 1)T
T
2 (1, 0, 0, 1) {t1 , t4 } (0, 1, 0, 0)T
T
3 (1, 1, 1, 0) {t2 , t3 } (1, 1, 0, 1)T
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
18 LM Torres, AK Wagler
Observe that t1 and t2 have to be switched concurrently at state x0 to reach
succ(x0 ), whereas at each of the other branching states a single transition is
switched to reach the corresponding successor state, namely, t3 at x1 or x4 , and
t4 at x2 . The enabled transitions are highlighted in gray in Figure 5, while the
transitions actually switched are marked in bold.
The above successor function cannot be realized with the help of a transi-
tion selection function trans due to the following reason. Considering x0 as initial
state, trans has to select one of the transitions t1 , t2 ∈ T (x0 ). However, any choice
leads to an intermediate state (x1 for trans(x0 ) = t1 , x2 for trans(x0 ) = t2 ) where
the remaining transition from T (x0 ) is still enabled but must not be selected, as
both trans(x1 ) = t3 and trans(x2 ) = t4 are implied by the specification of succ.
(See the reachability graph in Figure 5.) Thus, none of the potential interleaving
sequences between x0 and succ(x0 ) can be expressed by means of single transi-
tion switches such that every switch is determined by the value of trans at the
corresponding state.
3 t3 4 3 t3 b
4 3 b
t3 4
t1 t2 t1 t2 t1 t2
1 b
t4 b
2 1 b
t4 2 1 ? t4 b
2
x0 x2 x1,3
0
x
t1 t2
t1 + t2
x1 x2
t3 t4
(0, 1, 0, 1) (0, 0, 1, 1) (0, 1, 0, 0)
Fig. 5. A deterministic system whose dynamic behavior cannot be modeled via a tran-
sition selection function. The enabled transitions at each state are highlighted in gray,
the next transitions to be switched are shown in bold. All place capacities and arc
weights are assumed to be equal to one.
One way of dealing with these systems could be through the inclusion of
pseudo-nodes in the transition conflict graph, to account for the simultaneous
switching of various transitions. The advantage would be that all results from the
previous sections directly carry over to the extended setting. The disadvantage of
such a modification is, however, the dramatic increase in the size of the transition
conflict graph, as (in the worst-case) the number of required pseudo-nodes may
grow exponentially with respect to |T |.
An alternative approach consists in working on a slightly different transition
conflict graph, where an edge between two transitions means that they are in
dynamic conflict (i.e. when switching one transition disables the other). In this
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
The dynamics of deterministic systems – A survey 19
case, T (x) does not longer induce a clique in K. Yet we can now define an ori-
entation to be valid if for any state x ∈ X the set T (x) of enabled transitions
induces a subgraph containing at least one sink. These sinks reveal an anti-chain
of transitions with maximal priorities, which have to be switched concurrently.
Theorem 1 can be generalized to this new setting in a straightforward man-
ner, characterizing which deterministic systems admit valid orientations. The
advantage of this scheme is that it is still compact with respect to the size of
the network G. However, as the sets T (x) do not induce cliques in the conflict
graph, many of the combinatorial properties pointed out in Section 3-5 do not
hold anymore. Moreover, since all transitions that may switch concurrently are
required to do so, it is again possible to construct examples of deterministic sys-
tems whose behavior cannot be modeled in this way. Hence, further research is
necessary to ensure a compact encoding of a successor oracle for all deterministic
systems. For a large number of such systems, however, the here presented results
allow us already the use of such an oracle for the study of dynamic processes
from a global point of view, independent from a particular initial state and the
(complete) construction of the reachability graph.
References
1. Acharya, B.D., Las Vergnas, M.: Hypergraphs with cyclomatic number zero, trian-
gulated hypergraphs and an inequality. J. Combin. Theory (B) 33, 52–56 (1982)
2. Adam, N.R., Atluri, V., Huang, W.K.: Modeling and analysis of workflows using
Petri nets. J. Intell. Inf. Syst. 10(2), 131–158 (1998).
3. Balbo, G.: Introducation to stochastic Petri nets. In: Lectures on formal methods
and performance analysis: first EEF/Euro summer school on trends in computer
science, pp. 84–155. Springer-Verlag New York, Inc., New York, NY, USA (2002)
4. Berge, C., Duchet, P.: A generalisation of Gilmore’s theorem. In: M. Fiedler (ed.)
Recent Advances in Graph Theory, pp. 49–55. Acad. Praha, Prague (1975)
5. Billington, J., Diaz, M., Rozenberg, G.: Application of Petri Nets to Communica-
tion Networks, Advances in Petri Nets. Springer-Verlag, London, UK (1999)
6. David, R., Alla, H.: Discrete, Continuous, and Hybrid Petri Nets. Springer-Verlag
Berlin Heidelberg, Heidelberg (2005)
7. Duchet, P.: Propriété de Helly et problèmes de représentations. In: Problèmes
Combin. et Théorie des Graphes, Coll. Orsay 1976, pp. 117–118. CNRS Paris (1978)
8. Flament, C.: Hypergraphes arborés. Discrete Math. 21, 223–226 (1978)
9. Gu, T., Bahri, P.A.: A survey of Petri net applications in batch processes. Comput.
Ind. 47(1), 99–111 (2002).
10. Hardy, S., Robillard, P.N.: Modeling and simulation of molecular biology systems
using Petri nets: modeling goals of various approaches. Journal of Bioinformatics
and Computational Biology 2(4), 619–637 (2004)
11. M. Heiner, D. Gilbert, R. Donaldson: Petri nets for systems and synthetic biology,
In proceedings of SFM 2008, Springer, LNCS 5016:215–264, 2008.
12. M. Heiner, M. Herajy, F. Liu, C. Rohr, M. Schwarick: Snoopy – a unifying Petri net
tool. In proceedings of PETRI NETS 2012, Hamburg, Springer, LNCS 7347:398–
407, 2012.
13. M. Heiner, C. Rohr, M. Schwarick: MARCIE - Model checking And Reachability
analysis done effiCIEntly; In proceedings of PETRI NETS 2013, Milano, Springer,
LNCS 7927:389–399, 2013.
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015
20 LM Torres, AK Wagler
14. Jensen, K.: Coloured Petri nets: basic concepts, analysis methods and practical
use, volume 3. Springer-Verlag New York, Inc., New York, NY, USA (1997)
15. Lipton, R.: The reachability problem requires exponential space. Research Re-
port 62, Yale University, Computer Science Dept. (1976)
16. Marsan, M., Balbo, G., Donatelli, S., Franceschinis, G., Conte, G.: Modelling with
generalized stochastic Petri nets. Wiley Series in Parallel Computing (1995)
17. Marwan, W.: Theory of time-resolved somatic complementation and its use for the
analysis of the sporulation control network of physarum polycephalum. Genetics
164, 105–115 (2003)
18. Marwan, W., Starostzik, C.: The sequence of regulatory events in the sporula-
tion control network of physarum polycephalum analysed by time-resolved somatic
complementation of mutants. Protist 153, 391–400 (2002)
19. Marwan, W., Sujatha, A., Starostzik, C.: Reconstructing the regulatory network
controlling commitment and sporulation in physarum polycephalum based on hi-
erarchical Petri net modeling and simulation. J. Th. Biology 236, 349–365 (2005)
20. Marwan, W., Wagler, A., Weismantel, R.: A mathematical approach to solve the
network reconstruction problem. Math. Meth. Oper. Research 67, 117–132 (2008)
21. W. Marwan, A. Wagler, R. Weismantel: Petri nets as a framework for the recon-
struction and analysis of signal transduction pathways and regulatory networks,
Natural Computing 10, 639–654 (2011)
22. Matsuno, H., Aoshima, H., Doi, A., Tanaka, Y., Matsui, M.: Biopathways repre-
sentation and simulation on hybrid functional Petri net. In Silico Biology 3(3),
389–404 (2003)
23. Mayr, E.W.: An algorithm for the general Petri net reachability problem. In:
Proceedings of the 13th Ann. ACM Symposium on Theory of Computing, pp.
238–246. ACM Press (1981)
24. Mayr, E.W.: An algorithm for the general Petri net reachability problem. SIAM
J. Comput. 13(3), 441–460 (1984)
25. Reisig, W.: Petri nets: an introduction. Springer-Verlag New York, Inc., New York,
NY, USA (1985)
26. Reisig, W.: Elements of distributed algorithms: modeling and analysis with Petri
nets. Springer-Verlag New York, Inc., New York, NY, USA (1998)
27. Slater, P.J.: A characterization of soft hypergraphs. Canad. Math. Bull. 21, 335–
337 (1978)
28. Torres, L.M., Wagler, A.: Model reconstruction for discrete deterministic systems.
Electronic Notes of Discrete Mathematics 36, 175–182 (2010)
29. Torres, L.M., Wagler, A.: Encoding the dynamics of deterministic systems. Math-
ematical Methods of Operations Research 73(3), 281–300 (2011)
30. Torres, L.M., Wagler, A.: Analyzing the dynamics of deterministic systems from a
hypergraph theoretical point of view. RAIRO Oper. Research 47, 321–330 (2013)
31. Yakovlev, A., Koelmans, A., Semenov, A., Kinniment, D.: Modelling, analysis and
synthesis of asynchronous control circuits using Petri nets. Integr., VLSI J. 21(3),
143–170 (1996).
Proc. BioPPN 2015, a satellite event of PETRI NETS 2015