Assigning Ontological Meaning to Workflow Nets

Pnina Soffer1, Maya Kaner2, and Yair Wand3 
1University of Haifa, Carmel Mountain 31905, Haifa, Israel
2Ort Braude College, Karmiel 21982, Israel
3Sauder School of Business, The University of British Columbia, Vancouver, BC. V6T 1Z2, Canada
spnina@is.haifa.ac.il, kmaya@braude.ac.il, yair.wand@ubc.ca 
Abstract. One of the most common ways to represent organizational domains is the use of business process models. A Workflow-net (WF-net) is an application of Petri Nets (with additional rules) intended to model business process behavior. WF-nets have the advantage of being well-formalized. However, the use of WF-nets to model business processes has some shortcomings. In particular, no rules exist beyond the general constraints of Workflow-nets to guide the mapping of an actual process into a net. Furthermore, the token-based semantics is not anchored in the problem domain. Thus, syntactically correct WF-nets do not necessarily provide meaningful models of how organizations conduct their business processes. Moreover, the processes represented by these nets might not be feasible to execute or might not reach their business goals when executed. We propose a set of rules for mapping the domain in which a process operates into a WF-net. Following the tradition of assigning ontological semantics to conceptual models, we derive the rules by attaching ontological semantics to WF-nets. Specifically, we use the semantics of the Generic Process Model (GPM). The rules can guide the construction of WF-nets which are meaningful in that their nodes and transitions are directly related to the modeled (business) domains. Furthermore, the proposed semantics imposes on the process models constraints that can guide the development of valid process models, namely, models that assure that the process can accomplish its goal when executed.
1  Introduction
Process models are widely used to model how an organization conducts its activities to accomplish its goals. In that sense, process models are a widely used type of conceptual models. Process modeling is a complicated task and, hence, error-prone (e.g., Sadiq and Orlowska, 1997; Mendling, 2007). The syntax of process modeling languages specifies how to compose their constructs (which often have graphical notation) into process models. However, syntactically correct process models are not necessarily meaningful in terms of conveying the way the business conducts its activities. Moreover, a syntactically correct model might not even be feasible to execute, and even if it is, it cannot always be assured to reach its goal, namely, produce its required outcome. Some meaning can be represented in a process model via the semantics of the modeling language used. These semantics are believed to represent some real-world phenomena, and can be defined textually or mathematically. Either representation may have shortcomings. Textual definitions are typically semi-formal or informal (e.g., “An event is something that “happens” during the course of a business process” (Object Management Group, 2006)), and therefore do not provide representations that are sufficiently precise for formal analysis. In contrast, mathematically-based process representations (e.g., Petri nets (Petri, 1962), YAWL (Aalst and Hofstede 2005), Pi Calculus (Milner, Parrow and Walker, 1992)), allow formal analysis and automated verification of models, but their semantics may not be readily associated with the problem domain.
Much effort has been devoted to the formal analysis and verification of process models, leading to methods and tools for analyzing structural properties of process models and for detecting logical problems in them. In particular, Workflow nets (WF-nets) - a special case of Petri nets - have been proposed as tools for modeling the dynamics of processes (Aalst, 1998). A Workflow net is a Petri net which (1) has one input place and one output place; and (2) does not contain dangling transitions or places (namely, transitions that might not fire or places that might not be populated). This is equivalent to the net being strongly connected if the output place is interlinked to the input place via an additional transition (Aalst, 1998). Workflow nets employ a small set of constructs, yet possess an impressive expressive power and can be used to represent precisely the entire set of workflow patterns (Aalst et. al, 2003, Russel et al., 2006).
An extensive body of work exists regarding the mathematical, structural, and behavioral properties of Petri nets, such as free choice, liveness, boundedness and strong connectedness (e.g., Esparza and Silva, 1990; Jensen, 1990; Desel and Esparza, 1995). These properties have been adapted for WF nets, and additional properties (such as soundness, relating to the process dynamics) have been defined (e.g., Aalst, 2000). Furthermore, these properties serve for formalizing and analyzing models in other process modeling languages (such as in EPC (Aalst, 1999) and in general workflow (van Hee et al., 2008). 
The mathematical semantics of Petri nets (and of WF-nets) is based on the dynamics of tokens that propagate through the net. While supporting formal analysis of process dynamics, Petri net token-based models have several disadvantages. First, they provide abstraction of transitions that can occur during the process. However, being abstract, the transitions in a net do not necessarily convey clearly the real world (dynamic) phenomena that occur in the domain in which the process operates. In other words, a transition does not necessarily reflect a change in the domain that has a clear meaning to stakeholders. In particular, no rules exist for mapping of the real world domain (part of an organization or a business) in which the process takes place into a WF-net beyond the general requirements of WF-nets. Hence, such models are not necessarily meaningful to stakeholders and, beyond that, processes represented by WF-nets might not even be feasible to execute in practice or might not be able to accomplish stakeholders’ goals. Second, an important advantage of WF-nets is that they possess several structural or behavioral properties which can be useful in formal analysis. Structural properties relate to the structure of the net, independent of its specific marking and include, in particular, free choice and well-structuredness, (Aalst, 1998)). Behavioral properties are initial marking dependent and include, in particular, soundness, separability and serialisability (Aalst, 1998; van Hee, Sidorova and Voorhoeve, 2008; Salimifard and Wright, 2001)). However, without well-defined domain semantics assigned to places and transitions, the practical meaning of these properties, namely, what they imply about the domain phenomena they stand for, and their implication to process design is unclear.  Finally, the formal analysis and verification of the above properties can be successfully applied to already developed models and identify potential problems in executing these models. However, without a clear mapping of these properties to the process domain, such analysis does not provide guidance to process designers on how to develop valid process models.
In summary, while WF-nets have well-defined formal semantics, this semantics might not necessarily convey the actual business meaning of components of a model. Consequently, the various formally-defined properties of WF-net do not necessarily translate to phenomena that are meaningful to stakeholders. As well, the formal semantics does not provide guidance for constructing useful process models. In short, the use of WF-nets to model business processes might tend to sacrifice the understandability and meaningfulness expected from conceptual models for formality.
We propose that the above disadvantages of WF-nets can be overcome, at least in part, by attaching “real world” meaning to their main constructs – places, transitions, and tokens, and by constraining how actual process domains should be represented using these constructs. To accomplish this objective, we follow a line of research that analyzes conceptual models in general, and process modeling languages and their constructs in particular, using ontological concepts. Ontological models represent beliefs about what exists and might happen in the world. Hence, ontological concepts can be used to convey real-world semantics. Specifically, we use the Generic Process Model (GPM) which provides a process specification semantics based on ontological constructs and is intended as a framework for reasoning about process models in terms of their real-world meaning. GPM was used to define the notion of goals in business processes, to analyze process model validity, and to suggest an interpretation of control flow structures (Soffer and Wand, 2005; Soffer and Wand, 2007; Soffer, Wand and Kaner, 2007).
In this paper we show how the combination of the formal power of WF-nets and the “real world” semantics provided by ontology can lead to better-designed process models. We use GPM concepts to add ontological semantics to WF-nets and to generate necessary conditions for creating semantically meaningful WF-nets. In addition, we propose modeling rules to guide the development of models of processes that reach their goals when executed.
In the following, Section 2 summarizes the main WF-net concepts and motivates our work; Section 3 introduces GPM and its control flow interpretation; Section 4 maps GPM concepts into WF-net constructs; Section 5 analyzes some useful properties of GPM-mapped WF-net; Section 6 presents rules for constructing valid process models; Section 7 demonstrates the application of the proposed rules; Section 8 discusses related work; Section 9 discusses our proposition in a broader context of conceptual modeling, and Section 9 is a conclusion.
2  Petri-nets and Workflow-nets 
This section provides some definitions of Petri-nets in general and Workflow-nets in particular, and their properties which are relevant for our discussion.
A Petri-net is a directed bipartite graph with two node types called places (designated by circles) and transitions (designated by rectangles), connected by arcs. Connections between two nodes of the same type are not allowed.
Definition 1 (Petri net): A Petri-net is a triple (P, T, F): 
-	P is a finite set of places;
-	T is a finite set of transitions (PT = )
-	F(PxT)(TxP) is a set of arcs.
At any time a place contains zero or more tokens (designated as black dots inside the place circle). The state of the net is defined by the distribution of tokens over places. A place p is termed as input of transition t if it has an arc directed from it to t, and an output of t if there is an arc directed to it from t. The notations t, t, p, p indicate the sets of input (preset) and output (postset) places of transition t and the sets of transitions of which p is an output and input place, respectively.
The state of a Petri net changes through its execution according to the following firing rules:
(1)	A transition t is enabled iff each input place p of t contains at least one token.
(2)	An enabled transition may fire. If transition t fires, then t consumes one token from each input place p of t and produces one token for each output place p of t. 
A firing sequence is a sequence of transitions that occur where each one generates tokens in its output places so the next transition is enabled. Given two states M1 and Mn, M1Mn denotes that Mn is reachable from M1 through a firing sequence .
The syntax of Petri nets is almost free of restrictions, except for the alternating nature of places and transitions. Hence, the fact that a Petri net is syntactically correct does not imply that it represents some real system. Nevertheless, the mathematical basis of Petri nets enabled precise definitions of structural properties which may imply the behavior of systems that can be modeled through Petri nets. Some of these properties, relevant for our discussion, are defined below.
Definition 2 (bounded): A Petri net is bounded iff for each place p there is a natural number n such that for every reachable state the number of tokens in p is less than n. 
The meaning of boundedness is there cannot be a transition or a loop in the net that will cause the number of tokens in a place to increase indefinitely.
Definition 3 (free choice): A Petri net is a free choice Petri net iff, for every two transitions t1 and t2, t1t2 implies t1=t2.
Free choice means that if p is an input to t then every input place of t is also an input to every transition for which p is an input. Under such conditions all transitions that share p as input place are enabled when p is populated, and can fire independently of the state of the rest of the net (hence the name “free choice”). In a Petri net which is not free choice cases of combined concurrency and conflict arise. Such cases are hard to analyze and considered inappropriate (Aalst, 2000; Aalst, 2003). Most of the mathematically-based properties identified and analyzed with respect to Petri nets relate to free-choice Petri nets only.
Petri nets can be used for representing various kinds of systems. A specific form of Petri net, specifically intended for workflow modeling is a Workflow net (WF net, Aalst, 1998). 
Definition 4 (Workflow net): A Petri net (P, T, F) is a Workflow net (WF-net) iff:
(i)	There is one source place iP such that i=.
(ii)	There is one sink place oP such that o=.
(iii)	Every node xPT is on a path from i to o.
An activation of a WF-net is interpreted as representing the life-cycle of a single workflow case in isolation (Aalst, 1998). For a given case it has an initial state following the generation of a case, where only one token exists in place i, and a final state o after which the case is deleted. 
Several properties of interest are defined for WF-nets. Of particular importance is soundness which is considered desirable and for which WF-nets are expected to be verified.
Definition 5 (sound): A procedure modeled by a WF-net PN= (P, T, F) is sound iff:
(i)	For every state M reachable from state i, there exists a firing sequence leading from state M to state o.
(ii)	o is the only state reachable from state i with at least one token in place o.
(iii)	There are no dead transitions in (PN, i).
Soundness means that the modeled procedure will terminate eventually, and properly (i.e. no further transition will occur after the sink has been populated). It can be verified in polynomial time for free-choice WF-nets (Aalst, 2000).
Another property, closely related to soundness, is well-structuredness. In a well-structured WF-net a splitting point and a merging point which correspond to each other are of the same type, namely, a split at a place (transition) corresponds to a merge at a place (transition). More specifically, in a well-structured WF-net, when a place is an input to more than one transition – a choice occurs into two sequences. The two possible sequences must merge on a place that can be populated by transitions from either sequence. When a transition populates several places, this can cause parallel sequences that eventually lead to one transition, where the parallel sequences synchronize.
Soundness as well as other properties are useful for verifying a predictable behavior of the represented process (or workflow), and in particular, its ability to complete its execution. According to these properties, the prediction of behavior strictly relies on the net structure, regardless of the domain assumed to be represented. The implicit assumption is that the WF-net truthfully represents the domain under consideration. However, since the token semantics is detached from the real-world business semantics of the domain, this assumption is not straightforward, as shown in the example in Figure 1.
The WF net in Figure 1(a) is syntactically correct. However, when executed, only one of the transitions that follow the place Order registered can be fired, either Prepare product or Arrange shipment. As a result, the transition Deliver order will not be able to fire, and the net will be in a deadlock situation. This problem can be identified based on the token dynamics of the net: only one token can reach either the Product ready or the Shipment arranged places, while Deliver order requires tokens in both places. Note that this net is not sound, not free-choice, and not well-structured. Considering the (syntactically correct) WF net of Figure 1(b) in terms of token dynamics, no problem can be identified. The net is free choice, well structured, and sound. However, in terms of the domain semantics, it is not possible to concurrently manufacture a product and package it. Apparently, token-based semantics, which is not anchored in real-world concepts, cannot deal with this kind of modeling problems. Our aim in this work is to propose an alternative semantic interpretation of WF-nets, which will be able to account for both the identification and the prevention of both types of problems. To this end, we anchor the proposed semantics in the Generic Process Model (GPM), whose basis is a generic ontology, consisting of basic real world concepts, as presented in the following section.

