Synthesis is automatically producing a process model from specified behavior. If the desired process model is a Petri net, synthesis is tackled by so-called region theory. Region-based synthesis has been extensively explored for cases where the specification language is a transition system, a language or even a partially ordered language. Although the ideas of region-based synthesis are the same for every kind of specification, every type of specification has its own region definition and uses different representations of the set of all regions to synthesize a finite result. Up to this point, state-based and language-based regions are just two different concepts. In this paper, we introduce a new region definition we call Petri net regions and reason that every state-based and every language-based region is a Petri net region as well. Thus, there is no need to distinguish language-based and state-based regions anymore. With the help of Petri net regions every concept from one of the older region definitions can be directly applied to the other. Using Petri net regions, we introduce an implementation of a synthesis algorithm that handles state-based as well as language-based input. Furthermore, this algorithm can synthesize a Petri net from a set of labeled Petri nets.
Complex systems are often modeled by Petri nets [
Looking at the literature, the theory behind Petri net synthesis is called region theory [
2022 Copyright for this paper by its authors.
Today, region theory has two main branches. If the input is state-based, a transition system for
example, we apply the theory of state-based regions [
This workshop paper presents a glimpse at a new and very intuitive definition we call Petri net
regions. This definition can handle state-based and language-based input at once. We define Petri net
regions for transition systems, languages, partial languages, branching processes, and labeled Petri nets.
We get our new definition simply by lifting the notion of compact tokenflow regions [14] from partial
languages to labeled Petri nets. We lift the notion of state-based regions [
In the following preliminaries, we present compact token flow regions, state-based regions, and Petri nets by instructive examples and refer the reader to the literature for formal definitions. We assume the reader is familiar with the basic concepts of region theory.
To synthesize a Petri net model from a partial language we use the concept of compact tokenflow regions. Every compact tokenflow region is a distribution of tokens on the arcs of the specification and defines a valid place for the synthesis result. That means, every region describes the production, passing, and consumption of tokens between events in the related valid place and thus, adding this place to the synthesis result will generate a net which is still able to execute the specified behavior. Figure 2 depicts three copies of the specification of Figure 1 and three different compact tokenflow regions. The first region defines the valid place p2 of Figure 3. The second region defines the valid place p3. The third region defines the valid place p5.
A compact tokenflow based synthesis algorithm defines an ILP, so that every solution of the ILP is a compact tokenflow region. The solution-space of this ILP is not finite, but the set of all places related to the finite set of integer basis solutions will solve the synthesis problem. A second approach to receive a finite result from the ILP, is to use the concept of wrong continuations. Roughly speaking, the set of wrong continuations is the border between the specified and all other behavior. The set of wrong continuations is finite if the specification is finite as well. Figure 3 depicts the Petri net synthesized from the specification depicted in Figure 1 using compact tokenflow regions, an ILP synthesis algorithm, the concept of wrong continuations and deleting some implicit places as a last step.
Figure 4 depicts a transition system. A transition system is a set of states connected by a set of labeled arcs. Every arc models an event changing the state of the desired Petri net model. Partial languages can model concurrency, but they need to add extra runs whenever there is conflict. Transition systems can model conflict but are not able to model concurrency. Thus, depending on the specific application using one specific specification language can be more adequate than using the other.
To synthesize a Petri net model from a transition system we use the concept of state-based regions. Such region is a multi-set of states so that every pair of equally labeled events has the same gradient. That means, every label is entering, not-crossing, or exiting the region with the same weight. Thus, every event has a constant effect on the marking of the synthesized result. We add the related places to construct a Petri net so that its reachability graph will be isomorphic to the input if such a net exists.
Figure 5 depicts three copies of the specification of Figure 4 and three different state-based regions. The first region is the set of grey states and defines the valid place p2 of Figure 3. The second region is twice the set of black states plus the grey states and defines the valid place p3. The third region is the set of grey states and defines the valid place p5 without the short-loop to X. State-based regions usually do not generate short-loops because transition systems can not specify concurrency.
Most state-based region synthesis algorithms construct a set of so-called minimal regions. They start by a set of minimal candidate regions and repair these regions by adding states until labels have a constant gradient to get a finite Petri net result.
This section introduces Petri net regions. A Petri net region is a marking of a set of labeled Petri nets so that: (I) For every pair of equally labeled transitions, the difference between the sum of tokens in the post-set and the sum of tokens in the pre-set is the same. (II) For every pair of labeled Petri nets, the sum of tokens of all places with an empty preset is the same. We highlight the idea of this definition, by translating the specification of Figure 1 into three labeled Petri nets. Every event becomes a labeled transition, and we add a place to every relation. Figure 6 depicts three copies of the translated result, and we add markings related to the three different compact tokenflow regions of Figure 2.
It is easy to see that there is a one-to-one correspondence between a compact tokenflow region on the set of Hasse diagrams and a Petri net region on the labeled Petri nets. Thus, we propose that the following conjecture holds.
Conjecture 1. Let S be a set of labeled Petri nets and S be equivalent to a partial language L. There is a compact tokenflow region for L defining the valid place p iff there is a Petri net region for S defining the valid place p. We can solve the synthesis problem for partial languages using Petri net regions.
We translate the specification of Figure 4 into a labeled Petri net. Every state becomes a place, and every event becomes a labeled transition. Figure 7 depicts three copies of the translated result, and we add markings related to the three different state-based regions of Figure 5.
Again, it is easy to see that there is a one-to-one correspondence between a state-based region on a transition system and a Petri net region on the labeled Petri net. Thus, we propose that the following conjecture holds as well.
Conjecture 2. Let S be a labeled Petri net and S be equivalent to a transition system L. There is a statebased region for L defining the valid place p iff there is a Petri net region for S defining the valid place p. We can solve the synthesis problem for transition systems using Petri net regions.
Conditions (I) and (II) are very intuitive and easy to check/implement. To get a running synthesis algorithm we can construct Petri net regions by repairing minimal candidate regions or by solving a related ILP. To get a finite result we can use the set of minimal regions, a basis of the ILP, or use the concept of wrong continuations. Petri net regions can handle state-based and language-based input. There is no need to distinguish the two concepts anymore.
Petri net regions are not only unifying previous region definitions but have very interesting application if the input is neither a transition system nor a partial language. Remark, Petri net regions can handle general labeled Petri nets as an input. Note that, we have to be careful with condition (A) of the synthesis problem in this part of the paper because of a missing semantic defining when a net is in the language of another. But we will get the idea ;)
The left part of Figure 10 depicts another labeled Petri net where the state after the occurrence of the loop is not shared. The depicted marking is a minimal Petri net region. Taking the left-hand side as an input, the right-hand side of Figure 10 depicts the synthesis result. This time, the occurrence of X and the occurrence of B is restricted by the additional place.
In this section, we use the new concept of Petri net regions to implement a synthesis algorithm. Using regions, the region definition ensures that the output of every synthesis can execute the input. But if we implement a full-on synthesis algorithm, we must choose (a) the net class of the output, (b) the kind of regions we calculate, and (c) how regions are calculated. For the net class we can calculate nets with or without arc-weights or short-loops. We can calculate regions that are one-bounded and have at most one token in every place. To get a finite result, we can calculate a basis, a set of regions related to wrong continuations, or a set of minimal regions. Furthermore, we can construct regions by simulation, construction, or by implementing an ILP.
In this paper, to highlight the power of Petri net regions, we implement a synthesis algorithm using the new concept. The input to this algorithm is a set of labeled Petri nets. The algorithm uses an ILP to enforce conditions (I) and (II) of the Petri net region definition. Calculating the set of minimal Petri net regions, the algorithm will synthesize a Petri net without short-loops. We can toggle if regions will be one-bound or not. The synthesis algorithm is available at the I ❤ Petri Nets web toolkit (https://www.fernuni-hagen.de/ilovepetrinets/).
Petri net regions unify state-based and language-based region theory. They can handle transition systems, languages, partial languages, branching processes (see Figure 10), and general labeled Petri nets (see Figure 9). We present a synthesis algorithm using Petri net regions in the I ❤ Petri Nets web toolkit. Here, we use an ILP to generate a set of minimal Petri net regions and calculate results without short-loops. Obviously, this workshop paper only presents a first glance at Petri net regions, the formal definitions and proofs must be submitted in future work. [8] van Dongen, B. F.; de Medeiros, A.; Verbeek, H. M. W.; Weijters, A. J. M. M.; van der Aalst, W. M. P.: The ProM Framework: A New Era in Process Mining Tool Support. Petri Nets 2005, LNCS 3536, Springer, 2005, 381–390. [9] Carmona, J.; Cortadella, J.; Kishinevsky, M.: Genet: a Tool for the Synthesis and Mining of Petri
Nets. Application of Concurrency to System Design 2009, 2009, 181–185. [10] Borde, D., Dierkes, S., Ferrari, R., Gieseking, M., Göbel, V., Grunwald, R., von der Linde, B., Lückehe, D., Schlachter, U., Schierholz, C., Schwammberger, M., Spreckels, V.: APT: analysis of Petri nets and labeled transition systems. https://github.com/CvO-Theory/apt. [11] Bergenthum, R.; Desel, J.; Juhas, G.; Lorenz, R.: Synthesis of Petri Nets from Scenarios with
VipTool. Petri Nets 2008, LNCS 5062, Springer, 2008, 388–398. [12] Bernardinello, L.; De Michelis. G.; Petruni, K.; Vigna, S.: On The Synchronic Structure of
Transition Systems. Structures in Concurrency Theory, Springer, 1995, 69–84. [13] Bergenthum, R.; Desel, J.; Lorenz, R.; Mauser, S.: Synthesis of Petri Nets from Finite Partial
Languages. Fundamenta Informaticae 88, IOS Press, 2008, 437–468. [14] Bergenthum, R.: Synthesizing Petri Nets from Hasse Diagrams. Proceedings of Business Process
Management 2017, LNCS 10445, Springer, 2017, 22-39. [15] Bergenthum, R.; Desel, J.; Mauser, S.: Comparison of Different Algorithms to Synthesize a Petri
Net from a Partial Language. ToPNoC III, LNCS 5800, Springer, 2009, 216–243. [16] van der Werf, J.M.E.M.; van Dongen, B.F.; Hurkens, C.A.J.; Serebrenik, A.: Process Discovery Using Integer Linear Programming. Proceedings of PETRI NETS 2008, LNCS 5062, Springer, 2008. [17] Carmona, J.; Cortadella, J.; Kishinevsky, M.: A Region-Based Algorithm for Discovering Petri Nets from Event Logs. Proceedings of BPM 2008. LNCS 5240, Springer, 2008.