Solving reachability problems on data-aware workflows
Riccardo De Masellis Chiara Di Francescomarino Chiara Ghidini Sergio Tessaris







FBK]Riccardo De Masellis
demasellis@gmail.com
FBK]Chiara Di Francescomarinocor2
dfmchiara@fbk.eu
FBK]Chiara Ghidini
ghidini@fbk.eu
FUB]Sergio Tessaris
tessaris@inf.unibz.it
[cor2]Corresponding author


[FBK]Fondazione Bruno Kessler
[FUB]Free University of Bozen-Bolzano







	Recent advances in the field of Business Process Management have brought about several suites able to model complex data objects along with the traditional control flow perspective. Nonetheless, when it comes to formal verification there is still the lack of effective verification tools on imperative data-aware process models and executions: the data perspective is often abstracted away and verification tools are often missing. 

	In this paper we provide a concrete framework for formal verification of reachability properties on imperative data-aware business processes.

        We start with an expressive, yet empirically tractable class of data-aware process models, an extension of Workflow Nets, and we provide a rigorous mapping between the semantics of such models and that of three important paradigms for reasoning about dynamic systems: Action Languages, Classical Planning, and Model-Checking.

        

        Then we perform a comprehensive assessment of the performance of three popular tools supporting the above paradigms in solving reachability problems for imperative data-aware business processes,

        which paves the way for a theoretically well founded and practically viable exploitation of formal verification techniques on data-aware business processes.
    








§ INTRODUCTION





Recent advances in the field of Business Process Management have brought about several suites able to model complex data objects along with the traditional control flow perspective. Nonetheless, when it comes to formal verification, there is still a lack of effective tools on imperative data-aware process models and executions. Indeed, the data perspective is often either abstracted away due to the intrinsic difficulty of handling unbounded data, or investigated only on the theoretical side, providing decidability results for very expressive scenarios without actual verification tools (see <cit.> for an in depth analysis). 
Automated Planning is one of the core areas of AI where theoretical investigations and concrete and robust tools have made possible the reasoning about dynamic systems and domains. 
In the last few years, links between Automated Planning and Business Process Management have started to emerge, either to exploit Automated Planning techniques to address specific problems of Business Process Management (BPM), such as the one of process alignment <cit.>, trace completion <cit.> and process verification <cit.>, or to argue for a wider relationship between the two fields <cit.>. 

Despite this growing interest, a systematic investigation of the actual usefulness of Automated Planing techniques, and of its variant components, is still lacking in the BPM context. In fact, all the work above relies on specific and ad hoc encodings of a given 
task at hand, therefore leveraging specific Planning formalisms, mostly referring either to classical or to action based planning. 
As a consequence, which variants among classical and non-classical planning models <cit.> may be better suited for which complex real-world BPM challenge still remains unstudied, as also noted in the final discussion of <cit.>. This is not negligible, considering the articulated and vast area of different variants and approaches that constitute Automated Planning. 

In this paper we aim at 

 filling this gap by providing a first comprehensive evaluation of different Automated Planning formalisms on a complex and still open challenge in Business Process Management: the provision of a theoretically sound and practically supported data-aware business process verification technique. 
We fulfill this objective by focusing on reachability problems for imperative data-aware business processes.
In particular we [(i)] 

  * exploit an expressive, yet empirically tractable class of data-aware process models, built by extending the well established Workflow Nets formalism <cit.>;

  * we establish a rigorous mapping between our data-aware process models and three important paradigms for reasoning about dynamic systems, namely Action Languages, Classical Planning, and Model Checking[While one may argue that Model Checking does not typically figure among Automated Planning techniques, its usage as an approach to planning is well known and supported by decision procedures and tools. See e.g., <cit.>], based on a common interpretation of the three dynamic systems in terms of transition systems which allows us to

  * perform a first comprehensive assessment of the performance of three popular tools supporting the above paradigms in computing reachability for imperative data-aware business processes. The reasoning formalisms considered in this work exhibit different characteristics, whose impact in terms of reasoning with data-aware workflow net languages is not easily predictable without a robust evaluation. Therefore our work provides not only a solid contribution to a theoretically well founded and practically viable exploitation of Automated Planning to support formal verification on data-aware business processes, but it also paves the way to more general and rigorous investigations on the use of different planning formalisms for BPM. 

The paper is structured as follows. Section <ref> highlights the general motivations behind our work and introduces a running example; Section <ref> provides some background on Workflow Nets <cit.> and  describes the language of originally introduced in <cit.>; Section <ref> describes the approach and the main steps for exploiting the notion of transition system as a bridge between and the chosen Action Languages, Classical Planning, and Model-Checking languages, while details of the specific encodings of the reachability problem in the three specific formalisms are provided in  Sections <ref>, <ref>, and <ref>. Section <ref> introduces the problem of trace repair we use for the the empirical evaluation together with its recast in terms of reachability and lastly Section <ref> presents an extensive evaluation of three well known solvers (i.e., , and ) available for the different formalisms both on synthetic and real life logs. While the evaluation does not indicate a clear “winner”, it empirically shows that adding the data dimension dramatically affects the solvers' ability to return a result as well as their performance. Moreover, characteristics of the trace, such as its dimension, also have an important impact on which solver performs best. The code used and all datasets are publicly available (see Section <ref> for details). The paper ends with related work and concluding remarks. 










§ VERIFICATION OF DATA-AWARE BUSINESS PROCESSES



Commercial and non-commercial BPM suites such as Bonita, Bizagi, YAWL and Camunda support nowadays the modelling of both control and data flow and provide some form of verification support. Following the analysis in <cit.>, they nonetheless offer no or very limited formal verification support when it comes to detect the interdependencies between data and control flow: for instance, they fail to report the critical issue in the process in Figure <ref>. Although this process never terminates, due to the writing of variable y by activity T2, when verified by the tools above this is not revealed, and the process is labeled as potentially able to terminate. Indeed YAWL <cit.> offers verification features limited to the control flow  and thus it wrongly reports that such a process can always reach the termination state. All other tools instead only offer a simulation environment (i.e., no formal verification) that checks whether the process passes through all the sequence flows, without taking into account data.



If we move from actual tools to theoretical frameworks the situation improves. Indeed we may encode the example above in, e.g., Colored Petri Nets (CPN) as it offers verification support that takes into account conditions on labels and some interaction between activities and data. Nonetheless, CPN suffers of usability issues as by encoding data directly within the Net, it is difficult to couple it with tools that are based on common data models such as the relational model or attribute-value pairs.

In order to exploit the verification features of CPN the user would have to manually encode the data flow within the Net and if this may not prove convoluted for examples such as the one in Figure <ref>, the complexity can escalate with more elaborated examples such as the one illustrated in Figure <ref>, which we use as running example throughout the paper.  


 
This (data-aware) workflow, modelling a simple Loan Application process, is composed of 12 tasks (T1-T12). The application starts with task T1 where the customer asks for the application forms. Then, depending on whether the customer is asking for a student loan (loanType=s) or a worker loan (loanType=w) the process continues with a mutually exclusive choice between the sequence of activities T2-T4 and T3-T5. Once the appropriate (student or worker) request is filled, another mutually exclusive choice is presented for the execution: if the amount requested in lower than 5k, then task T6 is executed and only a local approval is needed; if the amount requested is greater than 100k, then the request needs to be approved by the bank committee (task T8); in all the other cases the process continues with task T7. Once the request is approved by means of the appropriate approval task, two parallel activities are executed: the approval is sent to the customer (task T10), and the approval documents are stored in the branch (task T11). Finally the loan is issued (task T12). 
Concerning the interaction between activities and data, task T1 assigns variable loanType to s or w; furthermore task T4 is empowered with the ability to write the variable request with a value smaller or equal than 30k (being this the maximum amount of a student loan). Similarly, task T5 is in charge of writing the variable request up to 500k, which is the maximum amount for a worker.

Given the example above one may check different properties which can be reduced to verifying a reachability problem <cit.>: whether the process admits at least one execution (that is, it can always reach the end from start), or whether termination is guaranteed from start if we also impose the execution of certain tasks. In our example it is easy to see that the interplay of the control and data flow would prevent any execution from start to end that includes both T2 and T8 for instance, as T2 can write the variable request with a value smaller or equal than 30k while T8 is executed only if request has a value greater that 100k. While these properties may be verifiable by exploiting the power of CPN or of extensions of Workflow-Nets (WF-Nets) <cit.>, the ad hoc encoding of the relational data model that is nowadays widely used to express data objects (in BPM suites and beyond) in the these formalisms is among the reasons for their failure to have a significant impact on practical tools. 

In the remaining of the paper we provide a first theoretically sound and empirically extensive investigation on the exploitation of automated planning techniques to compute reachability in data-aware business processes. The reason we focus on reachability is that,

as extensively illustrated in <cit.>, a number of crucial properties that define a sound Business Process can be formulated as reachability properties. These include, e.g., whether, no matter how the process evolves from its beginning, it is always possible to reach its end, or if there are no dead tasks, namely all of them could eventually fire.

Consequently, planning is a natural paradigm for solving reachability problems. Besides, it comes with solid tools that can be directly exploited to support practical applications and lastly it treats data objects as first class citizens, thus enabling a natural encoding of data-aware business processes based on common data models such as the relational data model or attribute-value pairs.




















§ THE FRAMEWORK: 


In this section we first provide the necessary background on Petri Nets and WF-nets (Section <ref>) and then suitably extend WF-nets to represent data and their evolution as transitions are performed (Section <ref>).



 §.§ The Workflow Nets modeling language
 


Petri Nets <cit.> (PN) is a modeling language for the description of distributed systems that has widely been applied to the description and analysis of business processes <cit.>. 

The classical PN is a directed bipartite graph with two node types, called places and transitions, connected via directed arcs. Connections between two nodes of the same type are not allowed. 


	
  A Petri Net is a triple P,T,F where P is a set of places; T is a set of transitions; F⊆ (P × T) ∪ (T × P) is the flow relation describing the arcs between places and transitions (and between transitions and places).

The preset of a transition t is the set of its input places: t = {p ∈ P | (p,t) ∈ F}. The postset of t is the set of its output places: t = {p ∈ P | (t,p) ∈ F}. Definitions of pre- and postsets of places are analogous.
Places in a PN may contain a discrete number of marks called tokens. Any distribution of tokens over the places, formally represented by a total mapping  M : P↦ℕ, represents a configuration of the net called a marking.  



PNs come with a graphical notation where places are represented by means of circles, transitions by means of rectangles and tokens by means of full dots within places. Figure <ref> depicts a PN with a marking M(p_0)=2, M(p_1)=0, M(p_2)=1. The preset and postset of t are {p_0, p_1} and {p_2}, respectively.  

Process tasks are modeled in PNs as transitions while arcs and places constrain their ordering.

For instance, the process in Figure <ref>

exemplifies how PNs can be used to model parallel and mutually exclusive choices, typical of business processes: sequences T2;T4 and T3;T5 are placed on mutually exclusive paths; the same holds for transitions T6, T7, and T8. Transitions T10 and T11 are instead placed on parallel paths. Finally, T9 is needed to prevent connections between nodes of the same type. 


The expressivity of PNs exceeds, in the general case, what is needed to model business processes, which typically have a well-defined starting point and a well-defined ending point. This imposes syntactic restrictions on PNs, that result in the following definition of a workflow net (WF-net) <cit.>.



A PN P,T,F is a WF-net if it has a single source place start, a single sink place end, and every place and every transition is on a path from start to end, i.e., for all n∈ P∪ T, (start,n)∈ F^* and (n,end)∈ F^*, where F^* is the reflexive transitive closure of F.


A marking in a WF-net represents the workflow state of a process execution.

We distinguish two special markings: the initial marking M_s, which has one token in the start place (M_s(start)=1) and all others places are empty (∀ p ∈ P∖start.M_s(p)=0), and the final marking M_e, which has one token in the end place (M_e(end)=1) and all others places are empty (∀ p ∈ P∖end.M_e(p)=0).


The semantics of a PN/WF-net, and in particular the notion of valid firing, defines how transitions route tokens through the net so that they correspond to a process execution. 


	
A firing of a transition t∈ T from M to M' is valid, in symbols M t M', iff

  
  * t is enabled in M, i.e., { p∈ P| M(p)>0}⊇t; and
  
  * the marking M' is such that for every p∈ P:
  
	  M'(p) =
    
      M(p)-1     if p∈t∖t

      M(p)+1      if p∈t∖t

      M(p)     otherwise
    
  


Condition 1. states that a transition is enabled if all its input places contain at least one token; condition 2. states that when t fires it consumes one token from each of its input places and produces one token in each of its output places. 



Notationally, t_1t_2t_3 . . . t_k is a sequence of valid firings that leads from M_0 to M_k iff M_0 t_1 M_1 t_2 M_2 t_3…k-1 M_k-1t_k M_k. In this paper we use the term case of a WF-Net to denote a sequence of valid firings 
M_0 t_1 M_1 t_2 M_2 t_3…k-1 M_k-1t_k M_k 
such that M_0=M_s is the initial marking and M_k=M_e is the final marking. A case is thus a sequence of valid firings that connect the initial to the final marking through the PN.

From now on we concentrate on safe nets, which generalise the class of structured workflows and are the basis for best practices in process modeling <cit.>. The notion of safeness is defined in terms of k-boundedness (see also <cit.>).


A marking of a PN is k-bound if the number of tokens in all places is at most k. A PN is k-bound if the initial marking is k-bound and the marking of all cases is k-bound. If k=1, the PN is safe.  

It is important to notice that our approach can be seamlessly generalized to other classes of PNs, as long as they are k-bound. 



  
Reachability on Petri Nets
  Given a PN and a set of “goal” markings G for its places, the reachability problem amounts to check whether there is a sequence of valid firings from the initial marking M_s of the PN to any of the markings in G.




 §.§ The modeling language
 


<cit.> is a data-aware extension of WF-nets which enriches them with the capability of reasoning on data. extends WF-nets by providing: (i) a model for representing data; (ii) a way to make decisions on actual data values; and (iii) a mechanism to express modifications to data.

It does it by introducing: 


  * a set of variables taking values from possibly different domains (addressing (i));

  * queries on such variables used as transitions preconditions (addressing (ii))

  * variables updates and deletion in the specification of net transitions (addressing (iii)).


follows the approach of state-of-the-art WF-nets with data <cit.>, from which it borrows the above concepts, extending them by allowing reasoning on actual data values as better explained in Section <ref>. 

Throughout the section we use the WF-net in Figure <ref>  extended with data as a running example.



  §.§.§ Data Model


The data model of WF-nets take inspiration from the data model of the IEEE XES standard for describing event logs, which represents data as a set of variables. Variables take values from specific sets on which a partial order can be defined. As customary, we distinguish between the data model, namely the intensional level, from a specific instance of data, i.e., the extensional level.


A data model is a tuple = (, Δ, , ) where:


  *  is a possibly infinite set of variables;

  * Δ = Δ_1, Δ_2, … is a possibly infinite set of domains (not necessarily disjoint);

  * : →Δ is a total and surjective function which associates to each variable v its domain Δ_i;

  *  is a partial function that, given a domain Δ_i, if (Δ_i) is defined, then it returns a partial order (reflexive, antisymmetric and transitive) ≤_Δ_i⊆Δ_i ×Δ_i.[To simplify the model we assume that if {(o,o'), (o', o)}⊆(Δ_i) then o = o'.]



A data model for the loan example is = {loanType, request, loan}, (loanType)=w, s, (request) =, (loan) =, with (loan) and (loanType) being total ordered by the natural ordering ≤ in .

An actual instance of a data model is simply a partial function associating values to variables.

Let = , Δ, , be a data model. An assignment for variables in  is a partial function : →⋃_iΔ_i such that for each v ∈, if (v) is defined, i.e., v ∈(η) where  is the image of η, then we have (v) ∈(v).


Instances of the data model are accessed through a boolean query language, which notably allows for equality and comparison. As will become clearer in Section <ref>, queries are used as guards, i.e., preconditions for the execution of transitions.


Given a data model, the language  is the set of formulas Φ inductively defined according to the following grammar:

    Φ   :=    true |(v) | v = t_2 | t_1 ≤ t_2 |Φ_1 |Φ_1 Φ_2

where v ∈ and t_1, t_2 ∈∪⋃_i Δ_i.


Examples of queries of the loan scenarios are request ≤5k or loanType=w.
Given a formula Φ or a term t, and an assignment , we write Φ[] (respectively t[]) for the formula Φ' (or the term t') where each occurrence of variable v for which  is defined is replaced by (v) (i.e. unassigned variables are not substituted).


Given a data model , an assignment  and a query Φ∈ we say that , satisfies Φ, written D, Φ inductively on the structure of Φ as follows:


  * ,  true;

  * , (v) iff v[] ≠ v;

  * ,  t_1 = t_2 iff t_1[], t_2[] ∉ and t_1[] ≡ t_2[];

  * ,  t_1 ≤ t_2 iff t_1[], t_2[] ∈Δ_i for some i and (Δ_i) is defined and t_1[] ≤_Δ_i t_2[];

  * , Φ iff it is not the case that , Φ;

  * , Φ_1 Φ_2 iff , Φ_1 and , Φ_2.
 


