Synthesizing object life cycles from business process models

Unified modeling language (UML) activity diagrams can model the flow of stateful business objects among activities, implicitly specifying the life cycles of those objects. The actual object life cycles are typically expressed in UML state machines. The implicit life cycles in UML activity diagrams need to be discovered in order to derive the actual object life cycles or to check the consistency with an existing life cycle. This paper presents an automated approach for synthesizing a UML state machine modeling the life cycle of an object that occurs in different states in a UML activity diagram. The generated state machines can contain parallelism, loops, and cross-synchronization. The approach makes life cycles that have been modeled implicitly in activity diagrams explicit. The synthesis approach has been implemented using a graph transformation tool and has been applied in several case studies.

Authors and Affiliations

1. Eindhoven University of Technology, P.O. Box 513, 5600 MB,  Eindhoven, The Netherlands

   Rik Eshuis & Pieter Van Gorp

Corresponding author

Correspondence to Rik Eshuis.

Communicated by Professor Brian Henderson-Sellers.

Appendix: Formal definitions

This appendix contains formal definitions of the syntax of activity diagrams and state machines (Appendix 9.1), the filtering rules (Appendix 9.2), the transformation rules that result in state machines (Appendix 9.3), the refactoring rules that deal with cross-synchronization (Appendix 9.4), plus a proof of correctness (Appendix 9.5).

1.1 Activity diagrams and state machines

An activity diagram is a graph that specifies the ordering of activities and the flow of objects that are used by the activities.

Definition 1

(Activity diagrams) An activity diagram is a tuple \((A,O,C,E,guard,instate)\) where

• \(A\) is the set of activities;

• \(O\) is the set of object nodes. For this paper, we assume that all object nodes refer to the same object, which is therefore not formalized;

• \(C\) is the set of control nodes, also called pseudo-nodes, partitioned into sets \(\{i\}\), \(DM\), \(FJ\), \(F\), where

  • \(i\) is the unique start node, which has no predecessor;

  • \(DM\) is the set of decisions and merges;

  • \(FJ\) is the set of forks and joins;

  • \(F\) is the set of final nodes, which have no successors;

• \(E \subseteq A \cup O \cup C \times A \cup O \cup C\) is the set of flow edges, where an edge that enters or leaves an object node in \(O\) is called an object flow; all other edges are control flows;

• \(guard: E \rightarrow L\) is a partial function assigning a guard label from the set of labels \(L\) to an edge. We only allow guard labels on edges leaving decision nodes;

• \(instate: O \rightarrow \mathcal {S}\) is a function that specifies for each object node the unique state in \(\mathcal {S}\) that the object is in.

We put some constraints on the edge relation \(E\):

• the induced graph is weakly connected, so for every pair of nodes \(n_1,n_2 \in A \cup O \cup C\), there is an undirected path between \(n_1\) and \(n_2\);

• \(i\) has no predecessor;

• each node \(f \in F\) has no successors;

• each activity \(a \in A\) has one incoming control flow and one outgoing control flow.

• each control node \(n \in C{\setminus }(\{i\} \cup F)\), except the initial and final nodes, has a predecessor and a successor.

As explained in Sect. 2, we consider in this paper only activity diagrams that process a single stateful object. Each different state of the object is represented with an object node. The stateful object has a life cycle that is represented in a state machine.

A state machine is hierarchical hypergraph [17], consisting of nodes arranged in a tree and directed hyperedges. There are three types of nodes: BASIC, AND, and OR. BASIC nodes are leaves of the tree, while AND and OR node are internal. The state machine formalization used here stems from earlier work [11]. That work also defines an execution semantics of state machines.

Definition 2

A state machine is a tuple \((N,H,source\), \(target, guard, child, default,r)\), where

• \(N\) is a set of nodes, which is partitioned into sets \(BN\), \(AN\), and \(ON\), where

  • \(BN\) is a finite set of BASIC nodes, which are not decomposed into other nodes;

  • \(AN\) is a finite set of AND nodes, which specify parallel decomposition;

  • \(ON\) is a finite set of (X)OR nodes, which specify exclusive-or decomposition;

• \(H\) is a finite set of hyperedges, \(N \cap H = \emptyset \);

• \(source: H \rightarrow \mathcal {P}(N)\) is a function defining the non-empty set of source nodes for each hyperedge;