Register order

Shipment needed

Order registered

Arrange shipment

Prepare product

Product ready

Shipment arranged

Deliver order

Order delivered

 Order received

 Order received

Issue Production order

Manufacturing is possible

Production order issued

Manufacture product

Package product

Product packaged

Product manufactured

Deliver order

Order delivered

(a)   						       (b)
Figure 1: WF-net examples
3  The Generic Process Model (GPM)
This section presents the Generic Process Model (GPM), which is the basis for our proposed WF-net semantics. We use the GPM for this purpose for two reasons. First, a WF-net can be considered as depicting state changes that can or must occur. GPM formalizes an abstract view of a process in terms of state transitions that occur rather than using common notions such as activities and control flows. Second, the GPM affords an integrated view of a goal as part of the process definition. Since incorporation of goals can support validity analysis of process models, we will use it to motivate or interpret desired characteristics of WF-nets.
The focus of GPM analysis is a domain, which is a part of the world consisting of interacting things. We describe the behavior of the domain using concepts from Bunge’s ontology (Bunge, 1977; Bunge, 1979) as adapted to information systems and to the evaluation of conceptual modeling (Wand and Weber, 1993; Wand and Weber, 1995; Weber, 2004) and to process modeling (Soffer and Wand, 2005; Soffer and Wand, 2007). A domain is represented by a set of state variables, each representing a property of the domain and its value at a moment in time. These properties are either inherited - properties of things in the domain, or emergent – properties that reflect interactions of things in the domain. The state of the domain can change either due to actions within the domain (internal events) or by stimuli from outside the domain (external events). An unstable state is a state that must change due to actions in the domain (manifested as internal events). A stable state is a state that only changes due to actions of the environment on the domain (manifested as external events). Internal events are governed by transformation (transition) laws that define the allowed (and sometimes necessary) state transitions (the internal events). A successful process is a sequence of state changes in the domain which can result from either internal transitions in the domain or external events to the domain. When the state is unstable, the law defines the transition that will change it (to an unstable or to a stable state). When the domain is stable, an external event must exist to change it. Thus the process is manifested as a sequence of states of the domain. The process ends on a stable state, which is in the set of goal states (simply – goal). A specific sequence of states leading to a goal state is termed a process path.
Since we view a process in terms of state changes, we start by formalizing these concepts as follows:
Definition 6 (domain model, state variables): A domain model is a set of state functions D={f1(t)…fn(t)}. The value of fk(t) at a given time is termed a state variable, denoted xk.
The set of state variables for domain D is denoted by XD={xk; kI={1…n}}. The state of the domain at a given time is s(D)=<x1,…xn> (or simply s). The set of possible states of the domain D is denoted by S(D).
For example, assume the domain refers to production in an industrial company. The domain comprises various workstations. The state variables can describe, at a given time, for each machine, the product it processes and the status of unprocessed and processed components near each machine.
Domain dynamics is described in terms of state changes. We describe state changes that can occur due to actions within the domain in terms of transformation law:
Definition 7 (transformation law): A transformation law on D is a mapping LD:S(D)→S(D)
For example, the law can specify that when a machine is not busy and there is a supply of unprocessed components available, the machine will change state to “busy, working on the specific components”. For some states there are no possible actions that can change them. Such states are mapped into themselves and are termed stable states. 
Definition 8 (stable / unstable state): A domain will be said to be in a stable state if LD(s)=s and in an unstable state if LD(s)≠s.
For example, when a machine is idle, and there is no available supply of components to be processed by it, the machine is in a stable state.
The above definitions do not limit the mapping defined by the transition law. In particular, it is possible that one state will map into several states. For example, if several types of components are available for an idle machine, the next state might involve working on any of these types. However, when designing business processes, we are usually interested in predictable behavior. Hence we define:
Definition 9 (well-defined law): A law will be said to be well-defined iff it is a function.  
Considering the machine example, assume the rule is that the machine will always begin working on the items that take the shortest amount of time. Assuming there are always differences in time to process different items, if the state information includes the number of items of each type available to be processed, then the transition law from “idle” to “busy” is a function.
Often, several domain states can be considered equivalent. For example, for no charge on transactions a bank account might only need to be above a minimal balance. Hence, the transformation law can be represented as a mapping between sets of states. Such a set can sometimes be specified by a predicate on values of the state variables - C(s) (as in the bank example above). In particular, often the process goal is a set of stable states, specified by a predicate that manifests business objectives to be fulfilled by the process. 
The notion of the transformation law (LD(s)) is of particular importance to our analysis. Since the transformation law defines the state changes that can or must occur, it determines the possible sequences of states – namely process paths. In this sense, the task of the process designer can be described as implementing a transformation law so that the process can accomplish its goal. 
In GPM, a process in an abstract fashion is a sequence of states in a domain. However, in practice, processes typically comprise actions that impact only part of the domain at a time. For example, in a production process, different machines might process different components at different times. Each machine can be considered as an independently operating part of the domain. We formalize this view by considering a domain as comprising sub-domains, each represented by a subset of the domain state variables. The partitioning of a domain to sub-domains provides the bridge between the (abstract) view of a process in terms of state changes of a domain and the actual implementation of the process in terms of active elements of the domain. Identification of such elements provides the business meaning of the state transitions that occur in a process. In our analysis of WF-nets, partitioning to sub-domains will be key to attaching business meaning to places and transitions. Hence, we explore the relationships between the behavior of the domain and its sub-domains.
When the state of the domain changes the state of at least one sub-domain must change. We say that the domain behavior is projected on its sub-domains. State changes that occur in a sub-domain when the domain changes state, are termed the projections of the state changes of the domain. Since the possible changes are defined in terms of the domain (transformation) law, the projections of these changes on a sub-domain can be viewed as defining a transformation law on the sub-domain. We term the latter the projection of the domain law on the sub-domain. In the following, definitions 10-13 formalize the concept of projection.
Definition 10 (sub-domain): A sub-domain is part of the domain described by a subset of the set of domain state variables XD.
Notation: A sub-domain D1 of D is described in terms of XD1XD; XD1={xk ; k I1I}. The state of D1 is s(D1)=<xk1,…xk|I1|>, kjI1 and kj≠kl for j≠l.
For example, in a job shop production environment, the state variables describing each machine can be viewed as describing a sub-domain of the full work in process (which comprises the states of all machines, workers, and products in processing).
We note that there might be many ways to partition a given domain into sub-domains. Different partitions can reflect different views of the process domain, and not all partitions will be meaningful to process stakeholders.
Definition 11 (state projection): Let the state of D be s=<x1…xn>. The projection of s on the sub-domain D1 is s/D1=<y1…y|I1|> where yk=xI1(k), k=1,…| I1|
In the job shop example, a possible sub-domain is a cluster of machines and workers. The projection of the job-shop state on this sub-domain is the part of the work-in process that occurs in the cluster.
It is possible that several domain states will map on the same state of the sub-domain. When considering this state of the sub-domain, it might appear as transforming in different ways, depending on the state of the whole domain. To see this point, consider the job shop example. Different states of the overall work-in-process might appear the same within the specific cluster. However as the work in process changes differently (e.g., different components completed), the cluster state might change in different ways (different components will arrive for processing).
It follows, that to understand the actual change of state in a sub-domain, we need to know the state of the whole domain. We therefore define:
Definition 12 (projecting set): Let v be a state of D1. The projecting set of v in D is the set of states of D that project into v in D1:  S(v;D)={sS(D) | s/D1=v}
In the example above, other clusters might change state, while a given cluster will stay in the same state. Thus, many work-in-process states will be mapped into one state in the cluster.
As noted above, key to our analysis is the view of domain state changes in terms of changes in sub-domains. The former are determined by the domain law. Consider a sub-domain state. There might be several domain states projecting to this sub-domain state. Each of these domain states might map differently. Each mapped state will have a projection in the sub-domain. Observing the sub-domain, it might appear that the original state can change in different ways. However, all are determined by the domain law. We define the effect of the domain law (L) on a sub-domain, D1 as follows.
Definition 13 (law projection): Let vS(D1) and let  s(v;D) be the projecting set of v in D. The law projection of LD on D1 (denoted L/D1) for v is defined by the mapping LD/D1:S(D1)→S(D1) such that LD/D1 (v)={L(s)/D1 | ss(v;D)}.
In words, each state, v, of the sub-domain is mapped into the union of projections of all states in the projecting set of v. For example, let the states in D projecting to state v of D1 be s1 and s2. Assume LD(sk)=s’k, k=1,2. Then, LD/D1 (v)={s1’,s2’}. In the job shop case, a worker can be in a state “assigned to task A” while other activities are being performed in the job shop. However, when each of these activities changes or is completed, the worker might be reassigned differently. 
In general, the effect of the projected law will appear as unpredictable changes in the state of the sub-domain. It is possible, however, that the projected behavior of the whole domain on a sub-domain creates a well-defined function in the sub-domain. In other words, a given unstable state of the sub-domain will always map in the same way, independent of the state of the whole domain, and hence independent of the states of other sub-domains. In the job shop case this would mean that the worker will be always reassigned the same way after performing a given task (independent of what else is happening in the workshop). We will then say that the sub-domain behaves independently or that it is independent. Partitioning of the domain into independently-behaving sub-domains is often a consequence of different actors acting in the domain. These actors can be people, departments, machines, computers and combinations of those. Hence, such partitioning is of special interest. It is possible that independent behavior of a sub-domain occurs for only a subset of domain states. For example, workers are assigned in the same way only when there are slack production resources. Formally, we define:
Definition 14 (independent sub-domain): A sub-domain D1 of D will be called an independently behaving (or independent) in a given state (of the sub-domain) iff the law projection on D1 is a function for this state. 
Corollary: For an independent sub-domain the law projection is a function that depends only on state variables of the sub-domain.
Consider now a process as a set of states the domain traverses. Assume that for these states a set of sub-domains behaves so that each sub-domain, is independent and ends on a stable state (of the sub-domain). When a sub-domain reaches stability, there are three possibilities. First, the whole domain might reach a (stable) goal state. Second, the whole domain reaches a stable state not in the goal. An external event must then occur for the process to continue. Third, some other independent sub-domains will become unstable and will begin transforming. Thus, a sequence of state changes occurs, some as a result of well-defined transformations within sub-domains and some as a result of external events. This sequence comprises a process. Note that the decomposition of a domain into sub-domains is not usually a partition, in that sub-domains would usually share state variables.
To demonstrate, assume a sales department comprises two units – one that deals with order taking and one responsible for  order fulfilling. An example for a process is that after order taking completes and the first sub-domain becomes stable, the fulfillment unit becomes unstable and starts planning how to fulfill the order.
 Process models usually include split and merge points, which reflect either concurrency or choice between possible alternative paths. We now interpret these in GPM terms. First, it is possible that a set of states arrived at can be partitioned so the next transformation is defined differently for each subset of states. Such partitioning might occur because the law becomes “sensitive” to a certain state variable. Consider, for example, a process where a standard product is manufactured, and then packaged according to each customer's requirements. Manufacturing does not depend on the customer (even when the customer is known). When manufacturing is completed, customer information will determine a choice between packaging actions (such approach is termed postponement). This situation is an exclusive choice (an XOR split) between two paths of the process. The different actions may lead to states which are again equivalent for determining the next action (the law will not distinguish between different packaging options), for example, transferring the products to finished goods inventory. This is the point where the paths merge. For example, the merge point in the fulfillment process will occur when the product is packaged and is ready for shipment.