Intuitively,  can be used to check if a variable has an associated value or not (recall that assignment η is a partial function); equality has the intended meaning and t_1 ≤ t_2 evaluates to true iff t_1 and t_2 are values belonging to the same domain Δ_i, such a domain is ordered by a partial order ≤_Δ_i and t_1 is actually less or equal than t_2 according to ≤_Δ_i.


    Let Φ∈, and (Φ) be its active domain – i.e. the set of constants appearing in Φ. Given an assignment  we consider the data model ' as the restriction of  w.r.t. (Φ)∪(), then
    
    , Φ iff ', Φ



The last lemma ca be easily proved by structural induction on the formula, and it makes the queries independent of the actual “abstract” domains enabling the use of finite subsets. Intuitively, the property holds because the query language doesn't include quantification over the variables.



  §.§.§ Data-aware net


Data-AWare nets () are obtained by combining the data model just introduced with a WF-net, and by formally defining how transitions are guarded by queries and how they update/delete data. 


  A  is a tuple ⟨, ,  , ⟩ where:

    
  * =P,T,F is a WF-net;
    
  * =, Δ, , is a data model;
    
  * : T ↦⋃_'⊆ (' ↦ 2^()), where ()=⋃_v ∈(v), is a function that associates each transition to a (partial) function mapping variables to a finite subset of their domain; that is satisfying the property that for each t, (t)(v)⊆(v) for each v in the domain of (t).
    
  * : T ↦ is a function that associates a guard to each transition.
  


Function  associates a guard, namely a query, to each transition. The intuitive semantics is that a transition t can fire if its guard (t) evaluates to true (given the current assignment of values to data). Examples are (T6)=request ≤5k and (T8)= (request ≤99999).

Function  is used to express how a transition t modifies data: after the firing of t, each variable v in the domain of (t) can take any value among a specific finite subset of (v). We have three different cases:

 
  * ∅⊂(t)(v) ⊆(v): t nondeterministically assigns a value from (t)(v) to v;
  
  * (t)(v) = ∅: t deletes the value of v (hence making v undefined);
  
  * v ∉dom((t)): value of v is not modified by t.

Notice that by allowing (t)(v) ⊆(v) in the first bullet above we enable the specification of restrictions for specific tasks. E.g., (T4):request↦0…30k says that T4 writes the request variable and intuitively that students can request a maximum loan of 30k, while (T5):request↦0…500k says that workers can request up to 500k.

The intuitive semantics of  and  is formalized in the notion of valid firing, which is based on the definition of state, and state transition. 
A state includes both the state of the WF-net, namely its marking, and the state of data, namely the assignment. 


A state of a , , , is a pair (,) where  is a marking for P,T,F and  is an assignment for .


Analogously to traditional WF-nets, we distinguish two special states: the initial state (_s, η_s), which is such that M_s is the initial marking of  and η_s is empty, i.e., dom(_0)=∅; and the final states (_e, η_e), such that _e is the final marking of  (no conditions on assignment η_e).