• \(target: H \rightarrow \mathcal {P}(N)\) is a function defining the non-empty set of target nodes for each hyperedge;

• \(guard: H \rightarrow L\) is a partial function assigning a guard label from \(L\) to a hyperedge;

• \(child \subseteq N \times N\) is a predicate that relates a child node to its parent node, so \((n,n') \in child\) means \(n\) is child of \(n'\). We require that \(child\) arranges the nodes in \(N\) in a rooted tree, so every node in \(N\), except the root, has one parent node, and every node is indirectly child of the root. We require \(x \in BN\) if and only if \(\{y ~|~(y,x) \in child\}=\emptyset \), so only BASIC nodes have no children.

• \(default: ON \rightarrow N\) is a function that identifies for each OR node \(n\) one of its children as the default node: \(default(n)\in children(n)\). As defined below in the semantics, if a hyperedge \(h\) enters \(n\) but does not explicitly enter any of its children, then \(h\) enters \(default(n)\).

• \(r \in N\) is the root of the tree induced by \(child\). For technical reasons, \(r\) is required to be an OR node.

1.2 Filtering rules

Formal definitions are presented for the filtering rules presented in Sect. 3. Each rule operates on an activity diagram \((A,O,C,E,guard,instate)\) and consists of a (pre)condition and an effect, which is the new activity diagram tuple \((A',O',C',E',guard',instate')\). We only define the elements of the tuple that are changed, so if for instance \(A'\) is omitted, then \(A'=A\).

To define the rules in a concise way, we introduce additional notation. Let \(n \in A \cup O \cup C\) be a node. Then \(in(n)=\{~n'~|~(n',n) \in E~\}\) and \(out(n)=\{~n'~|~(n,n')\in E~\}\). For a binary relation \(R\), the relation \(R(x \leftarrow y)\) is the relation obtained by replacing each appearance of \(y\) with \(x\) in each tuple of \(R\) [13].

Definition 3

(Rule R1) Condition. There is a node \(n \in A \cup C\) such that \({{|}{in(n)}{|}}={{|}{out(n)}{|}}=1\).

Effect. Let \(\{n_1\}=in(n)\) and \(\{n_2\}=out(n)\). Then