Formally, a choice between two process paths can be defined as follows:
Definition 15 (exclusive choice): Ssp is an exclusive choice splitting point iff there exist sets of states S1,S2,..Sn such that SiSsp, SjSk=, and s,t sSi tSj L(s)L(t)  ij, i,j=1…n.
In words, all states within a subset of states transform in the same way, and states from different subsets transform into different states.
The corresponding form of a merge (sometimes termed simple merge) is when a single set of states is reachable by law from different sets of states.
Definition 16 (simple merge): Let S1, S2, and Sme be non empty sets of states, such that S1S2=, SkSme=; sk states such that skSk. Sme is a simple merge iff L(sk)Sme. (k=1,2).
In words, a simple merge occurs when two different paths can reach states that map into the same given set of states. Note that this definition assumes the merge set is given. In particular, it enables defining a merge for any union of states that can be mapped into by the law from S1 and S2. However, we will be interested only in such unions where the states in Sme have some common characteristics. Specifically, this is the case when they are considered equivalent for the purpose of determining the next state changes in the domain. This means they are similar with respect to the domain law.  For instance, in the product packaging example – the different packaging options end in states which are the same with respect to the next activity – shipping. 
Also related to splitting and merging is concurrency. Since one domain cannot have concurrent transformations, concurrency should relate to transformations in different sub-domains. Concurrency means that each sub-domain proceeds independently through a sequence of (projected) states. All combinations of the projected states of the different sub-domains are possible (in principle). These combinations can be viewed as a “swarm” of states the decomposed domain undergoes. For example, in a domain comprising two machines that work in parallel, each going through three steps – setup, production, cleaning, the combined state can have different combinations. However, for such situations to occur a condition should be satisfied:
Lemma 1: Two sub-domains can transform concurrently only if they are independent. 
Proof: Assume that two sub-domains are not independent. Then the transitions in one can depend on the state of the other. In this case, only some combinations of states of each sub-domain are possible.  
It follows that a split leading to concurrency must be related to a decomposition of the domain into independently behaving sub-domains. In such a split, for the process to continue, at least one sub-domain must be unstable with respect to its (projected) law. If all these sub-domains are in unstable states for all states in the split, then this is a parallel split. Otherwise, several possibilities exist, depending on the number of the unstable sub-domains (see Soffer et. al. 2007). In particular, if exactly one sub-domain can be in an unstable state, then, based on Definition 15, this is an exclusive choice. Formally, a parallel split is defined as follows: 
Definition 17 (parallel split): Ssp is a parallel split iff there exist at least two sub-domains such that for every state in Ssp each sub-domain is independent and is in an unstable state.
For example, in the production and fulfillment process discussed above, once products are ready, the process domain can be decomposed into two independent sub-domains: one where shipment is arranged for some products, and one where the other products are transferred into the warehouse. These two sub-domains are independent and in an unstable state, thus they operate concurrently. 
A decomposable domain may entail different types of merge points (see Soffer, Wand and Kaner, 2007). In particular, in a simple merge the completion of action of any sub-domain causes the process to proceed. In Petri Nets all input places for a transition have to be populated for the transition to “fire”, thus, of particular interest is a synchronizing merge, where process continuation requires that all active sub-domains complete their tasks prior to continuation of the process. Consider a set of states in a merge point. These states should be unstable to enable the process to continue. They should be reachable from the split and hence for each sub-domain, the projected state at the merge should be reachable from the projected state at the split. In a synchronizing merge, each sub-domain becomes stable at the merge (“waiting” for the other sub-domains). Once all sub-domains reach the merge, the process can continue. For this, another sub-domain must become unstable. We term this the continuation sub-domain. This sub-domain must share some state variables with each of the synchronizing sub-domains. Otherwise, the state of the sub-domain will not affect the continuation sub-domain and synchronization will not occur. Formally:
Definition 18 (synchronizing merge): Let DkD, k=1...n be independent sub-domains operating concurrently following a split point Ssp.  Sme is a synchronizing merge iff a sub-domain DC exists, which shares state variables with each of the sub-domains (DCDk≠ k) such that:
 s Sme: s/DC is unstable  k=1...n ukS(Dk), uk=s/Dk, uk stable & vkS(Dk), vk≠s/Dk.
The definition implies three things: (1) Each sub-domain has at least two states. One state is stable (uk) and projected to from a domain state where the continuation sub-domain DC is unstable.  The other state (vk) does not project onto an unstable state of DC (otherwise, there will be no path in the sub-domain). (2) For each sub-domain, there is at least one uk that projects onto the same unstable state of DC as all other sub-domains. (3) There are no other unstable states of the DC projected into by a state in the merge set (Sme).The stability in (1) assures each sub-domain will “wait” for the others. Point (3) assures that DC will only begin changing when all sub-domains have “arrived” at their “appropriate” states (uk). Together, these conditions assure synchronization.
To demonstrate the definition, consider a process where several parts need to be manufactured for a product to be assembled. When the need to assemble the product arises, the domain enters a split state where each part is made by a separate production cell. When each cell has completed making the part, the cell “rests”. Only when all cells completed (hence each is at rest – in a stable state), the domain enters a state where the product can be assembled. Beginning of production for each cell is the projection of the split state onto an unstable state of the cell. End of production is the projection of the continuation state onto a stable state of the cell.
Finally, the explicit representation of process goal in GPM can be used to support the analysis of process models for goal reachability. A process whose design ensures its goal will always be achieved under a certain set of events external to the domain is termed valid (Soffer and Wand, 2007) with respect to this set of events.  
4 GPM as a semantic basis for WF-nets
In this section we propose a GPM-based semantics to WF- nets. For convenience, we first present an informal overview of the GPM interpretation of WF-net constructs and then provide formal definitions and an in-depth discussion of the consequences of this semantics. The main principles underlying the added semantics are:
(1)	A place in the net represents a set of states of a sub-domain. This sub-domain is represented by a sub-set of state variables of the domain in which the process operates). Below, we will refer to “input” or “output” sub-domains when a place is an input to or an output of a transition, respectively.
(2)	A populated place indicates that the sub-domain corresponding to the place is in one of the states represented by the place. If the place can have more than one token, this indicates the set of states represented by it can be partitioned.
(3)	 A transition indicates a change of state of a sub-domain. Since the transition depends on the input places and modifies the output places, the sub-domain in which it occurs must overlap (in terms of state variables) with the sub-domains of the input and output places.
We note that this semantics allows for different places on the net to represent states of the same sub-domain. Also, the sub-domain can be the whole domain. This is the case for the source and the sink nodes of a WF-net. We present an informal description of the semantics of the basic building blocks of WF-nets in Table 1.
Table 1: GPM interpretation of WF-Net constructs and basic building blocks (the word “state” in the table refers to a state of a sub-domain)
WF-net construct / building block	GPM interpretation	
Place p	A set of states of a sub-domain (the projection of a set of states over a sub-domain)	
A populated place 	A sub-domain is in one of the states represented by the place	
Transition t	A possible transformation in a sub-domain	
Arc	An arc into a transition means the transformation law uses the values of the state variables of the input sub-domains.
An arc into a place means the transformation can change the states of the output sub-domains.	

i

Initial place i	The initial set of states I 	

o

o

Final place o	The goal set (of domain states) G 	

p2

p1

t1

Sequence	t1 is a transformation in a sub-domain, from a set of states p1 into a set of states p2 	

p1

p2

P2

p1

p1

t1

A parallel split	t1 is a transformation after which the domain becomes decomposable, where p1 and p2 are state projections over different sub-domains. Note, if the domain is not decomposable, the places would be shown as one place (sequence).	

p2

p1

t1

A synchronizing 

P2

merge	t1 is a transformation whose initial set of states is p1p2   
p1 and p2 refer to different sub-domains.	

t1

p1

p1

An exclusive 

t2

choice	p1 is a set of states in which one of two sub-domain transformations is possible. 
These transformations can be in the same sub-domain or in different sub-domains.	

t1

p1

p1

A simple 

t2

merge	p1 is a set of states reachable by two transformations, t1 and t2, separately	

