Hierarchical Reachability Graph Generation for Petri Nets.
Reachability analysis is the most general approach to the analysis of Petri nets. Due to the well-known problem of state-space explosion, generation of the reachability set and reachability graph with the known approaches often becomes intractable even for moderately sized nets. This paper presents a new method to generate and represent the reachability set and reachability graph of large Petri nets in a compositional and hierarchical way. The representation is related to previously known Kronecker-based representations, and contains the complete information about reachable markings and possible transitions. Consequently, all properties that it is possible for the reachability graph to decide can be decided using the Kronecker representation. The central idea of the new technique is a divide and conquer approach. Based on net-level results, nets are decomposed, and reachability graphs for parts are generated and combined. The whole approach can be realized in a completely automated way and has been integrated in a Petri net-based analysis tool.
Introduction
Petri Nets (PNs) are an established formalism to describe and analyze dynamic systems. Among the
large number of available analysis techniques, the generation of the set of all reachable markings and all
possible transitions is the most general approach, which is theoretically applicable for every bounded net.
The resulting graph is denoted as the reachability graph (RG) or occurrence graph. The set of reachable
markings is denoted as the reachability set (RS). Reachable markings of the PN build the vertices of
the graph and transitions describe the edges. Edges may be labeled with the corresponding transition
identifier from the PN description. The RG contains the full information about the dynamic behavior
of the PN and can be easily analyzed to gain results about the functional behavior as required for the
verification of system properties. RGs are generated by an algorithm computing all successor markings
for discovered markings, starting with the initial marking of the net. This approach is conceptually simple
and is integrated in most software tools developed for the analysis of PNs. In practice, unfortunately, the
size of RGs often grows exponentially with the size of the PN in terms of places and tokens. Hence RG
generation is usable only for relatively small nets, much smaller than most practically relevant examples
are.
Consequently, a large number of approaches has been published to increase the size of RGs which can
be handled. A straightforward idea is to increase the available computing power and memory to increase
the size of RGs. This is done by using powerful parallel or distributed computer architectures. Examples
for this approach can be found in [1, 9] describing implementations on various parallel architectures and
[14, 25], where workstation clusters are used for RG generation. These approaches describe RG exploration
for Generalized Stochastic Petri Nets (GSPNs), however, they apply for RG exploration of PNs
as well. The general problem of parallel/distributed state space generation is still, that an exponentially
growing problem is attacked by increasing the available resources at most linearly. Additionally, the
problem of an efficient parallelization of RG generation arises. Efficient realization of the RG generation
algorithm in a distributed way is non-trivial since the different distributed tasks are dependent and require
synchronization introducing additional overhead. In particular, the speedup that can be reached by
a parallel implementation is model dependent which makes the problem of an efficient general purpose
realization of parallel RG generation even harder.
An alternative to handle large RGs is to reduce their size without loosing relevant information. This
idea can be exploited at two different levels. First, the net can be simplified by reducing the number
of places and transitions. The corresponding approaches are denoted as reduction rules, published for
uncolored PNs in [4] and subsequently for colored PNs (CPNs) in [16]. Reduction rules are defined with
respect to the properties of interest. Thus, first properties need to be defined and then reduction rules
which preserve these properties can be introduced, which yields a set of predefined rules for a set of
predefined properties as in [4, 16]. The main drawback of reduction rules is that their applicability is
restricted to relatively specific structures. Consequently, the gain obtained by reduction rules is for most
nets relatively small and reduction rules can most times only be used as an a priori step which does not
solve the problem of large RGs. The second approach to reduce the size of RGs is to perform the reduction
at the level of reachable markings. Such an approach requires a compositional state space generation
such that generation and reduction can be interleaved. Different techniques exploiting this idea exist.
The usual way is to define the complete PN as a collection of interacting components. Usually component
RGs are much smaller than the complete RG. Thus, RGs for the components are generated efficiently
and are reduced according to some reduction rules which preserve relevant properties. Subsequently,
reduced component state spaces are composed. In most approaches in this context, components interact
via synchronized transitions. In [13], an approach for CPNs is introduced where RGs of components
are generated in parallel by considering only local transitions. Additionally, a synchronization graph
describing synchronized transitions is defined. By interleaving local and synchronized transition firing
the complete RG can be generated or properties holding on the complete RG can be proved. Similarly
in [29], complete component RGs are generated first, which are finally combined and reduced such that
important properties like deadlocks or boundedness are preserved. In [34], a compositional analysis
method for place-bordered subnets is presented. It is also based on the interleaving of composition and
behavior preserving reduction. In [23], a different approach for components composed via synchronized
transitions is proposed. The approach introduces a compact representation of the complete RG and
an efficient way to characterize RS. The idea is that the incidence matrix characterizing RG can be
composed via Kronecker operations from incidence matrices of component RGs and RS is a subset of
the cross product of component reachability sets. Knowing RS and the RGs of the components, RS
and RG of the CPN are completely characterized. In [5], an approach for hierarchical RG generation is
proposed for hierarchically structured CPNs. Similar to the previous approach the RG is described using
component RGs by composing incidence matrices via Kronecker operations. The approach requires that
the complete net is structured in an appropriate way. The disadvantage of all these methods for efficient
RG generation is that the component structure has to be defined by the modeler and all methods are very
sensitive for the component structure. Techniques which reduce the size of RG by behavior preserving
reduction depend on the required results. If relatively detailed results are required, most reduction fail
or have only a small effect on the size of RG.
Other methods for efficient RG computation include the stubborn set method [35], which eliminates
unnecessary interleavings from RG during generation, and the exploitation of symmetries to reduce RG
[10, 22]. In both methods some additional computation is necessary during RG generation and the CPN
has to observe several structural conditions that the methods can be used in an efficient way (i.e., to
exploit symmetries, the CPN has to contain symmetric parts, otherwise the reduction has no effect). The
idea of symmetry exploitation combined with a compact representation of RG by composing component
RGs is described in [17] for quantitative analysis. Techniques based on ordered binary decision diagrams
(OBDDs) rely on symmetries as well, in [30] Pastor et. al. describe OBDD-algorithms mainly for 1-
bounded PNs.
Apart from techniques to characterize the complete or reduced RG in an efficient and compact way,
several approaches to derive results without generating RS and RG exist. Usually these approaches yield
only partial results in the sense that we can not formally prove results, we can only disprove some by
finding failure states. These techniques include simulation and invariant analysis [22].
In this paper, we introduce an approach which is related to the work presented in [23] and [5]. RS and
RG are handled in a compositional way, which allows the representation and generation of large RSs/RGs.
In contrast to other known methods performing compositional analysis, our approach represents the
complete RG. Behavior preserving reduction is not applied. Consequently, arbitrary properties can be
be checked on the resulting RG. However, it is also possible to combine the approach with behavior
preserving reduction, although this is not considered in this paper. The proposed technique can be
completely automated for a large class of PNs including all PNs which are covered by P-invariants. We
present the approach here for uncolored PNs to simplify notation. Keeping in mind that every CPN with
finite color sets can be unfolded to a uncolored PN [22], it obvious that the approach can be applied for
a large class of CPNs too.
The structure of the paper is as follows. In Sect. 2, the PN class is defined, reachability and invariant
analysis are introduced. Sect 3 describes the definition of regions which divide a PN into subnets. In Sect.
4 an abstraction operator is described which allows us to abstract from details in the net description to
reduce the size of RS. Afterwards, Sect. 5, introduces a hierarchical and compositional representation of
RS and RG. Then, different analysis approaches are proposed which exploit the hierarchical representation
of RS and RG. Sect. 7 contains a non-trivial example to clarify the advantages of the new approach
compared to conventional RG generation.
Basic Definitions and Known Results
We assume that the reader is familiar with PNs and the related basic concepts. For details about these
fundamentals we refer to [21, 22, 28].
net is a 5 tuple
is a finite and non-empty set of places,
is a finite and non-empty set of transitions
are the backward and forward incidence functions, and
IN is the initial marking.
The initial marking is a special case of a marking marking M can be interpreted as
an integer (row) vector which includes per place p one element which describes the number of tokens on
place p.
gives the set of input places for a transition t, and
gives the set of output places. Analogously we define
The notion can directly be extended to sets. In the sequel we consider connected nets, i.e. each place,
transition has at least one incoming and one outgoing arc. Transition t 2 T is enabled in marking M ,
transition enabled in M can fire, changing the marking of any p 2 P
to marking M 0 This will be indicated by M [t?M 0 , M [t? denotes that
t is enabled in M and M [? describes the set of enabled transitions in M . Considering firing sequences
yields to the definition of the language
which is the set of all reachable markings for PN . The reachability graph RG(PN) contains
nodes for every M 2 RS(PN) and an arc necessary, arcs can
be labeled with the corresponding transition and/or a transition rate as for stochastic Petri nets (SPNs).
SPNs [27] extend the above class slightly by the association of exponentially distributed firing times with
transitions. We define a function is the set of non-negative numbers.
W (t; M) is the rate of an exponential distribution associated with transition t in marking M . We assume
that W (t; M) ? 0:0 if t is enabled in M . The RG of a SPN results from the RG of the corresponding PN
by adding transition rates to the edges. RS is identical in both cases. SPNs can be used for performance
analysis by analyzing the continuous time Markov chain described by the SPN [27].
The incidence matrix C is a matrix which contains for each place p 2 P a row and for each transition
a column such that C(p; It can be used to define net-level properties of a
net PN .
covered by positive
-invariants, if for each place
A vector y covered by positive T -invariants, if
for each transition t 2 T a T -invariant y - 0 with y(t) ? 0 exists.
An algorithm for computation of invariants is given in [26], although its time complexity is exponential
for a worst case, usually invariant computation is much easier than generation of RS and RG. Incidence
matrix and invariants ensure certain properties, however they do not completely characterize RS. The
following theorem summarizes some classical results.
Theorem 1 For a PN with a set of P -invariants X and a set of T -invariants Y the following results
hold.
ffl If marking M 0 is reachable from marking M , then an integer vector z exists such that M
M+Cz T . This implies that for every M 2 RS(PN) an integer vector z M with
exists.
ffl If x; x Analogously for Y .
ffl For each reachable marking M the relation Mx has to hold for all x 2 X.
ffl If PN is covered by positive P -invariants, then it is bounded.
ffl If PN is bounded and live, then it is covered by positive T -invariants.
Proof: Proofs can be found in standard books on PNs. ffi
Although invariants offer some insight in the dynamic behavior of the modeled system, they are most
times not sufficient to obtain the required results. Thus, RS and RG have to be generated for a detailed
analysis. Usually, first RS is generated and the arcs of RG are computed in a second step. The following
algorithm computes RS for a PN , it terminates if RS contains a finite number of markings 1 .
generate RS (PN)
while (U 6= ;) do
remove M from U ;
for all t 2 M [? do
od
od
Set U contains markings for which successors have not been generated, whereas RS contains all
generated markings. For U a simple data structure like a queue or stack is sufficient since elements
only have to be added and removed. For RS a data structure allowing an efficient membership test is
necessary. Consequently, RS can be realized using an appropriate hash function or a tree like structure
allowing a membership test with an effort logarithmic in the number of elements. The problem with
hashing are possible collisions. It is usually very hard to avoid collisions for general PNs. Therefore,
most software tools use binary trees for the generation of RS.
We briefly analyze the effort required for the generation of RG, when a binary tree is used to store
RS. Let n be the number of markings in RS and let n \Delta d the number of arcs in RG. Hence the mean
slightly extended version catches infinite RS, see coverability graph construction in PN literature.
number of successors per marking is d. The time required for the generation of RS is in the order of
d
which is approximately d \Delta n \Delta log 2 (n). Additionally, memory limitations have
to be taken into account. Even if more sophisticated data structures are used for RS, the number of
markings which can be generated on a standard workstation lies between 150; 000 and 1; 500; 000. For
PNs including a large number of places, the value can be much smaller. In case of certain symmetries,
ordered binary decision diagrams (OBDDs) are able to handle extremely large sizes of RS and RG (see
[8] among others). Pastor et al [30] describe how OBDD-techniques can be applied for PNs. However,
the use of OBDDs requires the existence of symmetries to yield a compact representation.
After RS has been generated, the arcs in RG are generated in a second step. RG can be represented
by a n \Theta n incidence matrix Q. If transition identities and rates are not relevant, Q can be stored as a
Boolean matrix. Otherwise Q has to include the required information.
Autonomous Regions in PNS
In this section, we define parts of a PN which will be latter substituted by a less detailed representation
in an abstraction operation. These parts, which are denoted as regions, have a place border at the input
and a transition output border. This is different from other hierarchical constructs in the PN area [22],
where places or transitions are refined. However, the definition is natural from a behaviorally oriented
point of view (see also [11]), because a region describes a part acting for its own. Communication is
performed by receiving tokens from the environment (place bordered input) and sending tokens to the
environment (transition bordered output).
of a set of transitions of
r
r are the corresponding functions of PN
restricted to P r and T r , respectively. PN r defines a region iff the input bags of transitions in T r and
in T are disjoint, i.e., P r . For a region PN r , the set of output transitions T out
consists of all t 2 T r such that I
Analogously the set of input transition is
T in
A region describes an autonomous part of a PN, which will be used to define a hierarchical structure.
A region is minimal if it contains no region as a proper subset 2 . The concept is illustrated by the following
example, which will serve as a running example to accomplish the line of argumentation.
Example 1 We consider a producer/consumer model where a producer A successively fills two buffers B1
and B2. Fig. 1 shows the corresponding PN, where places fp1; p2; p3g describe the state of the producer.
Places fp5; p7g are buffer places, whose capacity is limited by places fp4; p6g. Buffer B2 is always filled
with two items/tokens at once, while B1 obtains single tokens. The model contains two consumers of
equal behavior. A consumer non-deterministically takes tokens from each buffer, but the first buffer is
only considered if two consumers are willing to consume. Places fp8; p9; p10g give the state of both
consumers. The model is clearly artificial and just intended to illustrate our concepts. Minimal regions
in this model are shown in Fig. 1 by shaded polygons.
Proposition 1 For a PN with regions N r1 ; N
1. minimal regions are disjoint, i.e. if N r1 , N r2 are minimal and N r1 6= N r2 then P
2. minimal regions define a partition, i.e. for each exactly one minimal region
ri with ri ),
3. regions are closed under union, i.e. if N r1 , N r2 are regions then T r1 [T r2 defines a subnet N r which
is a region.
Minimal regions coincide with the equivalence relation of the conflict relation [33].
p3
p6
Producer A Buffer B1 Consumer C22Buffer B2

Figure

1: Producer/Consumer Model and its partition into minimal regions
Proof. Straightforward for nets, where each place has at least one outgoing arc. If this is not the case,
one need to define an additional region, which consists of places with empty set of output transitions.
Minimal regions can be generated using the simple algorithm shown below.
while UT 6= ; do
remove t 0 from UT ;
while do
remove t with fflt " fflT i 6= ; from UT ;
od
od
Once the algorithm terminated, sets T i contains transitions which are used to define regions according
to Def. 3 (i.e., (fflT i
4 Generation of Abstract Views
Let PN be a Petri net. We want to enhance information associated to a place by the following kind of
vector:
Definition 4 A p-vector v p for a place p 2 P is a vector v p 2 ZZ n+m with index
Entries in v p are referenced by v p (x) for x
obtain lower index values.
An aggregation function AG : ZZ n+m \ThetaIN n \Gamma! IN for p-vectors and markings is defined as AG(v
A linear combination LC : ZZ n+m \Theta ZZ n+m \Theta T \Gamma! ZZ n+m of p-vectors v a , v b is defined for a t 2 T ,
lcm(jv a (t)j; jv b (t)j)=jv a (t)j and c
lcm gives the least common multiple of two integers and gcd of an integer vector is the greatest common
divisor of the elements. Note that v c
We inductively define extended nets which result from a sequence of net transformations based on
linear combinations:
be a sequence of transitions of a PN , and ffl denote the empty sequence. An
extended net is a tuple (N inductively defined as follows: (N is an extended net where
Let for better readability be an abbreviation for the resulting
new vectors of a linear combination w.r.t. transition t, and Used = fv a
A s g denote the vectors used to generate New for an extended net (N s
st st ; A st ) is an extended net if (N s is an extended net, s 2 (Tnftg)   and
st
st
st
st
st
s
I
st
I
s
st
Note that c a ; c b - 0 by construction.
We additionally distinguish ordinary places P ord
those generated in the extension sequence
denoted by P agg
s .
The definition separates available vectors A s from the total set of vectors V s in order to ensure that
vectors are used in at most one step of a sequence s. This restriction is made in order to focus on those
linear combinations which are relevant in the following. The net transformation basically mimicks the
computation of P-invariants according to [26]. (N s contains all transitions t 2 T
exactly once describes an extended net where each P -invariant is realized by a place p 2 P agg . For
an aggregated place p representing a P -invariant, the marking is constant (i.e., I
all We can interpret the marking of an aggregated place as a macro marking which includes
an abstract view of the detailed marking. Since the complete net does not exchange tokens with the
environment, macro markings representing P-invariants are invariant. However, if sequence s contains
only a subset of transitions, then the marking of an aggregated place represents possibly only a macro
marking for a subset of places belonging to a P -invariant. In this case, the marking of the aggregated
place changes whenever tokens are added to or removed from the partial P-invariant it represents. Since
the net transformation follows the computation of P-invariants, the effort is limited to the effort for
computing P-invariants. Often the effort is much smaller, since only a subset of transitions is used in s.
Example 2 Before we go into further details we come back on our running example: it contains P-
invariants (described as formal sums):
and a T-invariant (2 Fig. 2 shows the extended net for sequence
are hatched and arcs are dotted to indicate the differences from N ffl . The minimal
regions which are connected via t1, t6, and t7 have been merged; shaded polygons denote the new and
larger regions in N s . p-vectors and corresponding linear combinations are given in the tabular below:
p3
p6

Figure

2: Extended net
Note that the definition of extended net defines arc weights for new arcs connected to new places as
weighted arcs of the original net. This allows to consider bidirectional arcs (self-loops) appropriately, as
the arcs connected to places p12 and p13 in Fig. 2 illustrate.
A place represents a set of places in P ord , and
gives an
aggregated marking for the marking of this set. Aggregating information is the crucial point in deducing
a hierarchy. Before we describe a way to split an extended net into a high level net and a set of low level
nets to obtain the desired hierarchy, we formalize the aggregation and subsequently consider reachability
and language invariance of the net extension.
Proof. We consider an induction over transition sequences s, initially all
trivially fulfill the lemma
and P agg
;. For the induction step we consider a st which results from v
where v a ; v b 2 New at step s (the case p 2 P s is trivial in N st since for these places M 0 , I \Gamma and
I+ remain unchanged). We further consider an induction over firing sequences oe, initially M 0
holds by definition. For the induction step, we consider M where the
induction assumption ensures
we have to show M 0
after extending oe by a transition -.
according to the definition of successor marking and extended net. By induction assumption
such that we can replace M(p) in the equation above. Observe that I \Gamma ,I remain invariant for z 2 P ffl ,
such that we obtain:
st
st (z; -))
ut
The way in which places are added to a net in an extension sequence, ensures that the reachability
set and the language remain the same.
Lemma 2 For all s 2 T   for which an extended net (N s
Proof. by induction over sequences s, initially trivially fulfilled. For the induction step we start
with the special case directly implies equality. This case can occur e.g. if A
or if
6 9v a For the general case we give a proof by contradiction:
case
st [oe ? M st but oe not possible in PN s . Hence 9t 0 2 oe which is not enabled in PN s . i.e.
there are less tokens in a place p 2 P s . Contradiction to definition of extended nets, because M 0 ; I
changes only with respect to new places.
case
but oe not possible in PN st . Hence 9t 0 2 oe which is not enabled in PN st . i.e.
there are less tokens in a place st nP s . According to Lemma 1,
st
z;t and obviously for each z 2
z;t , we obtain a contradiction.
In summary equality holds. Equivalence of languages follows by the same line of argumentation. ut
A direct consequence of Lemma 2 is that invariants remain valid, T-invariants due to language equivalence
and P-invariants due to additivity of invariants, cf. Theorem 1. Furthermore we can decide for
places like p13 in our example, where I transitions t, whether a given initial
marking M 0 (p13) ensures that a transition is dead due to M 0 or whether the place
can safely by omitted since M(p13) - I \Gamma (p13; t) for all M 2 RS. If the former is the case, it is clear that
the net is not live.
So far we have described a way to add places to a net without changing its reachability set or
language. The notion of an extended net is only a formal prop to introduce a hierarchical net; it simplifies
argumentation why a hierarchical net indeed includes the reachability set or language of its N ffl . The key
issue for a hierarchy is abstraction: at a higher level the state of a subsystem must be represented in less
detail than at a lower level. We use aggregated places to obtain an aggregated state representation and
the notion of subsystem is build on the concept of region.
Let R(N ffl ) denote the set of minimal regions w.r.t. to an extended net When we extend
this net for a transition t 2 T out
r of a region N r 2 R(N ffl ), then the new places connect N r with regions
that contain tffl. Consequently we merge all these regions with N r , which yields a new region N 0
r according
to Prop. 1. Since we start from a partition into regions, the resulting set of regions is a partition again,
but this partition is less fine. t becomes internal in N 0
r , because fflt [
r , and new places give an
aggregated description of the internal behavior of N 0
r w.r.t. transition t. Following this procedure over a
sequence s of transitions yields (N s partition into regions, where some regions have internal
transitions and aggregated places. In this situation a decomposition of an extended net into a high level
net using the aggregated description and a set of low level nets resulting from regions with an internal
behavior gives the two-level hierarchy we aim for.
More formally, a high level net for a given extended net (N s results from a projection with
respect to A s .
be an extended net, its corresponding high level net
and I are the corresponding projections of I \Gamma , I
Example 3 Fig. 3 shows the high level net for the extended net of our running example in Fig. 2.2p4
p6
t5222

Figure

3: High level net for
Proof. uses previous lemma about equality for N ffl and N s , and that HN is deduced by omitting places
(releases enabling conditions thus increases RS) and by omitting transitions, which are isolated (since
all elements in the pre- and postset of such transitions are used in linear combinations and thus not
contained in A s anymore). Isolated transitions have no effect on RS. ut
P-invariants of HN are linear combinations of P-invariants of N ffl , hence if N ffl is covered by P-invariants,
so is HN . Consequently, we can guarantee finiteness of RS(HN) if N ffl is covered by P-invariants.
Lemma 3 states that the HN indeed considers a more abstract net, such that the detailed net can
only behave in a way which is consistent with this abstraction/aggregation. If a region in the extended
net contains all places of the set Used for a transition t, it shows an internal behavior, which allows to
define a non-trivial isolated low-level net:
Definition 7 A low level net for a region r in an extended net (N s
with respect to N ffl ).
I
I
I L+
I H+ (p)(t) if
I
If LN and the corresponding region r H in HN do not differ in their transitions, LN is trivial and
can be neglected. Otherwise LN is non-trivial.
Observe that both, HN and LNs do only pick aggregated places from A s , elements in V s nA s are neglected,
because their information is sufficiently represented by the linear combinations they contributed to.
A LN for a region r and its HN share places transitions T out
r . These common net
elements form an interface for the HN to communicate with the LN in an asynchronous manner. The
HN puts tokens via transitions t 2 T in
sends signals to the LN - and experiences output
behavior through firing of t 2 T out
r . The notion of hierarchy is justified, since the HN abstracts from the
details inside the LN, tokens on P describe a so-called macro marking of the LN, and T out
r
represent the aggregated behaviour of the LN. However an LN can be merged with the HN to observe
the detailed behavior. Formally we describe this as an extended LN (EN) as
are defined analogously. An EN is an ordinary
PN, with RS(EN) and L(EN) defined as before. The relationship between HN and LN is not symmetric,
because the HN has an aggregated description of the LN by P
r , but not vice versa.
As seen from the LN, a HN provides an environment, with whom the LN interacts in an asynchronous
manner, but the LN lacks the aggregated description of the HN behavior. Hence the reachability of a
LN cannot be seen independently of a HN, such that the reachability set RS(LN) of the LN for a given
environment HN needs the notion of EN and results from the projection of RS(EN)jLN . In the following
section we will use these concepts to give a hierarchical/compositional representation of RS(N) based on
RS(HN) and RS(i)j i for each LN i.
Example 4 Figs. 4,5 show the extended low level nets for the two non-trivial low level nets - indicated
by shaded polygons - of our running example. They result from the producer part, where transition t1
becomes internal, and from the consumer part, where transitions t6 and t7 become internal. For the
consumer region, only p13 becomes part of A t1t6t7 because v12 has been used for its construction. The
region with transition t3 has no internal transition.
Obviously selection of s has a massive impact on the resulting hierarchical net description. Consideration
of "optimal" sequences is subject to further investigations. At this state we can only formulate
goals and rules of thumb to follow:
1. it is clear, that a non-trivial LN results from merging adjacent regions, i.e. if for N s with regions
in s, then all t
should become element
of s.
p6
t722
Figure

4: Low level net and extended low level net for the consumer region
p3
p3
p6
t522
Figure

5: Low level net and extended low level net for the producer region
2. deriving a hierarchy is a divide and conquer strategy, so a sequence should yield a set of non-trivial
LNs, such that complexity is equally distributed over this set. This means that only those regions
are merged, whose result will not cover a majority of the net.
3. aggregated places introduce overhead, especially building all linear combinations can impose an
unacceptable increase of net elements. This is the reason for an exponential worst case time
complexity of invariant computation. In our case we have the freedom to select transitions and
to consider only a subset of transitions. Hence those transitions t are preferred where
w.r.t. N s is relatively small.
In our implementation of the proposed approach, we have integrated these heuristic rules to generate
appropriate transition sequences. First experiences with several examples (e.g., the example presented
in Sect. 7) are very encouraging. The program automatically chooses a sequence of transitions which
partions complex nets into non-trivial parts and a non-trivial HPN.
Hierarchical Representations of RS and RG
Dividing PN into HN and LNs allows us to generate and represent RS(PN) and RG(PN) in a space and
time efficient way. For notational convenience we assume that PN is decomposed into one HN and J LNs,
which are consecutively numbered 1 through J . Furthermore we assume in the sequel that all reachability
sets for the HN and the extended LNs are finite. Consequently, reachability sets are isomorphic to finite
sets of consecutive integers. Thus let x corresponds to the x-th
marking in RS(HN ), and we use x and M x interchangeably. We can represent RG(HN) by a nH \Theta nH
any two
markings in RG(HN) at most one transition exists. If more than one transition between M x and M y
exists, describes a list of transition indexes. We use for generality the notation t 2 Q H (x; y)
for all t that fulfill M x
The reachability set RS(j) of a LN j depends on the environment given by HN. Hence, we consider
the EN e that corresponds to j and define RS(j) as a projection of RS(e) on the places of j. Since any
LN j and the HN share some places as a projection of RS(j) onto places
from . Markings from g RS(j) are macro markings and allow to partition RS(j). Macro markings
are useful for RS(j) generation since full details of an HN are irrelevant at the LN level, one can redefine
transitions of T in
, such that their firing is marking dependent with respect to RS(HN)j P j "P h ' g
RS(j).
So EN is only a formal prop to obtain a clear notion of RS(j), in practice however, computation of
RS(j) can be performed more efficiently by using only macro marking dependent transitions of T in
since
transitions local to HN are ignored. The resulting set RS(j) might contain markings which are not in
RS(PN ), but these can be eliminated in a subsequent step, cf. Sect. 6.
Let g
and denote by RS(j; ~ x) with ~ x
1g the set of markings from
which belong to marking ~
x in g RS(j). Markings from a set RS(j; ~ x) are indistinguishable in the HN,
i.e., the marking of the places from is the same. Since reachability sets are assumed to be finite,
each set RS(j; ~ x) can be represented by a set of integers 1g. A marking M x 2 RS(HN)
uniquely determines the macro markings for all LNs. We denote by x j the macro marking of LN j
belonging to marking x and obtain M x
Markings of PN s can be characterized using J +1-dimensional integer vectors
Jg. xH describes a marking from RS(HN) and
a marking from RS(j; x j
H describes the macro marking of LNj when the marking of HN
equals xH . This implies M xH j P H "P . Since the previous relation holds, each integer vector
of the previously introduced form determines a marking of the extended net. We define a hierarchically
generated reachability set
Observe that the number of markings in RS H (PN s ) equals
Y
Lemma 4 The hierarchically generated reachability set and the reachability set are related as follows.
Proof. The previous lemmas imply that RS(PN s )j
Jg, and for each M 2 RS(PN s
By construction of the hierarchically generated reachability set M 2 RS H (PN s )
follows. The second relation follows since
Equation (8) describes a very compact way to represent huge reachability sets by composing a few
smaller sets. Observe that a few reachability sets with some hundred of markings are enough to describe
sets with several millions or billions of markings. To keep the representation compact, it has to be assured
that reachability sets of the LNs are roughly of the same size. Of course, this is hard to assure a priori,
but it is possible to generate regions in a way that they include a similar number of places and transitions
which is often sufficient to yield reachability sets of a similar size for the different regions. However, the
reachability set of the original net is not equal to RS H (PN s ), it is only included in the hierarchically
generated reachability set. Before we compute RS(PN s ) as part of RS H (PN s ), the reachability graph
is represented in a compact form similarly to the compact representation of the reachability set.
First of all, we define the effect of transitions locally for LNs. Two different classes of transitions have
to be distinguished with respect to LN j.
H the set of local transitions in LN j.
j the set of transitions, which describe the communication between LN j and HN.
The effect of transitions at marking level is defined using Boolean matrices. As usual we assume
that multiplication of Boolean values is defined as Boolean and and summation as Boolean or. Thus let
t [~x; ~ y] be a n j (~x) \Theta n j (~y) matrix describing transitions in the reachability graph of LN j due to firing
transition t. Q
transition t is enabled in marking x 2 RS j [~x] and firing of t yields
successor marking y 2 RS j [~y]. All remaining elements in the matrices are 0. Since transitions t 2 LT j
do not modify the marking of the HN, Q
y and t 2 LT j . Furthermore, we define for
y and 0 n j (~x);n j (~y) otherwise. I n is a n \Theta n matrix with 1 at
the diagonal and 0 elsewhere. 0 n;m is a n \Theta m matrix with all elements equal to 0. The reason for this
definition is that a transition
does not modify the marking of LN j and cannot be disabled
by LN j. This is exactly described by matrices I and 0. Define for
If q j
enabled by LN j in marking x. For the HN we define q H
In all other cases q H
The matrices describe the effect of transitions with respect to the HN or a single LN. The next step
is to consider the effect of a transition with respect to the global net. Transition t is enabled in marking
Y
It is straightforward to prove this enabling condition. Since q j
enabling depends only on the marking of parts where the transition belongs to. A transition
is enabled if it is enabled in all parts simultaneously. In a similar way we can characterize transitions
between markings. Transition t is enabled in marking its firing yields successor
marking (y H ; y
Y
This relation allows us to characterize the reachability graph completely. To do this in a more elegant
way, we define Kronecker operations for matrices.
Definition 8 The Kronecker product
A\Omega B of a nA \Theta mA matrix A and a nB \Theta mB matrix B is defined
as a nAnB \Theta mAmB matrix
The Kronecker sum A \Phi B is defined for square matrices only as
A\Omega I nB \Thetan I nA \Thetan
The definition of Kronecker sums/products does not include the data type of the matrix elements.
Indeed all kinds of algebraic rings can be used. In particular we consider here Boolean or real values.
Since the Kronecker product is associative we can define a generalization for J matrices A j of dimension
O
Y
I l j
O
O
I
In the same way the Kronecker sum can be defined for n
as
I l j
O
O
I
Observe that C is a matrix with
columns. If we consider the number of
non-zero elements in C in terms of the number of non-zero element in A j and denote the number of
non-zero elements in a matrix A as nz(A), then we obtain
Y
Kronecker sums and product are a very compact way to represent huge matrices. Implicitly Kronecker
operations realize a linearization of a J dimensional number. Row indices of matrix C or D are computed
from the row indices of the matrices A j using the relation
Y
where x is the row index in C or D, x j is the row index in A j and n j is the number of rows of A j . In
the same way column indices are computed from the relation
Y
y is the column index in C or D, y j is the column index in A j and m j is the number of columns of A j .
These representations are denoted as mixed radix number representations. Obviously x (y) determines
all x j (y j ) and vice versa. For complementary information about Kronecker operations and mixed radix
number schemes we refer to [15], considering an example with
is recommended.
Mixed radix numbering schemes can as well be applied to number markings in RS H (PN s ). However,
we use a two level scheme, where the first number describes the HN marking and the second number is
computed from the numbers of LN markings. Thus marking
where
Y
Using this numbering scheme, RG H (PN s ) can be represented using Kronecker products of Boolean
matrices. We define Q H
t as the incidence matrix of the reachability graph considering only transition t.
Using the two level marking number, Q H
t has a block structure with n 2
H block matrices.
includes all transitions between markings belonging to HN marking x and markings
belonging to HN marking y due to transition t in the net. Each submatrix can be represented as a
Kronecker product of LN matrices.
O
This form describes a very compact representation of a huge matrix.
Assume that Q t is a Boolean matrix describing transition t at RS(PN ), then
after appropriate ordering of markings (i.e., markings from RG(PN) " RG H (PN) are followed by markings
from RG H (PN) n RG(PN )). If
the initial marking is part of RG(PN) " RG H (PN ), the above representation implies that successors of
reachable markings can be computed using matrices Q H
t and, consequently, also reachability analysis can
be performed using these matrices.
The incidence matrix of RG H (PN) can be represented as
For a compact representation, the Kronecker representation is definitely preferable. It can be applied in
various analysis algorithms as shown in the Sect. 6. Local transitions cause a specific matrix pattern of
nonzero elements. Since Q i
t [x; x] equals an identity matrix for t 2 LT j , j 6= i and Q j
y,
I l j
]\Omega I u j (x) if
collecting local transitions in one matrix
l [x
we obtain the following representation for a submatrix of Q H
l [x
does not distinguish between different local transitions of the same LN. If such a distinction
is necessary, transitions which have to be visible can be excluded from the sets LT j . In this way it is
possible to keep all relevant information in the representation of RG H (PN s ).
If we consider SPNs, transitions are enhanced by a transition rate. Thus Q contains real instead of
Boolean values. However, the Kronecker representation of the matrix is very similar. If all transitions
have marking independent transition rates - t , matrix Q H is given by
In this case the elements of Q t are interpreted as real values 1:0 and 0:0, respectively.
Example 5 The running example is rather small so that we can not expect practical gain from representing
RS or RG in a compositional way as proposed in this section. However, even for this simple example
the representation becomes more compact and the example allows us to clarify the general concepts.
The following table summarizes the number of markings in column RS and the number of transitions
in the RG in the corresponding column for the various nets considered here. Obviously the HN has a RG
which is significantly reduced compared to PN .
Marking description Successor markings
no ap1 ap2 p2 p4 p5 p6 p7 tnr no tnr no tnr no
22
26

Table

1: Reachable markings and possible transitions of the HN.
RS RG transitions
PN 254 622
All markings and possible transitions of the HN are shown in Tab. 1. Macro markings with respect to
LN 1 are defined by projection of the HN marking on the places ap1; p4; macro markings for LN 2 are
defined by projection of the HN marking on ap2; p5; p7. In both cases 9 macro markings are generated.
From the extended nets, RS j and the matrices Q j
are computed. For LN 1 a macro marking represents
in the average 2 markings. This small number is not surprising since LN 1 consists internally of two
places connected via single transition, such that macro markings only abstract from the internal place
where tokens reside. For the second LN more internal details are hidden by the aggregated description
used in the HN. Consequently, a macro marking of LN 2 represents in the average 9 detailed markings.
The Kronecker representation requires 195 transitions to represent the complete reachability graph with
622 transitions. Of course, this comparison does not consider overhead to store different matrices in the
Kronecker representation. However, the overhead depends on the number of transitions in [ST i and
the number of LNs. Both quantities are negligible compared to the number of markings if we consider
large nets. The hierarchically generated reachability set RS h includes 270 markings, which means that
markings are unreachable. We consider this point in the subsequent section.
6 Hierarchical Analysis Approaches
We now introduce analysis approaches which rely on the Kronecker representation of RG(PN ). In
particular it is necessary to introduce a method to characterize RS(PN) and not only a superset in form
of RS h (PN s ). The central idea of reachability analysis is that the numbering of markings in RS h (PN s )
is a perfect hash function for markings in RS(PN ). This has first been exploited for efficient reachability
analysis of SGSPNs, a class of generalized SPNs consisting of components synchronized via transitions,
in the work of Kemper [23]. We can use a similar approach here, but do not necessarily rely on it, see e.g.,
[12] as an alternative. Let
the number of markings in RS h when the marking of the
HN is M x . Let r[x] be a Boolean vector of length n(x) which is used to store results of the reachability
analysis. Thus r[x H ](x L marking
after termination that
Formally we use here one Boolean vector per HN marking,
but it is obviously possible to store all these vectors consecutively in a single Boolean vector of appropriate
length. Reachability analysis requires, apart from the vectors r[x] and the different matrices introduced
in the previous section, a set U to store unexplored markings, similar to the set U used in generate RS.
However, now U only has to store integer pairs instead of complete marking vectors.
Let be the number of the initial marking, then r[x 0H ](x 0L ) is initialized with 1, all remaining
vector components are zero. Additionally, U is initialized with the following algorithm
is used to determine reachable markings.
generate structured RS (PN)
while (U 6= ;) do
remove
to J do
for all y j with
l do // compute successor in subnet j
for all y H with Q H do // compute successor in subnet HN
for all j with t 2 T j do
L with
exists then (*)
else
if y L - 0 then
In the step indicated by ( ), the algorithm exploits the fact that firing of transition t always yields
a unique successor marking. Therefore each row of a matrix Q i
t can include at most one element. The
approach can be easily extended for PNs where different successor markings are possible. This situation
occurs in nets where probabilistic output bags for transitions are allowed. Since the algorithm computes
all successor markings of reachable markings, it is straightforward to prove that generate structured RS
generates RS(PN) and terminates when RS(PN) is finite which is the case here, since RS h (PN s ) has
assumed to be finite.
The remaining point is the comparison of generate structured RS and generate RS. As before we
assume that the reachability set contains n markings and in the average d transitions are possible in
each marking. The theoretical time complexity of generate RS is O(nd log 2 n) if insert and member
functions on RS use log 2 n operations. The complexity of generate structured RS is in O(nd), since the
Boolean vectors allow us to test in O(1) whether a marking has been reached before. The reduction by
a logarithmic factor seems to be not too much on a first glance. However, the approach is used for large
reachability sets such that this implies a reduction by at least an order of magnitude. Additionally the
constants behind the asymptotic complexity are much lower for generate structured RS. The reason is
that all operations are performed with simple integer operations, while several operations of generate RS
are time consuming. For example, if a new marking M is found in generate RS; a data structure to
hold M has to be allocated and inserted into the data structure storing the already generated markings.
Since this data structure is usually a tree, pointers have to be modified. In generate structured RS the
same operation only requires to set a bit in vector r. Thus usually we can expect an improvement
of run times which is around two orders of magnitude for large reachability sets. However, to apply
generate structured RS, PN has to be decomposed first and the reachability sets and matrices for the
subnets have to be generated. The complexity of both problems is for large nets much lower than
reachability analysis. This can also be seen in the example presented below.
Apart from time complexity, we also have to compare space complexity. Of course, also the difference
in memory requirements depends on the concrete example. However, if the net has been decomposed
into LNs with roughly identical reachability set sizes and the size of RS h (PN s ) and RN(PN) does
not differ too much (i.e., not by several orders of magnitude), then (8) assures that the size of the
LN/HN reachability sets and matrices is negligible compared with the size of the complete reachability
set and graph. Experiences show that the approach allows us to handle much larger reachability sets. An
additional advantage of generate structured RS is that we make use of secondary memory in a very efficient
way. Since vector r is structured into subvectors and successor markings are computed consecutively for
subvectors, it is possible to preload required subvectors from secondary memory.
After the reachability set has been computed by setting the values in vector r, it can be decided in
O(1) whether a marking is reachable or not. Furthermore, all successor markings for a marking can be
computed from the Kronecker representation for local transitions in a constant time and for others in a
time at most linear in the number of subnets. Since the Kronecker representation includes information
about transitions yielding to successors, even successors reachable by specific transitions can be computed.
Based on these basic steps, standard algorithms for model checking can be applied for the nets.
In a similar way the Kronecker representation can be exploited for the quantitative analysis of SPNs.
The basic step here is to realize the product of a vector with a sum of Kronecker products of matrices.
However, this step is already known in numerical analysis and can be combined with various iterative
numerical analysis techniques [3]. Thus the Kronecker representation allows the analysis of large SPN
models, which cannot be handled using standard means. For further details we refer to the literature
Example 6 The size of the running example is so small that is useless to compare runtimes for reachability
graph generation. Instead we briefly consider unreachable markings appearing in the hierarchical
representation. As already mentioned RS h contains 270 markings, but only 254 of them are reachable.
As an example for unreachable markings we consider markings of the form (0;
the vector includes the number of tokens on the places p1 \Gamma p7. For the places p8; p9; p10, we now consider
possible markings. Obviously all three places are part of a P-invariant such that the sum of tokens on
these places has to equal 2. In the hierarchical generated reachability set all possible distributions of 2
tokens over the places p8; p9; p10 are included. However, reachability analysis shows that only markings
are reachable where place p10 is empty.
The reason for this restriction can be explained by considering the behavior of the net in some more
detail. A token on p10 implies that t5 has fired after t4. But since p6 is empty, t3 fired after t5 and,
since p2 is non-empty t1 and t2 fired also after t5. Now after firing t2 a token resides on p5 which has
to be transferred to p4 by firing t4. However, this means that t4 fired after t5 and p10 has to be empty.
The restriction which assures that p10 has to be empty when the marking of the places p1 \Gamma p7 is as
shown above, is a global restriction which depends on the whole net. So it is not visible in an isolated
part and the above mentioned markings belong to RS h , but reachability analysis shows that they are not
reachable and are not part of RS.
Two other optimizations can be used to improve generate structured RS.
First optimization As noticed in [23] certain unnecessary interleavings due to internal transitions can
be eliminated. The idea is that local transitions in different LNs do not interfere. Thus if t 1 2 LT i
are both enabled in some marking, then the sequences t 1 t 2 and t 2 t 1 are both possible
and yield an identical successor marking. Consequently it is only necessary to consider one sequence.
More general, for a set of local transitions which belong all to different LNs and which
are enabled in some marking, only those transition sequences which are described by a subset of T and
where transitions occur in the order as described in T need to be considered. This reduces the number of
possible sequences from
l
\Delta l! to
l
\Delta . In this way the time complexity of reachability analysis
can be reduced.
Second optimization In [6] an approach is discussed which reduces time and space complexity. The
idea is to reduce a priori the marking sets of LN by combining some markings which are always together
reachable or not. As a simple example consider two markings x; y 2 RS(i) and a pair of transitions
is enabled in x and its firing yields y and t 0 is enabled in y yielding successor marking
x, then x is reachable whenever y is reachable and vice versa. We denote this as identical reachability
of markings. Obviously identical reachability holds for all markings in an irreducible subset of a matrix
l [x; y]. In [6] it is shown that this condition can be further relaxed. However, this extension is beyond the
scope of this paper. Markings which are identically reachable can be aggregated a priori. Aggregation in
this case means that a set of identically reachable markings is substituted by a single aggregate marking
such that all transitions entering or leaving one marking in the subset are substituted by transitions
entering/leaving the aggregate marking and transitions between markings in the subset are substituted
by transitions starting and ending in the aggregate marking. These transformations are easily performed
by adding in the matrices Q i
all rows and columns belonging to markings in the subset to be aggregated.
The size of RS(i) and RG(i) is reduced by this aggregation which implies that the size of RS h (PN s )
and also the effort for reachability analysis are reduced too. After reachability analysis the reachability
of an aggregated marking implies that all markings represented by this aggregated marking are also
reachable and vice versa; if the aggregated marking is not reachable, then the detailed markings are also
not reachable.
Both optimizations depend on the net which is considered. However, for most nets the effort for
reachability analysis can be reduced significantly.
7 An Application Example
jsj reg, total reg, non-tr P agg RS h RS(HN) max RS(j) percent RS(PN)

Table

2: Hierarchical representation for sequence s
The running example we considered so far is only useful to illustrate formal concepts, in order to
demonstrate applicability of our approach we consider the production cell of [24], which has been subject
to modeling and analysis by a variety of tools and which is known to be non-trivial. The production
cell model originates from an existing production cell in an industrial setting, which physically consists
of six components: a elevating rotary table, a rotable robot with two extendable arms, a traveling crane
gen hierarchy gen struct RS
jsj CPU user CPU user
111 2.5 3.0 73.3 74.0
112 2.6 3.0 64.9 65.0

Table

3: Computation characteristics for sequence s
and two conveyor belts. The production cell performs transportation and processing metal plates in a
(cyclic) pipeline. A feeding conveyor belt transports metal plates to the elevating table, the table lifts
plates for the robot, the robot inserts plates into the press and takes them after pressing from the press
onto the second conveyor belt. Originally plates leave the system by the second belt, but in order to have
a closed system, the crane is installed to put plates from the second belt onto the feeding belt, such that
the number of plates within the system is constant. Thanks to the work of Heiner et al. [18, 19] a Petri
net model exists, which considers processing of 5 plates. Refinement is used to organize a model of this
size, however the dynamic behavior of the model is not defined unless all refined subnets are available in
full detail. This kind of hierarchy is very common for modeling purposes, but useless in terms of analysis.
Hence our analysis starts from a flat Place/Transition net with 231 places and 202 transitions 3 . From
[19] it is known that the net is live and 1-bounded. The reachability set contains 1,657,242 markings and
the reachability graph 6,746,379 transitions.
The algorithm to derive a hierarchy starts from a partition into minimal regions and considers a
sequence s, which starts with transitions being internal in minimal regions (which is the case for 74
transitions in our example), subsequently it considers small regions first. Fig. 6 shows how the total
number of regions decreases once the internal regions have been considered. On the other hand, the
number of non-trivial regions increases in an initial phase since the algorithm prefers small regions and
finally decreases when there are no trivial regions left and non-trivial regions are merged. Table 2 indicates
the influence of s on the hierarchical representation of RS, it gives the number of regions (non-trivial and
in total), the number of aggregated places P agg , cardinalities of the hierarchical reachability set RS h , the
reachability set of the high level net RS(HN ), and the maximal number of markings observed among
the low level nets. The quality of the whole construction is shown in column "percent RS(PN )", which
gives the reachable fraction of RS h . Table 3 gives corresponding computation times in seconds for the
computation of the two-level hierarchy and the subsequent computation of the reachability set RS(PN)
contained in RS h (PN ), times are given as CPU time and user (wall clock) time. These times have been
observed on a SPARCstation 4 with 64 MB main memory, 890 MB virtual memory, and 110 MHz CPU.
Obviously computation times are uncritical if the number of aggregated places does not explode.
It is worth mentioning that it takes slightly more than a minute to generate the complete reachability
set and reachability graph and represent them in a very space efficient way. About 6 Megabyte memory
space are necessary to generate and represent RG and RS. These values are excellent compared to conventional
RG generation algorithms. In [18] the same model has been analyzed on a similar workstation
using different PN analysis tools. RG generation with the tool PROD needs about 14 hours (see [18]).
The small runtimes and storage requirements show that much larger systems can be handled with the
approach. We have also analyzed an open version of the production cell for which other tools where not
able to generate RS (see [18]). For this version our method needs about 3 minutes real time to generate
RS with 2,776,936 markings and RG with 13,152,132 arcs.
As already noticed in [19], computation of a generating set of semi-positive P-invariants is difficult
for this net. Our approach is closely related to invariant computation: if we compute an extended net
for a sequence covering all transitions T , we obtain a generating set of P-invariants as well. However this
3 We thank J. Spranger for translating the model into the APNN format [2] used in our implementation.
length of sequence s10305070
regions
non-trivial regions

Figure

Total number of regions, number of non-trivial regions
length of sequence s50150250350450550
places
regions

Figure

7: Number of aggregated places, number of non-trivial regions
extreme is not suitable and we consider only a subset of transitions, in order to remain some activity in
the HN. From a pragmatic point of view the approach allows us to consider those transitions which can
be handled with acceptable computational costs and stop the derivation of a hierarchy if it becomes too
expensive. Fig. 7 clearly indicates that a careful selection of transitions can avoid high computational
costs. However there is a sharp increase after 108 steps, and the hierarchy derivation stops after 113
steps. For a P-invariant computation 202 steps are necessary, hence Fig. 7 also illustrates the difficulties
for invariant computation observed in [19]. According to the results in Table 2, the number of regions
and a limit for the number of aggregated places give suitable parameters to stop the automatic hierarchy
generation where it makes sense.
Conclusions
We have proposed a new approach for the efficient generation and compact representation of reachability
sets and graphs of large PNs. In contrast to other approaches, the technique can be applied to general
nets without definition of a hierarchical structure and without inherent symmetries. The structuring
of the PN into asynchronously interacting regions is done automatically by an algorithm which uses a
basic step related to invariant computation to make a transition internal to a region. The algorithm
considers a sequence of distinct transitions which can be arbitrary in principle. For our implementation
we use some heuristic rules in order to structure a net into regions of approximately the same size. The
algorithm stops once a user given number of regions has been obtained. Usually the number of regions
should not be chosen too large, to avoid a too complex HN. For nets covered by P-invariants termination
is guaranteed, however we cannot ensure termination for general PNs. The problem is that reachability
sets of some part, HN or a LN, can become unbounded, even if the reachability set of the complete net
is bounded. This problem can not occur for nets which are covered by P-invariants.
The non-trivial example considered in this paper illustrates our experience with the algorithm exercised
on a set of examples: the new approach allows the time and space efficient generation and
representation of huge reachability sets and graphs. This is, of course, a step towards the analysis of
complex PNs. Our current research aims at the integration of the algorithms for model-checking with
the Kronecker representation of the reachability graph. First results indicate that this approach allows
to analyze much larger nets than conventional means. Additionally, the Kronecker representation can
be used for the efficient analysis of SPNs using numerical analysis techniques. For an overview of these
techniques we refer to [7].



--R

State space construction and steady state solution of GSPNs on a shared-memory multiprocessor
Abstract Petri net notation
Complexity of Kronecker operations and sparse matrices with applications to the solution of Markov models
Transformation and decomposition of nets
Hierarchical high level
Hierarchical Structuring of Superposed GSPNs
Structured Analysis Approaches for Large Markov Chains
States and Beyond
Parallel state space exploration for GSPN models
On well-formed coloured nets and their symbolic reachability graph
Distributed simulation of
Storage alternatives for large structured state spaces
Modular state space analysis of coloured
Distributed state-space generation of discrete-state stochastic models
IEEE Trans.
A. reduction theory for coloured
Asynchronous composition of high level
Petri net based design and analysis of reactive systems
A case study in developing control software on manufacturing systems
Reachability trees for high-level
Coloured
Coloured
Reachability analysis based on structured representations
Formal development of reactive systems
Analysis of large GSPN models: a distributed solution tool
A simple and fast algorithm to obtain all invariants of a generalized Petri net
Performance analysis using stochastic

Hierarchical reachability graph generation of bounded
Petri net analysis using Boolean manipulation
A comparative study of methods for efficient reachability analysis
The numerical solution of stochastic automata networks
A class of modular and hierarchical cooperating systems
Compositional analysis with place bordered subnets
State of the art report: stubborn sets
--TR
Automatic verification of finite-state concurrent systems using temporal logic specifications
Transformations and decompositions of nets
A reduction theory for coloured nets
The concurrency workbench
Using partial orders for the efficient verification of deadlock freedom and safety properties
A symbolic reachability graph for coloured Petri nets
Colored Petri nets (vol.
Automated parallelization of discrete state-space generation
On generating a hierarchy for GSPN analysis
Structured analysis approaches for large Markov chains
Communication and Concurrency
Distributed Simulation of Petri Nets
Hierarchical Reachability Graph of Bounded Petri Nets for Concurrent-Software Analysis
Structured Solution of Asynchronously Communicating Stochastic Modules
Hierarchical Structuring of Superposed GSPNs
Application and Theory of Petri Nets
On Limits and Possibilities of Automated Protocol Analysis
An analysis of bistate hashing
Saturation
Modular State Space Analysis of Coloured Petri Nets
Parallel State Space Exploration for GSPN Models
A Toolbox for the Analysis of Discrete Event Dynamic Systems
Reachability Analysis Based on Structured Representations
{SC}*ECS
A survey of equivalence notions for net based systems
A Simple and Fast Algorithm to Obtain All Invariants of a Generalized Petri Net
Reliable Hashing without Collosion Detection
Compositional Analysis with Place-Bordered Subnets
Hierarchical High Level Petri Nets for Complex System Analysis
Superposed Generalized Stochastic Petri Nets
Petri Net Analysis Using Boolean Manipulation
Storage Alternatives for Large Structured State Spaces
State Space Construction and Steady--State Solution of GSPNs on a Shared--Memory Multiprocessor
Analysis of large GSPN models

--CTR
Michael Muskulus , Daniela Besozzi , Robert Brijder , Paolo Cazzaniga , Sanne Houweling , Dario Pescini , Grzegorz Rozenberg, Cycles and communicating classes in membrane systems and molecular dynamics, Theoretical Computer Science, v.372 n.2-3, p.242-266, March, 2007
invariant analysis;hierarchical structure;reachability graph;reachability set;petri nets