Activity diagrams are widely used in the business process modeling domain, for software documentation, and code generation. Revealing the semantic di erences between activity diagrams is crucial for model evolution analysis to explore design alternatives and to detect errors. Existing approaches to semantic di erencing of activity diagrams are based on complex and hard to understand translations to other problem spaces. The translations are implicit in the sense that they transform ADs to a model in the input format of a model checker, which again encodes another formalism. We present a simple and explicit translation from activity diagrams to nite automata and de ne the semantics of activity diagrams as the words recognized by these automata. This enables semantic di erencing of activity diagrams via language inclusion checking between nite automata. We formally de ne the translation and present an implementation. The resulting simple and explicit translation increases comprehensibility of the semantic di erencing operator and reduces implementation e orts.
Activity diagrams (ADs) describe how an activity or a process needs to be
performed. This paper considers an expressive variant of ADs with actions,
branching fragments modeled with decision and merge nodes, and parallel fragments
modeled with fork and join nodes. We use the standard notations of the UML [
In contrast to previous work [
We formally de ne the translation and present an implementation based on
the language workbench MontiCore [
Section 2 presents motivating examples, before Section 3 introduces preliminaries and notations as used in this paper. Then, Section 4 presents an abstract syntax for ADs, an operational semantics based on nite automata, a denotational semantics based on execution traces, and semantic di erencing of ADs. Afterwards, Section 5 presents an implementation of the di erencing operator as well as several example applications. Section 7 concludes. 2
This section motivates this paper's method with four example ADs previously
presented in [
Example 1
Figure 1 depicts two ADs from [
In the original work ow, the employee is rst registered. Then, the employee either directly gets assigned a project before her payment is authorized, or the employee gets a welcome package before her contact data is added to the company website, she is assigned a project, she is interviewed by the manager, and gets a manager report, before her payment is nally authorized. The actions of adding the employee to the company website and assigning the employee to a project can be executed independent of each other, i.e., there is no strict order
Manager Interview
Manager
Report Manager Interview in which the two actions have to be executed. The company decides to explicate that new employees must receive keys to enter the building. The company thus changes the work ow hire.v1 by adding the action labeled Assign Keys as depicted in the bottom part of Figure 1.
A manager wants to understand how the syntactic changes impact the AD's possible execution traces. Using our method for semantic di erencing reveals that there are possible execution traces of hire.v1 that are not possible in hire.v2 and vice versa. Thus, execution traces have been removed and new execution traces have been added. The manager gets presented that Register; Get Wel: Package; Assign to Project; Add to Website; Manager Interview; Manager Report; Authorize Payment is a possible execution trace of hire.v1 that is no execution trace of hire.v2. This execution trace has been removed during the evolution of the work ow. Vice versa, the manager is presented an execution trace including the action Assign Keys, which is possible in hire.v2 and not possible in hire.v1. This execution trace has been added during the evolution from hire.v1 to hire.v2. 2.2
Example 2
Figure 2 depicts two ADs previously presented in [
Record Claim
Check
Claim Record Claim
Check
Claim M1
D1 Retrieve Add. Data
Settle Claim Reject Claim Settle Claim Reject Claim
Send
Letter Calculate Loss Amount
Recalc.
Cost. Contr.
Send Declinature
Update Cost. Record
Calculate Loss Amount
Recalc.
Cost. Contr.
Send
Letter
Send Declinature
Call Costumer
Payout Close Claim
Payout wf1 wf2
Claim; Reject Claim, Send Declinature, Update Cost: Record, Close Claim is a possible execution trace of wf1 that is not possible in wf2. 3
This section introduces the notations for "-NFAs (e.g. [
Let A = (Q; ; ; Q0; F ) be an NFA. For all q 2 Q, let EA(q) Q denote the epsilon closure of q in A, i.e., the set of states reachable from q in A by following transitions from labeled with ". It is de ned as the smallest set satisfying q 2 EA(q) and 8p 2 EA(q) : 8(s; a; t) 2 : (s = p ^ a = ") ) t 2 EA(q).
Let n 2 N. The automaton A accepts a word w = w1; w2; :::wn 2 exists a nite sequence of states r = r0; r1; :::; rn 2 Q satisfying i there 1. r0 2 EA(q0), 2. ri+1 2 EA(r0) where r0 2 Q such that (ri; ai+1; r0) 2 3. rn 2 F . for all 0 i < n,
The language recognized by A is de ned as L(A) = fw 2 j A accepts wg.
There exist well-known algorithms for checking if the language recognized by an
"-NFA is included in the language recognized by another "-NFA [
This section de nes the syntax and semantics of ADs as used in this paper. To this e ect, we de ne the abstract syntax of ADs and a translation from ADs to "-NFAs. The semantics of an AD is then de ned as the language recognized by the "-NFA obtained from translating the AD. 4.1
Activity Diagram Syntax The abstract syntax of ADs is de ned as follows.
De nition 2. An AD is a tuple (L; N; A; i; F; XOR; AN D; T; l) where { L is an alphabet containing action labels, { N is a nite set of nodes, { A N is a set of action nodes, { i 2 N is the initial node, { F N is a non-empty set of nal nodes, { XOR N is a set of decision and merge nodes, { AN D N is a set of fork and join nodes, { T N N is the transition relation, { l : N ! L [ f"g is the node labeling function that is required to map each control- ow node to the empty word, i.e., 8n 2 N n A : l(n) = ", { fA; fig; F; XOR; AN Dg is a partition of N .
For an AD ad = (L; N; A; i; F; XOR; AN D; T; l) and all nodes n 2 N , we denote by a+d(n) d=ef f(n; x) T j x 2 N g the set of outgoing transitions starting in n. Similarly, ad(n) denotes the set of incoming transitions ending in n.
The AD hire:v1 (cf. Figure 1), for instance, can be formally de ned by hire:v1 = (L; N; A; i; F; XOR; AN D; T; l) with { labels L = fRegister; Assign to Project; Get Wel: Package; Add to
Website; Manager Interview; Manager Report; Authorize Paymentg, { nodes N = fR; AT P 1; GW P; AT P 2; AT W; M I; M R; AP; D1; M 1; F 1; J 1; i; f g, { action nodes A = fR; AT P 1; GW P; AT P 2; AT W; M I; M R; AP g, { initial node i, { nal nodes F = ff g, { decision and merge nodes XOR = fD1; M 1g, { fork and join nodes AN D = fF 1; J 1g, { the transition relation T = f(i; R); (R; D1); (D1; AT P 1); (AT P 1; M 1); (D1; GW P ); (GW P; F 1); (F 1; AT P 2); (F 1; AT W ); (AT P 2; J 1); (AT W; J 1); (J 1; M I); (M I; M R); (M R; M 1); (M 1; AP ); (AP; f )g, and { labeling function l with l(R) = Register, l(AT P 1) = Assign to Project, l(GW P ) = Get Wel: Package, l(AT P 2) = Assign to Project, l(AT W ) = Add to Website, l(M I) = Manager Interview, l(M R) = Manager Report, l(AP ) = Authorize Payment, and l(D1) = l(M 1) = l(F 1) = l(J 1) = l(i) = l(f ) = ".
Usually, the following (or even stronger) well-formedness rules apply (e.g. [
Activity Diagram Semantics This section explicitly de nes a mapping from ADs to "-NFAs. The "-NFA resulting from translating an AD encodes exactly the traces modeled by the AD under the assumption that exactly one action can be performed at a point in time. Stated di erently, no two action can be performed simultaneously. The semantics of an AD is then de ned as the language recognized by the "-NFA that it is mapped to. ADs contain action labels whereas "-NFAs contain transition labels. The mapping therefore inverts nodes and transitions of an AD during the translation, i.e., the nodes of the AD correspond to transitions in the "-NFA and the transitions in the AD correspond to the "-NFA's states. The state set of the automaton is given by the powerset of the set of transitions of the AD. Using the powerset is necessary as an AD can reside in several nodes simultaneously (after visiting a fork node). The set of transition labels in the "-NFA is equal to the set of node labels in the AD. The initial state of the automaton is the singleton set containing the transition that has the initial AD node as source node. The nal states are exactly the singleton sets containing a transition that has a nal AD node as target node. The transition relation is de ned as the smallest set of transitions satisfying two conditions. The rst condition encodes the AD's behavior in case it executes a node that is neither a join nor a fork node. If an action node is executed, then the AD moves out of the executed action via the action's outgoing transition to the next node and outputs the action node's label. The AD's execution state regarding other nodes remains unchanged. Similarly, if the AD proceeds through a decision or merge node, its state regarding the other nodes remains unchanged and it outputs nothing (the empty word "). The situation is di erent for fork and join nodes: An AD can only proceed through a join or fork node if its state contains all nodes that have a transition to the node. Further, if the AD proceeds through a fork or join node, it leaves all states that precede the node and enters all states that the node leads to. De nition 4. Let ad = (L; N; A; i; F; XOR; AN D; T; l) be a well-formed AD. The "-NFA associated to ad is de ned as nf a(ad) = (Q; ; ; q0; F 0) where { Q = P(T ), { = L, { q0 = f(s; t) 2 T j s = ig, { F 0 = ff(s; t)g T j t 2 F g, and { Q ( [ f"g) Q is the smallest set satisfying the following conditions: Move other than fork or join: 8X T : 8n1; n2; n3 2 N : ((n1; n2) 2 X ^ (n2; n3) 2 T ^ n2 2= AN D) ) (X; l(n2); (X n f(n1; n2)g) [ f(n2; n3)g) 2 Move fork or join: 8X T : 8j 2 AN D : ( ad(j) X) ) (X; "; (X n ad(j)) [ a+d(j)) 2 The trace semantics sem(ad) of an AD ad is de ned as the language recognized by the "-NFA associated to the AD ad, i.e., sem(ad) d=ef L(nf a(ad)).
As an example, Figure 3 depicts the "-NFA obtained from translating the AD hire.v1 (graphically illustrated in Figure 1 and formally de ned in subsection 4.1) after removing the states and transitions that are not reachable from the initial state. A possible execution trace of the AD is, for example, given by Register; Assign to Project; Authorize Payment 2 sem(hire:v1). 4.3
Semantic Di erencing of Activity Diagrams The (asymmetric) semantic di erence (ad1; ad2) between two ADs ad1, ad2 is de ned as the set of traces possible in the AD ad1 that are not possible in
AD
hire.v1
hire.v2
wf1
wf2
the AD ad2, i.e., (ad1; ad2) = sem(ad1) n sem(ad2). With the explicit
mapping from ADs to "-NFAs, reuse of well-known constructions from automata
theory [
We have implemented a prototype for the semantic di erencing operator using
the language workbench MontiCore [
Semantic di erencing of ADs is introduced in [
Other direct translations from ADs and business process models to nite
automata focus on deadlock detection [
Other semantics de nitions for ADs are based on Petri nets [
We formally de ned an abstract syntax of an AD variant. Based on this, we presented an operational semantics for ADs via a translation from ADs to "-NFAs and a denotational semantics given by the language recognized by these "-NFAs. This enabled to reuse well-known algorithms for language inclusion checking between "-NFAs for semantic di erencing of ADs. We presented a tool prototype and applied the semantic di erencing operator to four example ADs, which showed that the di erencing operator yields promising results. The translation enables a comprehensive and easy to implement method for semantic di erencing of ADs, which ultimately facilitates semantic AD evolution analysis.