We focus our discussion on WF-nets, since these have a distinct termination place, which may correspond to GPM’s goal concept. Nevertheless, most of the discussion is applicable to Petri nets in general. As shown in Table 1, every basic WF-net construct and building block can be assigned a GPM-based interpretation. We do not attempt to do a reverse mapping, namely interpret GPM terms using WF-nets, since GPM addresses issues beyond the control flow of the process, which are not in the scope of WF-nets. However, considering the proposed control flow mapping, this interpretation assumes certain domain semantics assigned to the places and transitions of a WF-net. This semantics poses requirements which do not exist in the WF-net syntax. If these requirements are not met, a WF-net cannot be transformed into a meaningful GPM specification. It can thus be claimed that the expressive power of WF-nets exceeds the expressive power of GPM with respect to control flow, in that the former enables structures not possible in the latter. Alternatively, it can be argued that WF-net syntax, being anchored in mathematical semantics of graphical symbols, allows structures which are not necessarily possible in reality. 
We now proceed to formally define the proposed GPM-based semantics for WF-net and resulting restrictions on the models. We define the following class of WF-nets which are consistent with the GPM-based semantics.
Definition 19 (well-mapped domain representation): A WF-net is a well-mapped domain representation iff it can be mapped to a GPM specification. Specifically:
1.	Each place can be associated with a set of states of a sub-domain.
2.	Each transition can be associated with a change of state of a sub-domain.
3.	The initial place represents unstable states of the domain.
4.	The sink place represents the goal states of a process in the domain.
While a well-mapped domain representation WF-net (well-mapped WF-net in short) can be understood using the traditional token-based semantics, its underlying semantics is based on GPM. This semantics imposes some restrictions on the model. We will now elaborate this semantics and its resulting restrictions. We start by assigning a meaning to WF-net places.
Definition 20 (populated place): A populated place in a well mapped WF-net represents a set of states of a sub-domain. Let pkP, then DkD such that pk is active iff Dk is in a given set of states SpkS(D)/Dk. 
As an example, a place where an order has arrived represents a set of states of the sub-domain of order management. We denote the sub-domain by Dpk, its state variables as Xpk and the set of states indicated by the place by Spk. To indicate that Dk is in a state in Spk we can use a place predicate - C(Xpk) defined by: C(Xpk)=’True’  s/ Dk Spk. Thus, pk is active iff C(Xpk) is TRUE. Sometimes C(Xpk) can be defined by a function on some state variables of Dk. For example, the sub-domain Dk might represent the state of a machine. The predicate will be true iff the machine is idle.
As indicated, C(Xpk)=TRUE is equivalent to the existence tokens in pk. Consider what having more than one token might mean. From the input view of the place, adding a token to an already populated place means a change in the state of the sub-domain without a change in the value of its predicate (which was already TRUE). From the output perspective, an active place pk implies that the sub-domain Dk is in a state which is necessary (and sufficient if it is the only input) for a transition to fire. After the transition has fired, if there was more than one token, the input place is still populated. This means that the domain Dk, although having changed its state, is still in one of the states defining the place. Hence, this implies the set of states represented by pk can be partitioned.  One possible way to represent such partitioning is to decompose the predicate C(Xpk) to components, each true iff is Dk is in one of the subsets of states. Clearly, C(Xpk ) must be a conjunction of these components. 
If these sub-predicates are based on state variables expressions, then the place predicate is of the form <Expression OR Expression OR…>. As an example, consider an order delivery process, where the customer orders several items which can be manufactured concurrently, and each item is delivered once it is ready. This can be modeled by a single place prior to delivery, whose predicate would be ((Item A=ready) OR (Item B=ready) OR…).  The arrival of each item can be modeled as adding a token to that place, triggering the delivery transition. The transition can fire again for each item.
Using the above interpretation, the maximal number of tokens in a place is the number of atomic expressions related by an OR in the predicate that defines it. If the place predicate cannot be decomposed, then the maximal number of tokens allowed in that place is 1. Also, it is clear that an infinite partitioning of the states associated with pk is impractical. Hence, the number of token should be bounded. Hence:
Lemma 2: A well mapped WF-net is bounded.
The dynamics of a well mapped WF-net is established by the transitions, each transforming the state of a defined sub-domain. According to the Petri net semantics, transitions are enabled by the existence of tokens in their input places, and they pass a token to each of their output places. According to the GPM view, a transition occurs in a sub-domain once it arrives at an unstable state and hence must transform it to a new state. If the process is to continue, the transition must cause a new sub-domain to reach a new state (which would be unstable unless it is the sink state). For this to happen, the affected sub-domain should share state variables with the one that has transformed. The above means that both input sub-domains and output sub-domains must share state variables with the transition domain. We formalize all this as follows:
Definition 21 (transition sub-domains): Let tT be a transition, t its input places, and t its output places. The input sub-domain of t is Dt defined by Xt ={Xp, pt} , the output sub-domain of t is Dt defined by Xt ={Xp, pt}. The transformed sub-domain Dt is the sub-domain changed by t, and its set of state variables is denoted Xt..
For example, a delivery transition has the customer order and the availability of goods in its input places; it transforms the order status and the inventory level state variables, so their new values should be reflected in the output place(s). 
Definitions 19, 20 and 21 address structural properties of the net. However, the net should also represent the dynamics of the domain. Hence, based on the definition of a well-mapped WF-net, and on the GPM dynamics, the following can be formulated (equivalent to the Petri net firing rules).
Dynamics rule: Let t be a transition in a well mapped WF-net. 
a.	Dt is in an unstable state iff C(Xpk)=TRUE pkt.
b.	“Firing” t results in C(Xpk)=TRUE pkt.
We have now defined the rules about structure and dynamics of a well-mapped WF-net. Each element in such a net has a well defined domain meaning. However, when modeling processes in GPM various relationships exist between transition laws and the definitions of sub-domains. In particular, a sub-domain is “meaningful” if the domain law projects on it a well-defined (i.e. a function) transition law. As well, the process goal must be a set of stable states. It follows, that when places and transitions in a WF-net are assigned domain meaning, certain constraints on the net must hold, so domain relationships will be correctly represented. This leads to four requirements on well-mapped WF-nets. These requirements are intended to assure four conditions:
1.	Each transition operates in, and only in, the sub-domains associated with its input and output places.
2.	Each transition represents a well defined law.
3.	For any concurrent decomposition – the sub-domains are independent.
4.	The sink place of the net represents only stable states.
Below we formulate these requirements in terms of four necessary conditions.
Necessary condition 1 (transition domain structure): tT:
a.	The input, output, and transformed sub-domains satisfy XtXt and XtXt.
b.	Let X*= Xt Xt and let Xdiff X* be the set of state variables whose values in the input places and in the output places are different. Xdiff cannot be empty, because otherwise t will have no effect.  Then Xdiff Xt.
For example, assume a transition represents manufacturing a product. Its input places indicate when raw materials and resources are available and a finished product is required. This is an unstable state. The transition should “use” only state variables from its inputs (e.g., raw materials and resources), transform their state (e.g., raw material is consumed, finished product is manufactured), so its output places (e.g., where the product is ready for packaging) become active. It is not possible for an unrelated state variable (e.g., delivery arrangement) to change its state through this transition. Note, the output places of this transition may still represent an unstable state, in case they serve as input places of other transitions (e.g. packaging and shipping the ready product).
For a transition to act within a sub-domain, the sub-domain must be independent (i.e. its law is a function) for the set of states represented by the transition’s input places. Hence, we formalize the following condition:
Necessary condition 2 (transition independence): tT, t represents a set of states in which Dt is independent. 
The dynamic rule and the transition independence condition have certain important implications. First, according to Necessary condition 2, if a place is the only input place of a transition, then it represents a set of states in which its sub-domain is independent. It follows that a place cannot be the sole input place of a transition and part of a set of input places of another one at the same time. If this could happen then it would be possible the other place will fire first, and the present transition will be unpredictable. This structure is often used in WF-nets and is sometimes associated with situations which are hard to analyze. As an example, consider two workers performing tasks in parallelEach worker, when completing the task, checks on the other worker and decides whether to wait for the other to finish so they can have coffee together, or continue independently with a new task. Such a situation is sometimes modeled as a decision between a transition of “having coffee” synchronizing the two sub-domains and a transition of “next task” with just one input place (worker finished previous task). However, this decision is not made independently of the other sub-domain – “next task” will be chosen if the other worker is still busy and not otherwise. Second, consider a set of places which are inputs for a transition. The transition can fire only when all places are populated. When this happens, at least one of the sub-domains must change its state (see the dynamic rule above). Hence, the input places cannot behave as independent sub-domains.
We now turn to address the notion of path. As opposed to the path definition in Petri nets, which relates to any sequence of connected elements, we relate to domain paths (D-paths), which correspond to selected sequences of states of the domain. GPM defines a path as a set of states the domain goes through, via a sequence of transitions, determined by the law and by external events (see Section 2). Petri nets (and specifically, WF-nets) do not explicitly address external events, assuming they will occur as expected (Aalst, 1998). The state of a WF-net (considering the process as operating over one domain) is defined as the distribution (“marking”) of tokens at a given moment in time. According to our view, we may look at the entire process domain or at any of its sub-domains. In the WF-net the state of a given (sub)domain is reflected by the predicate values of its places. Considering a sub-domain Da, its state is the distribution of active places (pj, C(Xpj)=TRUE) at a given moment in all the places pj that satisfy Xpj  XDa. We denote the state of sub-domain Da by MDa. The above indicates that as the network undergoes transitions, the sub-domain will be changing states. We formalize this as follows:
Definition 22:  Let Da be a sub-domain in a WF-net. A domain path (abbreviated to D-path) of Da is a sequence of states of D <MD1, MD2,…MDK>, such that a sequence of transitions <t1, t2,…tk-1> exists that satisfies MDi MDi+1… MDk, for 1 ≤ i ≤ k-1. 
For clarity, we hereafter relate to domain paths as D-paths and to “ordinary” (or “traditional”) Petri net paths simply as paths.

p1

p2

p3

p4

p5

p6

p7

Fig. 2: D-paths example
D-paths are demonstrated with respect to the WF-net in Fig. 2, which includes four D-paths: (1) p1 p6 p7, (2) p1 p2+p3 p4+p5 p7, (3) p1 p2+p3 p2+p5 p4+p5 p7, and (4) p1 p2+p3 p3+p4 p4+p5 p7. These are not equivalent to the three “ordinary” paths of the net. When examining the four D-paths, it is clear that three of them (D-paths 2, 3, and 4) relate to different orderings in which the concurrent transitions can be performed, while D-path 1 specifies a different way for reaching p7. This can be formalized in the following definition:
Definition 23 (distinct D-path): Let Ac be the set of places that become active in D-path C. Two D-paths C1 and C2 are termed distinct iff Ac1⊈Ac2 and Ac2⊈Ac1.
Fig. 2 demonstrates a significant difference between D-paths and “ordinary” paths. In concurrent threads that follow parallel splits (for example, the transition to p2 and p3 in Fig. 1) the domain is decomposed into independently transforming sub-domains. In the graphical Petri net representation the sequence of elements in each sub-domain forms a different “path”. Considering the sequences of states the (entire) domain may traverse in such situation, the number of D-paths is combinatorial. However, none of them is distinct with respect to the others (see for example three combinations of the sequences beginning on p2 and p3). It follows, that distinct D-paths of the same domain are formed where decisions are made (in Fig.1 – the decision between the two transitions at p1). Finally, note that considering the entire process domain, every D-path is equivalent to a path in the reachability graph of the net, going from the source node to the sink node.
We now turn to address concurrency. Based on Lemma 1 (Section 2), concurrently operating threads must operate over independent sub-domains. To behave independently, no transition in the sub-domain should be affected by state variables that can be changed in other domains. This implies that if two sub-domains share a state variable, then if this variable is changed in one sub-domain, it should have no impact on the transitions in the other sub-domain. For example, assume a manuscript is sent to a number of reviewers who review it in parallel. Each reviewer can be notified when another reviewer sends a review, but the decisions of each reviewer are independent. This can be modeled as independent sub-domains, sharing some state variables, transforming state variables which are not affected by the shared state variable. Finally, when all review reports are sent, a decision can be made about the paper. This can be considered synchronization of the sub-domains.  The above idea is formalized in the following necessary condition.
Necessary condition 3 (concurrency): Let D1 and D2 be two sub-domains that may operate concurrently. There should be no state variable xi XDj  that changes in Dk such that the value of xi affects the state changes occurring in Dk, kj, k,j=1,2. 
Note that while Necessary condition 3 addresses concurrency situations, we make no similar requirement with respect to choice-related splits (namely, several transitions sharing an input place). Since these may relate to both decomposable and non-decomposable domains (the transitions that are activated can occur in the same sub-domain or in different sub-domains), no strict rules can be formed. 
While concurrency relates to independent sub-domains, we also take interest in the situation where sub-domains stop being independent. The following Lemma shows that this can only happen through synchronization.
Lemma 3: In a well-mapped WF-net two concurrent sub-domains will stop being independent iff a transition exists that depends on the states of both.
Proof: (1) By Necessary Condition 1 (transition domain structure), if such a transition exists, then it depends on the states of both sub-domains and affects at least one. Hence the sub-domains are not independent any more. (2)  Assume one of the sub-domains reached a state in which it is not independent with respect to the other. This means, by definition, that the law for that state depends on the state of the other sub-domain. In a well-mapped WF-net this can only be shown by a transition that has as input places the states of the two sub-domains, namely, a synchronizing merge. 
One of the basic concepts in GPM is the goal of a process. The definition of well-mapped WF-net indicates that the sink place should represent the set of goal states of the process described by the net (condition (4) in definition 19). Since theses states should be stable, for a well-mapped WF-net the sink should represent a set of stable states. It follows that: 
Necessary condition 4 (Stability): The sink place in a well-mapped WF net o marks a set of stable states of the entire process domain.
Consider now what stability at the goal means for a well-mapped WF-net. When the domain reaches the goal state, the process completes and there are no more transitions that can happen. This means that no sub-domain can be in an unstable state when the process reaches its goal. In the net, this would mean that no transition can “fire”. For a transition to fire all its input places need to be active which means that the associated sub-domains must be in the states matching the input places. Thus, for no transition to be activated at least one input place for each transition should be empty. The following Lemma formalizes this:
Lemma 4: Let the set of domain states that match the sink place be SSink. A necessary and sufficient condition for a well-mapped net to be in a stable state at the sink is: s SSink, t, pt  such that s/DpSp.
A special case applies to loops in which action continues in parallel to the continuation of the process, namely, loops whose exit point is a parallel split, as formulated in the following corollary.
Corollary: Let a WF-net be well-mapped, and consider a transition t and three places p1, p2, and p3, such that p1=t, p2=p3=t. Then p1 is not reachable from p2 or from p3.
Proof: Assume p1 is reachable from p2. When t fires, p2 and p3 become active, and while p3 may lead to o, p2 will lead infinitely to the sequence that activates t. This means that o may be reached while the loop sub-domain is unstable, in contradiction to Necessary condition 4 (stability). 
5 Interpreting Workflow-net properties
Much of the research devoted to Petri nets in general, and WF-nets in particular, has addressed particular properties (such as free choice and well-structuredness) defined for these models. While these properties are well-defined in terms of model structure, their behavioral consequences are not well understood. In general, they are claimed to be associated with “good” process behavior (Aalst, 2000), but this claim is typically made in an informal manner and is not theoretically grounded. In this section we use the GPM-based semantics in order to explain the behavior associated with these properties. Furthermore, we show that the proposed semantics enables a more fine-grained distinction between “good” and “bad” behaviors of the structures under consideration. We focus on three known properties of WF-nets: being free- choice, well-structured, and S-coverable.
5.1 Free Choice
A Petri net is said to be free choice iff, for every two transitions t1 and t2, t1t2 implies t1=t2 (Definition 3). A Petri net which is not free-choice usually involves a mixture of choice and parallelism, which is hard to analyze and considered inappropriate (albeit syntactically possible).  Many of the properties identified and analyzed for Petri nets relate to free-choice Petri nets only (see Desel and Esparza, 1995).