• \(A'=A {\setminus } \{n\}\);

• \(C'=C {\setminus } \{n\}\);

• \(E'=(E \cap ((A'\cup O'\cup C') \times (A'\cup O' \cup C') )) \cup (n_1,n_2)\)

• \(instate'=instate \cap (O' \times S)\).

Definition 4

(Rule R2) Condition. There are decisions/merges \(d_1,d_2 \in DM\) such that \((d_1,d_2) \in E\) and \({{|}{in(d_2)}{|}}=~1\).

Effect.

• \(C'=C {\setminus } \{d_2\}\);

• \(E'=(E {\setminus } \{(d_1,d_2)\})(d_1 \leftarrow d_2)\);

• \(guard'=(guard \cap ((A \cup O \cup C')\times L)) \oplus \{(d_2,x)\mapsto g~|~x \in A \cup O \cup C' \wedge g=guard((d_1,d_2)) \wedge guard(d_2,x)\}\),

where \(\oplus \) denotes function overriding.

Definition 5

(Rule R3) Condition. There are decisions/merges \(d_1,d_2 \in DM\) such that \((d_1,d_2) \in E\) and \({{|}{out(d_1)}{|}}=~1\).

Effect.

• \(C'=C {\setminus } \{d_1\}\);

• \(E'=(E {\setminus } \{(d_1,d_2)\})(d_2 \leftarrow d_1)\);

Definition 6

(Rule R4) Condition. There is a decision/merge \(n \in DM\) such that \((n,n) \in E\).

Effect.

• \(C'=C {\setminus } \{n\}\);

• \(E'=E {\setminus } \{(n,n)\}\);

Definition 7

(Rule R5) Condition. There are fork/joins \(n_1,n_2 \in FJ\) such that \((n_1,n_2) \in E\) and there is a simple path of length 2 or more from \(n_1\) to \(n_2\).

Effect.

• \(E'=E {\setminus } \{(n_1,n_2)\}\);

Definition 8

(Rule R6) Condition. There is a fork or join \(n \in FJ\) and a final node \( f\in F\) such that \((n,f) \in E\) and \({{|}{out(f)}{|}}>1\).

Effect.

• \(C'=C {\setminus } \{f\}\);

• \(E'=E {\setminus } \{(n,f)\}\);

Definition 9

(Rule R7) Condition. There are forks or joins \(n_1,n_2 \in FJ\) such that \((n_1,n_2) \in E\), \({{|}{out(n_1)}{|}}>1\) and \({{|}{in(n_2)}{|}}=1\).

Effect.

• \(C'=C {\setminus } \{n_2\}\);

• \(E'=(E {\setminus } \{(n_1,n_2)\})(n_1 \leftarrow n_2)\);

Definition 10

(Rule R8) Condition. There are forks or joins \(n_1,n_2 \in FJ\) such that \((n_1,n_2) \in E\), \({{|}{out(n_1)}{|}}=1\) and \({{|}{in(n_2)}{|}}>1\).

Effect.

• \(C'=C {\setminus } \{n_1\}\);

• \(E'=(E {\setminus } \{(n_1,n_2)\})(n_2 \leftarrow n_1)\);

Definition 11

(Rule R9) Condition. There is a decision \(d \in DM\) and object node \(o \in O\) such that

• there is a fork \(f \in FJ\) such that \(in(d)=\{f\}=in(o)\);

• \(out(d)=out(o)\);

• \(out(d),out(o) \subseteq FJ\).

Effect.

• \(C'=C {\setminus } \{d\}\);

• \(E'=E \cap (( A \cup O \cup C') \times ( A \cup O \cup C')) \);

• \(guard'=(guard \cap ((A \cup O \cup C')'\times L)) \oplus \{(o,x)\mapsto g~|~x \in N' \wedge g=guard((d,x))\}\).

Definition 12

(Rule R10) Condition. There is a merge \(m \in DM\) and object node \(o \in O\) such that

• there is a join \(j \in FJ\) such that \(out(m)=\{j\}=out(o)\);

• \(in(m)=in(o)\);

• \(in(m),in(o) \subseteq FJ\).

Effect.

• \(C'=C {\setminus } \{m\}\);

• \(E'=E \cap (( A \cup O \cup C') \times ( A \cup O \cup C')) \);

1.3 Transformation rules

There are three transformation rules. Each rule operates on an expanded activity diagram. An expanded activity diagrams contains AND/OR trees, the leaves of which are object nodes or control nodes that are not bars. The internal nodes of each tree are AND and OR nodes. Edges only connect bars and OR nodes that root the AND/OR trees.

We first define expanded activity diagram; next, we define the initialization rule that transforms a filtered activity diagram into an expanded activity diagram.

Definition 13

(Expanded activity diagram) An expanded activity diagram is a tuple \((A,O,C,E,guard, instate, AN\), \(ON,parent)\) where

• \(A\), \(O\), \(C\), \(guard\), and \(instate\) are as defined for activity diagrams;

• \(E \subseteq (ON \cup FJ) \times (ON \cup FJ)\) is the edge relation, now defined between OR nodes and fork and joins only;

• \(ON\) is the set of OR nodes;

• \(AN\) the set of \(AND\) nodes;

• \(parent: (O\cup C \cup AN \cup ON) \rightarrow (AN\cup ON)\) is a function that maps a child node to its unique parent node.

Definition 14

(Initialization) Condition. None of the filtering rules R1–R8 apply to the activity diagram \((A,O,C,E\), \(guard,instate)\), so \(A=\emptyset \). There is no edge connecting two forks/joins: \( E \cap (FJ \times FJ)=\emptyset \). If the latter constraint is violated, so there are forks or joins \(n_1\), \(n_2 \in FJ\) and \((n_1,n_2)\in E\) then a dummy object node \(o\) can be inserted between the forks/joins, so \((n_1,n_2)\) is replaced with \((n_1,o)\) and \((o,n_2)\) in \(E\).

Effect. The expanded activity diagram is defined as the tuple \((A',O',C',E',guard',instate',AN',ON',parent')\), where

• \(A'=A\);

• \(O'=O\);

• \(C'=C\);

• \(E'=E(on_n \leftarrow n)\) for each \(n \in A \cup O \cup (C{\setminus } FJ)\);

• \(guard'=\{~(on_n,x)\mapsto g~|~n \in DM \wedge x \in A \cup O \cup C \wedge g=guard(on_n,x)~\}\)

• \(instate'=\emptyset \);

• \(AN'=AN\);

• \(ON'=\{~on_o~|~o \in O~\} \cup \{~on_c~|~c \in C {\setminus } FJ~\} \);

• \(parent'=\{~(n,on_n)~|~n \in O'\cup C'~\} \).

The transformation rules T1 and T2 operate on expanded activity diagrams. As the filtering rules, each transformation rule has a condition and an effect, which is the definition of the new activity diagram \((A',O',C',E',guard'\), \(instate'\), \(AN',ON',parent')\).

We define two versions of T1. Version a operates on an edge connecting two OR nodes. Version b operates on a fork/join node that has a single predecessor and a single successor, both of which are OR nodes. Such a fork/join results after applying T2a to the source and target sets of the fork/join.

Definition 15

(Rule T1a) Condition. Let there be nodes \(o_1,o_2 \in ON\) such that \(out(o_1)=\{o_2\}\) and \(in(o_2)=\{o_1\}\), and for every fork/join \(n \in FJ\), \(o_1\) and \(o_2\) are not both input or both output for \(n\), so \(o_1,o_2 \not \in in(n)\) and \(o_1,o_2 \not \in out(n)\).

Effect. Let \(o\) be a fresh OR node, so \(o\not \in ON\).

• \(E'=E{\setminus } \{(o_1,o_2)\}\);

• \(ON'=(ON {\setminus }\{o_1,o_2\}) \cup o\);

• \(parent'=parent(o_1 \leftarrow o,o_2\leftarrow o)\).

Definition 16

(Rule T1b) Condition. Let there be nodes \(o_1,o_2 \in ON\) such that there is a fork/join \(n \in FJ\) such that \(out(o_1)=\{n\}\) and \(in(o_2)=\{n\}\), and for every other fork/join \(n' \in FJ\), \(o_1\) and \(o_2\) are not both input or both output for \(n'\), so \(o_1,o_2 \not \in in(n')\) and \(o_1,o_2 \not \in out(n')\).

Effect. Let \(o\) be a fresh OR node, so \(o\not \in ON\).

• \(C'=C {\setminus } \{n\}\);

• \(E'=E{\setminus } \{(o_1,n),(n,o_2)\}\);

• \(ON'=(ON {\setminus }\{o_1,o_2\}) \cup o\);

• \(parent'=parent(o_1 \leftarrow o,o_2\leftarrow o)\).

Definition 17

(Rule T2a) Condition. Let there be a fork/join \(n \in FJ\) and a set \(X\) of OR nodes such that \(in(n)=X\) or \(out(n)=X\) such that for each pair of nodes \(x_1,x_2 \in X\), \(in(x_1)=in(x_2)\) and \(out(x_1)=out(x_2)\).

Effect. Let \(a\) and \(o\) be a fresh AND and OR node, respectively, so \(a\not \in AN\) and \(o \not \in ON\).

• \(E'=E(o \leftarrow X)\);

• \(AN'=AN \cup \{a\}\);

• \(ON'=ON \cup \{o\}\);

• \(parent'=parent \cup \{ ~(x,a)~|~x \in X~\} \cup \{(a,o)~\}\)

In the definition, \(E(o\leftarrow X)\) abbreviates \(E(o \leftarrow x_1, \ldots , o \leftarrow x_n) \) where \({{|}{X}{|}}=n\).

Rule T2b is a minor variation on T2 that is needed if T3 has been applied. In that case, an expanded activity diagram results in which there are no edges but only OR nodes that root the AND/OR trees. One of these AND/OR trees is rooted by the node whose incident edges were removed in T3.

Definition 18

(Rule T2b) Condition. Let \(X\) be a set of OR nodes. Each node \(x \in X\) has no parent, and every OR node \(o \in ON{\setminus } X\) does have a parent. The set of edges \(E\) is empty.

Effect. Let \(a\) and \(o\) be a fresh AND and OR node, respectively, so \(a\not \in AN\) and \(o \not \in ON\).

• \(AN'=AN \cup \{a\}\);

• \(ON'=ON \cup \{o\}\);

• \(parent'=parent \cup \{ ~(x,a)~|~x \in X~\} \cup \{(a,o)\}\).

Definition 19

(Rule T3) Let there be a fork \(f\) and join \(j\), where \(f,j \in FJ\) and an OR node \(o \in ON\) such that \((f,o),(o,j)\in E\).

Condition. T1 and T2 are not applicable, and \({{|}{out(f)}{|}}>1\) and \({{|}{in(j)}{|}}>1\).

Effect. All edges from and to \(o\) are removed, so

• \(E'=E \cap (((ON{\setminus }{o}) \cup n ) \times ((ON{\setminus }{o}) \cup n ) )\);

Definition 20

(Finalization) Let \(AD=(A,O,C,E,guard\), \(instate)\) be the filtered activity diagram and let \(EAD\)= \((A,O,C,E\),\(guard,instate,AN,ON,parent)\) be the expanded activity diagram that results after repeatedly applying T1, T2, and T3 to the expanded activity diagram derived from \(AD\).

Condition. Rules T1, T2, and T3 are not applicable to \(EAD\). Next, the set of edges of \(EAD\) must be empty, so \(E_{EAD}=\emptyset \). This condition implies that the set of forks and joins of \(EAD\) is empty.

Effect. The state machine tuple becomes \((N',H'\), \(source'\), \(target',guard',child',default',r')\), where

• \(N'=BN' \cup AN' \cup ON'\), where

  • \(BN'=\{~instate(o)~|~o \in O_{AD}~\} \cup (C_{AD} {\setminus } FJ_{AD})\)

  • \(AN'=AN_{EAD}\)

  • \(ON'=ON_{EAD}\)

• \(H'=FJ \cup \{ ~e \in E_{AD}~|~{{|}{in(e)}{|}}={{|}{out(e)}{|}}=1~\}\)

• \(source'=\{~(x,y) \mapsto \{x\} ~|~(x,y) \in E_{AD} \cap H'~\} \cup \{~n \mapsto in(n)~|~n \in FJ_{AD}~\}(instate(o)\leftarrow o\text {, for each }o \in O_{AD})\).

• \(target'=\{~(x,y) \mapsto \{y\} ~|~(x,y) \in E_{AD} \cap H'~\} \cup \{~n \mapsto out(n)~|~n \in FJ_{AD}~\}(instate(o)\leftarrow o\text {, for each }o \in O_{AD})\)

• \(guard'=\{h \mapsto g~|~ h \in H' \wedge h \in E_{AD} \wedge g=guard_{AD}(h)\}\)

• \(child'=parent_{EAD}(instate(o)\leftarrow o\text {, for each }o \in O_{AD})\)

• \(default'=\{~(on_i,i)~\}\)

• \(r'= on_i\)

Function \(default\) only specifies the default completion for the root node, which contains the initial node of the activity diagram as BASIC node. The default nodes are redundant for regular edges since the source set and target set of each hyperedge are complete: no default nodes need to be added to enter a valid configuration [11].

1.4 Refactoring

If T3 was applied to synthesize a state machine, then the generated state machine is not consistent with the filtered activity diagram, and the state machine needs to be refactored, as discussed in Sect. 5.

The refactoring rules use state machines with events and guards. Consequently, the state machine tuples are expanded with a set \(E\) of events and partial functions \(event, action:H\rightarrow E\). Next, we allow guard conditions to reference BASIC nodes using predicate \((n)\), where \(n \in BN\), which is true if \(n\) is currently active. The intended meaning is that if for hyperedge \(h\), these functions are defined, \(h\) is enabled if \(event(h)\) occurs, its states in \(source(h)\) are active, and \(guard(h)\) evaluates to true. If \(h\) is taken, \(action(h)\) is generated.

We now define an initialization rule and two refactoring rules. As before, when defining the new state machine tuples, only the changed elements are defined.

Definition 21

(Initialization refactoring) Let \((N,H,source\), \(target,guard,child,default,r)\) be a state machine. Let \(O \in ON\) be an OR node in the state machine.

Condition. Node \(O\) was processed in T3.

Effect. The state machine tuple becomes \((N',H',source'\), \(target',guard',child',default',r',E',event',action')\), where

• \(N'=BN' \cup AN' \cup ON'\), where

  • \(BN'=BN \cup \{~\text {init}_O\}\)

  • \(AN'=AN\)

  • \(ON'=ON\)

• \(child'=child \cup \{(\text {init}_O,O)\}\)

• \(default'=default \cup \{(O,\text {init}_O)\}\)

• \(E'=\emptyset \)

• \(event'=\emptyset \)

• \(action'=\emptyset \)

The first refactoring rule processes hyperedges that enter the OR node \(O\) that was processed in T3.

Definition 22

(Refactoring-1) Let \((N,H,source,target\), \(guard,child,default,r,event,action)\) be a state machine. Let \(O \in ON\) be an OR node in the state machine. Let \(h \in H\) be a hyperedge.

Condition. The initialization rule has been applied. Node \(O\) was processed in T3. A target node of \(h\) is contained in \(O\), so there is a BASIC node \(n\in target(h)\) such that \(child^*(n,O)\).

Effect. The state machine tuple becomes \((N',H',source'\), \(target',guard',child',default',r',event',action')\), where

• \(H'=H \cup \{\text {copy}_h\}\)

• \(source'= source \cup \{(\text {copy}_h,\text {init}_O)\}\)

• \(target'= (target\, \cup \, \{(\text {copy}_h,X)\}) \oplus \{(h,target(h){\setminus } X) \}\)

• \(E'=E \cup \{\text {event}_h\}\)

• \(event'=event \cup \{(\text {copy}_h,\text {event}_h)\}\)

• \(action'=action \cup \{(h,\text {event}_h)\}\)

where \(X=\{~n~|~n \in target(h)\wedge child^*(n,O)\})\).

In the definition of \(target\), operator \(\oplus \) denotes function overriding.

The second refactoring rule processes hyperedges that leave the OR node \(O\) that was processed in T3.

Definition 23

(Refactoring-2) Let \((N,H,source,target\), \(guard,child,default,r,event, action)\) be a state machine. Let \(O \in ON\) be an OR node in the state machine. Let \(h \in H\) be a hyperedge.

Condition. The initialization rule has been applied. Node \(O\) was processed in T3. A source node of \(h\) is contained in \(O\), so there is a BASIC node \(n\in source(h)\) such that \(child^*(n,O)\).

Effect. The state machine tuple becomes \((N', H', source'\), \( target', guard', child', default', r', E', event', action')\), where

• \(H'=H \cup \{\text {copy}_h\}\)

• \(source'= (source \cup \{(\text {copy}_h,X)\}) \oplus \{(h,source(h){\setminus } X) \}\)

• \(target'= target \cup \{\text {copy}_h,(\text {init}_O)\}\)

• \(guard'=guard \oplus \{h \mapsto g ~|~g=guard(h) \wedge \bigwedge _{x \in X}{}(x)\}\)

• \(E'=E \cup \{\text {event}_h\}\)

• \(event'=event \cup \{(\text {copy}_h,\text {event}_h)\}\)

• \(action'=action \cup \{(h,\text {event}_h)\}\)

where \(X=\{~n~|~n \in source(h)\wedge child^*(n,O)\})\).

1.5 Correctness

We prove the transformation from filtered activity diagrams to state machines correct for a subset of activity diagrams. We first introduce auxiliary definitions.

Definition 24

(Minimal areas) Let \(AD=(A,O,C\), \(E,guard,instate)\) be a filtered activity diagram such that no edge \((x,y) \) connects two fork/join nodes, so \(E \cap (FJ \times FJ)=\emptyset \). An area is a set \(X \subseteq A \cup O \cup C\) such that for each \(x \in X\),

• if \(x \in FJ\) then \(in(x)\subseteq X \iff out(x)\subseteq X\);

• if \(x \not \in FJ\) then \(in(x) \cup out(x) \subseteq X\).

A minimal area for a set \(Y \subseteq A \cup O \cup C\) of nodes is an area \(X\) such that \(Y \subseteq X\) and \(X\) is minimal, so for each area \(Z\), if \(Z \subset X\) then \(Y \not \subseteq Z\).

For instance, for Fig. 5, the minimal area for {} is set {, }, while the minimal area for {,} is the set of successor nodes upto and including the merge node.

Definition 25

(Consistent areas) Let \(AD=(A,O,C,E\), \(guard,instate)\) be an activity diagram such that no edge \((x,y) \) connects two fork/join nodes, so \(E \cap (FJ \times FJ)=\emptyset \). A fork/join node \(n \in FJ\) has consistent areas if for each pair of disjoints set \(X,Y\) such that \(X,Y \subseteq in(n) \) or \(X,Y \subseteq out(n) \) the minimal areas of \(X\) and \(Y\) are disjoint. Activity diagram \(AD\) has consistent areas if each fork/join node \(n \in FJ\) has consistent areas.

For instance, the activity diagram in Fig. 5 has consistent areas. For example, the minimal areas for sets {} and {, } are disjoint.

The activity diagram in Fig. 14 does not have consistent areas. The minimal areas for sets { and {} overlap, since both contain . Also, the activity diagram in Fig. 16a does not have consistent areas: the minimal area for {} is a subset of the minimal area for {}, which is the entire set of nodes minus the fork.

Theorem 1

Let \(AD=(A,O,C,E,guard,instate)\) be a filtered activity diagram, so \(A=\emptyset \) and let \(SC=(N,H,source,target,guard,child,default,r)\) be the state machine that results by applying the transformation rules T1, T2, and T3. If \(AD\) has consistent areas, then \(AD\) and \(SC\) have equivalent behavior.

Proof

Activity diagram \(AD\) maps into a marked Petri net \(PN=(P,T,F,M)\) where

• \(P= (O \cup C ) {\setminus } FJ\)

• \(T= FJ \cup \{t_{(x,y)} | (x,y) \in E \wedge x,y \not \in FJ \}\)

• \(F= \{(x,y)| (x,y) \in E \wedge ((x \in FJ \wedge y \not \in FJ ) \vee (x \not \in FJ \wedge y \in FJ)) \}\) \(\cup \, \{(x,t_{(x,y)}),(t_{(x,y)},y) | (x,y) \in E \wedge x,y \not \in FJ \} \)

• \(M=\{(i,1)\} \cup \{(x,0)|x \in P{{\setminus }}\{i\}\}\)

The definition states that every node in \((O \cup C) {\setminus } FJ\) maps to a Petri net place. Every node in \(FJ\) and every edge \(e \in E\) that is not incident to a fork or a join maps to a Petri net transition. For every edge that connects two nodes in \(FJ\), a place is created. The flow relation \(F\) is defined accordingly.

Elsewhere [10] we have defined transformation rules T1 and T2 plus the notion of areas in the context of Petri nets. There, we proved that that if \(PN\) has consistent areas and the areas are nestable, so for every pair of overlapping areas \(X,Y\) either \(X \subseteq Y\) or \(Y \subseteq X\), then applying transformation rules T1 and T2 to \(PN=(P,T,F,M)\) results in a state machine \(SC\) that has equivalent behavior, in the sense that the reachable markings of \(PN\) are isomorphic to the reachable configurations of \(SC\).

We now argue that if rule T3 has been applied, the behavior of the filtered activity diagram is preserved in the refactored state machine. Let \(O\) be an OR node to which T3 is applied. Let \(f \in FJ\) be a fork node of which \(O\) is a target node in the reduced activity diagram. In the filtered activity diagram, if \(f\) is taken then all nodes in \(in(f)\) are left and all nodes in \(out(f)\) are entered. The state machine before refactoring contains a hyperedge \(f\) whose source set by construction (Def. 20) equals \(in(f)\) and whose target set equals \(out(f)\). Refactoring rule 1 ensures that when in the refactored state machine hyperedge \(f\) is taken, every BASIC node that is entered is in the target set of \(f\) before refactoring. Since \(AD\) has consistent areas, if \(in(f)\) is active, then no node in \(out(f)\) is active. Therefore, \(f\) only leaves BASIC nodes that are sources of \(f\) before refactoring, plus the fresh node \(init_O\). Therefore, when \(f\) is taken in the filtered activity diagram, the nodes left and entered correspond to the BASIC nodes left and entered when hyperedge \(f\) is taken in the refactored state machine.

Symmetrically, let \(j \in FJ\) be a join node of which \(O\) is a source node in the reduced activity diagram. Refactoring rule 2 ensures that when in the refactored state machine hyperedge \(j\) is taken, every BASIC node that is left is in the source set of \(j\) before refactoring, and every BASIC node that is entered is either in the target set of \(j\) before refactoring or \(init_O\). Because of the guard condition, \(j\) only leaves BASIC nodes that are sources of \(j\) before refactoring. Therefore, when \(j\) is taken in the filtered activity diagram, the nodes left and entered correspond to the BASIC nodes left and entered when hyperedge \(j\) is taken in the refactored state machine.

Consequently, the behavior of the refactored state machine corresponds to that of the filtered activity diagram. \(\square \)

Reprints and permissions