Given a , , ,, a firing of a transition t∈ T is a valid firing from (,) to (','), written as (,)t(','), iff 

  
	  
  * t' is a WF-Net valid firing
  
  
  * , (t), 
  
  
  
  
  
  
  
  
  
  
  * assignment ' is such that, if wr = v |(t)(v)≠∅, del  =  v |(t)(v)=∅:
  
  	
  * its domain dom(') = dom()∪wr∖del;
        
  * for each v∈ dom('):
        
          '(v) =
          
            d ∈(t)(v)     if v∈wr

            (v)      otherwise.
          
        
  



Conditions 2. and 3. extend the notion of valid firing of WF-nets imposing additional pre- and postconditions on data, and in particular preconditions on  and postconditions on '. Specifically, 2. says that for a transition t to be fired its guard (t) must be satisfied by the current assignment . Condition 3. constrains the new state of data: the domain of ' is defined as the union of the domain of η with variables that are written (wr), minus the set of variables that must be deleted (del). Variables in dom(') can indeed be grouped in three sets depending on the effects of t: (i) old = dom(η) ∖wr: variables whose value is unchanged after t; (ii) new = wr∖ dom(η): variables that were undefined but have a value after t; and (iii) overwr = wr∩ dom(η): variables that did have a value and are updated with a new one after t.

The final part of condition 3. says that each variable in new∪overwr takes a value in (t)(v), while variables in old maintain the old value η(v).

Similarly to regular PNs, a case of a is a sequence of valid firings 
(_0,_0)t_0 (_1,_1) t_1…t_k-1 (_k-1,_k-1)t_k(_k,_k) 
such that (_0,_0) is the initial state and (_k,_k) is a final state.


Note that, since we assumed a finite set of transitions and (t) is finite for any transition t, for any model W we can consider its active domain (W) as the set of all constants in (t) and (t) for all the transitions t in W. Moreover, given the Lemma <ref>, we can consider the restriction of the model to the finite set of states defined by the active domain.


   Let W = , , , be a with =, Δ, , and =P,T,F, (W) be its active domain. We consider the data model _W as the restriction of  w.r.t. (W).
   
   The finite version of W, denoted as W, is defined as _W, , ,.


By looking at the definition of valid firing and using Lemma <ref> it's easy to realise that the set of states of W is closed w.r.t. the relation induced by the valid firing. As we'll see later on, this enables us to focus on finite models. 




  
Reachability on 
  Analogously to PN, given a W and a set of goal states G, the reachability problem in amounts to check whether there is a path from the initial state (_s, _s) of W to any of the goal states in G.

  Although such a definition is quite general, in practical applications one may be interested in the reachability of a specific marking M_g of W: in this case, the goal is the set of states of W with M_g as the first component and any assignment in the second (by virtue of Definition <ref> and Lemma <ref>, goal sets defined in this way are always finite).
  
In fact, in this paper we focus on what we call clean termination: the reachability, from the initial state, of any of the final states (_e, _e), namely no tokens in any place except in the sink, which should instead contain a (single) one, and any assignment _e.

We remark, however, that our technique is general and allows for solving reachability of any set of goal states.



















§ REACHABILITY: FROM THEORY TO PRACTICE



In this section we illustrate our approach to verify reachability properties of by exploiting state-of-the-art techniques and tools. 


The paradigms we selected are: action languages, classical planning, and model checking. The specific tools[Hereafter we will often refer to these tools as solvers.] we used are , , and respectively, which in turn are paired with the representation languages , , and briefly summarised later in the paper.

In the following sections, given a W, we show how to encode W in the specific language used by each paradigm/tools and formulate the reachability problem as a termination condition.

We then prove that such encodings are sound and complete, i.e., if a property is verified within one of the encodings, then it is indeed valid for the original , otherwise it is not.

Notably, we do so by providing the semantics of the above tools in terms of transition systems, which provide an intermediate representation that could support the extension of this work to new paradigms/tools whose semantics can be expressed likewise.

This also allows us to use the same structure for the sound and completeness proofs for the encodings, whose main conceptual steps are now described.


In order to exploit the notion of transition systems as a bridge between and the three chosen paradigms, we first need to 
connect transition systems and . To do so, we observe that the behaviour of a is possibly nondeterministic, as in each state, in general, more than one transition can fire: thus, while cases define a possible evolution, a transition system, called reachability graph, captures all possible evolutions.

 
Let W = , , , be a with =, Δ, , and =P,T,F, then its reachability graph is a transition system _W=(T, S, s_0, δ) where:


  * S is the set of states, each representing a (, ) state;

  * s_0 = (_s, _s) is the initial state;

  * S and δ⊆S× T ×S are defined by induction as follows:


  * s_0 ∈S;

  * if (, ) ∈S and (, ) t (',') is a valid firing then s'=(',') ∈S and (s, t, s') ∈δ (and we write s t s' ∈δ).




Let us consider the finite version of W as defined in Definition <ref>; clearly the initial state is among its states and, since the set of its states is closed w.r.t. the relation induced by the valid firings, we get the following: 


  Let W = , , , be a model and W its finite version, then their reachability graphs are identical.

In virtue of the above lemma, in the rest of the paper when we mention the states of a W we intend the states of  W, that is, we restrict to the finite set of states defined by the active domain.

As we are going to show in the following sections, the semantics of the chosen paradigms can be captured by means of transition systems as well. Therefore, given a W, let us denote with (W), (W) and (W) the encodings of W in the respective languages and with _(W), _(W) and _(W) the transition systems generated by the above encodings.

A path of a transition system _W is a sequence of states obtained by starting from the initial state of  and traversing its transitions, thus it represents a possible evolution or behaviour (indeed, each path of  is a trace of W by definition). If we can show that for each path in _∗, with ∗∈(W), (W), (W), there is an equivalent (see later) path in , then the encoding of the reachability problem for W in the ∗ language is sound, as the tool only generates behaviours. Likewise, if for each path in  there is a path in _∗, then the encoding is complete as all behaviours are captured by _∗. This property is called trace equivalence <cit.>, and is of utmost importance for us as trace-equivalent transition systems are indistinguishable by linear properties, which include reachability properties. In other words, if  is trace equivalent with _∗, a reachability property in _∗ is true if and only if it is true in , which allows us to use the above tools for solving our trace repair problem.

In order to formalise trace equivalence we shall first define what does it mean for two paths, generated by different transition system, to be equivalent.

Let π : s_0 t_1 s_1 t_2…t_n s_n and π' : s_0' t_1' s_1' t_2'…t_n' s_n' be paths generated by RG and TS_∗ respectively. We say that π and π' are equivalent if s_0 = s_0' and for each i ∈1, …, n we have that s_i = s_i' and t_i = t_i'.

Technically however, states of _∗ encode information on the state of the net (, ) in different ways, and possibly also use some additional information for technical reasons.

Let us then call _∗(, ) the encoding of (, ), and _∗(t) the encoding of t in the language ∗∈, ,. Then π is equivalent to π' (w.r.t. _∗) if _∗(s_0) = s_0' and for each i ∈1, …, n we have that _∗(s_i) = s_i' and _∗(t_i) = t_i'.



	Let  be a reachability graph and TS_∗ a transition system, then  and _∗ are trace equivalent iff there is an injective function _∗ from the states and transitions of  to those of _∗ s.t.
	
	
  * for each path s_0 t_1 s_1 t_2…t_n s_n of , 
    _∗(s_0) _∗(t_1)_∗(s_1) _∗(t_2)…_∗(t_n)_∗(s_n)
 is a path of _∗; and
	
  * for each path s_0' t_1' s_1' t_2'…t_n' s_n' of _∗ there is a path s_0 t_1 s_1 t_2…t_n s_n of  s.t. _∗(s_0) = s'_0, and _∗(s_i) = s'_i _∗(t_i) = t'_i for 1≤ i≤ n.
	



Recall that the reachability problem expresses whether, given a set of goal states G of W, at least one of those can be reached from the initial one (M_s, η_s). Given Definition <ref>, it immediately follows that if  and _∗ are trace equivalent, then, if a state is reachable in , it is also reachable in _∗ by performing the very same transitions and vice-versa, thus they satisfy the same reachability properties.



Note that, in order to exploit the specific algorithms to verify reachability in the “target” system, we need also to show that the corresponding language for specifying the termination property is expressive enough to capture all and only the states corresponding to the final states.












In the next sections, for each language ∗∈, , we 
prove that  and _∗ are trace equivalent, and therefore they can be used to solve the above mentioned reachability problem. These sections are organised in three parts: in the first one the specific formalism is introduced, then the following ones provide the encoding and the proofs.












§ THE ENCODING IN ACTION LANGUAGES


In this section we will show how the transition system underlying can be represented by means of the so called action languages <cit.>, in order to use the ASP based solver to verify reachability properties. In our work we will be focusing on the language as introduced in <cit.>, but the same idea can be applied to different frameworks (e.g.  <cit.>).



 §.§ The  action language


An action description in the language includes a finite set of symbols: fluent, and action constants. Each fluent constant is associated to a finite set, of cardinality greater or equal than 2, called the domain. Boolean fluents have the domain equal to {, }. An atom is an expression of the form f = v, where f is a fluent constant, and v is an element of its domain.

A description contains static and dynamic laws; the former are 
expressions of the type

    |A_0 if  A_1,…, A_n ifcons  A_n+1,…, A_m|

while the second are of the form

    |A_0 after  A'_1,…, A'_n  ifcons  A_n+1,…, A_m|

with 0 ≤ n≤ m, where A_0, A_1,…, A_m are atoms, and A'_1,…, A'_n can be atoms or action constants.

Intuitively, static laws assert that each state satisfying A_1,…, A_n and where A_n+1,…, A_m can be assumed satisfies A_0 as well. In dynamic laws, instead, A'_1,…, A'_n must be satisfied in the preceding state. An action constant is satisfied if the action is being “executed” in a specific state.

Initial states can be specified with statements of the form

    | initially  A|

where A is an atom, that is, an expression of the form f=v.

Semantics of a description  is given in terms of a translation into a sequence P_ℓ() of ASP programs where atoms are of the form i : A with 0≤ i≤ℓ, and A being a fluent or action constant. Each static law (<ref>) is translated as the set of ASP rules with strong negation

  i : A_0 ←i: A_1,…, i : A_n, (i:A_n+1),…, (i:A_m)

where 0≤ i ≤ℓ. Each dynamic law (<ref>) is translated as

  i+1 : A_0 ←i: A_1,…, i : A_n, (i+1:A_n+1),…, (i+1:A_m)

where 0≤ i< ℓ. If A_0 is |false| the corresponding rules are constraints.

Initial state constraints of the form initially f=v force the value of fluent f in the first state and are therefore translated as

  0:f=v


In addition to the rules corresponding to static / dynamic laws and initial constraints, the ASP program contains rules to: [(i)] 
  * set the initial state by nondeterministically assigning the values of fluents

    0:f=v  (0:f=v)

for each fluent f and elements v of its domain; 
  * force total knowledge on action execution

    i:a  (i:a)

for each action constant a and i<ℓ; and finally 
  * impose existence and uniqueness of values for the fluents

    ← (i:f=v_1), …,  (i:f=v_k) 
     i:f=v    ← i:f=w

for any fluent f, v, v_1, …, v_k, w elements of its domain, v≠ w, and i≤ℓ.

Given a stable model M_ℓ of P_ℓ(), we indicate as i(M_ℓ) the variable assignments in the corresponding state 0≤ i≤ℓ:

    i(M_ℓ) = { f↦o |f∈, ifo∈M_ℓ}

Note that the above rules on fluents guarantee that i(M_ℓ) is well defined: total and functional.

Although not originally introduced in <cit.>, we introduce the implicit transition system induced by a description in order to relate it with the reachability graph as explained in Section <ref>.


    Let be a description over the set of fluent, and of action constants. Let S_ be the set of all total assignments for fluents in satisfying the domain restrictions. Then its transition system _()=(, S, S_0, δ) is defined as:
    
        
  * S_0⊆ S_ is the set of initial states
        
    S_0 = {0(M_0) |M_0 is a stable model of P_0()}

        
  * S⊆ S_ and δ⊆ S_× 2^× S_ are the minimum sets s.t.:
        
        
  * S_0 ⊆ S;
        
  * if M_ℓ+1 is a stable model of P_ℓ+1() for some ℓ≥ 0, and ℓ(M_ℓ+1)∈ S; then ℓ+1(M_ℓ+1)∈ S and (ℓ(M_ℓ+1),{a∈|ℓa∈ M_ℓ+1},ℓ+1(M_ℓ+1))∈δ
        
     


While states of a transition system can be easily compared with reachability graph states, enables concurrent and “empty” transitions (δ⊆ S_× 2^× S_); therefore the encoding should take that into account (see Section <ref> for details).

The solver

 we use in Section <ref> to compute reachability on problems expressed with the language is the Coala compiler and ASP solver <cit.>. Within the tool, the final states to define the reachability problem can be specified using a set of (possibly negated) atoms using |finally| statements analogous to the |initially| previously described in Equation (<ref>).



 §.§ Encoding in 



Given a W, its encoding in the , denoted as (W), introduces:[(i)] 
  * a fluent for each variable in W, with the domain corresponding to the variable domain plus a special constant (representing the fact that a variable is not assigned); 
  * a boolean fluent for each place; and 
  * an action constant for each transition. To simplify the notation we will use the same constant names. Moreover, without loss of generality we assume that guards are in conjunctive normal form.[We do not expect huge guards, therefore we ignore the potential exponential blowup due to the conversion to CNF of arbitrary queries.]

Let ⟨,,,⟩ be a as defined in Definition <ref>, where =P,T,F and =, Δ, ,. Let '⊆ be the (finite) set of variables appearing in the model, and (v) be the active domain of v∈', that is, (v) = ⋃_t∈ T(t)(v).
The encoding (W) starts by representing in key properties of transactions in a :


	
  * All fluents are “inertial”, that is their value propagates through states unless their value is changed by the transitions:

    |v=o after v=o ifcons v=o|      for v∈' and o∈(v)∪{}
       |p=o after p=o ifcons p=o|      for p∈ P and o∈{true, false}



  * Transitions modify the value of places and variables; for each transition |t|∈ T:

    |p=false after t|      for all |p|∈t∖t
       |p=true after t|      for all |p|∈t∖t
       |v=d after t ifcons v=d|      for all (|v|,|d|)∈(t) 
       |v=null after t|      for all v s.t. (t)(v) = ∅
       |false after t ifcons v=d|      5cmfor all v∈' s.t. (t)(v)≠∅,
        d∈{}∪(v)∖(t)(v)


Note that equation (<ref>) ensures that after the execution of a transition the value of a variable modified by it must be among the legal values.


  * Transitions cannot be executed in parallel:

    |false after t, s|      for (t, |s|)∈ T× T  and |t|≠|s|



  * Transitions cannot be executed unless input places are active:

    false after t, p=false      for |t|∈ T  and |p|∈t



  * Initially, all the places but the start one are false and variables are unassigned

    initially start=true
       initially p=false      for |p|∈ P  and |p|≠start
       initially v=null      for |v|∈'



  * In a state progression does not require an actual action. To disallow this scenario we need to track states that have been reached without the execution of an action. This is achieved by including an additional boolean fluent trans that is true if a state has been reached after a transition:

    trans=true after t      for t∈ T
       initially trans=true



We now describe the encoding in of queries. Due to the rule-based essence of we consider a Disjunctive Normal Form characterisation of the queries defined in Definition <ref>): for any query Φ there is an equivalent normal form Φ[Φ is not unique.] s.t. Φ=⋁_i=1^k t_1^i… t_ℓ_i^i where each term t_j^i is either of the form v = o or (v).

To prove the existence of such formula Φ we consider the disjunctive normal form of Φ, and to each term not in the form v = o or (v) we apply the following equivalences that are valid when considering the finite domain data model _W (which we can consider without loss of generality because of Lemma <ref>):

    v_1 = v_2    ≡⋁_o∈(v_1)∩(v_2) v_1 = o  v_2 = o 
     (v_1 = v_2)    ≡⋁_(o_1,o_2)∈(v_1)×(v_2), o_1≠ o_2 v_1 = o_1  v_2 = o_2 
     (v = o )    ≡⋁_o∈(v)∖{o} v = o 
    
       v ≤ o    ≡⋁_(o',o)∈(v) v = o 
     
       o ≤ v    ≡⋁_(o,o')∈(v) v = o 
     
       v_1 ≤ v_2    ≡⋁_(o_1,o_2)∈(v_1)∩(v_2) v_1 = o_1  v_2 = o_2 
    (v)    ≡⋁_o∈(v) v = o


Given a query Φ, and its Disjunctive Normal Form characterisation  Φ=⋁_i=1^k t_1^i… t_ℓ_i^i, we define the translation Φ of Φ as ⋁_i=1^k t_1^i…t_ℓ_i^i; where v = o↦v = o and (v)↦v = null.[This rather inefficient explicit representation is convenient for the proofs, and it can be optimised in the actual ASP implementation via grounding techniques and explicit representation of the orderings by means of ad hoc predicates.]

Having encoded the queries we can now encode the fact that transitions cannot be executed unless the guards are satisfied. This condition is encoded as a set of dynamic constraints preventing the execution unless at least one of the clauses of the guard is not satisfied.

For each transition t s.t. (t) ≢true we consider (t)=⋁_i=1^k t_1^i…t_ℓ_i^i and include the following dynamic constraints:

    !false after t, !t_1^1, …, t_ℓ_1^1
       …
       !false after t, !t_1^k, …, t_ℓ_k^k

The set of final states for the reachability problem can be specified as the ones in which all place fluents are  but the one corresponding to the sink:

    finally sink=true
       finally p=false      for |p|∈ P  and |p|≠sink





 §.§ Correctness and completeness of the  encoding


Let () be the encoding of a . In this section we are going to show that _() and the reachability graph of are trace equivalent as per Definition <ref>. This section reports all the main  steps involved, while further technical details and proofs are presented in <ref>.

To simplify the proofs we first relate sequences of valid firings in  of arbitrary length ℓ to stable models of P_ℓ(()). In fact, the definition of _() (Definition <ref>) is based on the notion of stable models.

To map sequences of valid firings into stable models we observe that stable models P_ℓ(()) include both the fluent assignments and the information regarding the action constants that “cause” a specific state transition; therefore we split the mapping in two parts to separate these two distinct aspects:

    Let ρ = (_0,_0)t_0(_1,_1)t_2…t_ℓ-1(_ℓ,_ℓ) be a sequence of valid firings in (with ℓ≥ 0).[We consider (_0,_0) a sequence of size 0.] The mapping _i(ρ) (for 0≤ i≤ℓ) is defined as following:
    
    _i^ν(ρ) =    { i:p=, (i:p=)| p∈ P, _i(p) > 0 }∪
       { i:p=, (i:p=)| p∈ P, _i(p) = 0 }∪
       { i:v=o, (i:v=) | v∈', _i(v) = o }∪
       { i:v=| v∈', _i(v)  is undefined}∪
       {(i:v=o) | v∈', o∈(v), _i(v) ≠ o  or _i(v)  is undefined}∪
       { i:trans=, (i:trans=)}
    _i^τ(ρ) =    ∅   for i≥ℓ
    { i:t_i}∪{(i:t)| t∈ T, t≠ t_i}   for i<ℓ
    _i(ρ) =    _i^ν(ρ) ∪_i^τ(ρ)



Note that Definition <ref>, together with Definition <ref>, enable us to say that the firing (_i,_i)t_i(_i+1,_i+1) in ρ corresponds to the _() transition i(_i^ν(ρ)){t| i:t ∈_i^τ(ρ)}i+1(_i+1^ν(ρ)). Moreover, the definition of _i^ν(·) depends only on the state (_i,_i) and not on the selected path ρ, which provides just the “witness” for being a state of the reachability graph.

Before proving completeness and correctness we show that the states of the two transition systems preserve the satisfiability of [_] queries:

lemmalemmaBCquery
  Let   be a model, and ρ = (_0,_0)t_0(_1,_1)t_2…t_ℓ-1(_ℓ,_ℓ) be a sequence of valid firings of (with ℓ≥ 0).

  For every state (_i, _i) (0≤ i≤ℓ) and query Φ∈[_]
    
    _i, _i Φ iff _i(ρ) i:Φ

  where i:Φ is the formula where i:· is placed in front of each term t, and _i(ρ) i:t iff i:t∈_i(ρ).

The proof is by induction on [_].

We are now ready to state the completeness of encoding.

[Completeness of encoding]lemmalemmaBCencComplete
    Let be a and () its encoding, then for any ℓ≥ 0 if ρ is a sequence of valid firings of of length ℓ, then ⋃_i=0^ℓ_i(ρ) is a stable model of P_ℓ(()).


To prove correctness we first prove few properties about the reachability graph _().

lemmalemmaDWNetBCmap
    Let _()=(, S, S_0, δ), then
    
        
  * S_0 = { s_0 };
        
  * if (s,A,s')∈δ then |A| = 1.
      
 
By using this lemma, given a model , we can compare the transition system corresponding to its reachability graph _W=(T, S, s_0, δ) to _() (Definition <ref>). This because it guarantees that there is a single initial state, and the transitions (the δ of Definition <ref>) contain exactly one action each.[allows transitions without or with multiple parallel actions.] The following definition introduces the mapping from stable models to sequences of valid firings.


    For any stable model M_ℓ of P_ℓ(()) with ℓ≥ 0 we also define the “inverse” relation _i(M_ℓ) = (_i, _i) for 0≤ i≤ℓ:
    
    _i =    { (p, 1)| p∈ P, i(M_ℓ)(p)=}∪
       { (p, 0)| p∈ P, i(M_ℓ)(p)=}
    _i =    { (v, o)| v∈ V', i(M_ℓ)(v)=o, o≠}

    and the transition τ_i(M_ℓ) for 0≤ i< ℓ:
    
    τ_i(M_ℓ) = a       s.t. (i:a)∈ M_ℓ

    where a is an action constant in P_ℓ(()).


[Correctness of encoding]lemmalemmaBCencCorrect
    Let be a and () its encoding, then for any ℓ≥ 0 if M_ℓ is a stable model of P_ℓ(()), then 
        
    ρ = _0(M_ℓ) τ_0(M_ℓ)_1(M_ℓ) τ_1(M_ℓ)…τ_ℓ-1(M_ℓ)_ℓ(M_ℓ)

        is a sequence of valid firings of of length ℓ.


We are now ready to state the main result of this section, namely trace equivalence between (()) and RG=(T, S, s_0, δ). We do that by instantiating the abstract notion of _∗ introduced in Section <ref> to , and by using the completeness and correctness lemmata <ref> and <ref>.


  Let  be a model and =(T, S, s_0, δ) its reachability graph, then _() and  are trace equivalent.



  To demonstrate trace equivalence we define the mapping _(·) as follows: for each (,)
  
    _((,)) =    { (p,)| (p,1)∈}∪
       {(p,)| (p,0)∈}∪
       {(v,)| v  not in the domain of }∪

   and _(t) = {t} for each transition in T.
   
  Note that, by construction, for each sequence of valid firings (_0,_0)t_0(_1,_1)t_2…t_ℓ-1(_ℓ,_ℓ),   _((_i,_i))=i(_i^ν(ρ)), and for any stable model M_ℓ of P_ℓ(()) _(_i(M_ℓ)) = i(M_ℓ).

  Therefore the proof is a consequence of the  lemmata <ref> and <ref>.


The trace equivalence demonstrated by Theorem <ref> enables the use of ASP based planning to verify the existence of a plan satisfying the termination conditions expressed in Equation (<ref>). 

Moreover, it is immediate to verify that the set of final states as characterised in Equation (<ref>) corresponds to all and only the final states of the model mapped via _(·).














§ THE ENCODING IN CLASSICAL PLANNING


Automated planning has been widely employed as a reasoning framework to verify reachability properties of finite transition systems. It is therefore natural to include it among the verification tools that we considered for our evaluation.

In order to be as general as possible without committing ourselves to a specific planner we based our encoding on the de facto standard, namely PDDL <cit.>, however to simplify the formal discussion we will adopt the state-variable representation <cit.> instead of the more common classical. There is no loss of generality, since it is known that state-variable planning domains can be translated to classical planning domains with at most a linear increase in size.



 §.§ State-Variable Representation of Planning Problems


A detailed description of the planning formalism is outside the scope of this paper and the reader is referred to the relevant literature – e.g. <cit.> – however in this section we briefly outline the main concepts for our setting.

Given a set of objects B, a state variable is a symbol v and an associated domain Range(v)⊆ B.[In this context we restrict to state variables as 0-ary functions.] The (finite) set of all the variables is denoted by X, a variable assignment over X maps each variable v to one of the objects in Range(v). In addition, we will consider a set of rigid relations R over B that represent non-temporal relations among elements of the domain.

An atom is a term of the form , r(z_1,…, z_n), or v = z_1; where r∈ R, v∈ X, and z_i are either constants or parameters.[We use the term parameter to denote mathematical variables, to avoid confusion with state variables.] A literal is a positive or negated atom.

An action template is a tuple α = ((α), (α), (α)): (α) is an expression act(z_1,…,z_k) where act is an (unique) action name and z_i are parameters with an associated finite Range(z_i)⊆ B, (α) is a set of literals (the preconditions), and (α) is a set of assignments v← z where z is a constant or parameter. All parameters in α must be included in (α). A state-variable action  (or just action) is a ground template action where the parameters are substituted by constants from their corresponding ranges.


    A classical planning domain is a triple Σ = (S, A, γ) where
    
        
  * S the set of variable assignments over X;
        
  * A is the set of all actions;
        
  * γ : S'× A' → S with S'× A' = { (s,a)∈ S× A |(a)  is satisfied in  S} and
        
    γ(s,a) =    { (v,w) | v ← w ∈(a) }
       { (v,w)∈ s |∀ w'∈ B  v ← w' ∉(a) }.

    



    A plan is a finite sequence of actions π = ⟨ a_1, …, a_n ⟩, or the empty plan ⟨⟩. A plan is applicable to a state s_0 if there are states s_1,…, s_n s.t. γ(s_i-1, a_i) = s_i (empty plans are always applicable).
    
    If π is applicable to s, we extend the notation for γ to include plans γ(s, π): where γ(s, ⟨⟩) = s and γ(s, π.a) = γ(γ(s, π), a).[⟨ a_1,…, a_n⟩.a is defined as ⟨ a_1,…, a_n, a⟩.]



    A state-variable planning problem is a triple P = (Σ, s_o, g) where Σ is a planning domain, s_0 the initial state, and g a set of ground literals called the goal.
    
    A solution for P is a plan π s.t. γ(s_0, π) satisfies g.


To simplify the encoding introduced in Section <ref> we will consider an extended language for the precondition of action templates. This extended language enables the use of boolean combinations as well as atoms in which state variables can be used in place of constants, that is, v = v', or r(v_1,…, v_n). Planning domains using the extended language can be encoded into classical planning domains by considering the disjunctive normal form of the original preconditions and introducing a new template for each conjunct.[This transformation might introduce an exponential blow-up of the domain due to the DNF transformation. However, this can be prevented in the overall conversion from by imposing the DNF restriction in the original model as well.]

The extended syntax concerning state variables can be dealt with by introducing a (new) parameter for each variable in the precondition appearing within a rigid relation or in the left hand side of an equality. This new parameter z_v for the variable v will be substituted to the original occurrence of v and the new term v = z_v is included in the precondition.

The above definitions can be re-casted for the extended language, and plans for the extended and corresponding classical planning domains can be related via a surjection projecting the “duplicated” template (introduced by the DNF conversion) into the original ones.



 §.§ Encoding in 



The main idea behind the encoding of a W in , denoted with (W), is similar to the one presented in Section <ref>, where state variables are used to represent both places and variables, and actions represent transitions. The main differences lay in the fact that: (i) nondeterminism in the assignments must be encoded by means of grounding of action schemata; and (ii) the language for preconditions does not include disjunction, and thus more than a schema may correspond to a single transition.

Let = ⟨,,,⟩ be a as defined in Definition <ref>, where =P,T,F and =, Δ, ,. '⊆ be the (finite) set of variables appearing in the model, and (v) be the active domain of v∈', that is, (v) = ⋃_t∈ T(t)(v).

The encoding () is defined by introducing: a state variable for each v∈', with domain corresponding to the domain of v plus a special constant ; and a boolean state variable for each place p∈ P. To simplify the notation we will use the same constant names.
In addition to the state variables we introduce a rigid binary relation  to encode the partial ordering of Definition <ref>:

    = ⋃_Δ_i ∈Δ{ (o, o')∈Δ_i^2| o≤_Δ_i o'}

and unary relations wr_t,v to encode the range (t)(v) of Definition <ref>:

    wr_t,v   = { o | o∈(t)(v) }      for all t∈ T and v∈ s.t. (t)(v)≠∅
    
        wr_t,v   = {}      for all t∈ T and v∈ s.t. (t)(v)=∅

   
Note that Lemma <ref> guarantees the finiteness of , while (t)(v) are finite by definition.

Given a query Φ  (Definition <ref>) we denote with Φ its translation in the preconditions, defined as:

    true   = 
    (v)   =  (v =  ) 
    v = t_2   =   (v =  )  (v = t_2) 
    t_1 ≤ t_2   =  (t_1, t_2) 
    Φ_1   =  Φ_1
    Φ_1 Φ_2   =  Φ_1Φ_2


Analogously to the previous section we introduce an action template for each transition in  where preconditions, in addition to the guard, include the marking of the network (token in the places). The selection of the actual value to be assigned to the updated variables is selected by means of action parameters (one for each variable).
Formally, 
	
 let t be a transition in , and {v_1, …, v_k} the variables in the domain of (t); then () includes the action template α_t = ((α_t), (α_t), (α_t)) defined as follows:


    (α_t)    = t(z_v_1, …, z_v_k)       
    (α_t)    = (t)⋀_v∈{v_1, …, v_k} wr_t,v(z_v) ⋀_p∈t (p = )
    (α_t)    = ⋀_v∈{v_1, …, v_k} (v = z_v )⋀_p∈t∖t (p = ) ⋀_p∈t (p = )


Analogously to the case, the goal of the planning problem is described by the set of ground literals corresponding to the state in which all place fluents are  but the one corresponding to the sink:

    sink = 
       p=      for p∈ P ∖{sink}





 §.§ Correctness and completeness of the  encoding


To show that the transition systems underlying a W and its encoding (W) are equivalent we define a bijective mapping between the states of the two systems and we show that for each valid firing in W there is a ground action “connecting” the image of the states in γ and vice-versa.

Let (,) be an arbitrary state of , we define the mapping  to states of  () as:

    (,) =    { v↦ v[] | v∈, v[]≠ v }∪
       { v↦| v∈, v[] = v }∪
       { p↦| p∈ P, (p)>0 }∪
       { p↦| p∈ P, (p)=0 }

Since we restrict to 1-safe nets, it is easy to show that  is a bijection; moreover:

  Let   be a model, for every state (, ) of  and query Φ∈[_]
    
    , Φ iff (,)Φ




    The statement can be easily proved by induction on [_] formulae and by using Equation (<ref>) for base cases.


Now we can show that valid firings of corresponds to transitions in the planning domain

lemmalemmaPDDMenc
    Let  a model and () its encoding into a planning domain:
    
        
  * if (,)t(',') is a valid firing of , then there is a ground action a_t of α_t s.t. ((,), a_t, (','))∈γ;
        
  * if there is a ground action a_t of α_t s.t. (s, a_t, s')∈γ, then (s)t(s') is a valid firing of .
    


The proof is in <ref>.

To compare the PDDL encoding of  with the reachability graph _=(T, S, s_0, δ) (introduced in Definition <ref>) we consider the transition system _() derived from the planning domain ().


    Let  a model. The transition system _() = (T, S_, s_0, δ_) is defined as follows:
    
        
  * s_0 = (s_0)
        
  * S_ is the minimum set that includes s_0 and if s∈ S_ and (s, a_t, s')∈γ then s'∈ S_
        
  * δ_ = { (s,t,s')∈ S_× T × S_| (s, a_t, s')∈γ, a_t  is a ground action of α_t }
    



    Let  be a model, then _ and _() are trace equivalent.



	We define _(·) as the restriction of  (as defined in Definition <ref>) to the set of states of _, and the identity w.r.t. the transitions. We show that _(·) satisfies the properties of Definition <ref> by induction on the length of the paths.
	
	The base case of a path of length 0 is satisfied because s_0 = _(s_0) = (s_0) is a state in _() by Definition <ref>.
	
    For the inductive step we just need to consider the last element of the paths:
    
    	
  * If s_0 t_1 s_1 t_2… s_n-1t s_n is a path in _, then s_n-1t s_n is a valid firing, therefore by Lemma <ref> there is a ground action a_t of α_t s.t. ((s_n-1), a_t, (s_n))∈γ. By Definition <ref> ((s_n-1), t, (s_n)) is a transition of _(), and so is (_(s_n-1), _(t), _(s_n)).
        
  * If {(s_0,t_1,s_1),…,(s_n-1,t,s_n)}⊆δ_ then there is a ground action a_t of α_t s.t. (s_n-1, a_t, s_n)∈γ; therefore (s_n-1)t(s_n) is a valid firing of  by Lemma <ref>. So (s_n-1) and (s_n) are states of _ and _((s_i)) = s_i by construction.
    


The trace equivalence demonstrated by Theorem <ref> enables the use of classical planning tools to verify the existence of a plan satisfying the termination conditions expressed in Equation <ref>.

Moreover, it is immediate to verify that the set of states as characterised by the goal in Equation <ref> corresponds to all and only the final states of the model mapped via _(·).

















§ THE ENCODING IN 



Model checking <cit.> tools take as input a specification of system executions and a temporal property to be checked on such executions. The output is “true” when the system satisfies the property, otherwise “false” is returned as well as a counterexample showing one (among the possibly many) evolution that falsifies the formula. In particular, reachability properties can be easily expressed as liveness formulas of the kind: “Eventually one of the states satisfying some property is visited.”

In , the system is specified in an input language inspired by smv <cit.> and the properties in a temporal language, such as linear-time temporal logic (ltl, see <cit.> Chapter 5, for an introduction).

Let W be a and _W its reachability graph. We show how to encode _W in the input language and the reachability of a set of goal states as a ltl formula such that, when processed by , an execution reaching one of the final states is generated in the form of a counterexample, if any.






 §.§ The input language


Many of the available tools for traditional model checking, including , deal with infinite-executions systems, and hence they require systems transition relation to be left-total. On the contrary, our 

 models are based on workflow-nets which by definition represent process which usually terminates. Also, in transitions have no label. 
For this reason, we adapt the reachability graph so as to have infinite paths and no transition labels, and we call such a modified reachability graph _W^∼. This kind of transformations are customary using tools requiring infinite-executions to describe finite-execution ones. Despite _W^∼ being semantically different from _W, it is also possible to tweak the formal properties to be verified in such a way that the adaptation is sound and complete. From here on we abstract from such technical subtleties and refer to <cit.> for the details.

Intuitively, _W^∼ is obtained from _W by: [(i)] 
  * moving transition labels in the source state; 
  * adding a fresh self-looping (with transition ) state s_ϵ and 
  * adding a () transition from every sink state of _W to s_ϵ, as the following definition formalizes.

 
Let _W=(T, S, s_0, δ) be a reachability graph of a . We build a transition system _W^∼ = (T ∪, , S, S_0, δ) as follows:


  * the set of states are triples (, , t) with t ∈ T ∪, where we distinguish the special state s_ϵ = (_ϵ, _ϵ, ) where _ϵ and _ϵ are arbitrary;

  * set S_0 is built as follows: if there exists (_0, _0) t (', ') ∈δ then S_0 =  (_0, _0, t) |∃ t, ', '.(_0, _0) t (', ') ∈δ, otherwise S_0 = (_0, _0, ).

  * S and δ⊆ S × S are the least sets s.t.:

  * S_0 ∪s_ϵ⊆ S;

  * s_ϵ s_ϵ∈δ;

  * if (, ) t (', ') ∈δ then:


  * if (', '), t', (”, ”) ∈δ then s=(, , t)  s'=(', ', t') ∈δ and s, s' ∈ S;

  * otherwise s=(, , t)  s'=(', ', ) ∈δ, (s', s_ϵ) ∈δ and s, s' ∈ S;


  * if δ = ∅ then (_0, _0, )  s_ϵ∈δ (notice that if δ = ∅ then S_0 = (_0, _0, )).










We now describe from a very high-level perspective the syntax and semantics of , i.e., how a transition system _(m) is built given syntactic description of a so-called module m. In general, allows for several modules descriptions, but in our case one it is enough to represent _W^∼.



A module is specified by means of several sections and, in particular:


  * A VAR section where a set of variables and their domains are defined. Each complete assignment of values to variables is a state of the module.

  * A INIT section where a formula representing the initial state(s) of the system is defined.
  
  * A TRANS section where the transition relation between states is specified in a declarative way by means of a list of ordered rules r_1, …, r_n in a switch-case block[There are several equivalent ways to describe a transition relation in , we just choose one.]. Each rule r_i has the form (pre_i, post_i), where pre_i is (a formula representing) a precondition on the current state and post_i is (a formula representing) a postcondition on the next state (and possibly the current state). In , postconditions are expressed by means of primed variables, namely v̂'= 𝑣𝑎𝑙𝑢𝑒 means that in the next state variable v̂ is assigned to 𝑣𝑎𝑙𝑢𝑒. Intuitively, state q' is a successor of q iff i is the smallest index such that q models pre_i and (q, q') models post_i. With slight notational abuse we write q φ when the current state (recall that a state is an assignment of values to variables) satisfies a formula containing only unprimed variables and we write (q, q') φ' when the pair current state, next state satisfies a formula containing both primed and unprimed variables.
  
  

   
Let m be a module and  be the set of variables in its VAR section. Module 𝑚 defines a transition system _(m)=(, Q, Q_0, ρ) where:


  * Q is the set of states, each representing a total assignment of domain values to variables;

  * the initial states Q_0 are those satisfying the formula in the INIT section;

  * states Q and transition function ρ⊆ Q × Q are defined by mutual induction as follows:


  * Q_0 ⊆ Q;

  * if q ∈ Q and i is the smallest index such that q  pre_i (such an i is required to exist by ), then (q, q') ∈ρ and q' is such that (q, q')  post_i.







 §.§ Encoding of in 



We present our encoding of W in for each section of the module (W).
  

  
VAR section We have:


  * one boolean variable p̂∈P̂ for each place p ∈ P;

  * one t̂r̂ variable which ranges over T ∪,;

  * one variable v̂∈ for each v ∈ ranging over (v) ∪ where  it is a special value not contained in any of the (v).


Let _(, ) be the encoding for markings and assignments to formulas in of the kind:

    ⋀_p ∈ Pp̂= , ⋀_v ∈v̂_̂î=d

where p̂= iff (p)=1 and p̂= otherwise; v̂_̂î=d iff (v) is defined; and (v)=d or d= if (v) is undefined.
Besides, let _(t) be the encoding of transition t to the formula t̂r̂ = t, for t ∈ T ∪,.

 
The pair of functions _(, ) and _(t) are a bijection between states S of _W^∼ and states Q of _(W).




  
INIT section
We have:


    [       _ (_0, _0);            t̂r̂≠;  ⋀_t ∈ Tt̂r̂=t t; t̂r̂= (⋀_t ∈ Tt) ]

where t is a formula representing the preconditions for executing t according to the semantics of the : it thus consists of guard (t) as well as preconditions on the input set t.



  
TRANS section 
We have:



  * one rule for each t ∈ T which has:

    pre := _(t)



    [                         post :=                  ∀ p ∈t∖t. p̂ =;                                                  ∀ p ∈t∖t. p̂ =;                                                 p̂=p̂ otherwise;                                 ∀ v ∈((t)) (t)(v) ≠∅. v̂∈(t)(v);                                      ∀ v ∈((t)) (t)(v) = ∅. v̂=;                                                 v̂=v̂ otherwise;                                                 ⋀_t ∈ Tt̂r̂=t t;                                                t̂r̂= (⋀_t ∈ Tt);                                                      t̂r̂=t̂r̂= ]

where t is likewise formula t but with all its variables primed (thus referring to the next state). Intuitively, the postcondition contains:  [(i)] 
  * a condition on the (next) values of pre- and post-sets of t; 
  * a condition on the (next) values of the variables according to function  of the and 
  * conditions on the (next) value of variable t̂r̂: next value of t̂r̂ is t, only if the (next) state is consistent with the preconditions for executing t. 



  * a rule for t̂r̂=:

    pre := _()



    [   post :=     t̂r̂=;           _(_ϵ, _ϵ) ]




  * a rule for looping in the ended state with t̂r̂=:

    pre := _()



    [   post :=     t̂r̂=;           _(_ϵ, _ϵ) ]




We notice that since ⋃ pre_i form a partition for all possible values of t̂r̂ we have that for each assignment to , i.e., state q, there exists a unique i such that q  pre_i. In other words, the ordering of rules does not matter.



 §.§ Correctness and completeness of the encoding


As introduced in Section <ref>, we prove soundness and completeness of the encoding by proving trace equivalence between _W^∼ and the transition system _(W) generated by module (W). A standard technique to prove trace equivalence amounts, in fact, to provide a bisimulation relation between states of _W^∼ and _(W) as the latter implies the former <cit.>.

A bisimulation relation has a co-inductive definition which says that states of the two transition systems are bisimilar if:
[(i)]

  * they satisfy the same local properties;
  
  * every transition from one state can be mimicked by the other state and their arrival states are again in bisimulation (and vice-versa).

If every initial states of _W^∼ is in bisimulation with an initial state of _(W), then they are trace equivalent, as any trace start from an initial state.

 
_W^∼=(T, S, S_0, δ) be the reachability graph of a and _(W)=(, Q, q_0, ρ) be the transition system of its encoding. We define bisimulation relation B ⊆ S × Q as follows: (s=(M, , t), q) ∈ B implies:


  * q = _(, ) _(t);

  * for all s  s ∈δ there exists q' ∈ Q such that q  q' ∈ρ and (s', q') ∈ B; and

  * for all q  q ∈ρ there exists s' ∈ S such that s  s' ∈δ and (s', q') ∈ B.



We prove that there exists a bisimulation between _W^∼ and _(W) by showing one.

theoremthNuxmvSoundComp

  Let R ⊆ S × Q be such that ((s=(M, , t), q) ∈ R) iff q = _(, ) _(t). Then:
  
  
  * R is a bisimulation relation;
  
  * for each s_0 ∈ S_0 there exists q_0 ∈ Q_0 such that (s_0, q_0) ∈ R and vice versa.
    
  
  


We first prove 1.

Let s'=(', ', t') be such that s  s' ∈δ, then we have to prove that there exists a q' such that q  q' ∈ρ and (s', q') ∈ R. We have three cases:


  * t ∈ T: then, by inspecting the corresponding rule in the TRANS section, it is immediate to see that q and s are such that '(p) p̂ (such values are deterministic). Let us now consider the value of a generic variable v ∈ assigned nondeterministically by '. We have again three cases:[(i)] 
  * v ∈((t)) and (t)(v) ≠∅, hence its new value will be in (t)(v); 
  * ((t)) and (t)(v) = ∅, hence its new value will be ; or 
  * v ∉((t)) and its new value will be the same as the old one. Such cases are coded in conjunction in the rule: let us assume the first one applies with value v'=c, by Definition <ref> then there exists q' such that (q, q')  post_i and q'(v)=c; for the other two cases the choice is deterministic, either q'(v)= or q'(v)=q(v). It follows that there exists a q' that agrees on _(', '). It remains to show that there exists a q' such that also q'(t̂r̂)=t': if t' ∈ T, then it means that ' and ' satisfy the preconditions of the firing of t', meaning that t t is satisfied, hence there exists such a q' (there exists at least one, the choice of t' is nondeterministic); if t'= then, from Definition <ref> we have that no t”, ”, ” such that (', ') t” (”, ”) exist, i.e., ⋀_t ∈ Tt holds, hence q'(t̂r̂)=. Notice that we assumed t ∈ T, hence it is never the case that t'=. Since q' agrees with s' on the markings, the values of variables and the transition, it follows that (s', q') ∈ R.


  * t=, then from Definition <ref> we have that s'=s_ϵ and t'=. Since q(t̂r̂)=, then rule t= applies in the encoding and from its definition, (s', q') ∈ R immediately follows.


  * t=, then from Definition <ref> we have that s'=s_ϵ and t'=. Since q(t̂r̂)=, then rule t= applies in the encoding and from its definition, (s', q') ∈ R immediately follows.


Now, let q' such that q  q' ∈ρ. We have to prove that there exists a s' = (', ', t') such that s  s' ∈δ and q' = _(', t') _smvts(t).
We have three cases: t ∈ T, t = and t =. Analogous considerations to
of
 the previous case hold, as the rules in the encoding are not only sound, but also complete.


We now show 2. Given Remark <ref>, it is enough to show that (s, q) ∈ R implies s ∈ S_0 ↔ q ∈ Q_0.

We first prove the left to right direction, i.e., that (s=(_0, _0, t), q) ∈ R implies q ∈ Q_0, namely that formula _(_0, _0) _(t) satisfies the first conjunct of the INIT section. By definition of INIT, the first conjunct is satisfied, thus it remains to prove _(t). By Definition <ref> and Definition <ref> either (1) t ∈ T or (2) t=. If (1) then there is no valid firing in (, ), which entails that ⋀_t∈ Tt and if (2), then t can fire in (_0, _0) hence its preconditions are satisfied, which means _(_0, _0) satisfies t. In both cases the formula in the INIT section is satisfied and q ∈ Q_0.

The right to left direction in analogous by noticing that  trivially encodes the preconditions for firing t.


We conclude the section by observing that, by virtue of Remark <ref>, the formula Φ := ên̂d̂ = ⋀_p ∈ P∖endp̂= captures all and only states in _(W) that correspond to final states in the DAW-net.

Therefore, when checks the ltl formula: “a Φ-state is never visited”, it returns “true” if no final state can be reached and “false” and a path to a final state otherwise.





















§ TRACE COMPLETION
 




In order to evaluate the proposed encodings and the scalability of the three chosen solvers,

 in this paper we focus on the problem of repairing execution traces that contain missing entries (hereafter shortened in trace completion).  

The need for trace completion is motivated in depth in <cit.>, where missing entities are described as a frequent cause of low data quality in event logs. 

The starting point of approaches to trace completion are (partial) execution traces and the knowledge captured in process models. To illustrate the idea of trace completion, and why this problem becomes interesting in data-aware business processes, 	 let us consider the simple process model of the Loan Request (LR) depicted in  Figure <ref>, page fig:imgs_SampleWFnet.

A sample trace[In this work we are interested in (reconstructing) the ordered sequence of events that constitutes a trace, and thus we ignore timestamps as attributes. In the illustrative examples we present the events in a trace ordered according to their execution time.]
 that logs the execution of a LR instance is:

    {T1,T3, T5, T7, T9, T10, T11, T12}.


In this trace all the executed activities have been explicitly logged. Consider now the (partial) execution trace 

    {T3, T7}.

which only records the execution of tasks T3 and T7. 
By aligning the trace to the model using the techniques presented in <cit.>, we can exploit the events stored in the trace and the ordering of activities (i.e., control flow) specified in the model to reconstruct two possible completions: one is the trace in (<ref>); the other is: 

    
T1, T3, T5, T7, T9, T11, T10, T12

which only differs from (<ref>) for the ordering of the parallel activities. 

Consider now a different scenario in which the partial trace reduces to {T7}. In this case, by using the control flow in Figure <ref> we are not able to reconstruct whether the loan is a student loan or a worker loan. This increases the number of possible completions and therefore lowers the usefulness of trace repair. Assume nonetheless that the event log conforms to the XES standard and stores some observed data attached to T7 (enclosed in square brackets): 


    {T7[request=60k,loan=50k]}

Since the process model is able to specify how transitions can read and write variables, and furthermore some constraints on how they do it, the scenario changes completely. In our case, we know that transition T4 is empowered with the ability to write the variable request with a value smaller or equal than 30k (being this the maximum amount of a student loan). Using this fact, and the fact that the request examined by T7 is greater than 30k, we can understand that the execution trace has chosen the path of the worker loan. Moreover, since the model specifies that variable loanType is written during the execution of T1, when the applicant chooses the type of loan she is interested to, we are able to infer that T1 sets variable loanType to w. 


This example, besides illustrating the idea of trace completion, demonstrates why taking into account data (both in the process model and in the execution trace) is essential to accomplish this task.  
Also, as already observed in <cit.>, by considering corner cases of partial traces, such as empty traces and complete traces, the ability to produce a complete trace compliant with the process model can be also exploited to compute model consistency and trace conformance,

 respectively (see Figure <ref>).















 §.§ Trace completion as reachability



Having introduced the problem of trace completion we now show that we can reduce it to a reachability problem in a modified that takes into account both the original model and the given (partial) trace. Here we formalise the completion problem and its encoding into reachability. Full details and proofs are contained in <ref>.

A trace is a sequence of observed events, each one associated to the transition it refers to. Events can also be associated to data payloads in the form of attribute/variable-value pairs. Among these variables we can distinguish those updated by its execution (see Definition <ref>) and those observed. Executions (<ref>), (<ref>), and (<ref>) at page eq:trace-data provide examples of traces without and with data payloads for our running example.[We remark the conceptual and practical difference between a case and a trace: a case is a semantic object intuitively representing an execution/behaviour of the business process model while a trace is asyntactic object that comes from the real world of which we would test the soundness by providing a possible repair.]




 
Let W = , , , be a .
An event of W is a tuple t,w, w^d where t∈ T is a transition, w ∈⋃_'⊆ ('↦()) is a partial function that represents the variables written or observed by the execution of t, and w^d⊆ the set of variables deleted (undefined) or observed to be undefined by the execution of t. Obviously, w^d and the domain of w do not share any variable.

A trace of W is a finite sequence of events
τ = (e_1,…, e_n). In the following we indicate the i-th
event of τ as τi. Given a set of transitions T, the set of traces is inductively
defined as follows:


  * the empty trace is a trace;

  * if τ is a trace and e an event, then τ· e
  is a trace.





Notice that the definition above constrains the transitions neither to be complete nor correctly ordered w.r.t. W. What we would like to check is indeed if τ can be completed so as to represent a valid case of W.

Intuitively, a trace τ is compliant with a case C of a W if C contains all the occurrences of the transitions observed in τ
(with the corresponding variable updates) in the right order, as the following definition formalises.

  An event t',w, w^d is compliant with a (valid) firing (,)t(',') iff t = t', dom(w)⊆ dom(') ⊆∖ w^d, and for all v∈ dom(w) w(v) = '(v).

A trace τ = (e_1,…, e_ℓ), ℓ > 0, is compliant with a sequence of valid firings 
    (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k)
 iff there is an injective mapping γ between [1…ℓ] and [1… k] such that:[If the trace is empty then ℓ=0 and γ is empty.]
  
    ∀ i,j  s.t.  1≤ i < j ≤ℓ  γ(i) < γ(j)
    ∀ i  s.t.  1≤ i ≤ℓ    e_i  is compliant with  (_γ(i-1),_γ(i-1))t_γ(i)(_γ(i),_γ(i))

When ℓ = 0 we impose that τ is compliant with any sequence of valid firings.
  
We say that a trace τ is compliant with a W if there exists a case C of W such that τ is compliant with C.



Although the previous definition is general we notice that, since the last state of a case C must be a final state, τ being compliant with W means that it can be completed so as to represent a successful execution of the process W.








To simplify the presentation we assume (without loss of generality) that models start with the special transition start_t and terminate with the special transition end_t. Both have a single input and output places: start_t input is the start place, and end_t output place is the sink. Both the transitions have empty guards (always satisfiable) and don't modify variables; moreover, start and sink places shouldn't have any incoming and outgoing edge respectively.

Every process can be reduced to such a structure as informally illustrated in the top part of of Figure <ref> by the arrows labeled with (1). Note that this change would not modify the behaviour of the net: any sequence of firing valid for the original net can be extended by the firing of the additional transitions and vice versa.

We now illustrate the main idea behind our approach by means of the bottom part of Figure <ref>: we consider the observed events as additional transitions (in red) and we suitably “inject” them in the original . By doing so, we obtain a new model where we aim at forcing tokens to activate the red transitions when events are observed in the trace. When, instead, there is no red counterpart, i.e., there is missing information in the trace, the tokens are free to move in the black part of the model.



More precisely, for each event e corresponding to the execution of a transition t with some data payload, we introduce a new transition t_e in the model such that:

  
  * t_e is placed in exclusive or with the original transition t;
  
  * t_e includes an additional input place connected to the preceding event and an additional output place which connects it to the next event;
  
  * (t_e) is a conjunction of the original (t) with the conditions that state that the variables in the event data payload that are not modified by the transition are equal to the observed ones;
  
  * (t_e) updates the values corresponding the variables updated by the event payload, i.e. if the event sets the value of v to d, then (t_e)(v) = d; if the event deletes the variable v, then (t_e)(v) = ∅.
  
  
  
 Note that an event t,w,w^d cannot be compliant with any firing unless w(v)∈(t)(v) for each variable in dom(w)∩ dom((t)), and w^d∩ dom((t))⊆{v | (v,∅) ∈(t)}. Since these properties can be verified just by comparing the events to the model, then in the following we assume that they are both satisfied for all the events in a trace.
  
  
Given a W, and a trace τ, the formal definition of the “injection” of τ into W, denoted with W^τ, is given below.
  
  
Let W = ,  = P,T,F, , be a and τ = (e_1,…, e_n) – where e_i = t_i,w_i, w_i^d – a trace of W. The trace workflow W^τ = , ^τ = P^τ,T^τ,F^τ, ^τ, ^τ is defined as follows:

  
  * P^τ = P ∪p_e_0∪p_e| e∈τ, with p_e_0, p_e new places; 
  
  * T^τ = T ∪t_e| e∈τ, with t_e new transitions; 
  
  * F^τ = F ∪  

	     (t_e_i,p)| i=1… n, (t_i,p)∈ F∪(p,t_e_i)| i=1… n, (p,t_i)∈ F∪

		 (t_e_i,p_e_i)| i=1… n∪(p_e_i-1,t_e_i)| i=1… n∪(start_t,p_e_0), (p_e_n,end_t)
  
  * ^τ(t) = v ↦{w_i(v)}| v∈ dom(w_i)∩ dom((t_i))∪
 v↦(t_i)(v)| v∈ dom((t_i))∖ dom(w_i)   for t = t_e_i
(t)    for t∈ T
 
  * ^τ(t) = (t_i)⋀_v∈ dom(w_i)∖ dom((t_i)) v = w_i(v) 
 ⋀_v∈ w_i^d∖ dom((t_i))(v)    for t = t_e_i
(t)    otherwise













It is immediate to see that W^τ is a strict extension of W (only new nodes are introduced) and, since all newly introduced nodes are in a path connecting the start and sink places, it is a , whenever the original one is a net.
	


By looking at this definition, at its graphical illustration at the bottom of Figure <ref>, and also at the simple example in Figure <ref> it is easy to see why the red transitions must be preferred over the black ones in all the sequences of valid firings that go from start to end (i.e., in all cases). Intuitively, transition end_t needs a token in the red place p_e_n to fire, in addition to the token in the original end of the initial net. By construction all the red places are only connected to red transitions. Thus, to properly terminate, when choosing between t_e and t, t_e must be preferred so that it produces in output all the tokens for the original black output places plus the one for the new red place. Note that whenever t was able to fire in the original net, t_e can fire as well. Indeed it is easy to see that, by construction, the token generated by start_t in p_e_0 is only consumed and produced by red transitions, and propagated into red places.
  



We now prove the correctness and completeness of the approach by showing that W^τ characterises all and only the cases C of W to which τ is compliant with. We focus here only on the main intuitive steps of the proof, whose technical details are reported in full in <ref>. 

Roughly speaking what we need to show is that: 

	
  * (correctness) if C is an arbitrary case of W^τ, then there is a “corresponding” case C' of W such that τ is compliant with C'; and
	
  * (completeness) if τ is compliant with a case C of W, then there is a case C' in W^τ “corresponding” to C. 


A fundamental step for our proof is therefore a way to relate cases from W^τ to the original W. To do this we introduce a projection function _τ that maps elements from sequences of valid firings (cases) of the enriched W^τ to sequences of valid firings (cases) composed of elements from the original W. 
The formal definition of _τ is given in Definition <ref> of <ref>. In essence _τ maps newly introduced transitions t_e to the original transition t corresponding to the event e, and projects away the newly introduced places in the markings.

Once defined the projection function _τ the correctness and completeness statement can be formally formulated as follows: 

theoremthTraceWorkflow
	
  Let W be a and τ = (e_1,…, e_n) a trace; then W^τ characterises all and only the cases of W compatible with τ. That is
  
    
  ⇒ if C is a case of W^τ then τ is compliant with the case of W _τ(C); and 
    
  ⇐ if τ is compliant with the case of W C then there is a case C' of W^τ s.t. _τ(C') = C.
  


The proof of correctness follows from two foundamental properties of W^τ and the projection function _τ respectively. The first property, ensured by construction of W^τ, states that τ is compliant with all cases of W^τ. The second property, instead, states that any case for W^τ can be replayed on W trough the projection _τ, by mapping the new transitions t_e into the original ones t, as shown by Lemma <ref> in <ref>.  
Given these two properties, it is possible to prove that, if C is a case

 of W^τ, then τ is compatible with it and with its projection _τ(C) on W (See Lemma <ref> in <ref>).

The proof of completeness instead is based in the fact that we can build a case for W^τ starting from the case of W with which τ is compliant, by substituting the occurrences of firings corresponding to events in τ with the newly introduced transitions (See Lemma <ref> in <ref>).

Theorem <ref> provides the main result of this section and is the basis for the reduction of the trace completion for W and τ to the reachability problem for W^τ: indeed, to check if τ is compliant with W all we have to do is finding a case of W^τ.



 
  Let W be a and τ a trace; then τ is compliant with W iff there is a final state (_e, η') of W^τ that can be reached from the initial state (_s, η_s).



	This is immediate from Theorem <ref> because a final state of W^τ can be reached from its initial state iff there exists at least a case of W^τ.








We conclude the section by stating that the transformation generating W^τ is preserving the safeness properties of the original workflow (proof in <ref>).

theoremlemmaKSafe
	
  Let W be a and τ a trace of W. If W is k-safe then W^τ is k-safe as well.















§ EVALUATION




In this section we aim at evaluating the three investigated solvers , and , and the respective paradigms answer set programming, automated planning and model checking, on the task of trace completion for

 data-aware workflows. In detail, we are interested to answer the following two research questions:




  * What are the performance of the three solvers when accomplishing the task of trace completion

 by leveraging also data payloads?

  * What are the main factors impacting the solvers' capability to deal with the task of trace completion?



The first research question aims at evaluating and comparing the performance of the three solvers, both in terms of capability of returning a result within a reasonable amount of time and, when a result is returned, in terms of the time required for solving the task. The second research question, instead, aims at investigating which factors could influence the solvers' capability to deal with such a task (e.g., the level of incompleteness of the execution traces, the characteristics of the traces, the size of the process model, the domain of the data payload associated to the events, or the data payload itself).  

In order to answer the above research questions by evaluating the three investigated solvers in different scenarios, we carried out two different evaluations: one based on synthetic logs and a second one based on real-life logs. Indeed, on the one hand, the synthetic log evaluation (Subsection <ref>) allows us to investigate the solvers' capabilities on logs with specific characteristics. On the other hand, the real-life log evaluation (Subsection <ref>) allows us to investigate the capability of the solvers to deal with real-life problems. 
In the next subsections, we detail the two evaluations (Subsections <ref> and <ref>) and we investigate some threats to the validity of the obtained results (Subsection <ref>). 


All the experiments have been carried out on a Kubernetes cluster running over a pool of virtual machines hosted on hardware based on Intel Xeon X5650 2.67GHz processors. For the container running the experiments a single CPU has been allocated since the reasoning systems we used do not exploit multiprocessing. For each run we set up a (real) time limit of one hour, and a memory limit of 8GiB.[Given the single task nature of the container, the CPU time is only marginally lower than the real time.] 

The code used for the experiments is available for download from <https://doi.org/10.5281/zenodo.3459656>. The directory  includes the models and experiments descriptions, as well as a  file with the details on how to run them.



 §.§ Synthetic Log Evaluation


In order to investigate the performance of the three solvers in different settings, we built synthetic models with different characteristics. For each of them, we identified different traces with different features and, in turn, for each trace, we considered different levels of trace completeness ranging from the complete trace (100% complete) to the empty trace (0% complete). 
In the next subsections we describe the datasets, the procedure and the metrics used, as well as the obtained results.


  §.§.§ Dataset, procedure and metrics

We built five different synthetic models M1 - M5 with different characteristics and of different size. In detail, M1 is the model reported in Figure <ref>. The model deals with 5 different variables: number, first, second, third, fourth and fifth. Activity A is able to write four variables (first, second, third and fourth), activity I writes variable number and, finally, activity G writes variable fifth. 



Figure <ref> also shows the guards related to model M1. In detail, the exit condition from the loop (L - I) is variable number equals to 5 at I, while whenever the value of number written by I is different from 5, the loop is exited and M is executed. Moreover, variables first, second and third determine the branch to be taken at the end of the model. In detail, if at M first is equal to 1, the branch with N is taken, if second is equal to 2, the branch O is taken, while if third is equal to 3, the branch starting with P is taken[For the sake of readability first, second and third are shortened in f, s and t in Figure  <ref>.]. Whenever more than one of the three conditions are verified, one of the three branches can be non-deterministically taken. 



We built the synthetic models M2 … M5 starting from model M1 and creating replicas of M1. For notation simplicity, we denote with K the core part of M1, i.e., the model obtained by excluding the start and the end event (see Figure <ref>) and we enumerate the replicas of K in M2 … M5 with a progressive number. In detail, M2 concatenates two replicas of K, labelled as K0 and K1 (see Figure <ref>), M3 uses the parallel construct to compose together two replicas of K, namely K0 and K1 (see Figure <ref>). M4 concatenates three replicas of K, namely K0, K1 and K2 (see Figure <ref>). Finally, in M5, three replicas of K are composed in an exclusive choice. In detail, one of the two alternative branches concatenates two replicas of K, i.e., K0 and K1, while the other exclusive branch is composed of a single replica of K, named K2 (see Figure <ref>). Different replicas of K do not share variables, which are renamed in order to avoid interactions that could limit the compatible traces. 

For each of the five models M1 … M5, we generated 8 different execution traces of different length and with different characteristics. In detail, we generated 4 compliant traces and 4 non-compliant traces. Out of the 4 compliant traces, in two traces (trace types T3 and T4)

 the loop(s) of K replica(s) is(are) never executed, while in the remaining two, the loop is executed twice. Moreover, in two (trace types T1 and T3)

 out of the four cases of the compliant traces, the path followed by the trace is deterministically driven by the values associated by the activity A to the variables 𝑓𝑖𝑟𝑠𝑡, 𝑠𝑒𝑐𝑜𝑛𝑑 and 𝑡ℎ𝑖𝑟𝑑, while in the remaining two traces more than one branch could be activated based on the values of the variables at activity M. Also in the case of non-compliant traces, two traces (trace types T5 and T7)

 do not execute any loop iteration, while the other 2 traces iterate over the loop two times. Finally, out of the four non-compliant traces, two (trace type T5 and T6)

 are not compliant only because of control flow violations (mutually exclusive paths are executed in the same trace), while the remaining two traces are non-compliant due to data constraint violations (a path that is not activated by the corresponding guard is executed). Table <ref> reports, for each trace t_ij of model M_i and trace type T_j, some information about its characteristics.


a>Grayc

b>LightGrayc



Finally, for each of the 40 traces, we considered five different levels of completeness[The execution traces have been made incomplete by removing events so as to preserve the non-compliance of traces (compliance is always preserved), as well as the capability for a solver to reconstruct the missing events.], ranging from 100% (i.e., the complete trace) to 0% (i.e., the empty trace). Table <ref>, column Completeness shows four level of completeness (100%, 75%, 50% and 25%) for each of the considered traces and the corresponding characteristics. In the table we did not report the information related to the empty traces (0% of completeness), which is the same for all the 8 different types of traces.
For each of the three solvers, hence, we carried on, in total, 165 runs (5 models, 8 traces for each model and 4 levels of incompleteness for each trace and model, as well as 5 empty traces per model). 

We evaluated the first research question (RQ1) by computing, for each solver (i) the number/percentage of runs the solver is able to return; (ii) when a solution is returned, the time required by the solver for returning the solution. For RQ2, instead, we evaluated the metrics reported above, when changing factors, such as the level of incompleteness of the traces, the characteristics of the traces, as well as the model used for generating the traces. 




  §.§.§ Results

Only 2 runs out of the 495 runs carried out for the synthetic datasets did not return a result because they exceeded the maximum time threshold. 

Differently from , which exceeded the maximum time limit in 2 cases (∼1% of the runs), both and were always able to return results.




















Figure <ref>, besides the small percentage of timed-out runs of , 

 shows the average CPU time (and the corresponding variance) required by each of the three solvers to return results.
We can clearly observe that and are the solvers with the best performance. Differently from , which fails in returning results within the time-out threshold for two runs, 

 the two solvers are able to return results for each of the runs. Moreover, and have comparable performance in terms of time required for trace completion (see the overlapping lines of and in Figure <ref>). The time required by the two solvers (few seconds on average)


 is always lower than the time required by , which takes, on average, about 8 minutes. 




 


This analysis allows us to assess that, overall, in case of synthetic datasets (of medium size), and are the most reliable in finding solutions in a reasonable amount of time, and the fastest ones among the three considered solvers. has instead lower performance both in terms of capability to return results in a reasonable amount of time, as well as in terms of the average amount of time required to return computations (RQ1).






In detail, Figure <ref> shows the performance of the three solvers for different levels of incompleteness. By looking at the figure, we can observe that the level of incompleteness has an impact on : the more the trace is empty, the more the solver is able to return results (i.e., the less timed-out runs occur), the faster it is, and the lower the variance of the runs is. 






The plot in Figure <ref>, which reports solvers' performance for traces with different characteristics (the empty trace and the 8 types of traces considered), shows that the only runs for which is unable to return results relate to traces of type T5 and T6, i.e., traces non-compliant due to issues  related to the control flow. However, the characteristics of these two types of traces, do not seem to impact the average time required by to return results.  Differently from what happens for timed-out runs, the types of traces that require more time to seem to be T3 and T8.









Finally, Figure <ref> investigates the impact of different models on the solvers. The plot suggests that all the solvers are able to manage well small and medium models (e.g., M1, M2 and M3). has instead difficulties with larger models. In particular, both the two timed-out runs relate to model M4, which is the largest model, i.e., the model whose traces are always the longest traces (see Table <ref>). Moreover, the runs related to this model that are able to complete, require more time than other runs for returning results.

Differently from , none of the three investigated factors affects the performance of and , which are always able to return a solution in few seconds.



Overall, we can assess that, in case of synthetic datasets (of medium size), trace completeness has a strong impact on , which performs better on empty traces. performance are also influenced by the model size and, in particular, by the length of the traces that it generates: the larger the model and the longer the traces, the worse the performance of the solver. On the contrary, none of the investigated factors has an impact on the and performance (RQ2). 

































































 §.§ Real-life Log Evaluation


In order to evaluate the capability of the three solvers to deal with real-life settings, we exercised them on a real world event log. In the next subsections we first describe the considered dataset, the procedure and the metrics used for its evaluation; we then show the obtained results.



  §.§.§ Dataset, procedure and metrics

In order to exercise the three solvers in a real-life setting, we resorted to the BPI Challenge 2011 <cit.> (BPIC2011) event log. The log pertains to a healthcare process and, in particular, contains the executions of a process related to the treatment of patients diagnosed with cancer in a large Dutch academic hospital. The whole event log contains 1143 execution cases and 150291 events distributed across 623 event classes (activities). Each case refers to the treatment of a different patient. The event log contains domain specific attributes that are both case attributes and event attributes. For example, Age, Diagnosis, and Treatment_code are case attributes and Activity_code, Number_of_executions, Producer_code, Section and Group are event attributes.





The inputs required for accomplishing the task of trace completion are a process model and incomplete traces. We hence extracted a data-aware Petri Net model and we generated a set of incomplete traces by applying the following procedure:


  

  * We discovered the data-aware Petri net from the BPIC2011 event log by applying the ProM Data-flow Discovery plugin <cit.>. [As input for the Data-flow Discovery plugin we used the Petri Net discovered with the Inductive Miner algorithm by setting the Noise threshold parameter of the plugin to 0.20.] The discovered data-aware Petri Net has 355 transitions, 61 places and 710 edges and 4 variables (Activity_code, Producer_code, Section and Group), which are read and written by the Petri net transitions and constrained in 25 guards throughout the data-aware Petri net. An example of a discovered guard is reported in (<ref>).

    (Producer_code="CHE2") && (Activity_code=="370422")


  * For the testing set generation, we randomly selected 9 complete traces - details on the traces and their length are reported in columns Trace ID and Trace length in Table <ref> - from the dataset.

  * For each of the 9 randomly selected traces, 3 incomplete traces - obtained by randomly removing 25%, 50% and 75% of the events 

 are added to the testing set.

  * The empty trace is added to the testing set. 


We evaluated the 3 solvers on each trace of the testing set for a total of 37 runs per solver (9 different traces for 4 different levels of completeness and the empty trace).



























Also in this case, we evaluated RQ1 by computing, for each solver (i) the number/percentage of runs the solver is able to return; (ii) the time required for returning the solution. For the second research question (RQ2), instead,  




 we focused on the factors that could impact the results. Besides looking at the degree of trace completeness and at different traces, we also investigated the impact of data and of its domain on the performance of the solvers on large real-life datasets. To this aim, we evaluated the three solvers by computing the metrics reported above in three different settings: 
 
  

  * : in this setting we considered the data payloads associated to events and we did not apply any restriction to their domain;

  * : in this setting we reduced the domain of the data to the only constant values occurring in the model; [Please notice that we were able to reduce the domain of the variables to the sole constant values, as we only have guards with equality constraints.]

  * : in this setting we do not use data at all.

For each setting, we performed the 37 runs described above, we collected the metrics and we compared the results.




  §.§.§ Results






















Table <ref> reports, for each of the three scenarios, the number of timed-out and out-of-memory runs for the three solvers on the BPIC2011. When applying the three solvers to the task of completing incomplete traces of a large real-life event log in the scenario, the only solver able to return results (in 15 runs out of the 37 ones carried out) is ; and fail in each of the executed runs due to out-of-memory issues.



Indeed, when applied to large datasets, the and grounding phase, which likely allows the solver to complete the runs in short time for small datasets, is unable to complete due to a memory space explosion.  







Figure <ref> plots the performance (percentage of timed-out/out-of-memory runs and average time) of the three solvers for different levels of trace completeness and for the different considered traces (the empty trace and the 9 traces of the BPIC2011). Overall, no general trend or pattern related to the trace completeness and to the trace type can be identified for the 15 runs for which was able to return a result and the required time ranges from ∼20 seconds to one hour. 


Differently from the synthetic datasets, an opposite trend can be observed with large real-life logs: performance improves with more complete traces. For instance, the timed-out runs and the average time required for 75%-complete traces are less than the timed-out runs and the average time required for the 50%-complete traces. Moreover, we can notice that for a couple of traces - t610 and t1132 -is also not able to provide any result, as the other two solvers. 



Figure <ref> shows the obtained results for the scenario.  Despite the domain restriction, and are still unable to return results, while an improvement can be observed in the capability of to return results: the number of timed-out runs decreases of about 50% (from 22 to 12 runs), as reported in Table <ref>. The trend observed for the timed-out runs is similar to the one of the scenario (the percentage of timed-out runs is null for the empty traces and reaches its peak for 50%-complete traces), while some differences are registered in terms of required time (e.g., the average time required for 75%-complete traces increases almost of a factor of 3 with respect to the scenario). If we look at different traces, trends are instead quite different from the scenario. For instance, in the scenario, was unable to deal only with 20% of the runs for the trace t610, which was a problematic trace in the scenario. On the contrary, the percentage of timed-out runs for trace t296 (50%) remains unchanged moving from the to the scenario.








		










Finally, the three solvers have been evaluated in the scenario. In this setting, each of the three solvers is able to return some results (see the last row in Table <ref>). When data are not taken into account, the performance of the solvers are close to the results obtained with the syntetic datasets: is the only one able to deal with all the 37 runs, followed by registering 12 timed-out runs and, finally, by with 20 out-of-memory runs. Moving from a to a scenario has hence a strong impact on the capability of and to return results, while this is not the case for , whose number of timed-out runs remains the same of the scenario. 


The plots in Figure <ref> report, besides the percentage of timed-out and out-of-memory runs, also the time required by the solvers for the returned runs. As for the synthetic datasets, is the solver with the best performance (it takes from few seconds to few minutes) followed by (∼300 seconds, for the runs it is able to complete) and (∼20 minutes with a high variance).  The time required by seems to slightly depend on the level of trace incompleteness: the more the trace is complete, the larger the encoded net, the more time requires to complete the task. 

Overall, when dealing with real-life datasets enriched with data (both with and without domain restrictions), is the best solver, while and are unable to deal with this scenario. When, instead, data are not taken into account, outperforms the other two solvers both in terms of returned results and of required time. Although fails in returning results in less runs (about half) than , has better performance than in terms of required time (RQ1).

Moreover, although no general pattern and trend can be identified with respect to trace incompleteness and trace type, data has a strong impact on  and and the data domain affects the capability of of returning results (RQ2).




Summarizing the above results, we can conclude that is the most robust approach as it is able to deal reasonably well with very complex settings as real-life event logs with data. On the other hand, , which on large search spaces ends up in out-of-memory errors, on synthetic and on real-life medium-size search spaces

 outperforms its competitors, carrying on the trace completion task in few seconds (RQ1).
Concerning RQ2, for each of the three solvers, no global trends or patterns related to the level of trace completeness and to the characteristics of the trace have been identified. The only exception is and its capability to better deal with incomplete rather than with complete traces for synthetic event logs and in  part viceversa for large real-life event logs. The size of the resulting search space and, in particular, leveraging data, has a huge impact on the difficulties of and to solve the trace completion task.

We remark that, although the focus of the evaluation is on the specific task of trace completion for

 data-aware workflows, 


since the task is recasted to a reachability problem
 (see Section <ref>), the problem we are tackling is actually a wider one.

 The evaluation carried out shows the performance of the three solvers on the reachability problem for large automata, as for instance, the one obtained from the analysis of the discovered from the BPI2011 event log.



 §.§ Threats to Validity


The main threats affecting the validity of the reported results are external validity issues, which hamper the generalization of the  findings. Indeed, we evaluated the solvers on a single real-life log and tested them only on a small number of log traces. Nevertheless, we tried to mitigate the above threat, by carrying on a systematic evaluation on the synthetic datasets and randomly selecting the subset of traces in the real-life event log used in the evaluation. A second threat to the external validity of the results relates to the choice of the data and of the guards. However, also in this case, we tried to reduce the threat by considering different data attributes and values in the synthetic evaluation, and by relying on data and guards discovered by the ProM Data-flow Discovery plugin. 
Finally, 

we used the solvers as informed users, i.e., we did not apply to them special optimizations. 

 Dedicated encodings and tuning strategies could improve the performance of the solvers. However, the threat is mitigated by the fact that none of the three solvers has been optimized.






§ RELATED WORK






In the field of verification techniques for data-aware processes, a number of theoretical works exist both in the area of data-aware processes and of (variants of) PNs. Unfortunately, when combining processes and data, verification problems suddenly become undecidable <cit.>.

We can divide this literature in two streams. In the first stream, PNs are enriched, by making tokens able to carry various forms of data and by making transitions aware of such data, such in CPNs <cit.> or in data variants such as (Structured) Data Nets <cit.>, ν-PNs <cit.> and Conceptual WF-nets with data <cit.>. 

For full CPNs, reachability is undecidable and usually obtained by imposing finiteness of color domains. Data variants instead weaken data-related aspects. Specifically Data Nets and ν-PNs consider data as unary relations, while semistructured data tokens are limited to tree-shaped data structures. Also, for these models coverability is decidable, but reachability is not. The work in <cit.> considers data elements (e.g., Price) that can be used on transitions' preconditions. 
However, these nets do not consider data values (e.g., in the example of Section <ref> we would not be aware of the values of the variable request that T4 is enabled to write) but only whether the value is “defined” or “undefined”, thus limiting the reasoning capabilities that can be provided on top of them. For instance, in the example of Section <ref>, we would not be able to discriminate between the worker and the student loan for the trace in (<ref>), as we would only be aware that request is  after T4. 

The second stream contains proposals that take a different approach: instead of making the control-flow model increasingly data-aware, they consider standard data models (such as relational databases and XML repositories) and make them increasingly “dynamics-aware”.

Notable examples are relational transducers <cit.>, active XML <cit.>, the artifact-centric paradigm <cit.>, and  DCDSs <cit.>.

Such works differ on the limitations imposed to achieve decidability, but they all lack an intuitive control-flow perspective.


A further recent work presents  <cit.>, a framework that joins the two streams above by directly combining a control-flow model based on PNs and standard data models (à la DCDS) as first class citizens, in which activities/tasks are expressed in a STRIP-like fashion. Verification in is shown to be decidable when the number of objects accumulated in the same state is bounded (but still infinitely many values may occur in a run) and first-order quantification is restricted on the active domain of the current state. The definition of follows the approach of in combining control-flow model based on PNs and standard data models (à la DCDS) as first class citizens. However, the current work differentiates from that of in that we consider a data model with variables only, which, on the one hand, does not require complex restrictions to achieve decidability of reasoning tasks and, on the other hand, is still expressive enough to address the trace completion problem with events carrying data. We indeed remark that the payload of XES standard for traces is a set of attribute-value pairs, thus making data-aware process models with relational data structures needlessly cumbersome for solving reasoning tasks on concrete logs.

The VERIFAS system <cit.> leverages model checking techniques for the verification of temporal properties of infinite-state transition systems arising from processes that carry and manipulate unbounded data. Although in principle the system can be used to verify reachability properties of models, it's difficult to compare because the representation language for the models is more expressive, and the language for specifying the properties that can be verified can be used for more than reachability. Moreover the software used for their experiments <cit.> cannot be used directly for our purposes and it would require nontrivial modifications in order to be included in our experiments.

Moving to the exploitation of verification techniques in the BPM field, 

 we can notice that planning techniques have already been used in this context, e.g., for verifying process constraints <cit.>, for accomplishing business process reengineering <cit.>, for conformance checking <cit.> as well as for the construction and adaptation of autonomous process models <cit.>.



 









In <cit.> automated planning techniques have been applied for aligning execution traces and process models.




 In <cit.> and <cit.>, planning techniques have been used for addressing the problem of incomplete execution traces with respect to procedural models. 
 Compared to these two works, where the focus was on an ad hoc encoding of the problem of trace repair using a specific Action Language, this paper tackles the more general problem of formal verification of reachability properties on imperative data-aware business processes, it introduces a more general encoding technique based on finite transition systems and provides an extensive evaluation of different solvers. The new technique highlights the core dynamic properties of Workflow Nets, and enables a seamless encoding of the decision problems under investigation in a variety of formal frameworks.

In <cit.> an action language similar to (see Section <ref>), and its encoding in ASP, is exploited for the verification of Business Processes enriched with a lightweight ontology language for describing semantic relations among data objects. 







The problem of trace completion, which we used for the empirical investigation, has been explored in a number of works of trace alignment in the field of process mining.
Several works have addressed the problem of aligning event logs and procedural models, without <cit.> and with <cit.> data. 
All these works, however, explore the search space of possible moves in order to find the best one aligning the log and the model.
Differently from them, in this work[(i)] 
  * we assume that the model is correct and we focus on the repair of incomplete execution traces; 
  * we want to exploit state-of-the-art formal verification techniques to solve the problem as a reachability problem on control and data flow rather than solving an optimisation problem.























§ CONCLUSIONS



This work provides a concrete solution for formal verification of reachability properties on imperative data-aware business processes and contributes to advancing the state-of-the-art on the concrete exploitation of formal verification techniques on business processes in two different ways: first it presents a rigorous encoding of a data-aware workflow nets based language into Action Languages, Classical Planning, and Model Checking based on a common interpretation in terms of transition systems; second it provides a first comprehensive assessment of the performance of different solvers, one for each language, in terms of reasoning with data-aware workflow net languages on both synthetic and real-life data. The evaluation shows that is the most robust approach as it is able to deal reasonably well with diverse types of event logs with data. On the other hand, , outperforms its competitors on medium-size search spaces. 

In the future, we plan to investigate the impact of optimized encodings and tuning strategies to further improve the performance of the solvers.

Also, we believe that it is crucial to push forward the general research direction of this paper, namely providing real verification support for data-aware workflows models. We plan at fulfilling this objective by moving to more expressive models, such as the one in <cit.>, and by supporting not only reachability properties, but ideally a full-fledged temporal language.




 
 
  
  








§ TECHNICAL DETAILS OF SECTION <REF>


*

	Without loss of generality we can assume that Φ is in the DNF form described in Section <ref>; i.e. ⋁_i=1^k t_1^i… t_ℓ_i^i where each term t_j^i is either of the form v = o or (v). In this case to prove the lemma is sufficient to show that for the base cases _i, _i  t iff i:t∈_i(ρ):
	
		
  (v = o) _i, _i  v = o iff _i(v) = o iff (by Definition <ref>) {i:v=o}⊆_i^ν(ρ)⊆_i(ρ);
		
  ((v)) _i, _i (v) iff _i(v) is undefined iff (by Definition <ref>) {i:v=}⊆_i^ν(ρ)⊆_i(ρ).
	



*

    We prove the lemma by induction on the length of the case ρ that ⋃_i=0^ℓ_i(ρ) is a stable model of P_ℓ(()).

    For ℓ = 0 there is only the initial state and P_0(()) includes only rules derived from the static laws (none), the initially statements:
    
    0:start=   
    
            0:p=         for |p|∈ P  and |p|≠start
    
            0:v=         for |v|∈'
    
            0: trans=

    and the encoding of into ASP:
    
        
  * for all the places and the additional fluent for enforcing actions p∈ P∪{trans}
    
    0:p=d  (0:p=d)          for d∈{, }
     0:p=d'    ← 0:p=d       for d,d'∈{, } and d≠ d'

    
    ← 0:p=d,  0:p=d       for d∈{, }
       ← (0:p=),  (0:p=)

    
  * for all the variables v∈ V'
     
    0:v=d  (0:v=d)          for d∈(v)∪{}
     0:v=d'    ← 0:v=d       for d,d'∈(v)∪{} and d≠ d'

    
    ← 0:v=d,  0:v=d       for d∈(v)∪{}
       ← (0:v=d_1), …,  (0:v=d_k), (0:v=)       s.t. {d_1,…, d_k} = (v)

   
  By the definition of (_0,_0)
    
    _0^ν((_0,_0)) =    {0start, 0start}∪
       {0p, 0p| p∈ P∖{start}}∪
       {0v| v∈'}∪{0vo| v∈', o∈(v)}∪
       {0trans, 0trans}
    _0^τ((_0,_0)) =    ∅

   It's not difficult to see that all the above rules are satisfied by _0((_0,_0)). We need to show also that it's the minimal model of the reduct P_0(())^_0((_0,_0)) of P_0(()) w.r.t. _0((_0,_0)). To this end we note that in the reduct all the rules including NAF literals are removed because each fluent is assigned to a value, and the remaining constraints 
    ←0fo, 0fo
 are satisfied by construction because {0fo, 0fo}⊈_0((_0,_0)).[Remember that a constraint ←ℓ_1,…, ℓ_n corresponds to the rule f ← f, ℓ_1,…, ℓ_n.]
   
   In _0((_0,_0)) there are just literals 0fc and 0fc. Removing any positive (i.e. 0fc) literal would falsify the the initially statements, and removing the negative ones would contradict the corresponding rules: 
    0fo'←0fo
 where 0fo∈_0((_0,_0)) and o'≠ o.
   
   This concludes that _0((_0,_0)) is a minimal model for P_0(())^_0((_0,_0)).
   
   For the inductive step we assume that for an arbitrary case ρ of length ℓ, ⋃_i=0^ℓ_i(ρ) is a stable model of P_ℓ(()) and we show that ⋃_i=0^ℓ+1_i(ρt_ℓ(_ℓ+1,_ℓ+1)) is a stable model of P_ℓ+1(()).
   
   Note that, by construction, 
    ⋃_i=0^ℓ+1_i(ρt_ℓ(_ℓ+1,_ℓ+1)) = ⋃_i=0^ℓ_i(ρ)∪_ℓ^τ(ρt_ℓ(_ℓ+1,_ℓ+1))∪_ℓ+1^ν(ρt_ℓ(_ℓ+1,_ℓ+1))

      and P_ℓ+1(()) is equal to P_ℓ(()) plus the rules:
   
    ℓtℓt         for all t∈ T
    ℓ+1vo   ←ℓvo, ℓ+1vo      for v∈' and o∈(v)∪{}
    ℓ+1po   ←ℓpo, ℓ+1po      for p∈ P and o∈{, }
    ℓ+1vd   ←ℓt, ℓ+1vd      for all t∈ T, (v,d)∈(t)
    ℓ+1p   ←ℓt      for all t∈ T, p∈t∖t
    ℓ+1p   ←ℓt      for all t∈ T, p∈t∖t
    ℓ+1v   ←ℓt      for all v∈', t∈ T, s.t. (t)(v)=∅
    ℓ+1trans   ←ℓt      for all t∈ T
    ℓ+1pd'   ←ℓ+1pd      for p∈ P∪{trans}, d,d'∈{, } and d≠ d'
    ℓ+1vd'   ←ℓ+1vd      for v∈'d,d'∈(v)∪{} and d≠ d'

the constraints

    ←ℓt, ℓs      for t,s∈ T, s.t. t≠ s
       ←ℓt, ℓ+1vd      [t]15emfor t∈ T, v∈' s.t. (t)(v)≠∅, d∈{}∪(v)∖(t)(v)
       ←ℓt, ℓp      for t∈ T, p∈t
       ←ℓ+1pd, ℓ+1pd      for p∈ P∪{trans}, d∈{, }
       ←ℓ+1p, ℓ+1p      for p∈ P∪{trans}
       ←ℓ+1vd, ℓ+1vd      for v∈', d∈(v)∪{}
       ←ℓ+1vd_1,…, ℓ+1vd_k, ℓ+1v      for v∈', {d_1,…, d_k} = (v)

and the constraints corresponding to the guards; that is, for each transition t s.t. (t) ≢true we consider (t)=⋁_i=1^k t_1^i… t_ℓ_i^i:

    ←ℓt, ℓt_1^1, …, ℓt_n_1^1
       …
       ←ℓt, ℓt_1^k, …, ℓt_n_k^k

To show that ⋃_i=0^ℓ+1_i(ρt_ℓ(_ℓ+1,_ℓ+1)) is a stable model of P_ℓ+1(()) we use the Splitting Sets technique as introduced in <cit.>; a generalisation of stratification which enables the splitting of a program in two parts on the basis of atoms in the head of the rules, and provides a way of characterising the stable models in terms of the stable modes of the two parts. More specifically, A splitting set for a program P is any set of atoms U such that, for every rule r ∈ P, if head(r) ∩ U≠∅, then atoms(r) ⊆ U. The set of rules r ∈ P such that atoms(r) ⊆ U is the bottom of P relative to U, denoted by bot_U(P). The set top_U(P) = P ∖ bot_U(P) is the top of P relative to U.


Let's consider the set

    U =    {ifd| i≤ℓ, f fluent constant and d constant}∪
       {ia| i<ℓ, a action constant}

then U is a splitting set for P_ℓ+1(()) and bot_U(P_ℓ+1(())) = P_ℓ(()); therefore we just need to show that _ℓ^τ(ρt_ℓ(_ℓ+1,_ℓ+1))∪_ℓ+1^ν(ρt_ℓ(_ℓ+1,_ℓ+1)) is a stable model of e_U(P_ℓ+1(()) ∖ P_ℓ(()),⋃_i=0^ℓ_i(ρ)) where e_U(P,X) is defined in <cit.> as:
    
    e_U(P,X) = { r |exists r'∈ P s.t. body^+(r')∩ U⊆ X, body^-(r')∩ U∩ X = ∅
    
            head(r)=head(r'), body^+(r) = body^+(r)∖ U, body^+(r) = body^+(r)∖ U }

    that is, only rules whose bodies are not falsified by X, and the remaining literal in U are removed.

Following Definition <ref>:
    
    _ℓ+1^ν(ρ) =    {ℓ+1:p=, (ℓ+1:p=)| p∈ P, _ℓ+1(p) > 0 }∪
       {ℓ+1:p=, (ℓ+1:p=)| p∈ P, _ℓ+1(p) = 0 }∪
       {ℓ+1:v=o, (ℓ+1:v=) | v∈', _ℓ+1(v) = o }∪
       {ℓ+1:v=| v∈', _ℓ+1(v)  is undefined}∪
       {(ℓ+1:v=o) | v∈', o∈(v), _ℓ+1(v) ≠ o  or _ℓ+1(v)  is undefined}∪
       {ℓ+1:trans=, (ℓ+1:trans=)}∪
    _ℓ^τ(ρ) =    {ℓ:t_ℓ}∪{(ℓ:t)| t∈ T, t≠ t_ℓ}

    
We can discard the actual constraints, since they are satisfied by construction of  _ℓ^τ(ρt_ℓ(_ℓ+1,_ℓ+1))∪_ℓ+1^ν(ρt_ℓ(_ℓ+1,_ℓ+1)) because we assume that (_ℓ,_ℓ)t_ℓ(_ℓ+1,_ℓ+1) is a valid firing. The constraints referring to guards are satisfied because either ℓt∈_ℓ^τ(ρt_ℓ(_ℓ+1,_ℓ+1)) or at least one of the ℓt_i^j∈_ℓ^ν(ρt_ℓ(_ℓ+1,_ℓ+1)) for each of the constraint, because t_i^j holds in _ℓ iff ℓt_1^k∈_ℓ^ν(ρ) (Lemma <ref>).

We then focus on the rules in e_U(P_ℓ+1(()) ∖ P_ℓ(()),⋃_i=0^ℓ_i(ρ)) with terms in the head. The positive ones:

    ℓtℓt         for all t∈ T
    ℓ+1p   ←ℓt      for all t∈ T, p∈t∖t
    ℓ+1p   ←ℓt      for all t∈ T, p∈t∖t
    ℓ+1v   ←ℓt      for all v∈', t∈ T, s.t. (t)(v)=∅
    ℓ+1trans   ←ℓt      for all t∈ T
    ℓ+1transd'   ←ℓ+1transd      for d,d'∈{, } and d≠ d'
    ℓ+1pd'   ←ℓ+1pd      for p∈ P, d,d'∈{, } and d≠ d'
    ℓ+1vd'   ←ℓ+1vd      for v∈'d,d'∈(v)∪{} and d≠ d'

and the ones with weak negation in the body:

    ℓ+1vo   ←ℓ+1vo      for v∈' and o=_ℓ(v)
    ℓ+1v   ←ℓ+1v      for v∈' and v∉_ℓ
    ℓ+1p   ←ℓ+1p      for p∈ P and _ℓ(p) > 0
    ℓ+1p   ←ℓ+1p      for p∈ P and _ℓ(p) = 0
    ℓ+1vd   ←ℓt, ℓ+1vd      for all t∈ T, (v,d)∈(t)

whose reduct w.r.t. _ℓ^τ(ρt_ℓ(_ℓ+1,_ℓ+1))∪_ℓ+1^ν(ρt_ℓ(_ℓ+1,_ℓ+1)) are:

    ℓ+1vo         for v∈' and o=_ℓ+1(v)
    ℓ+1v         for v∈' and v∉_ℓ+1
    ℓ+1p         for p∈ P and _ℓ+1(p) > 0
    ℓ+1p         for p∈ P and _ℓ+1(p) = 0
    ℓ+1vd   ←ℓt      for all t∈ T, (v,d)∈(t), d=_ℓ+1(v)

We show that _ℓ^τ(ρt_ℓ(_ℓ+1,_ℓ+1))∪_ℓ+1^ν(ρt_ℓ(_ℓ+1,_ℓ+1)) is also a minimal model for the reduct. It's easy to see that it satisfy all the rules by construction, so we show minimality.

Removing any term from _ℓ^τ(ρ) would contradict one of the rules

    ℓtℓt

therefore ℓt_ℓ must be in _ℓ^τ(ρ) and it's the only positive action constant term. Therefore ℓ+1trans cannot be removed as well, otherwise the rule

    ℓ+1trans←ℓt_ℓ

would be violated as well.

Positive literals ℓ+1vo, ℓ+1po in _ℓ+1^ν(ρt_ℓ(_ℓ+1,_ℓ+1)) for v∈', p∈ P cannot be removed because it'd contradict the corresponding  rule among the ones:

    ℓ+1vo         for v∈' and o=_ℓ+1(v)
    ℓ+1v         for v∈' and v∉_ℓ+1
    ℓ+1p         for p∈ P and _ℓ+1(p) > 0
    ℓ+1p         for p∈ P and _ℓ+1(p) = 0

On the other hand, the negated literals must be included otherwise some of the rules

    ℓ+1pd'   ←ℓ+1pd      for p∈ P, d,d'∈{, } and d≠ d'
    ℓ+1vd'   ←ℓ+1vd      for v∈'d,d'∈(v)∪{} and d≠ d'

would be unsatisfied.


*

    To prove the first statement we should note that P_0(()) includes the following facts derived from the initially statements:
    
    0:start=   
    
            0:p=         for |p|∈ P  and |p|≠start
    
            0:v=         for |v|∈'
    
            0: trans=

    which fixes a value for each fluent, therefore for any pair of stable models M, M' of P_0(()) 0(M) = 0(M') = s_0.
    
    Regarding the second property, we first note that for all s∈ S, s(trans) = because  P_ℓ(()) only the literals itrans appear in the head of any rule for all i≤ℓ, and the constraint
    
    ←itrans, itrans

    forces either itrans or itrans to be in any stable model. Therefore itrans must be in any stable model of P_ℓ(()) for any i≤ℓ.
    
    Then we recall that (s,A,s')∈δ iff there is a stable model M_ℓ+1 of P_ℓ+1(()) for some ℓ≥ 0, s.t. ℓ(M_ℓ+1) = s', ℓ(M_ℓ+1) = s, and {a∈ T |ℓa∈ M_ℓ+1} = A. First A cannot be empty because the only rules with ℓ+1trans in the head are
    
    ℓ+1trans   ←ℓt      for all t∈ T

    therefore there must be at least a a∈ T s.t. ℓt∈ M_ℓ+1. Moreover, the dynamic laws
      
    |false after t, s|      for (t, |s|)∈ T× T  and |t|≠|s|

correspond to the constraints

    ← i:t, i:s       for (t, |s|)∈ T× T  and |t|≠|s|

which prevent two parallel actions.


*

   We prove the lemma by induction on ℓ. First we consider P_0(()), which contains the facts

    0start   
    0p         for |p|∈ P  and |p|≠start
    0v         for |v|∈'
    0trans

that, together with Lemma <ref>, ensures that _0(M_0) = (_0, _0) satisfies the conditions

    _0 =    { (start, 1) }∪{ (p, 0)| p∈ P∖{start}}
    _0 =    ∅

corresponding to the initial state (M_s, η_s).

For the inductive step, let M_ℓ+1 be a stable model for P_ℓ+1(()), then we show that _ℓ(M_ℓ+1) τ_ℓ(M_ℓ+1)_ℓ+1(M_ℓ+1) is a valid firing according to Def. <ref>. Since Lemma <ref> ensures that the mappings are well defined, we need to show that
  
  
  * a = τ_ℓ(M_ℓ+1) is enabled in _ℓ(M_ℓ+1):
   
    ℓp   ∈ M_ℓ+1      for p∈a

  and that's the case because if  there's p'∈a s.t. ℓp∉M_ℓ+1 then ℓp∈ M_ℓ+1 and the constraint
  
    ←ℓa, ℓp'

  deriving from <ref> would be contradicted.
  
  * the guard of a is satisfied in _ℓ(M_ℓ+1); i.e. the formula ⋁_i=1^k t_1^i… t_n_i^i≡_'(t) is not satisfied in _ℓ(M_ℓ+1):[Each term t_j^i is either of the form v = o or (v), and v = o↦v = o, (v) ↦v = null.]
  
    {ℓt_1^1,…, ℓt^1_n_1}   ⊈M_ℓ+1
    …
    {ℓt_1^k,…, ℓt^k_n_k}   ⊈M_ℓ+1

  if for any r {ℓt_1^r,…, ℓt^r_n_r}⊆ M_ℓ+1 then the corresponding constraint
  
    ←ℓa, ℓt_r^1, …, ℓt_n_r^r

  would be contradicted.
 
  * the marking of _ℓ+1(M_ℓ+1) is updated according to Def. <ref>:
  
    ℓ+1p   ∈ M_ℓ+1      for p∈a∖a
    ℓ+1p   ∈ M_ℓ+1      for p∈a∖a
    ℓ+1pd   ∈ M_ℓ+1      ℓpd∈ M_ℓ+1, for p∈ (P∖a∪∖a)∪ (a∩a)

  the first two conditions are ensured by the rules generated by laws <ref> and <ref>
  
    ℓ+1p   ←ℓa      for all p∈a∖a
    ℓ+1p   ←ℓa      for all p∈a∖a

  while the “inertial” laws <ref>
  
    ℓ+1po   ←ℓpo, ℓ+1po      for p∈ P and o∈{, }

  ensure the third condition; because those are the only kind of rules where a term like ℓ+1pb appears in the head.
  
  * the assignment ' of _ℓ+1(M_ℓ+1) is updated according to (a):
  
    ℓ+1v   ∈ M_ℓ+1      for v∈' s.t. (a)(v)=∅
    ℓ+1vd   ∈ M_ℓ+1      for v∈' s.t. (a)(v)≠∅, and some d∈(a)(v)
    ℓ+1vd   ∈ M_ℓ+1      ℓvd∈ M_ℓ+1, for v∈'∖ dom((a))

  The first condition is ensured by the rule
  
    ℓ+1v   ←ℓa      for all v∈', s.t. (a)(v)=∅

  derived from law <ref>. The second from the constraints
  
    ←ℓa, ℓ+1vd      [t]20emfor v∈' s.t. (a)(v)≠∅, d∈{}∪(v)∖(a)(v)

  derived from the law <ref> since if ℓ+1vo∉M_ℓ+1 then ℓ+1vo∈ M_ℓ+1, because a value must be associated to any variable and this will cause the inclusion of all the “negated” assignments for the other values different from o:
  
    ←ℓ+1vd_1,…, ℓ+1vd_k, ℓ+1v      for v∈', {d_1,…, d_k} = (v)
       ℓ+1vd'←ℓ+1vd      [t]15emfor v∈'d,d'∈(v)∪{} and d≠ d'

  The last property derives from the “inertial” constraint
  
    ℓ+1vd'   ←ℓ+1vd      for v∈'d,d'∈(v)∪{} and d≠ d'

  derived from law <ref> and the fact that any other rule with terms like ℓ+1vo in the head have ℓt in the body for some t∈ T therefore would be covered by the previous two conditions (if t = a) or trivially satisfied by a false body.















§ FURTHER TECHNICAL DETAILS OF SECTION <REF>


*



    
  * Let (,)t(',') be a valid firing of , then by Definition <ref>:
      
  
  * { p∈ P| M(p)>0}⊇t
  
  * for every p∈ P:[The simplification derives from the 1-safe assumption.]
  
	  M'(p) =
    
      0     if p∈t∖t

      1      if p∈t

      M(p)     otherwise
    
  
  
  * , (t), 
  
  * assignment ' is such that, if wr = v |(t)(v)≠∅, del  =  v |(t)(v)=∅:
  
  	
  * its domain dom(') = dom()∪wr∖del;
        
  * for each v∈ dom('):
        
          '(v) =
          
            d ∈(t)(v)     if v∈wr

            (v)      otherwise.
          
        
  

Let's consider a grounding a_t of α_t = (t(z_v_1, …, z_v_k), (α_t), (α_t)) as in Equation (<ref>) where z_v_i = '(v_i) if v_i∈wr and z_v_i = otherwise. We show that ((,), a_t, (','))∈γ by proving that (a) is satisfied in (,) and that γ((,),a_t) = (',').

    By definition
    
    
    (α_t) = (t)⋀_v∈{v_1, …, v_k} wr_t,v(z_v) ⋀_p∈t (p = )

    
    (t) is satisfied because , (t) and Lemma <ref>; for all v_i∈{v_1, …, v_k} z_v_i='(v_i)∈(t)(v_i) or z_v_i=, therefore '(v_i)∈ wr_t,v_i as defined in Eq. <ref>; finally for all p∈t p = because { p∈ P| M(p)>0}⊇t.
    
    By Definition <ref> and given that the effects of the action are
    
    
    (α_t) = ⋀_v∈{v_1, …, v_k} (v = z_v )⋀_p∈t∖t (p = ) ⋀_p∈t (p = )

    
    the planning state γ((,),a_t) is defined as
    
    γ((,),a_t) =    { (v↦'(v)) | v ∈wr∖del}∪
       { (v↦) | v ∈del}∪
       { (v↦ o) | v ∈∖wr, (v↦ o)∈(,) }∪
       { (p↦) | p∈t∖t}∪
       { (p↦) | p∈t}∪
       { (p↦ b) | p∈ P∖(t∪t), (p, b)∈(,) }

    therefore γ((,),a_t) = (',').


  * Let a_t be a ground action of α_t = (t(z_v_1, …, z_v_k), (α_t), (α_t)) and (s, a_t, s')∈γ, then by Equation (<ref>) and Definition <ref>


  * s satisfies (t);

  * for all z_v where v∈wr, z_v∈(t)(v) if v∉del and z_v= otherwise;

  * (p↦)∈ s for all p∈t

because s satisfies (a_t), therefore the state (,) = (s) satisfies

    { p∈ P| M(p)>0}⊇t
    , (t)


Moreover the state s' is such that
    
    s' = γ(s,a_t) =    { (v↦ z_v) | v ∈wr∖del}∪
       { (v↦) | v ∈del}∪
       { (v↦ o) | v ∈∖wr, (v↦ o)∈ s }∪
       { (p↦) | p∈t∖t}∪
       { (p↦) | p∈t}∪
       { (p↦ b) | p∈ P∖(t∪t), (p↦ b)∈ s }

so the state (',') = (s') satisfies

    '(v)    =
        
        z_v∈(t)(v)    if v∈wr∖del
    undefined   if v∈del
    (v)     otherwise
    
        M'(p)    =
        
          0    if p∈t∖t
    
          1     if p∈t
    
          M(p)    otherwise


Therefore (s)t(s') is a valid firing.









§ TECHNICAL DETAILS OF SECTION <REF>


To relate cases from W^τ to the original workflow W we introduce a “projection” function _τ that maps elements from cases of the enriched workflow to cases using only elements from the original workflow. To simplify the notation we will use the same name to indicate mappings from states, firings and cases.


  Let W = ,  = P,T,F, , be a , τ = (e_1,…, e_n) – where e_i = t_i,w_i, w_i^d a trace of W, and W^τ = , ^τ = P^τ,T^τ,F^τ, ^τ, ^τ the corresponding trace workflow. The mapping _τ is defined as following:
  
    
  * let ' be a marking of W^τ, then
    
    _τ(') = '∩ P×ℕ

    is a marking of W;
    
  * let (',') be a state of W^τ, then
    
    _τ((',')) = (_τ('),')

    is a state of W;
    
  * let t be a transition in T^τ, then
    
    _τ(t) = 
        t_i    for t = t_e_i
    
        t    for t∈ T

    is a transition of W;
  
  * let (,)t(',') be a firing in W^τ, then
  
    _τ((,)t(',')) = _τ((,))_τ(t)_τ((','))

    is a firing in W;
  
  * let C = f_0,…,f_k be a sequence of valid firings in W^τ, then 
  
    _τ(C) = _τ(f_0),…,_τ(f_k)

  is a sequence of valid firings in W.
  


In the following we consider a W = ,  = P,T,F, , and a trace τ = (e_1,…, e_n) of W – where e_i = t_i,w_i, w_i^d. Let W^τ = , ^τ = P^τ,T^τ,F^τ, ^τ, ^τ be the corresponding trace workflow. To simplify the notation, in the following we will use t_e_0 as a synonymous for start_t and t_e_n+1 as end_t; as if they were part of the trace.

 
	
  If C is a sequence of valid firings in W^τ then _τ(C) is a sequence of valid firings in W.



  Let C = (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k), to show that _τ(C) is a case of W we need to prove that 
 [(i)]
  
  * _τ((_0,_0)) is an initial state of W; and 
  
  * the firing _τ((_i-1,_i-1)t_i(_i,_i)) is valid w.r.t. W for all 1≤ i≤ n.

[i)]

  * By definition _τ((_0,_0)) = (_τ(_0),') and _τ(_0)⊆_0. Since the start place is in P, then start is the only place with a token in _τ(_0).

  * Let consider an arbitrary firing f_i = (_i-1,_i-1)t_i(_i,_i) in C (valid by definition), then _τ(f_i) = (_τ(_i-1),_i-1)_τ(t_i)(_τ(_i),_i).

  Note that – by construction – (t_i) is a restriction of (_τ(t_i)), _τ(t_i) = t_i∩ P, _τ(t_i) = t_i∩ P, dom((t_i)) = dom((_τ(t_i))) and (t_i)(v)⊆(_τ(t_i))(v) ; therefore
  
    
  
  * p∈ P^τ|_i-1>0∩ P = { p∈ P|_τ(_i-1)>0}⊇_τ(t_i) because p∈ P^τ|_i-1>0⊇t_i;
  
  * , (_τ(t_i)) because , (t_i)
  
  * for all p∈ P _τ(_j)(p) = _j(p), therefore:
  
    _i(p) = _τ(_i)(p) =
    
      _i-1(p)-1 = _τ(_i-1)(p) - 1     if p∈_τ(t_i)∖_τ(t_i)

      _i-1(p)+1 = _τ(_i-1)(p) + 1     if p∈_τ(t_i)∖_τ(t_i)

      _i-1(p) = _τ(_i-1)(p)     otherwise
    
  
  because f_i is valid w.r.t. W^τ;
  
  * the assignment _i satisfies the properties that its domain is 
    dom(_i) = dom(_i-1)∪v|(_τ(t_i))(v)≠∅∖v|(_τ(t_i))(v)=∅
 and for each v∈ dom(_i):
  
    _i(v) =
    
      d ∈(t_i)(v)⊆(_τ(t_i))(v)     if v∈ dom((t_i)) = dom((_τ(t_i)))

      _i-1(v)      otherwise.
    
  
  because f_i is valid.





Before going into details, we will consider some properties of the “trace” workflow.


  Let W = ,  = P,T,F, , be a and τ = (e_1,…, e_n) – where e_i = t_i,w_i, w_i^d – a trace of W. If C = (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k) is a sequence of valid firings in W^τ then for all 0≤ i≤ k: 
    Σ_p∈ P^τ∖ P_i(p)≤_0(start)



  By induction on the length of C.
  
    
  * For k=1 then the only executable transition is start_t, therefore t_1 = start_t which – by assumption – has two output places and – by construction – start_t∖ P = p_e_0. Since the firing is valid, then _1(p_e_0) = _0(p_e_0) + 1 = 1≤_0(start).
    
  * Let's assume that the property is true for a sequence C of length n and consider C' = C (_n,_n)t_n+1(_n+1,_n+1). By construction, each p∈ P^τ∖ P has a single incoming edge and t∈ T^τ| e_i∈t = t_e_i and t∈ T^τ| e_i∈t = t_e_i+1. Therefore the only occurrence in which a p_e_i∈ P^τ∖ P can increase its value is when t_n+1 = t_e_i. Since the transition is valid, then _n+1(p_e_i) = _n(p_e_i) + 1 and _n+1(p_e_i-1) = _n(p_e_i-1) - 1; therefore Σ_p∈ P^τ∖ P_i(p) = Σ_p∈ P^τ∖ P_i-1(p)≤_0(start) – by the inductive hypothesis.
  



  Let W = ,  = P,T,F, , be a and τ = (e_1,…, e_n) – where e_i = t_i,w_i, w_i^d – a trace of W, C = (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k) a sequence of valid firings in W^τ, and t_e_i is a transition of a firing f_m in C with 1≤ i≤ n, then
    [(i)]
    
  * t_e_i-1 is in a transition of a firing in C that precedes f_m, 
    
  * and if _0(start)=1 then there is a single occurrence of t_e_i in C.
    

  


  The proof for the first part follows from the structure of the workflow net; because – by construction – each p∈ P^τ∖ P has a single incoming edge and t∈ T^τ| e_i∈t = t_e_i and t∈ T^τ| e_i∈t = t_e_i+1.
  Since each firing must be valid – if f_m = (_m-1,_m-1)t_e_i(_m,_m) is in C, then _m-1(p_e_i-1)≥ 1 and this can only be true if there is a firing f_r = (_r-1,_r-1)t_e_i-1(_r,_r) in C s.t. r<m.
  
  To prove the second part is enough to show that for each 1≤ i≤ n, if t_e_i appears more than once in C then there must be multiple occurrences of t_e_i-1 as well. In fact, if this is the fact, then we can use the previous part to show that there must be multiple occurrences of t_e_0 = start, and this is only possible if _0(start)>1. 
  
  By contradiction let's assume that there are two firings f_m and f_m', with m<m', with the same transition t_e_i, but there is only a single occurrence of t_e_i-1 in a firing f_r. Using the previous part of this lemma we conclude that r<m<m', therefore _m-1(p_e_i-1) = 1 because a token could be transferred into p_e_i-1 only by t_e_i-1, so _m(p_e_i-1) = 0. In the firings between m and m' there are no occurrences of t_e_i-1, so _m'-1(p_e_i-1) = _m(p_e_i-1) = 0 which is in contradiction with the assumption that f_m' is a valid firing. 


Now we're ready to show that the “trace” workflow characterises all and only the cases compliant wrt the given trace. We divide the proof into correctness and completeness.

 Let W = ,  = P,T,F, , be a , τ = (e_1,…, e_n) – where e_i = t_i,w_i, w_i^d – a trace of W, and C = (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k) be a sequence of valid firings in W^τ s.t. _0(start) = 1; given ℓ = max(i| t_e_i is in a firing of C∪0), then the trace τ' = (e_1,…, e_ℓ) if ℓ > 0 or τ' = ∅ if ℓ = 0 is compatible with the sequence _τ(C) in W. 



  By induction on the length of C.
  
    
  * If C = (_0,_0)t_1(_1,_1) then t_1 = start_t because the firing is valid and the only place with a token in _0 is start; therefore ℓ = 0 and τ' is the empty trace, and C trivially satisfy the empty trace.
    
  * Let C = (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k) s.t. _τ(C) is compliant with τ'. Let's consider C' = C · (_k,_k)t_k+1(_k+1,_k+1): either t_k+1∈ T^τ∖ T or t_k+1∈ T.
    
    In the first case t_k+1 = t_e_ℓ for some 1≤ℓ≤ n, and – by using Lemma <ref> – in C there are occurrences of all the t_e_i for 1≤ i<ℓ and it's the only occurrence of t_e_ℓ. This means that ℓ = max(i| t_e_i is in a firing of C∪0) and we can extend γ to γ' by adding the mapping from ℓ to k+1. The mapping is well defined because of the single occurrence of t_e_ℓ. By definition of t_e_ℓ, (_k,_k)t_k+1(_k+1,_k+1) is compliant with e_ℓ because the additional conditions in ^τ'(t_k+1) guarantee the proper assignments for variables that are not assigned by the transition (Def. <ref>). Moreover the mapping _τ preserve the assignments, therefore _τ(_k,_k)t_k+1(_k+1,_k+1) is compliant with e_ℓ as well. By using the inductive hypnotises we can show that C' is compliant as well.
    
    In the second case the mapping is not modified, therefore the inductive hypothesis can be used to provide evidence of the first two conditions for trace compliance of Definition <ref>.
  


 Let W = ,  = P,T,F, , be a , τ = (e_1,…, e_n) – where e_i = t_i,w_i, w_i^d – a trace of W, and  C = (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k) be a sequence of valid firings in W such that τ is compliant with it, then there is a sequence of valid firings C' in W^τ s.t. _τ(C') = C.


  Since C is compliant with τ, then there is a mapping γ satisfying the conditions of Definition <ref>. Let C' = ('_0,_0)t'_1('_1,_1)… ('_k-1,_k-1)t'_k('_k,_k) a sequence of firing of W^τ defined as following:
  
    
  * '_0 = _0∪(p_e_i,0)| 0≤ i≤ n
    
  * t'_1 = t_1 and '_1 = _1∪(p_e_j,0)| 1≤ j≤ n∪(p_e_0,1)
    
  * for each ('_i-1,_i-1)t'_i('_i,_i), 2≤ i≤ n:
    
    
  * if there is ℓ s.t. γ(ℓ) = i then t'_i = t_e_ℓ and 
    '_i = _i∪(p_e_j,0)| 0≤ j≤ n, j≠ℓ∪(p_e_ℓ,1)

    
  * otherwise t'_i = t_i and 
    '_i = _i∪('_i-1∩ (P^τ∖ P)×ℕ)

    
  
  It's not difficult to realise that by construction _τ(C') = C. 
  
  To conclude the proof we need to show that C' is a sequence of valid firing in W^τ. Clearly ('_0,_0) is a starting state, so we need to show that all the firings are valid. The conditions involving variables – guards and update of the assignment – follows from the fact that the original firings are valid and the newly introduced transitions are restricted according to the trace data.
  
  Conditions on input and output places that are both in W and W^τ are satisfied because of the validity of the original firing and the additional conditions for the guards of newly introduced transitions are satisfied because of τ is compliant with C. The newly introduced places satisfy the conditions because of the compliance wrt the trace, which guarantees that for each firing with transition t_e_ℓ there is the preceding firing with transition t_e_ℓ-1 that put a token in the p_e_ℓ-1 place.


*
 


  
  ⇒ If C is a case of W^τ then it must contain t_e_n (the only transition adding a token in the sink), therefore the ℓ of Lemma <ref> is n so τ' = τ and τ is compliant with _τ(C).
  
  ⇐ If τ is compliant with C then by Lemma <ref> there is a case C' of W^τ s.t. _τ(C') = C. Morevover, since the last state of C is a final state, so must be the final state of C' because by construction there cannot be any token in the newly introduced places after the last transition t_e_n.

 



*



  We prove the theorem by induction on the length of an arbitrary sequence of valid firings C = (_0,_0)t_1(_1,_1)… (_k-1,_k-1)t_k(_k,_k) in W^τ . Note that by construction, for any marking M' of W^τ and p∈ P, M'(p) = _τ(M')(p).
  
    
  * For a case of length 1 the property trivially holds because by definition _0(start) ≤ k and for each p∈ P^τ (different from start) _0(start) = 0, and since (_0,_0)t_1(_1,_1) is valid the only case in which the number of tokens in a place is increased is for p∈t_1∖t_1. For any p different from start this becomes 1≤ k; while since the start place – by assumption – doesn't have any incoming arc therefore _1(start) = _0(start) - 1≤ k.
    
  * For the inductive step we assume that each marking _0,…_m-1 is k-safe. By contradiction we assume that _m is not k-safe; therefore there is a place p∈ P^τ s.t. _m>k. There are two cases, either p∈ P^τ∖ P or p∈ P. In the first case there is a contradiction because, by Lemma <ref>, Σ_p∈ P^τ∖ P_i(p)≤_0(start) = k. In the second case, since _τ(C) is a case of W and _τ(_m)(p) = _m(p), there is a contradiction with the hypothesis that W is k-safe.
  






plainnat