p1

p1

t1

p2

t1

p2

t2

p3

t2

(a)	 					(b)
Figure 3: non free-choice structures
We now analyze the meaning of free choice in a well-mapped WF-net. We will show, by example, that the real issue is not the topology of the net, but rather the independence of sub-domains that are associated with the nodes in the net. To understand what non free choice might mean for well-mapped WF-nets consider the non free-choice structures depicted in Figure 3(a) and 4(b). We assume the diagrams are part of a well-mapped WF-net. 
In Figure 4(a) the two places – p1 and p2 – are input places of the transition t1 hence this transition synchronizes their sub-domains. In addition, place p2 is a sole input place of transition t2. By Necessary condition 2 – transition independence – p2 must be independent. However, what happens to the p2 sub-domain depends also on p1. It is impossible for one set of states to have an independent law and to depend on synchronization with another sub-domain at the same time. Hence, this structure is not possible in a well-mapped WF-net.
In contrast, consider the non free-choice structure in Figure 3(b). First – to attach sub-domain semantics to it, assume that p1 and p3 are different sets of states of sub-domain D1 (reached by different distinct D-paths of that sub-domain), and that p2 is defined over sub-domain D2. D1 and D2 are synchronized either by t1 or by t2 and hence are not independent at the states represented by p1 and p3 for D1 and by p2 for D2. This does not contradict sub-domain independence as neither domain is expected to behave independently due to synchronization by either transition. While this structure is not allowed in a free-choice WF-net, it is meaningful in the GPM semantics. Hence, it should be allowed in a well-mapped WF-net. 
This analysis demonstrates how the use of ontological semantics can provide meaning to topological properties that have been formalized but not necessarily well-justified. Specifically, the difficulty faced by non free-choice models is not the (topological) combination of choice and parallelism. In practical situations such a combination can occur. Rather, the difficulty reflects the inability to distinguish independent sub-domains from dependent ones (where the dependence reflects the need to synchronize sub-domains that were independent prior to synchronization).
To resolve this difficulty, we suggest replacing the original definition of free choice property by a new one which we term relaxed free-choice.
Definition 24 (relaxed free choice): A WF-net is relaxed free choice iff for every two transitions t1, t2, t1t2 implies Dt1=Dt2.
In a relaxed free choice WF-net, when two transitions share inputs the domains of their inputs are associated with the same sub-domain. The intuitive meaning is as follows: each transition can synchronize the common sub-domain with the other input domains it has. Hence, the common sub-domain and the other input should be viewed as one joint sub-domain. Since they share a sub-domain, the joint sub-domains for both are the same. 
Due to the conditions imposed on a well-mapped WF-net it should reflect correctly the independence of sub-domains. This is reflected in the following lemma:
Lemma 5: A well-mapped WF-net is relaxed free-choice.
Proof: from Necessary condition 2 – transition independence. If the network was not a relaxed free choice, then some transitions could be shown to operate in sub-domains that are not independent (namely, the transitions could “fire” differently under the same conditions). 
Note, in WF-nets which are not free choice it is possible that transitions are not independent as the exact states of the domain represented by a marking are not known. However, in a well-mapped WF-net more is known about the places. They are configured such that each transition operates independently.
Note that every free choice WF-net is also relaxed free choice. This is because the topology of the free choice net proscribes the possibility of transitions that are not independent.
5.2 Well-structuredness
A WF-net is said to be well-structured iff, for any pair of nodes x and y such that one is a place and the other a transition and for any pair of elementary paths P1 and P2 leading from x to y, P1P2={x,y} implies that P1=P2.
As mentioned in Section 3, well-structuredness requires a parallel split (a transition leading into several places) to be complemented by a synchronizing merge (several places leading to a transition), and an exclusive choice split (a place leading to several transitions) to be complemented by a simple merge (several transitions leading to a place). To understand this property in GPM terms, let us examine the examples in Figure 4. We assume the net is well-mapped and thus use GPM concepts to discuss the meaning of situations that do not satisfy the well-structureness requirement.

t1

t2

p3

p2

t2

p4

p2

t1

p3

t3

p1

t3

p1

p4

