Simple Control Flow Patterns
We now discuss how YAWL supports control flow patterns. It is obvious that
the basic control flow patterns are directly supported. The sequence pattern
is shown in Figure 4.55, where two alternative representations are shown: in
extended workflow nets, the control flow edge can directly connect A and B, so
that the condition place can be dropped. Notice that these two representations
are equivalent, i.e., any extended workflow net with conditions connecting two
tasks can be transformed to an equivalent extended workflow net with direct
connections, and vice versa.
And split and and join patterns are shown in part (a) of Figure 4.56.
On completion of the split task A (split(A) = and), tasks B, C, and D are enabled, and the three tasks can be executed concurrently. The join task
E (join(E) = and) is enabled only if B, C, and D have been completed.
The exclusive or split shown in part (b) of that figure selects exactly one
alternative, so that E can start if exactly one branch is completed. In this
case, split(A)= join(E) = Xor.
Workflow specifications require additional information that allows evaluating
conditions to decide, for instance, which path in an exclusive or split
to take. These conditions, however, are not part of the formal specification of
workflow specifications in YAWL.
Figure 4.57 shows the inclusive or split. From a notation point of view,
the or split and the or join can be defined similarly to the other control flow
structures. However, the decision on when the or join is activated is complex.
These aspects will be discussed in more detail when the execution semantics
of YAWL is investigated.
The execution semantics in YAWL is defined by state transition systems.
Each workflow specification has a corresponding state transition system that describes the execution semantics of process instances based on that workflow
specification. The rules implemented in this state transition system are of
a generic nature, so that they can be applied to any workflow specification
expressed in YAWL.
The overall idea for expressing the execution semantics is that each task
is represented by an individual state transition diagram. A state transition
diagram of a task specifies its current state. The state of the process instance
is then represented by the combined state of all tasks involved in the process
instance plus conditions that are currently met at the process level.
State transition diagrams consist of conditions represented by circles and transitions
represented by rectangles. Since multiple instances tasks can take more
states than single instance tasks, single instance tasks are investigated first.
The state transition diagram for single instance tasks is shown in Figure 4.58.
In this section, task instances are investigated before state transition diagrams
at the process level are investigated. To stay in line with terminology
in YAWL, this section uses the term task instance, which describes the same
concept as the term activity instance this book has used so far.
The following conditions are available for a task instance:
enabled: Task instance is enabled, but not yet executing
exec: Task instance is currently executing
completed: Task instance is completed
active: Task instance is currently active
The execution semantics of a task instance is specified by the state transition
diagram shown in Figure 4.58. Despite the fact that transitions do not use Petri net transition semantics, it is appropriate to discuss the basic operation
of state transition diagrams with Petri net terminology.
When the task instance is entered, a token is put on the active and enabled
conditions. An enabled task instance can start. Once the start transition fires,
the task instance enters the exec condition.When the task instance completes,
it enters the completed condition; finally, the task instance is terminated by
firing the exit transition. Note that the active condition and the exit transition
are somewhat artificial for single instance tasks; their role will become clear
when multiple instances tasks are addressed.
To summarize, the state transitions for a task t have the following semantics.
The state transition enable checks the join condition of t; t might be
a join node of type And, Xor, or Or, as specified by join(t). When the enable
transition occurs, the input tokens as defined by the join condition are
removed from the input conditions of the task.
In case of a single instance task, one token is put in the active condition and
one token is put in the enabled condition. When the start transition occurs,
one token is removed from the enabled condition and one token is added to
the exec condition. The task instance is now executing. The termination of a
task instance is represented by the completed transition in the state transition
diagram. In this case, one token is removed from the exec condition and one
token is added to the completed condition.
The exit transition is specifically relevant for multiple instances tasks,
because it fires if the termination condition of a multiple instances task is met.
In case there is a cancellation region defined for task t, the exit transition also
removes tokens from the cancellation region of the workflow specification, as
defined by rem(t). Finally, the exit state transition generates tokens depending
on its split behaviour, defined by split(t) The state transition diagram for multiple instances tasks is shown in Figure
4.59. There is an additional state transition, add, that spawns new task
instances. Arcs drawn in bold indicate that multiple tokens can flow along
To discuss the execution semantics of a multiple instances task, the static
case is considered first. In this case, all task instances are created up front,
and no task instances can be added while instances of the task run. Consider
a multiple instances task with [4, 6, 4, s]: four to six task instances are created,
and the multiple instances task terminates when the threshold of four
instances that have completed is reached.
Consider a process instance in which the enable transition creates five
task instances by putting five tokens in the active condition and five tokens
in the enabled condition. For each token in the enabled condition, the start
transition can fire.
The termination of the overall task (completion of the required task instances)
is realized by the exit transition. Exit can fire if the threshold number
of tokens are in the completed condition, indicating the completion of a
sufficient number of task instances. Assuming four task instances have been
completed, the threshold value is reached, and the exit transition removes
four tokens from the completed condition and four tokens from the active
However, since five task instances have been started, there is one additional
task instance present. This task instance is represented by one token in the
active condition and one token in either the enabled or the exec condition.
This task instance might also have already entered the completed condition.
In the example shown in Figure 4.60, the task instance is still executing To implement a proper completion of the task, the exit transition needs
to delete all remaining tokens from the state transition system of the task. In
this case, two tokens that collectively represent the fifth (and not required)
task instance are removed, completing the task and all its task instances, of
which four have been performed completely.
In the example discussed, the number of task instances was statically defined,
so that the dynamic creation of new task instances was not possible. In
the following example, additional task instances can be created at run time.
Let [3, 10, 8, d] define the multiple instances property of the task. This means
that there are at least three instances, at most ten instances, and the threshold
is eight completed task instances.
Assume that three task instances are started up front. In this case, the
enable transition puts three tokens in the active condition and three tokens
in the enabled condition. The enabled task instances can start.
The dynamic creation of new task instances is represented by the state
transition add. As soon as there is one task instance in the active condition,
the add transition can fire. When it fires, an additional token is put in the
enabled and active conditions, representing the creation of a new task instance
at run time. In this way add realizes the dynamic creation of task instances at
run time. Using this feature, YAWL directly supports the multiple instances
without a priori run time knowledge control flow pattern, introduced in Section
The other parts of the state transition system remain unchanged, so that
the originally created task instances and the dynamically created task instances
are handled equivalently: the exit transition can fire if there are a
sufficient number of completed task instances available, in this case, eight.
The actual trigger for creating new task instances is not in the scope of
the state transition system. It is assumed that the user or a software system
spawns new task instances as desired. The state transition system is capable
of monitoring the state of a task, including the states of its task instances.