(a)	 						(b)
Figure 4: Non well-structured examples
Figure 4(a) includes a WF-net in which an exclusive choice is taken in place p1. Recall, an exclusive choice may stand for two situations. First, the entire domain may select one of two (or more) different D-paths. Since the domain is not decomposable, Necessary condition 3 (concurrency) does not hold, hence synchronization in t3 is not possible. Second, the domain may be decomposable into different sub-domains, and the choice is which one of them becomes active. Since only one sub-domain can become active, it is impossible for p2 and p3 to be active at the same time and activate t3. Hence, this is a case of deadlock (this case will be revisited in the next section) and can prevent the process from reaching its goal.
The WF-net in Figure 4(b) includes a parallel split in t1, after which two sub-domains become active. However, no synchronization is made, and p4 can be reached twice. Unlike the example of Figure 4(a), this situation is possible in practical situations, and is included in the workflow patterns collection as a “discriminator” (Aalst et al., 2003). As an example, consider two teams competing for a trophy, which is awarded to the winning team once it arrives at the finish line. A problem may arise if the winner is already announced and the trophy is given, while the other team is still on its way, unaware that the game is over. According to Necessary condition 4 (stability), the goal of the process (the sink place of the net) should be a stable state of the entire domain, which is not the case if one team is still active. Some action is required for notifying the losing team that the game is over, before the goal of the process is reached. Such action entails a synchronization of the actions of the two teams. This is formalized in the following lemma.
Lemma 6: In a well-mapped WF-net for every two concurrent sub-domains D1, D2 represented by net places there exist two places pkDk, k=1,2, and a transition t such that t={p1,p2}.
Proof: In a well mapped WF-net, from Necessary condition 4 (stability), once the sink is reached, no more transitions can happen, namely, no sub-domain is unstable. Consider two independent sub-domains D1 and D2 represented by the net that are concurrently active. If D1 reached the sink, D2 cannot be unstable. It follows that the two sub-domains must stop being independent before the sink. By Lemma 3, there is a transition t synchronizing D1, D2 before the sink. 
Note that Lemma 6 does not proscribe non well-structured nets like the one in Figure 4(b), which may be useful from a business point of view. Yet, it requires some synchronization of the sub-domains to be made. It is possible that the continuation of the process does not depend on the arrival of both sub-domains at the merge (namely, no synchronization at the merge, as required in well-structured WF-nets). However, in this case synchronization must be made elsewhere, before the goal of the process can be reached. 
5.3 S-coverability
The property of S-coverability in WF-nets relies on the following definitions (Aalst, 1998).
Definition 25 (state machine): A Petri net is a state machine iff every transition has exactly one input and one output place.
Definition 26 (S-component): A subnet PNs=(Ps, Ts, Fs) is called an S-component of a Petri net PN=(P, T, F) if PsP, TsT, FsF, PNs is strongly connected, PNs is a state machine, and for every qPs and tT: (q,t)F implies that (q,t)Fs and (t,q)F implies that (t,q)Fs. 
Definition 27 (S-coverable): A Petri net is S-coverable iff for any node there exists an S-component which contains this node.
Finally, a WF-net is S-coverable iff the short-circuited net is S-coverable.
S-coverability is perceived as some kind of generalization of well-structuredness and free choice (Aalst, 2000) (although a net can satisfy any of these properties without satisfying the others (Jianchun and Dongqing, 2002). Aalst (2003) argues that although it is possible to construct sound WF-nets which are not S-coverable, from a practical point of view it should be avoided. He proposes an intuitive interpretation of this property by using a metaphor of document flows, where each such flow corresponds to an S-component. 
Consistently with this metaphor, we interpret each S-component as the projection of the process into a sub-domain. To be an S-component, two conditions must hold with respect to the sub-domain. First, it should be possible to view the behavior of the sub-domain as a separate stand-alone process (or WF-net). Like every process, it has a law which acts independently, and it may have some transitions which depend on external events (events outside the sub-domain). Second, an S-component stands for a non-decomposable sub-domain. 
Since an S-component should be possible to view as a stand-alone process, all its places must relate only to the sub-domain under consideration. For example, the WF-net in Figure 4(b) is not S-coverable, because the sub-domain of p4 includes state variables from both the sub-domains of p2 and p3 (Necessary condition 1). 
While the strong decomposability of the domain which is reflected in an S-coverable WF-net makes its behavior predictable and relatively easy to analyze, we do not consider it a mandatory property of a process. Rather, we rely on the restrictions that are posed on a well-mapped WF-net to achieve this predictability. In particular, Necessary conditions 2 (transition independence) and 3 (concurrency) as well as Lemma 6 (which assures that concurrent sub-domains must synchronize) resolve some of the problems typical to WF-nets which are not S-coverable. To demonstrate that, we make an analogy to the corollary presented by Aalst (2000), who showed that a sound well-structured WF-net is S-coverable. In analogy to that, we propose the following Lemma. 
Lemma 7: A well-mapped and well-structured WF-net is S-coverable. 
Proof: Consider a well-mapped and well-structured WF-net. Assume first, that the process domain is not decomposable, then the entire net is an S-component (there is no concurrency in the domain, hence no transition leading to more than one place). Second, assume the process domain is decomposable at some set of states to at least two independently transforming sub-domains. Consider the sub-net PNs, depicting the behavior of one. PNs is not included in an S-component if (a) there is a place pPs and a transition tTs, such that tp, or (b) there is a place pPs and a transition tTs, such that tp. (a) is not possible for the following reason: t must be in another independent sub-domain (Necessary condition 3 – concurrency); hence, there must be a parallel split on the paths from i to p and from i to t, where the decomposition took place. Since the net is well-structured, p is a place and t is a transition, this is not possible. (b) is not possible since it is in violation of Necessary condition 2 (independence). 
Note that a well-mapped WF-net is not necessarily sound, hence Lemma 7 is more general than the result presented by Aalst (2000). 
6 Process validity and soundness
In this section we address the GPM concept of process validity on one hand, and the WF-net property of soundness on the other hand. According to GPM, validity of a process model can only be assessed with respect to a set of expected external events and to a defined goal (Soffer and Wand, 2007). How these are determined is outside the scope of the current analysis. We consider only the reachability of the process termination state, assuming that it represents the process goal. Assuming that all the expected external events occur, validity relates to completeness of the internal law definition (which relates to internal events) and to its consistency with the goal definition (Soffer and Wand, 2007).
Incompleteness reflects potential deadlock situations. Following Kiepuszewski, Hofstede and Aalst (2003), a process instance is in deadlock iff it is not in the goal and no transition is enabled. GPM also allows for a process execution “hanging” when external events fail to occur, but we assume here no such failure happens. Thus, deadlock means that the process is in a state for which the law is not defined. In a well mapped WF-net this may occur when a transition has more than one required input place (i.e., it is a synchronizing merge which joins different sub-domains) and it is possible the net reaches a state where not all input places can be populated.  Two situations are possible: 
(1)	Not all sub-domains have been activated at the split point.
(2)	At least one of the sub-domains took a D-path which does not lead to the input place of the merge transition.
We will specify modeling rules to avoid each of these cases. Case (1) is only possible if an exclusive choice (i.e., a place leading to more than one transition) is followed by a synchronizing merge. As discussed in Section 5.2, this is only possible if the domain is decomposable. While such structures do not appear in a well-structured WF-net ‎0(Aalst, 1998; Aalst, 2000), we do not require well-structuredness. Instead, we only require that every synchronizing merge be preceded by a split, where all branches would be activated. This may be a parallel split (transition) or an exclusive choice (place) activated at least once for each branch. Note, following Lemma 6 (synchronization of sub-domains), if the split is an exclusive choice, it should be activated exactly once for every branch. As opposed to well structuredness, we leave simple merges (merges in a place) unconstrained as to the type of split they should be preceded by.  is the above considerations (including the result of Lemma 6) is formalized in Modeling rule 1: 
Modeling requirement: In a well-mapped WF-net a place can only be connected to a transition by two or more elementary paths if each elementary path is activated exactly once.
A corollary of the modeling requirement is that the possible number of activations of the place (its maximal number of tokens) should be equal to the number of the elementary paths.
Following the modeling requirement, the combinations listed in Table 2 are possible.
Table 2: Allowed split / merge combinations
split	merge	When possible	
Place	Place	Always allowed	
Place	Transition	Allowed only if the possible number of activations of the place is equal to the number of elementary paths to the transition.	
Transition	Place	Always allowed	
Transition	Transition	Always allowed 	

We are interested in practical rules that can guide the construction of a WF-net that satisfies the modeling requirements. To do that, we will use the fact that a WF-net has only one initial place. This implies that for any place to be activated a given number of times, there should be enough parallel splits in the net to enable the creation of the required number of tokens. We therefore conclude that for a place to be activated a given number of times it must be preceded (not necessarily immediately) by the same number of parallel net paths (which represent the same number of concurrently active sub-domains). We can use the following construction rule to assure that each path leading from the split (place) under consideration is activated once. In each path leading from the split place there should be a transition also conditioned by exactly one of the parallel paths that must be active to assure the required number of activations of the place. Formally:
Modeling Rule (MR) 1: Let p be a place connected by n≥1 elementary paths to a transition t. 
(a)	If p can be activated at most once (its maximal number of tokens is 1) then the net should satisfy n=1.
(b)	Else, for n>1 let Dk, k=1..n, be concurrently operating sub-domains prior to place p. Let tkp. Then the net should satisfy the following: for each k, pk in Dk such that pk=tk. 
Part (b) of MR1 is sketched in Figure 5, focusing on the domain Dk, where the rest appear in dashed lines without details.

pk

tk

Dk

t

p

Figure 5: Illustration to MR1 (part b) 
 To avoid the case (2), the modeler needs to make sure that if two sub-domains that have alternative distinct D-paths need to synchronize, then every possible combination of these D-paths has a merging transition defined for it. To illustrate the idea, consider the examples of Fig. 6.

Fig. 6: D-path combinations
In Fig. 6(a), the process domain is split in t1 to two concurrently active sub-domains, and both these sub-domains have different D-paths that can be selected. The process may clearly deadlock, if one sub-domain takes a D-path leading to p7 while the other reaches p10, or if one sub-domain reaches p8 while the other takes a D-path that leads to p9. There are more combinations of D-paths that can be taken than combinations that lead to the goal of the process. The sub-domain on the left side has two distinct D-paths: (1) p2p7, and (2) p2p8. The sub-domain on the right side has four distinct D-paths: (1) p3p4p6p9, (2) p3p4p6p10, (3) p3p5p6p9, and (4) p3p5p6p10. To eliminate the possible deadlock, we need to define action in every possible situation the process may reach. We may look for a place which is reached from all D-paths. Considering the right side sub-domain, p6 is reachable in all the distinct D-paths. Hence, it is guaranteed to be reached. Let us examine a possible correction, where p6 is connected to t11. Then t6, t7, and t11 would share p6 as an input place, while t11 is also preceded by p8 (whose domain is different). This is in contradiction to the relaxed free choice requirement that if two transitions share some input places, then the sub-domains of the inputs are the same. Following this analysis, p9 and p10, which are reachable in two distinct D-paths each and together “cover” all the four D-paths, do not represent states where the sub-domain is independent (since they lead to a merge). A complete solution, addressing every possible situation, requires the net to include a transition defined for every possible combination of non-independent places in the two sub-domains, namely, (p7, p8)(p9, p10), as shown in Fig. 6(b).
The above analysis is formalized in Modeling rule (MR) 2 that requires that if a transition depends on a combination of states of two sub-domains, and that combination is not guaranteed to happen, there must be other transitions specified for all other possible state combinations. 
Modeling rule (MR) 2: Let D1, D2 be two sub-domains, and t a transition such that t={p1,p2}, where pk is associated with sub-domain Dk. 
Let, for each Dk (k=1,2) PMk  be set of places for which Dk is not independent and  are on distinct D-path in Dk. Then for every pPM1 and qPM2, there must be a transition tp,q such that  tp,q ={p,q}.
Note: D1 and D2 can be identified by backtracking paths from p1 and p2 until the first transition which is included in both paths. Inconsistency between the law and the goal definition relates to infinite loops. In WF-nets, since every element must be on a path from i to o, loops must have (at least one) exit points. These may be parallel splits or exclusive choice splits. According to the corollary of Lemma 4, parallel splits cannot be exit points of loops in a well-mapped domain representation WF-net. We shall hence examine the possible structures in which loops whose exit point is an exclusive choice may become infinite. When a loop has an exclusive choice as an exit point at place p, two cases are possible:
(1)	The next transition has only one input place (t={p}). Then the exit depends on one sub-domain only. Structurally, this is not an infinite loop. The exit from the loop depends on the decision criteria defined by the analyst (based on the actual state that is reached in the set of states represented by the place).
(2)	The next transition has more than one input place (i.e., it merges a number of concurrent sub-domains). In this case, if the merge deadlocks, the loop will continue infinitely. However, merging deadlocks can be eliminated by using modeling rules 1 and 2. Hence, if the modeling rules are used in a well-mapped WF-net, it does not include infinite loops.
Theorem 1: A well-mapped WF-net which satisfies Modeling rules 1 and 2 is sound.
Proof: soundness has three requirements. We first address conditions (ii) and (iii).
(ii) proper termination – follows directly from Necessary condition 4 (stability) and Lemma 6. (iii) no dead transitions – follows from Necessary condition 2 which requires the input domain of every transition to be independent, and from MR1, which ensures that if more than one sub-domain is required for enabling a transition, they all will be activated. To prove (i), namely that o is reachable from every state reachable from i, we will show that for any state M reachable from i there is a transition t that can be fired. Since all the elements in a WF-net are on a path from i to o and no infinite loops are possible, if any arbitrary state M transforms, o will be reached.
We will show that in a given state M every transition is either (a) within an independent sub-domain, or (b) a result of a merge between two (or more) sub-domains. In the first case, a transition will be fired with certainty. In the second case, by MR1, all the required sub-domains should be active, and by MR2 there is a transition defined for every possible combination of D-paths of the sub-domains. Hence a transition will be fired.
Formally: Let P(M) be the set of active places in M, and consider a place p1P(M) and a transition t1p1. Two cases are possible: (1) t1P(M), then t1 fires at M. (2) t1P(M), then t1 cannot fire at M. We will show that when Rules 1 and 2 hold, there exists a transition t2 that can fire at M. 
Having more than one input place, t1 merges two or more independent sub-domains with at least one having a place which is not active in M.  Let this place be p2t1, p2P(M). By the definition of a well-mapped WF-net p2 represents states in a sub-domain D2 and is active for at least one marking M’. Now, t1 synchronizes p1 and p2 and due to MR 1, prior to t1 there are two independent and necessarily activated sub-domains D1 and D2 (which are the domains whose states are represented by p1 and p2). According to our assumption, when the net is in M, D2 is not in a state corresponding to p2 (otherwise, t1 could fire). However, since D2 is part of the input of t1, it cannot be independent at the domain state for M. Due to MR 2, a transition t2 should exist to synchronize D2 with an active domain in M (concurrent to D2). This transition can fire. 
In summary, following the necessary conditions and modeling rules, it is possible to construct a sound and meaningful WF-net. 
7 Applying the Rules in Constructing Process Models
This section demonstrates the application of the ideas presented in this paper for the construction of well-mapped WF-nets. We will demonstrate the application using the following order fulfillment process in a company which sells and installs communication systems. 
To fulfill an order, components need to be sourced (either by in-sourcing or by outsourcing) and delivered to the customer’s site. Concurrently, infrastructure should be prepared at the customer’s site. The infrastructure preparation as well as the delivery of the ready components to the customer’s site can be done by the customer or by the company. When the infrastructure is ready and the components delivered, the communications system can be installed. The common practice is either that the customer takes responsibility for both infrastructure installation and component delivery or both are done by the company. This is captured in Fig. 6(a), which corresponds to the case by assigning the place and transition meanings listed in Table 3.
 However, in some cases the customer may only take responsibility for the infrastructure installation or the delivery. These cases would lead to deadlock in Fig. 6(a) (as there are no transitions that can occur when these situations arise). An alternative model, in which such combinations are feasible (i.e., can lead to project completion) is shown in Fig. 6(b).

Table 3: Place and transition labels for Fig. 6.
Place	Label		Transition	Label	
p1	Order status: received		t1	Order fulfillment initiation	
p2
	Infrastructure status: to be installed		t2	Issue outsourcing order for components	
p3	Components status: to be sourced		t3	Issue production order for components	
p4	Components status: ordered from supplier		t4	Receive components from supplier	
p5	Components status: manufactured		t5	Receive components from production	
p6	Components status: all are available		t6	Coordinate delivery by customer	
p7	Infrastructure status: installed (by customer)		t7	Coordinate delivery by company	
p8	Infrastructure status: installed (by company)		t8	Infrastructure installation by customer	
p9	Customer delivery coordinated		t9	Infrastructure installation by company	
p10	Company delivery coordinated		t10	Install system (infrastructure and delivery handled by customer)	
p11	System status: installed		t11	Install system (infrastructure and delivery handled by company)	
			t12 
(b only)	Install system (infrastructure handled by company, delivery by customer)	
			t13
(b only)	Install system (infrastructure handled by customer, delivery by company)	

We now use this example to demonstrate the guidelines to be followed when constructing a sound well-mapped WF-net.  Table 4 provides a summary of these guidelines. The table indicates the origin of each guideline in the formal part of the paper, and provides examples from the communication company order fulfillment process. 
Table 4: Modeling guidelines that follow the formal discussion
	Guideline	Derived from	Example	
	Basic modeling 	
1	Each place should match a set of states of a sub-domain.
In practice: The set of states can be defined by a condition on state variables.	Definition 20 (meaning of a populated place)	Place: p6
Sub-domain: state variables describing the components.
Condition: components status=’all are available’ 	
2	Transitions should transform values of state variables from initial values (at input places) to final values (at output places)	Necessary condition 1 (transition domain structure)	Transition: t4
From components status: ‘ordered from supplier’ (p4) to components status: ’all are available’ (p6)	
3	Define the sink place as the goal of the process.
In practice: a condition defining a set of desired stable domain states.	Necessary condition 4 (stability)	Sink is Place p11.
Domain states: system status = ’installed’	
	Splits	
4	Consider a split transition:

For each branch: the state variables that change in the branch do not affect changes that occur in the other branches.	Necessary condition 3 (concurrency)	Split transition: order fulfillment initiation (t1).
Branches “obtain and deliver components” and “prepare infrastructure” change different state variables. 
Note, there might be common state variables which do not change (e.g. customer ID).	
5	A split at a place should lead to a set of transitions that 
(a)	All have only the place as an input OR
(b)	All synchronize the place with at least one other place.	Necessary condition 2 (independence), Lemma 5 (relaxed free choice)	Place: p6 (components status: “all are available”). 
Transitions t6 (“coordinate delivery by customer”) and t7 (“coordinate delivery by company”) have only p6 as input.
Note: each transition represents a different decision in the “components” sub-domain.
Place p10 (in Fig. 6 (b)) splits to t13 (delivery by company, infrastructure by customer) and t11 (delivery and infrastructure by company). Each synchronizes the “components” and the “infrastructure” sub-domains.	
6	There should be no loop where the only exit is on a transition split.	Corollary of Necessary condition 4 (stability)		
	Merges	
7	For concurrently changing sub-domains, when the next transition of at least one cannot be determined independently, a merge is needed at that point (with one of the others).	Necessary condition 3 (concurrency)	For p9 and p10 (components status=’delivered’) installation (t10…t13) can only take place when the other concurrent sub-domain - infrastructure - is ready (p7 and p8).	
8	The sub-domains merged at a transition should satisfy for each branch: the state variables that change in the branch do not affect changes that occur in the other branches.	Necessary condition 3 (concurrency)	Install system (t10…t13) synchronize “components” and “infrastructure”.	
9	A merge at a transition:
(1)	All input places must be synchronized at all their output transitions OR
(2)	All output transitions of an input place must have the same input domain.	Necessary condition 2 (independence), Lemma 5 (relaxed free choice)	Transitions t10 and t11 (in the original model) synchronize the infrastructure and components sub-domains. They both satisfy condition (1).	
10	When a merge at a transition corresponds to a split at a place (1) the number of possible activations of the place should be equal to the number of branches. (2) Each branch contains a transition that depends on the split place and on preceding independent branch*	Modeling rule 1	Assume that upon completion and verification of either components delivery or infrastructure a supervisor is notified, and sends experts to sign off and approve quality. Installation can be carried out only after both approvals have been obtained. This is depicted in the diagram in Figure 7. The place Supervisor notified will be activated twice. The activation of each of the outgoing branches is assured by two additional places, one in the component domain and the other in the infrastructure domain.	
11	If concurrent sub-domains are merged in a place (namely, the place is populated whenever one sub-domain “reaches” it), the sub-domains should be synchronized after the place (by one or more transitions).	Lemma 6 (synchronization of sub-domains)	Referring to the example in the above cell, the components and infrastructure sub-domains are synchronized at installation.	
12	When two sub-domains synchronize at a transition, there should be merging transitions for all the combinations of possible states each sub-domain can reach (final places of distinct D-paths).	Modeling rule 2	In the original model (Fig. 6 (a)), the possibility existed that both components and infrastructure were ready and installation could not be done. For example, when infrastructure was done by company (p8) and delivery by customer (p9). Similarly, for p7 and p10).This is resolved by adding transitions t12 and t13. 	
* This rule can also be categorized under “split”. For brevity the full condition is not included, see MR1.	

Figure 7: Addition to the order fulfilling process, demonstrating guideline 11
8 Related Work
The basic formalism of Petri nets (Petri, 1962) has been assigned numerous extensions that are intended to add semantics to the net, serving a variety of purposes over the years (Salimifard and Wright, 2001). Examples are timed Petri nets (e.g., Zuberek, 1991), stochastic Petri nets (e.g., Bause and Kritzinger, 1996), reset nets (e.g. Dufourd, Finkel and Schnoebelen, 1998) and hierarchical Petri nets (e.g. Chrastowski-Wachtel et al, 2003). While in this paper we specifically address WF-nets, which are a restricted class of the traditional Petri nets, our approach can be viewed as being similar to Colored Petri nets (CPN) (Jensen, 1990). CPN appear graphically as Petri nets, where tokens have “colors”, representing different types of data. Places are associated with color sets which determine the types of data they may contain. This is analogous to the place sub-domain in our terminology, where the state variables of the sub-domain represent information (about the state). The marking (state) of a CPN is the distribution of tokens in places. It is changed by the occurrence of transitions, which consume and create the tokens according to expressions specified on the arcs. These expressions determine the number and colors of the tokens that should be moved along each arc. The expressions can be compared to our notion of transformation laws which govern the transitions.
While the colors used in CPN incorporate domain information into the model, similarly to our state variables, there are major differences between our approach and CPN. First, CPN is aimed at formally representing certain information about the domain for execution purposes (Liu et al., 2002). In contrast, we aim at understanding how the nature of this information affects the structure of the model and the behavior of processes. Second, CPN uses the Petri net syntax and adds more information to it. We use the Petri Net syntax, and rely on an ontological model to provide meanings to the syntactical constructs. From this meaning we derive restrictions on the types of nets that can be constructed. These rules can be viewed as semantic rules intended to make the models consistent with ontological principles. The information conveyed by CPN and by our model can be similar; still, its implications are completely different. Third, CPN entails verification procedures (Jensen, 1997), to be applied to a complete model. Our approach, in contrast, is intended to support the process designer in the construction of semantically (i.e., ontologically) meaningful models, and by implication, to assure the models are valid, in being able to reach their goals. 
To produce a WF net that is an actual representation of the modeled domain, overcoming possible gaps between the model and the process reality, a possible approach is process mining (Aalst and  Weijters, 2004; Aalst et al., 2007). Process mining starts by gathering the information of the real process based on the event log of an information system, and develops the process model (e.g. WF-net) based on this information.  Although this approach supports representation of an existing real world system, it does not employ some generic semantics for this purpose. Rather, following actual process events, process mining avoids process design difficulties that may result in erroneous process models. Nevertheless, process mining cannot be used for the design of new non-existing processes.
A mapping of Petri nets to the ontological model of Bunge has already been performed by Recker and Indulska (2007). The purpose of this mapping was to evaluate the expressive power of Petri nets rather than to enhance their semantics. As such, their mapping is done on a construct-by-construct basis in a technical manner, not attempting to achieve a coherent semantic model. The basis of this mapping is the general ontological framework adapted to information systems (also known as BWW ontology), and not GPM, which specializes the ontological model for business processes. Finally, since no coherent semantic model is established, no modeling rules can be derived from their mapping.
Over the years, many properties of Petri nets (and later of WF-nets) have been investigated. Process complexity metrics relate to the syntax of the model (e.g., the Cardoso metric, Cardoso, 2005) and to the complexity of process behavior (e.g., structuredness metric, Lassen and Aalst, 2009). Model complexity is assumed to hamper designer’s understanding and to cause difficulties in model interpretation. However, these metrics only reflect possible difficulties, and do not lead to principles that may help resolve possible modeling problems. In contrast, the relationships between precisely defined structural properties (see, e.g., Esparza and Silva, 1990; Desel and Esparza, 1995) and the behavioral property of soundness in WF-nets have been established on a mathematical basis. However, a rigorous explanation for why these properties are related to soundness has not, to the best of our knowledge, been given so far. Our enhancement of WF-net semantics to reflect domain concepts provides such an explanation. Moreover, this enhancement reveals that in some cases possessing a structural property is not the reason for the “good” behavior of the modeled process. Rather, it reflects, for a well-mapped WF-net, domain properties such as decomposability and independent sub-domain behavior. These domain properties, in turn, are the real cause for the “good” behavior achieved. Based on this understanding, we showed that it is possible to define properties which are less restrictive than the pure structural properties (e.g., relaxed free choice), yet overcoming the unpredictable behavior the structural properties are intended to prevent when fulfilled by a WF-net.
Using our proposed semantics, we show how sound process models can be constructed. Soundness by construction has been claimed to be achieved by other works as well. Chaudron et. al. (2003) propose two ways for constructing sound WF-nets: (a) Top down: by stepwise refinement of places and transitions of a given start net, where the start net as well as the refinement fragments should be sound; and (b) Bottom up: by connecting existing sound component nets. These two ways are techniques for creating a sound composite model from simpler sound models. They apparently ease the task of creating sound models, but do not support such construction from scratch. Van Hee et. al. (2008) propose a generic modeling formalism whose semantics is based on a history log, and show how sound models can be constructed using this formalism. Their approach is a generalization of the top-down and bottom-up operations discussed above (Chaudron et. al., 2003). Using a history log as a basis is more suitable for modeling a process which is already being executed, while our approach is intended to support the design of new processes.
9  Discussion
As indicated in the introduction, process models are a commonly used type of conceptual models (Wand & Weber, 2002). Specifically, the purpose of process models is to represent the behavior of business domains. On a more general note, conceptual models are intended to enable stakeholders and business and systems analysts communicate about a business domain. Thus, they should clearly convey the meaning of the represented domain. However, formal Process models, in particular WF-Nets, do not directly and clearly convey this meaning. 
To overcome this limitation, this work aims at providing a clear domain meaning to WF-Nets. This is done by assigning ontological semantics to the modeling constructs and by imposing certain rules on models to be considered acceptable (in that they provide a direct mapping of domain phenomena). This is in line with approaches that analyze conceptual modeling techniques and suggest ways to apply or improve them based on ontological considerations. Therefore, to place this work in a wider context, we now briefly discuss approaches to analyzing conceptual modeling grammars in general. 
In the conceptual modeling literature, ontology-based frameworks have mainly been applied for evaluating the representational capabilities of modeling grammars (Wand & Weber, 1993; Opdahl & Henderson-Sellers, 2001; Opdahl & Henderson-Sellers, 2002; Green & Rosemann, 2004). In addition, there have also been attempts to use ontology as a basis for deriving modeling rules, intended to achieve a consistent representation of domain phenomena in a model (Guizzardi, Ferreira & van Sinderen, 2005; Evermann & Wand, 2005; Evermann & Wand, 2009; Bera, P., Krasnoperova, A. & Wand, forthcoming). This line of work is very closely related to the approach presented in this paper. However, there are clear differences between our set of rules and the ontology-based rules for conceptual modeling in the above works. These differences stem from differences in the purposes the models may serve. While conceptual models mainly serve for communication and understanding (Mylopoulos, 1992), process models may also serve as a basis for workflow execution (Dussart, Aubert & Patry, 2004). As a first consequence, the models expected to be created with grammars used or suggested for conceptual modeling (e.g., UML) are not required to be as formal as the models created with the grammar addressed here (WF-nets). A second consequence of these different purposes is the different quality criteria proposed for conceptual models in comparison to those defined for process models . Quality dimensions of conceptual models include semantic quality, namely the correspondence between the conceptual model and the domain, syntactic quality, namely the correspondence between the model and the modeling language, and pragmatic quality, which relates to the audience’s interpretation of the model or its understandability (Lindland,  Sindre & Solvberg, 1994). In contrast, although recently some quality criteria of process models relate to their understandability (Mendling and Strembeck, 2008), the most commonly addressed criteria, such as soundness, serve the purpose of executability. 
The rules presented in the paper, similarly to conceptual modeling ontology-based rules, are concerned with the semantic quality of the model. This quality aspect has not been addressed so far with respect to formal process models, in particular those that apply token-based semantics. Not only it provides for more meaningful models, but it also reveals the meaning of net qualities so far considered mostly technical in nature (such as free choice). Furthermore, an important result shown in the paper is that addressing semantic quality also supports the executability purpose through soundness. 
10  Conclusion 
Most process modeling techniques do not provide the degree of formality needed to mathematically analyze process model characteristics.  To enable such analysis, Petri Net models of process dynamics, in particular Workflow Nets, can be used. However, while supporting the analysis of workflow behavior, WF-nets do not possess well-defined and clear domain semantics. Hence, there are no rules on how to model a given domain using WF-nets or how to interpret a given net in domain terms. Moreover, the use of WF nets might lead to process models which do not directly convey the semantics of the domain in which they operate. 
To support formal analysis and to enable the construction of semantically meaningful models, we propose to assign ontologically-based semantics to Petri Net constructs.  We base our semantics on GPM, which is an adaptation to process modeling of a general ontological model proposed by Bunge. Based on GPM, we suggest a specific assignment of semantics to Petri Net constructs. We show how modeling guidelines, based on this semantics, can assist in constructing process models to avoid problems that traditionally could only be detected by verification of the completed models.
Existing verification algorithms for WF-nets can analyze in polynomial time only specific classes of models (free-choice or well-structured). The modeling rules suggested here can lead to the creation of sound WF-nets which are not necessarily free-choice or well-structured. The modeling rules do not constitute a verification approach. Rather, they form a construction approach, which yields sound models when applied. We have also shown that net properties such as free choice and S-coverability can be explained using the ontological semantics.
Based on the ontological semantics, we also suggest modeling rules for constructing process models that are assured to reach their goals when executed. The essence of the analysis is in mapping common situations that can occur when a domain undergoes state transitions, into a WF-net representation. For a process to be guaranteed to reach its goal, its definition should fulfill three conditions: (1) no situations should arise where it “hangs”, (2) completeness: all possible states should have defined transitions, and (3) infinite loops should not be possible. Process “hanging” can happen when several conditions need to be fulfilled for the process to continue – i.e. in merge situations. Merges occur because a split has occurred earlier in the process. By choosing only appropriate combinations of splits and merges, the process can be guaranteed to proceed. This was the purpose of Modeling Rule 1. Completeness requires that the process model will specify continuation for all possible states – this was the purpose of Modeling Rule 2. Both rules and the incorporation of goal definition into the model ensure the absence of infinite loops. Constructing models that conform to these two rules, assures therefore that the process, when executed, can always complete (in the sense of reaching its goal). It is important to note that the rules can be used to guide the actual construction of process models, rather than being applicable only to already existing models.
Besides the contribution to process modeling, the paper also makes a theoretical contribution regarding GPM and Bunge’s ontology. The modeling rules and restrictions proposed here are strictly based on the ontological analysis of domain behavior. Nevertheless, we showed that following these restrictions leads to sound models, namely, models that satisfy a specific mathematically defined property. Since the usefulness of ontologies can only be determined empirically (Wand & Weber, 2002), this result provides an evidence supporting the usefulness of GPM and its underlying ontology.
This work can be extended in several ways. First, as GPM concepts are generic, they can be applied to other modeling languages. This can help provide techniques for mapping process models created in other languages into well-mapped Workflow nets. This application would require mapping of a process modeling grammar to GPM and deriving appropriate restrictions and modeling rules for models constructed in the grammar. Second, the modeling rules can be tested empirically to examine their effectiveness in creating WF-nets of realistic situations. The resulting models can be evaluated for their quality. Finally, since the rules are well formalized, they can be used as the basis for computerized tools to support the development of meaningful and valid process models.

Acknowledgement: The authors are indebted to very helpful suggestions made by W.M.P. van der Aalst at CAiSE 2008. This work was supported in part by a grant from the Natural Sciences and Engineering Research Council of Canada to one of the authors.
References
Aalst, W.M.P., van der (1998). The application of petri nets to workflow management. The Journal of Circuits, Systems and Computers, 8(1), 21–66. 
Aalst, W. M. P. van der  (1999). Formalization and verification of Event-driven Process Chains, Information and Software Technology, 41(10), 639-650. 
Aalst, W. M. P. van der  (2000). Workflow Verification: Finding Control-Flow Errors Using Petri-Net-Based Techniques, In W.M.P. van der Aalst, J. Desel, and A. Oberweis (eds), Business Process Management: Models, Techniques, and Empirical Studies,(LNCS 1806), pp. 161-183, Springer-Verlag, Berlin. 
Aalst, W. M. P. van der  (2003). Challenges in business process management: Verification of business processes using Petri nets. Bulletin of the EATCS, 80, 174-199. 
Aalst, W. M. P. van der, Hofstede, A. H. M. ter, Kiepuszewski, B., & Barros, A. P. (2003). Workflow Patterns, Distributed and Parallel Databases, 14(1), 5-51.
Aalst ,W.M.P., van der & Hofstede, A.H.M. ter. (2005). YAWL: Yet Another Workflow Language. Information Systems, 30(4), 245-275. 
Aalst, W.M.P., van der & Weijters, A.J.M.M. (2004). Process mining: a research agenda. Computers in Industry, 53(3),231-244.
Aalst, W.M.P., van der, van Dongen, B.F., Herbst, J. , Maruster L., Schimm G., & Weijters A.J.M.M.. (2007). Workflow mining: A survey of issues and approaches. Information Systems, 32(5),713-732.
Bause, F. & Kritzinger, P. S. (1996). Stochastic Petri Nets, An introduction to the Theory Verlag-Vieweg, Berlin.
Bera, P., Krasnoperova, A. & Wand, Y. Using Ontology Languages for Conceptual Modeling. JDM, forthcoming.
Bunge M. (1977). Treatise on Basic Philosophy: Vol. 3, Ontology I: The Furniture of the World, Boston: Reidel.
Bunge, M. (1979). Treatise on Basic Philosophy: Vol. 4, Ontology II: A World of Systems, Boston: Reidel. 
Cardoso, J. (2005) Control-flow complexity measurement of processes and Weyuker's Properties. Transactions on Informatika, Systems Sciences and Engineering, volume 8, Budapest 2005, pp. 213-218. Springer Verlag.
Chrastowski-Wachtel, P, Benatallah, B., Hamadi, R., O’Dell, M. & Susanto, A. (2003). A top-down Petri net-based approach for dynamic workflow modeling. In: W.M.P. van der Aalst et al. (Eds.): Business Process Modeling 2003, LNCS 2678, (pp. 336–353), Springer-Verlag, Berlin.
Chaudron, M., van Hee, K., & Somers, L. (2003). Use cases as workflows, in W.M.P. van der Aalst et al. (Eds.): Business Process Modeling 2003, LNCS 2678, (pp. 88–103), Springer-Verlag, Berlin.
Desel, J. & Esparza, J. (1995). Free Choice Petri Nets volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK.
Dussart, A., Aubert, B. A., & Patry, M. (2004). An evaluation of inter-organizational workflow modeling formalisms. Journal of Database Management, 15(2), 74-104.
Dufourd, C., Finkel, A. &. Schnoebelen, P. (1998), Reset nets between decidability and undecidability, In: K. Larsen, S. Skyum & G. Winskel (Eds.), Proceedings of the 25th international colloquium on automata, languages and programming. LNCS 1443, (pp. 103–115), Springer-Verlag, Berlin.
Esparza, J. & Silva, M. (1990). Circuits, Handles, Bridges and Nets. In Rozenberg G. (ed), Advances in Petri Nets 1990, LNCS 483, pp. 210-242, Spreinger-Verlag, Berlin.
J. Evermann and Y. Wand, “Ontology Based Object-Oriented Domain Modelling: Fundamental Concepts”, Requirements Engineering Journal, Volume 10, Number 2, May 2005 pp. 146-160.
Evermann, J., & Wand, Y. (2009). Ontology based object-oriented domain modeling: Representing behavior. Journal of Database Management, 20(1), 48-77.
Green, P., & Rosemann, M. (2004). Applying ontologies to business and systems modelling techniques and perspectives: Lessons learned.  Journal of Database Management, 15(2), 105-117.
Guizzardi, G., Ferreira P. L. & van Sinderen, M. 2005. An ontology-based approach for evaluating the domain appropriateness and comprehensibility appropriateness of modeling languages. ACM/IEEE 8th International Conference on Model Driven Engineering Languages and Systems, Montego Bay, Jamaica, 2005, Lecture Notes in Computer Science LNCS 3713, Springer-Verlag.
Jensen, K. (1990). Coloured Petri Nets: A High Level Language for System Design and Analysis. In G. Rozenberg, editor, Advances in Petri Nets 1990, volume 483 of Lecture Notes in Computer Science, pp. 342–416. Springer-Verlag, Berlin.
Jensen, K. (1997). Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use. Volume 1. EATCS monographs on Theoretical Computer Science. Springer-Verlag, Berlin.
Jianchun, S. & Dongqing, Y. (2009). Process mining: Algorithm for S-Coverable workflow nets.. WKDD 2009: Proceedings of the Second International Workshop on Knowledge Discovery and Data Mining, (pp. 239-244). IEEE Computer Society.
Kiepuszewski, B., Hofstede, A.H.M. ter, & Aalst, W.M.P. van der (2003) Fundamentals of control flow in workflows, Acta Informatica, 39(3), 143-209.
Lassen, K. B. & Aalst, W.M.P., van der  (2009). Complexity metrics for workflow nets.  Information and Software Technology, 51, 610–626.
Lindland, O.I., Sindre, G. & Solvberg, A. 1994. Understanding quality in conceptual modeling. IEEE Software 11 (2), 42–49.
Liu, D.,  Wang, J., Chan, S., Sun , J. & Zhang, L. (2002). Modeling workflow processes with colored Petri nets. Computers in Industry. 49, 267-281. 
Mendling, J. (2007) Detection and Prediction of Errors in EPC Business Process Models, PhD thesis, Vienna University of Economics and Business Administration
Mendling, J. & Strembeck, M. 2008. Influence Factors of Understanding Business Process Models. Business Information Systems LNBIP 7, Springer-Verlag Heidelberg, 142-153.
Milner, R., Parrow, J.  & Walker, D. (1992). A calculus of mobile processes. Information and Computation, 100 (100), 1-40.
Mylopoulos, J. (1992). Conceptual modeling and telos. In P. Locoupoulos & R. Zicari (Eds.), Conceptual modeling, databases,and cases. New York, NY: John Wiley & Sons, Inc.
Object Management Group (OMG) (2006) Business Process Modeling Notation Specification, www.bpmn.org
Opdahl, A., & Henderson-Sellers, B. (2001). Grounding the OML meta-model in ontology. The Journal of Systems and Software, 57(2), 119-143.
Opdahl, A., & Henderson-Sellers, B. (2002). Ontological evaluation of the UML using
the Bunge-Wand-Weber model. Software and Systems Modeling, 1(1), 43-67.
Petri, C.A. (1962) Kommunikation mit Automaten. PhD thesis, Fakult¨at f¨ur Mathematik und Physik, Technische Hochschule Darmstadt, Darmstadt, Germany.
Recker, J. & Indulska, M. (2007). An Ontology-Based Evaluation of Process Modeling with Petri Nets. Journal of Interoperability in Business Information Systems, 2(1), 45-64.
Russell, N., Hofstede, A.H.M. ter Aalst, W.M.P. van der & Mulyar, N. 2006. Workflow Control-Flow Patterns: A Revised View. BPM Center Report BPM-06-22, BPMcenter.org. 
Sadiq, W., & Orlowska, M.E. (1997). On Correctness Issues in Conceptual Modeling of Workflows, In: Proceedings of the 5th European Conference on Information Systems, Cork, Ireland, 943-964.
Salimifard,  K. &  Wright, M. (2001). Petri net-based modeling of workflow systems: An overview. European Journal of Operational Research, 134, 664-676.
Soffer, P. & Wand, Y. (2005). On the notion of soft goals in business process modeling. Business Process Management Journal, 11(6), 663-679.
Soffer, P. & Wand, Y. (2007) Goal-Driven Multi-Process Analysis, Journal of the Association of Information Systems 8(3), 175-203.
Soffer P., Wand Y., & Kaner, M. (2007) Semantic Analysis of Flow Patterns in Business Process Modeling, Proceedings of Business Process Management (BPM’07) (LNCS 4714), pp. 400-407, Springer-Verlag, Berlin.
Van Hee K., Oanea, O., Serebrenik, A., Sidorova, N. & Voorhoeve, M. (2008). History-based joins: semantics, soundness and implementation.  Data & Knowledge Engineering 64, 24-37.
Van Hee K.,, Sidorova, N. & Voorhoeve, M. (2008). Soundness and separability of workflow nets 
in the stepwise refinement approach. In: W.M.P. van der Aalst & E. Best (Eds.). ICATPN 2003, LNCS 2679, (pp. 337–356), Springer-Verlag, Berlin.
Wand, Y. & Weber, R. (1993). On the ontological expressiveness of information systems analysis and design grammars, Journal of Information Systems (3), 217-237.
Wand, Y. & Weber, R. (1995). Towards a theory of deep structure of information systems, Journal of Information Systems 5(3), 203-223. 
Wand, Y. and Weber, R. (2002) Research Commentary: Information Systems and Conceptual Modeling – a Research Agenda, Information Systems Research (13)4, pp. 363-378.
Weber, R. (2004). Conceptual modelling and ontology: Possibilities and pitfalls. Journal of Database Management, 14 (3), 1-20.
Zuberek, W. M. (1991). Timed Petri nets – definitions, properties and applications,” Microelectronics and Reliability, Special Issue on Petri Nets and Related Graph Models, 31(4), 627-644.