A Formal Semantics of Time Patterns
for Process-aware Information Systems
Andreas Lanz1, Manfred Reichert1, and Barbara Weber2
1Institute of Databases and Information Systems, Ulm University, Germany
{Andreas.Lanz,Manfred.Reichert}@uni-ulm.de
2Quality Engineering Research Group, University of Innsbruck, Austria
Summary.
Companies increasingly adopt process-aware information sys-
tems (PAISs) to coordinate, monitor and evolve their business processes.
Although the proper handling of temporal constraints (e.g., deadlines
and minimum time lags between activities) is crucial in many application
domains, existing PAISs vary significantly regarding their support of the
temporal perspective of business processes. Both the formal specification
and operational support of temporal constraints constitute fundamental
challenges in this context. In previous work, we introduced time patterns
facilitating the comparison of PAISs in respect to their support of the
temporal perspective and provided empirical evidence for them. To avoid
ambiguities and to ease the use as well as implementation of the time
patterns, this paper formally defines their semantics. To enable pattern
use in a wide range of process modeling languages and pattern integration
with existing PAISs, this semantics is expressed independent of a particu-
lar process meta model. Altogether, the presented pattern formalization
will foster the integration of the temporal perspective in PAISs.
Key words:
Process-aware Information System, Workflow Patterns,
Time Patterns, Temporal Perspective, Temporal Constraints
1 Introduction
Companies strive for improved life cycle support of their business processes [
1
,
2
].
In particular, IT support for analyzing, modeling, executing and monitoring
these processes results in competitive advantages [
3
,
4
]. In this context, process-
aware information systems (PAISs) offer promising perspectives towards process
automation by enabling companies to define a business process in terms of an
explicit process schema and to execute related process instances based on this
schema in a controlled and efficient manner [1].
Both the formal specification and operational support of temporal constraints
constitute fundamental challenges of any PAIS [
5
,
6
,
7
,
8
]. In contemporary PAISs,
however, time support is very limited. Furthermore, there exist no criteria for
systematically assessing the degree of support of the temporal perspective across
different PAISs and PAIS-enabling technologies (e.g., workflow management
systems and case handling tools [
9
]). To make PAISs better comparable and
2 Andreas Lanz, Manfred Reichert, and Barbara Weber
facilitate the selection of PAIS-enabling technologies in a given application
environment, workflow patterns have been introduced [
10
,
11
,
12
,
13
]. These
patterns allow analyzing the expressiveness of process modeling languages and
tools in respect to different process perspectives, like, for example, control flow
[
10
], data flow [
11
], resources [
12
], activities [
14
], exceptions [
15
], and process
change [13, 16, 17].
1.1 Problem Statement
Recently, we extended the workflow patterns by a set of 10 time patterns suitable
for evaluating the support of the temporal perspective in a PAIS [
18
,
19
]. Examples
of such time patterns include Time Lags between Activities,Durations, and Fixed
Date Elements. Empirical evidence we gained in a number of case studies has
confirmed that identified time patterns are common in practice and required for
properly modeling the temporal perspective of processes in a variety of application
domains [
19
,
20
]. Furthermore, we evaluated different approaches and tools in
respect to their time pattern support [19].
Our evaluations have emphasized the need for a precise and formal semantics of
the identified time patterns. In particular, ambiguities in respect to this semantics
would hamper both pattern implementation and comparison of existing PAISs.
So far, the time patterns we identified have lacked a formal semantics. Similar
to workflow patterns [
21
], however, the latter is crucial in order to enable a
widespread use of the time patterns, i.e., for each time pattern, its effects on
process enactment must be precisely defined. This becomes necessary to ensure
that different implementations of the respective pattern have the same basic
meaning. Note that this is also required to ensure a common understanding of
process schemata containing time patterns. Furthermore, it becomes necessary
to specify how the time patterns interact with different elements of the control
flow perspective (i.e., control flow patterns like loops, XOR-splits, or AND-joins).
Finally, for time patterns depending on run-time data (i.e., process instance
data), it must be precisely defined which data value to use, otherwise different
implementations might result in different behaviour.
1.2 Contribution
This paper complements our previous work on time patterns [
19
] by additionally
formalizing the semantics of these patterns. This will allow users to ground
pattern implementation as well as pattern-based analysis of PAISs on a solid and
formal basis. Furthermore, it will foster the widespread use of the time patterns
by PAIS engineers and researchers.
We provide a precise, formal semantics for the time patterns presented in [
19
].
This semantics is defined independent of a specific process modeling language
or paradigm. Furthermore, we illustrate pattern semantics in terms of examples
and detailed explanations. Finally, we validate the proposed pattern semantics
to ensure that it meets the one expected by domain experts.
Formal Semantics of Time Patterns 3
When defining the semantics of the time patterns, a particular challenge
is to provide a formal pattern description independent of a particular process
modeling language. Only then PAIS engineers will be able to integrate the time
patterns without need to cope with language-specific issues, which again might
result in ambiguities. To define a pattern semantics independent of any process
modeling language and closely related to the execution semantics of processes, we
use process execution traces as basis for our formalization [
22
]. In particular, an
execution trace can be considered as execution history of a process instance, i.e.,
it records what happened during the execution of a particular process instance.
We then formally describe the semantics of time patterns by indicating which
traces can be produced on a given process schema containing a particular time
pattern, i.e., which traces are compliant with pattern semantics. Amongst others,
this makes it possible to implement techniques for checking the conformance [
23
]
of a process instance in respect to a process schema and its temporal constraints
(i.e., occurrences of the time patterns).
In case a pattern instance additionally depends on run-time data of the
process instance we precisely define which data value is valid for a specific
pattern instance. In particular, if the same data object is modified several times
during process execution, we precisely define which of these data values shall
be considered for a pattern instance. This is especially important in connection
with loops or concurrent data access; otherwise ambiguities will hamper pattern
implementation.
Based on the defined semantics, pattern implementation is put on a sound
basis. Moreover, ambiguities are avoided regarding the implementation of the
patterns in a PAIS as well as their use for assessing existing PAISs. Finally, a
precise formal semantics is a prerequisite for verifying the temporal perspective
of business processes at both build- and run-time [
5
,
6
,
7
,
24
,
25
]. Overall, the
defined semantics will foster the integration of the temporal perspective into
existing PAISs and hence broaden their scope significantly.
The remainder of this paper is organized as follows: Section 2 provides
background information and recalls the time patterns we informally presented in
[
19
]. Section 3 discusses the research method applied for defining and validating
the proposed formal pattern semantics. Section 4 provides the formal semantics
of the time patterns. In Section 5, we provide a validation of the formal semantics
by evaluating how well it matches the semantics inherent to other academic
approaches. In Section 6, we discuss the expected impact of the proposed formal
pattern semantics as well as its usefulness for implementing time support in
PAISs. Section 7 discusses related work and Section 8 concludes with a summary.
2 Backgrounds
This section provides basic notions needed for understanding this paper. Further,
it summarizes the time patterns we informally introduced in [18, 19].
4 Andreas Lanz, Manfred Reichert, and Barbara Weber
2.1 Basic Notions
Aprocess-aware information system (PAIS) is a specific type of information
system providing process support functions. It is characterized by the separation
of process logic from application code. At build-time, process logic is explicitly
defined based on the constructs provided by a process meta model. For each
business process to be supported, a process type represented by a process schema
is defined. The latter corresponds to a directed graph that comprises a set of
nodes – representing activities and control connectors (e.g., Start-/End-Nodes,
XOR-splits, and AND-joins) – and a set of control edges linking these nodes, i.e.,
control edges specify precedence relations between nodes. Further, the notion of
activity set refers to any subset of the activities of a process schema, whereby
the elements of such set do not need to meet structural requirements (e.g.,
compoundness). In turn, when referring to specific regions of a process schema,
we use the notion of process fragment. Such a fragment refers to a sub-graph of a
process schema with single entry and single exit node.
In addition to the described control flow elements, a process schema contains
process-relevant data objects as well as data edges linking an activities with data
objects. More precisely, a data edge either represents a read or write access of
the respective activity to the referred data object.
At run-time, process instances are created and executed according to the
predefined process schema. Activity instances, in turn, represent executions of
single process steps (i.e., activities) of a particular process instance. Moreover,
during run-time a particular data element may be written multiple times, resulting
in a series of data values for it. Finally, the notion of process instance set refers
to a set of process instances executed by the PAIS. In turn, the process instances
of such a set may be enacted based on the same process schema, but may also
run on different process schemes.
During the execution of a process instance, events may be triggered, either
by the process instance itself (e.g., start / end event of the process instance), by
a process node (e.g., start / end event of an activity instance, cf. Fig. 1), or by an
external source (e.g., receipt of a message). We use the notion of event as general
term for something happening during process execution. We assume that activity
instances are executed according to the activity life cycle depicted in Fig. 1.
When a process instance is started, its activities have state Not Activated. As
soon as a particular activity becomes enabled, its enters state Activated. When a
user starts the activity instance in this state, the latter switches to state Started
and a corresponding start event is generated. As soon as the user completes the
activity instance, its state switches to Completed and an end event is generated.
Finally, non-executed activities enter state Skipped (e.g., activities contained in
an outgoing path of an XOR-split not selected during run-time).
2.2 Time Patterns
Time Patterns (TP) represent temporal constraints commonly occurring in
PAISs. In [
18
,
19
], we identified 10 time patterns (cf. Fig. 2) and described them
Formal Semantics of Time Patterns 5
NOT ACTIVATED ACTIVATED STARTED COMPLETED
SKIPPED
enable
disable
start finish
skip
skip
start event end event
Activity Instance State
Event
Fig. 1. Activity life cycle and relevant events
informally. We further provided empirical evidence for the relevance of these
patterns, i.e., each time pattern was observed in at least 3 different application
domains.
The 10 time patterns can be divided into 4 distinct categories based on
their semantics (cf. Fig. 2). Pattern Category I (Durations and Time Lags)
provides support for expressing durations of process elements at different levels
of granularity, i.e., activities, activity sets, processes, or sets of process instances.
Further, it covers time lags between activities or—more generally—between
process events (e.g. milestones). Pattern Category II (Restricting Execution
Times) allows specifying constraints regarding possible execution times of single
activities or entire processes (e.g., activity deadlines). In turn, Category III
(Variability) provides support for expressing time-based variability during process
execution (e.g., varying control-flow depending on temporal aspects). Finally,
Category IV (Recurrent Process Elements) comprises patterns for expressing
temporal constraints in connection with recurrent activities or process fragments
(e.g., cyclic flows and periodicity).
Time
Patterns
Category IV: Recurrent Process Elements
TP9 Cyclic Elements
TP10 Periodicity
Category III: Variability
TP8 Time-dependent Variability
Category II: Restricting Execution Times
TP4 Fixed Date Elements
TP5 Schedule Restricted Elements
TP6 Time-based Restrictions
TP7 Validity Period
Category I: Durations and Time Lags
TP1 Time Lags between Activities
TP2 Durations
TP3 Time Lags between Events
* TP = Time Pattern
Fig. 2. Pattern catalogue [19]
Example 1 introduces a simple process along which we will illustrate selected
time patterns (cf. Example 2). A basic understanding of these patterns is required
in order to understand their formal definition given in Section 4.
6 Andreas Lanz, Manfred Reichert, and Barbara Weber
Example 1 (Patient Treatment Process).
Consider the simplified patient
treatment process depicted in Fig. 3. First, a doctor orders a medical procedure
for his patient. Then, the responsible nurse makes an appointment with the
department (e.g., radiology department) the procedure will take place. Before the
treatment may be performed, the patient needs to be informed about the procedure
and be prepared for it. Just before the treatment starts, a specific preparation is
required. In turn, after completing the treatment, the doctor creates a short report
if requested. Finally, aftercare is provided and the doctor creates a final medical
report, which is then added to the patient record.
instruct
procedure
make
appointment
inform
patient
prepare
patient
perform
after-care
~
create
report
perform
treatment
prepare
treatment
create short
report
appoint-
ment
TP2: Duration
maximum duration 1h
TP4: Fixed Date Element
appointment
TP1: Time Lag between two Activities
maximum 1 week
TP1: Time Lag between two Activities
exactly 1 day
TP10: Periodicity
Drug A at 8am, 1pm and 6pm
Drug B every 2h
TP5: Schedule Restricted Element
Monday till Friday from 8am to 4pm
TP2: Duration
1h - 4h
Fig. 3. Treatment process with temporal constraints
When considering the temporal perspective of this rather simple business
process, a number of temporal constraints can be observed. Example 2 relates
these temporal constraints to the time patterns from Fig. 2.
Example 2 (Temporal Constraints).
Consider again Fig. 3. The appoint-
ment of the
treatment
, made in the context of activity
make appointment
, must
be observed during process execution. This constitutes a
Fixed Date Element
(TP4) restricting the earliest start date of the respective activity. Furthermore,
the respective date will be set during run-time by activity
make appointment
and stored in data object
appointment
. In particular, this constraint affects the
scheduling of preceding activities as well; e.g., the patient needs to be prepared
exactly 1 day before his or her
treatment
takes place. This represents a
Time
Lag between two Activities
(TP1) from the start of
prepare patient
to the
start of
perform treatment
. Hence,
preparation
needs to be scheduled in ac-
cordance with the appointment of the
treatment
. Additionally,
preparation
of
the patient may be only done during opening hours of the anesthetics department,
i.e., from Monday till Friday between 8am and 4pm. In turn, this represents a
Schedule Restricted Element
(TP5). It further restricts possible execution
times of
prepare patient
and hence the ones of the
treatment
itself. Next, due
to a tight schedule of the treatment room, the
preparation
of the treatment must
not take more than 1 hour; otherwise the
treatment
is delayed. This represents
a maximum
Duration
(TP2) on activity
prepare treatment
. The
treatment
Formal Semantics of Time Patterns 7
itself, in turn, may take from 1 hour up to 4 hours, which represents a mini-
mum and maximum
Duration
, i.e., an interval. Finally, during the execution of
activity
perform aftercare
, different drugs are given to the patient according
to a treatment plan defined by activity
perform treatment
. Such a treatment
plan may state, for example, that drug A must be administered every day at
8 am, 1 pm, and 6 pm, and drug B every two hours except when drug A is
administered within the same hour. This plan represents a
Periodicity
(TP10);
more precisely, it constitutes the underlying periodicity rule of the
Periodicity
represented by activity perform aftercare.
This example demonstrates the diversity and complexity of the temporal perspec-
tive of business processes. It further illustrates why process modeling languages
like BPMN are by far not sufficient to properly describe the temporal perspec-
tive of business processes. For example, time patterns like Schedule Restricted
Elements (TP5), Time Lags between two arbitrary (not succeeding) Activities
(TP1), and Periodicity (TP10) cannot be properly described using BPMN [
19
].
Similarly, Example 2 emphasizes the need for a precise and formal semantics of
the different time patterns.
To cope with the variability and to keep the number of distinct patterns
manageable, design choices (DC) allow for the parametrization of the time
patterns [
18
,
19
]. For example, whether a time lag represents a minimum value,
maximum value, or both (i.e., an interval) constitutes a design choice of the Time
Lags between Activities pattern (TP1). We denote a specific combination of design
choices of a time pattern as pattern variant. Usually, existing PAISs only support
a subset of the design choices available for a particular pattern (i.e., pattern
variants). Note that design choices influence the formal semantics of the time
patterns as well. For example, consider the Duration pattern (TP2) applied to an
activity. To be able to exactly decide on the semantics of this pattern, it becomes
necessary to specify whether the duration corresponds to a minimum value, a
maximum value, or both (i.e., a time interval); i.e., the semantics of this time
pattern is determined by taking the respective design choice into account. Hence,
the formalizations provided in this paper consider design choices as well. Finally,
when applying a specific pattern variant to a process schema the particular
restriction represented by the pattern occurrences needs to be determined (e.g.,
the time of the appointment for pattern Fixed Date Element, or the duration
value for pattern Duration). For this purpose parameter values allow determining
the specific temporal constraint represented by a pattern occurrence. Parameter
values, in turn, may either be set at build-time (i.e., all process instances share
the same value) or at run-time, i.e., when creating or executing process instances.
In the latter case, the particular parameter value is stored in a data object of
the process instance when creating it or executing an activity. The stored data
value is then read by the corresponding pattern occurrence during run-time. For
this purpose, a pattern occurrence may be linked to a data object by means of a
data edge (e.g., data object appointment in Fig. 3).
8 Andreas Lanz, Manfred Reichert, and Barbara Weber
3 Research Method
This paper complements our previous work on workflow time patterns. Our
goal is to provide a formal semantics for each of the time patterns independent
of a particular process meta model. The overall procedure comprising pattern
identification and the definition of pattern semantics is illustrated in Fig. 4. This
section describes the research method (cf. Fig. 4) applied when identifying the
time patterns (i.e., selection criteria and identification procedure) [
18
,
19
]. We
further describe essential requirements for defining pattern semantics and the
procedure applied for their elicitation. Finally, we sketch the validation procedure
we applied to ensure that pattern semantics meets the one expected by domain
experts (cf. Fig. 4).
Pattern
Identification
Pattern
Validation
Definition of
Patterns Semantics
Validation of
Patterns Semantics
Systematic
Literature
Review
Data
Sources
Domain
Experts
Academic
Approaches
Lanz et. al (2012) This paper
Fig. 4. Applied research method
3.1 Initial Pattern Identification
Selection criteria for the time patterns have been “patterns covering temporal
aspects relevant for the modeling and control of business processes and activities
respectively” [
19
]. In particular, other process aspects (e.g., data flow) or time
support features (e.g., escalation management, verification) were not considered
and are thus outside the scope of this paper as well.
To ground the time patterns on a solid basis, first of all, a candidate list
was created based on the knowledge and experiences of the authors in this field.
Design choices were introduced for parameterizing the patterns in order to keep
the number of different patterns manageable. Following this, large sets of cases
and process schemata were analyzed (cf. Table 1) in order to provide empirical
evidence for each of the time patterns and to further refine the pattern list. This
finally resulted in a set of 10 time patterns.
To validate the time patterns and to further asses their relevance and com-
pleteness, in addition, a systematic literature review was conducted [
19
]. Finally,
different approaches and tools were evaluated regarding the support of the time
patterns proposed [19].
Formal Semantics of Time Patterns 9
3.2 Pattern Semantics: Requirements and Procedure
On the one hand, formal pattern semantics should be as generic as possible, on
the other, it must be as specific as necessary to avoid ambiguities. Additionally,
it must consider all pattern variants that may be configured due to different
combinations of design choices.
We first analyze the data sources used for pattern identification (cf. Table 1)
to elaborate on the intended semantics of each pattern occurrence. Next, we
combine semantics of all occurrences of a specific pattern to obtain its overall
semantics. Thereby, we specifically consider the respective variant of the pattern
occurrence. Finally, if possible, we remove unnecessary restrictions from the
overall patterns semantics.
Data Sources
Healthcare Domain (Women Hospital) [26, 27, 28] 88 processes
Healthcare Domain (Internal Medicine) [29, 30, 31, 32, 33] 93 processes
Automotive Domain [34, 35] 55 processes
On-demand Air Service [36, 37] 2 processes
Airline Catering Services [38] 1 process
Transportation [39] 9 processes
Software Engineering [40] 10 processes
Event Marketing 1 process
Financial Service 10 processes
Municipality Processes [41] 4 processes
Total: 273 processes
Table 1. Data sources [19]
As emphasized, any pattern semantics is only useful for PAIS engineers if it
is defined independent of a particular process modeling language (e.g., BPMN,
EPC) or process modeling paradigm (e.g., imperative vs. declarative). Workflow
patterns have been defined based on languages such as Petri Nets [
10
] or pi-
calculus [
42
], which have an inherent formal semantics. However, such formalisms
cannot be used to define the semantics of time patterns without significant
extensions since they do not consider the temporal perspective at all. Beyond
that, different techniques commonly used for describing the temporal properties
of a system exist. Examples include temporal logics [
43
], timed petri nets [
44
], and
timed automata [
45
]. In principle, these techniques can be also used for describing
the formal semantics of time patterns as well. However, most of them are either
related to a particular process modeling paradigm or cannot be intuitively applied
to describe high-level temporal constraints.
To be independent of such particulars, this paper uses execution traces as
basis of pattern formalization due to their language-independence as well as
their close relation to the execution semantics of processes. An execution trace
represents a possible execution of a process schema indicating all events that
occurred during the execution of the respective process instance together with
their time stamps (cf. Sec. 4.1 for details). Based on execution traces we can
10 Andreas Lanz, Manfred Reichert, and Barbara Weber
specify which execution traces (i.e., process instances) are valid according to the
time patterns found in the respective process schema. Thus, we are independent
of the particular process modeling language and paradigm; yet we are still able
to precisely define pattern semantics.
3.3 Pattern Semantics: Validation
To validate the formal semantics of the time patterns, we reconsider each pattern
occurrence observed in any data source (cf. Table 1), and compare the described
semantics with our formal definitions. If the semantics of one of the pattern
occurrences in our data sources is not precise enough, we ask domain experts
to provide further details. Whenever necessary, we discuss a pattern occurrence
with the respective domain expert in order to be sure that our pattern semantics
meets the one the expert has in mind.
To further validate the formal semantics, we present it to different domain
experts and process engineers and ask them whether they meet the description
of the respective time pattern as well a their own expectations. For this purpose,
we develop a representative set of interactive animations of the different time
patterns and respective pattern variants displaying the defined formal semantics
(a sub-set of these animations can be found on the project website [
20
]). We
then present these animations to different subjects (i.e., domain experts and
process engineers) and ask them to (a) describe the meaning of the shown pattern
variant and (b) whether or not this matches their expectation. Regarding process
engineers, we further show them a set of process fragments each exhibiting a set
of temporal constraints. We then ask them to describe their interpretation of the
respective process fragment. Next, for half of the process fragments we ask the
subject to give a set of execution traces of the process fragment which are either
consistent or inconsistent with respective temporal constraints. For the other
half of cases we present the subject a set of corresponding execution traces and
ask them whether or not in their opinion they are consistent with the temporal
constraints of the process fragment.
In case a modification of the formal definition of the semantics of a particular
time pattern is required, we implement it. Then the overall validation process is
started from scratch for that particular pattern semantics. This is to ensure that
the respective modification has no unintended consequences.
In a final step, we compare our formal semantics with existing approaches
for verifying the consistency of the temporal perspective (cf. Sec. 5). Since these
approaches are based on some formalism used for verification (e.g., temporal
constraint networks [
46
], project network technique [
47
]) they come along with
an inherent semantics that can be derived from the respective formalism. Thus,
for each pattern supported by the respective approach we compare our formal
semantics with the one of the respective approach. The latter, in turn, we obtain
by combining the formalism used for verification and the translation procedure
from the process schema to this formalism.
Formal Semantics of Time Patterns 11
4 On the Formal Semantics of Time Patterns
Since we use execution traces to define pattern semantics, Section 4.1 first defines
basic notions (e.g., event and trace) used throughout this paper. Section 4.2 then
provides the formal semantics of each of the time patterns presented in [19].
4.1 Temporal Execution Traces
We use the notion of event as general term for something that happens during the
execution of a process instance (cf. Fig. 5). For example, the start and end of an
activity, executed in the context of a particular process instance, constitute such
events (cf. Fig. 1 and Fig. 5). However, external events (e.g., reaching a milestone
or receiving a message) may exist as well. Additionally, there are intermediate
activity events, which may be triggered inside a long-running activity (cf. Fig. 5).
A1
A3
A5
A4
A6
Activity End Event
Activity Start Event
e0
e9
e2e7
e
10
e
8
eA1SeA1E
eA3SeA3EeA4SeA4E
eA5SeA5EeA6SeA6IeA6E
Process End Event
External Event
Process Event
Process Start Event
Milestone Event
Intermediate Activity Event
Fig. 5. Events occurring during a process
Definition 1 (Process schema, Process instance, Event, Event occur-
rence).
Let
PS
be the set of all process schemes and let
E
be the set of all
Events. Then, the set of all events that may occur during the execution of an
instance
I
of process schema
S
P
PS
is denoted as
ES
E
(Note, that without
loss of generality we assume unique labeling of events). Let further
C
be the total
set of absolute time points. Then:
ϕ
p
e, t
q P
E
C
denotes the occurrence of event
e
P
E
at time point
t
P
C
, i.e.,
t
defines the exact
point in time at which event
e
occurred. Moreover,
ΦS
ES
C
denotes the set of
all possible event occurrences during the execution of process schema
S
. Finally,
for the sake of brevity, we use notions
ϕe
and
ϕt
when referring to event
e
or
time stamp tof an event occurrence ϕ
p
e, t
q
.♦
Based on events and event occurrences, we define the notion of temporal
execution trace (trace for short). We assume that all events related to the
12 Andreas Lanz, Manfred Reichert, and Barbara Weber
execution of a particular process instance are recorded in a temporal execution
trace together with a time stamp designating their time of occurrence.
1
Formally:
Definition 2 (Temporal Execution Trace).
Let
PS
be the set of all process
schemes. Then:
QS
denotes the set of all possible temporal execution traces
producible on process schema
S
P
PS
. Let
ΦS
be the set of all possible event
occurrences that may occur during the execution of
S
and
ϕ
p
e, t
q P
ΦS
denote
the occurrence of event
e
at point in time
t
. A temporal execution trace
σS
P
QS
is then defined as ordered set of event occurrences ϕi:
σS
hϕ1, . . . , ϕni, ϕi
P
ΦS, i
1, . . . , n, n
P
N
Without loss of generality, we assume that events in
σS
do not occur at exactly
the same point in time. ♦
Since pattern semantics is defined based on events and event occurrences
we provide a definition of nodes and activities based on events. In particular,
respective definitions are based on the events that may occur during the execution
of the particular node (activity). Thereby, nodes represent both activities and
control connectors (cf. Sec. 2.1).
Definition 3 (Node and Activity). Let PS be the set of all process schemes
and
NS
2
ES
be the set of all nodes based on which process schema
S
P
PS
is
specified. Further, node
n
P
NS
is defined as unique, non-empty set of events
n
ES
(i.e.,
@
n
P
NS
:
n
H
) Thereby, the sets of events of all nodes of a
process schema
S
are disjoint:
@
n, m
P
NS, n
m
:
n
X
m
H
. An occurrence
of a node
n
in a temporal trace
σS
is marked by the occurrence of at least one of
the respective events, i.e.,
D
e
P
n,
D
t
P
C:ϕe
p
e, t
q P
σS.
An activity, in turn, is a special kind of node with a single start and a single
end event (cf. Sec. 2.1). Let
AS
NS
be the total set of activities based on
which process schema
S
P
PS
is specified. An activity
a
P
AS
contains (at
least) a unique start event
eaS
and a unique end event
eaE
, i.e.,
@
a
P
AS
:
D
eaS, eaE
P
ES
:
t
eaS, eaE
u
a
. In turn, occurrence of an activity
a
is marked by
the occurrence of at least both the start event
eaS
and the end event
eaE
in trace
σS, i.e.,
D
t1, t2
P
C:ϕaS
p
eaS, t1
q P
σS
^
ϕaE
p
eaE, t2
q P
σS.♦
Without loss of generality, we can assume that the processing of control connectors
(e.g., XOR-splits, and AND-joins) does not take any time during process execution.
If a control connector does consume time during its execution (e.g., evaluating
an XOR decision), this can be represented by an activity directly preceding the
control connector.
To illustrate these definitions consider Example 3.
1
A temporal execution trace can usually be extracted from the execution log generated
by a PAIS during the execution of a process instance [1].
Formal Semantics of Time Patterns 13
Example 3 (Temporal Execution Trace).
Consider Fig. 5. A temporal exe-
cution trace of the depicted process schema may be as follows:2
σ
h
p
e0,2
q
,
p
eA1S,5
q
,
p
eA1E,10
q
,
p
e2,11
q
,
p
eA5S,15
q
,
p
eA5E,18
q
,
p
e10,19
q
,
p
eA6S,30
q
,
p
eA6I,32
q
,
p
eA6E,37
q
,
p
e7,38
q
,
p
e8,39
q
i
This trace indicates that the particular process instance was started (i.e.,
e0
) at
time point 2. At time point 5, activity
A1
was started (
eA1S
). In turn,
A1
was
completed at time point 10 (
eA1E
). Next, event
e2
occurred at time point 11 and
the lower path was chosen, which is indicated by the occurrence of start event
eA5S
related to activity
A5
. Further note that none of the events of the upper path
occur within the trace as the respective path has been deselected. After completing
activity
A5
(
eA5E
), milestone event
e10
was triggered. Next,
A6
was started at
time point 30. Furthermore, during the execution of
A6
, the intermediate activity
event
eA6I
was triggered. Finally, after completion of
A6
, events
e7
and
e8
were
triggered completing the process instance.
A path constitutes a connected part of a process schema with a single entry
and a single exit node.
Definition 4 (Path).
The set of all paths within a process schema
S
P
PS
is
denoted as
PS
. In turn, a path
%
P
PS
is represented as subset E
%
ES
of all
events producible on process schema
S
, where E
%
contains all events that may
occur during the execution of path
%
. In particular, a path is compound and has
a single entry and a single exit node connecting it with the remaining process.
Thereby, for each split node, the respective join node is also contained and vice
versa. ♦
Paths are also denoted as single-entry single-exit regions (SESE) [48].
Example 4 (Paths).
Consider Fig. 5 which shows a process schema with several
different paths. For example, activities
A3
and
A4
(i.e., events
eA3S
,
eA3E
,
eA4S
,
and
eA4E
) constitute a path. Likewise, activities
A5
and
A6
represent a path.
Furthermore, the process fragment containing activities
A1
,
A3
,
A4
,
A5
, and
A6
as well as nodes
e2
and
e7
constitutes another path. Finally, note that according
to Definition 4 each of the activities represents a path by its own.
When defining time pattern semantics, we must also deal with patterns for
which the iteration of a loop structure needs to be taken into account.
Example 5 (Cyclic Elements).
Consider the process depicted in the upper
part of Fig. 6. It contains two nested loops: the inner loop
L2
contains two
alternative branches either executing activity
A6
or
A7
. Therefore, the time lag
between
A6
and
A7
must be a Cyclic Element (TP9) since
A6
and
A7
cannot be
executed within the same iteration of the respective loop. In turn, time pattern
TP9 requires the target activity to be contained in an iteration succeeding the
2
Note that in the following, without loss of generality, we use integers starting at 0
for representing absolute time points c
P
C.
14 Andreas Lanz, Manfred Reichert, and Barbara Weber
one to which the source activity belongs. Assume that the cyclic element only
restricts the maximum time lag between directly succeeding iterations of the two
activities (design choice K[a]), i.e., only if
A7
is executed in an iteration of Loop
L2
directly after
A6
, but without executing another instance of
A6
,
A7
or
A10
in between, the respective maximum time lag must be obeyed. To formalize this
semantics, it is not sufficient to introduce an iteration counter for activities. For
instance, considering Example 5 it cannot always be detected whether another
iteration of loop
L1
has been executed between the two instances of activities
A6
and
A7
. Hence, the current iteration of the outer loop
L1
must be considered as
well.
Generally, it is necessary to always consider the iteration of the inner-most
loop in respect to the iteration of any surrounding loop. When considering Fig. 6,
for example, an instance of activity
A6
may belong to the 3rd iteration of loop
L2within the 2nd iteration of loop L1.
For the sake of simplicity and to be able to uniquely identify the iteration of
each activity, we presume well-nested loops (see Fig. 6). Based on this, we define
the notion of (loop) iteration as follows:
Definition 5 (Iteration).
Let
S
P
PS
be a process schema. Then: a loop
L
is a
specific path
%
P
PS
with the loop start node as entry node and the corresponding
loop end node as exit node. The set of possible iterations of process schema
S
P
PS
is then given as
IS
2
PS
N
. Based on
IS
, the iteration of a loop is
defined as ordered set
I
h
p
L0:nL0
q
,...,
p
Lk:nLk
q
i
P
IS
I
uniquely identifies each loop and its current iteration with respect to the iteration
of any surrounding loop. Thereby,
L0
is the respective process schema and
Li
p
1
¤
i
¤
k
q
the
i
-th loop structure. In turn,
nLi
p
1
¤
i
¤
k
q
designates the
iteration count of loop Liwith respect to its directly surrounding loop Li
1.
In turn, function
iter
p
σS, ϕ
q
returns the current iteration of the inner-most
loop surrounding event ϕe. Formally:
iter : QS
ΦS
ÞÑ
IS
with
iter
p
σS, ϕ
q
h
p
L0:nL0
q
,...,
p
Lk:nLk
q
i
with L1, . . . , Lkbeing the loop structures surrounding event ϕe.♦
Example 6 (Iteration).
In Fig. 6 below the depicted process schema, a temporal
execution trace, together with the respective value of
iter
p
σS, ϕ
q
for each of the
events in the trace, is shown. For example, regarding the occurrence of event
eA7S
during the 2nd iteration of loop
L2
within the 1st iteration of loop
L1
, we obtain
iter
p
σS,
p
eA7S,
qq
h
p
L0: 1
q
,
p
L1: 1
q
,
p
L2: 2
q
i
This is indicated in the second line of the execution trace depicted in Fig. 6.
Formal Semantics of Time Patterns 15
A1e2
e0A3
A6
A7
e4e9
A10 e11
e13
A12
e5e8
loop L1
loop L2
process schema L0TP9: Cyclic Element
Possible trace (without timestamps) and respective iterations:
Trace (Events)
loooooooomoooooooon
iter
p
σS,ϕ
q
ñ
e0, eA1S, eA1E,
loooooooomoooooooon
h
p
L0
:1
q
i
e2, eA3S, eA3E,
loooooooomoooooooon
h
p
L0
:1
q
,
p
L1
:1
q
i
e4, e5, eA6S, eA6E, e8, e9,
looooooooooooooomooooooooooooooon
h
p
L0
:1
q
,
p
L1
:1
q
,
p
L2
:1
q
i
. . .
...,e4, e5, eA7S, eA7E, e8, e9,
loooooooooooooooomoooooooooooooooon
h
p
L0
:1
q
,
p
L1
:1
q
,
p
L2
:2
q
i
eA10S, eA10 E, e11,
loooooooooomoooooooooon
h
p
L0
:1
q
,
p
L1
:1
q
i
e2, eA3S, eA3E,
loooooooomoooooooon
h
p
L0
:1
q
,
p
L1
:2
q
i
. . .
...,e4, e5, eA6S, eA6E, e8, e9,
looooooooooooooomooooooooooooooon
h
p
L0
:1
q
,
p
L1
:2
q
,
p
L2
:1
q
i
eA10S, eA10 E, e11,
loooooooooomoooooooooon
h
p
L0
:1
q
,
p
L1
:2
q
i
eA12S, eA12 E, e13
looooooooomooooooooon
h
p
L0
:1
q
i
(eAiS: start event,
and eAiE: end event
of activity Ai)
Fig. 6. Nested loops and iterations
Based on Definition 5, Table 2 summarizes useful notions. Note that, these
facilitate the formalization of the time patterns.
Since a particular event may occur multiple times within a trace (e.g., in
connection with loops), we further define function
occur
p
σS, e
q
. It returns all
event occurrences of an event ewithin a trace :
Definition 6 (Trace Occurrences).
Let
S
P
PS
be a process schema and
σS
a temporal trace on
S
. Then:
occur
p
σS, e
q
corresponds to a function returning
all occurrences ϕ
p
e,
q
of event e
P
ESwithin σS. Formally:
occur : QS
ES
ÞÑ
2ΦS
with
occur
p
σS, e
qt
ϕ
P
σS
|D
t
P
C:ϕ
p
e, t
q P
σS
u
♦
Note that Definition 6 implies that
occur
p
σS, e
qH
holds, if
E
t
P
C
:
p
e, t
q P
σS
,
e.g., in case the respective path has been skipped (cf. Example 3).
Similar to events, activities may occur multiple times within a trace. In turn,
each instance of an activity is marked by the occurrence of its start and end event
(cf. Definition 3). Therefore, we define function
occur
p
σS, a
q
, which returns all
instances of a particular activity
a
(i.e., occurrences of the start and end events)
within a trace:
Definition 7 (Activity Occurrence).
Let
S
P
PS
be a process schema and
σS
a temporal trace on
S
. Then:
occur
p
σS, a
q
is a function that returns all oc-
currences
p
ϕS, ϕE
q
of the start and end event
eaS, eaE
P
ES
of activity
a
P
AS
16 Andreas Lanz, Manfred Reichert, and Barbara Weber
Let
σS
hϕ1,...,ϕni
P
QS
be a temporal execution trace on process
schema S. Then:
Iteration Ioccurs in trace σS, denoted as σS
$
I, iff
D
ϕ
P
σS: iter
p
σS, ϕ
q
I
For an iteration
I
h
p
L0:nL0
q
,...,
p
Lk:nLk
q
i
, the next iteration
succ
p
I
q
is defined as
succ
p
I
q
p
L0:nL0
q
,...,
p
Lk
1:nLk
1
q
,
p
Lk:nLk
1
q
Iteration Iais adjacent to iteration Ib, denoted as IakIb, iff
–Ibrepresents the first iteration of an inner loop of Ia, i.e, for n
¥
1:
Ia
h
p
L0:nL0
q
,...,
p
Lk:nLk
q
i
^
Ib
h
p
L0:nL0
q
,...,
p
Lk:nLk
q
,
p
Lk
1: 1
q
,...,
p
Lk
n: 1
q
i
or
–Iarepresents the last iteration of an inner loop of Ib, i.e., for n
¥
1:
Ia
p
L0:nL0
q
,...,
p
Lk
n:nLk
n
q
,...,
p
Lk:nLk
q
^
Ib
p
L0:nL0
q
,...,
p
Lk
n:nLk
n
q
^
@
m
Pr
k
n,k
s
:
nLm
max
!
x
|
σS
$
p
L0:nL0
q
,...,
p
Lm
1:nLm
1
q
,
p
Lm:x
q
)
Iteration Ibis a succeeding iteration of iteration Ia, denoted as Ia
Ib, iff
p
succ
p
Ia
q
Ib
q _
D
I
1
P
IS:
succ
p
I
1
q
Ib
_
I
1
kIb
^
Ia
I
1
Table 2. Useful notions
within
σS
.
3
Thereby, two occurrences of events
eaS
and
eaE
belong to the same
activity instances if they occurred within the same iteration. Formally:
occur : QS
AS
ÞÑ
2ΦS
ΦS
with
occur
p
σS, a
q tp
ϕS, ϕE
q P
ΦS
ΦS
|
ϕS
P
occur
p
σS, eaS
q ^
ϕE
P
occur
p
σS, eaE
q
^
iter
p
σS, ϕS
q
iter
p
σS, ϕE
qu
♦
Finally, for the sake of readability, we will omit subscript
S
in the formulas if
the respective process schema is evident in the given context.
3Remember that
t
eaS, eaE
u
a(cf. Definition 3)
Formal Semantics of Time Patterns 17
4.2 Time Pattern Semantics
The semantics of the time patterns can now be defined by characterizing the
temporal execution traces
σS
that may be produced by instances of process
schema
S
. In particular, we specify which temporal execution traces satisfy the
temporal constraints expressed by any time pattern applied to S. Formally:
Definition 8 (Compliance).
A temporal execution trace
σS
P
QS
is compliant
with the set of temporal constraints defined on process schema
S
P
PS
if and
only if
σS
is compliant with each of the temporal constraints corresponding to
S
.
In this context, compliance of a trace with a particular temporal constraint on
S
is defined by the semantics of the respective time pattern. ♦
Note that the notions from Definitions 1-8 are independent of any particular
process meta model. Based on them, we describe the formal semantics of the
time patterns. Thereby, we do not differentiate whether the parameter values of
a pattern are set during build-time, process creation-time, or run-time (Design
Choice A) as this does not affect formal pattern semantics. Nevertheless, we
consider which value of a parameter is valid for a specific pattern instance; i.e., if
the parameter value of a pattern occurrence may be modified during run-time
(e.g., deadlines may be changed), we specify which value is relevant for a particular
instance of a pattern occurrence when defining pattern semantics.
Example 7 (Run-time Parameter Values).
Consider the process schema
depicted in Fig. 7. The process contains a maximum time lag between activities
A2
and
A4
. The respective value of the time lag is provided during run-time by
data object
time lag
. Data object
time lag
, in turn, is written by activities
A1
and
A5
. It is important to note that activity
A5
may be executed (or more
important be completed) either before, during, or after executing activity
A4
.
Depending on the completion time of activity
A5
the time lag may use different
parameter values, i.e., values of data object
time lag
. It is therefore important
to know which of these values is valid for a particular instance of the time lag.
A1A2
e0e7
A4
A5
e3e6
time
lag TP1: Time Lag between Activities
maximum value
parameter value
Fig. 7. Run-time parameter value and concurrent change
18 Andreas Lanz, Manfred Reichert, and Barbara Weber
Finally, to structure formalization effects, we bundle time patterns having
similar or related foundations (and therefore formalization).
Our first set of time patterns having similar foundations comprises patterns
TP1 (Time Lags between two Activities), TP2 (Duration), TP3 (Time Lags
between Arbitrary Events), and TP9 (Cyclic Elements). These patterns restrict
the relative time distance between pairs of events that may occur during the
execution of a process instance. What kind of relative time distance is expressed,
constitutes a pattern-specific design choice (Design Choice D); i.e., the time
distance can be a minimum value, a maximum value, or an interval (i.e., both
minimum and maximum). The kind of events to which a specific pattern can
be applied may be also restricted by the pattern itself; e.g., a time lag between
activities may only be applied to the start or end events of two different activities.
Furthermore, only pairs of event occurrences whose iterations are compliant with
the respective pattern may be considered; e.g., for time pattern activity Duration
(TP2; DC C[a]), the occurrences of the start and end event of the respective
activity must belong to the same iteration.
Definition 9 (Relative time distance between events).
Let
C
be the total
set of absolute time points and
D
be the set of relative time distances. Let
eX
and
eY
represent source and target events of the time distance, i.e., the events
between which the time distance is specified. Compliance of a given trace
σ
with
a relative time distance between events eXand eYis then defined as follows:
All valid pairs of event occurrences
ϕ
p
eX,
q
and
ψ
p
eY,
q
must satisfy
the relative time distance as it is effective at the occurrence time of the target
event
ψ
. Thereby, a pair of event occurrences is valid if their iterations are
compliant with the respective pattern. This is expressed by pattern-specific function
valid
:
Q
Φ
Φ
Ñ
Boolean
. In turn, function
distance
:
Q
E
E
C
Ñ
2
D
represents the parameter value of the respective pattern occurrence between events
eX
and
eY
as it is effective at time
t
(cf. Example 7). Finally, whether or not a
pair of event occurrences
ϕ
and
ψ
satisfies the relative time distance, depends on
the kind of temporal distance represented by the pattern (i.e., minimum distance,
maximum distance, or time interval; cf. Design Choice D). In turn, this is defined
by function
compareR : C
C
2D
Ñ
Boolean
with
compareR
p
ϕt, ψt, d
q
$
'
&
'
%
ϕt
min
p
d
q ¤
ψtif min distance (DC D[a])
ψt
¤
ϕt
max
p
d
q
if max distance (DC D[b])
ϕt
min
p
d
q ¤
ψt
¤
ϕt
max
p
d
q
if time interval (DC D[c])
All patterns of the first set (i.e., pattern TP1, TP2, TP3, and TP9) can now
be formalized using Formula (1) and applying different restrictions to
eX
,
eY
,
and valid
p
σ, ϕ, ψ
q
:
@
ϕ
P
occur
p
σ, eX
q
,
@
ψ
P
occur
p
σ, eY
q
:
valid
p
σ, ϕ, ψ
q ñ
compareR
p
ϕt, ψt,distance
p
σ, eX, eY, ψt
qq
(1)
Formal Semantics of Time Patterns 19
♦
Formula (1) expresses that for each valid pair of occurrences of the source and
target events, the time distance between them must be compared with the current
parameter value of the respective pattern (according to the kind of time distance
represented by the pattern; cf. Design Choice D). In this context, note that only
the parameter value (i.e., the data value) which is valid at the occurrence time of
the target event is considered (see
distance
p
,
,
, ψt
q
and cf. Example 7). Based
on this general definition, the semantics of time patterns TP1, TP2, TP3, and
TP9 will be defined.
Time pattern TP1 restricts the time lag between two activities Aand B.
Pattern Semantics 1 (TP1: Time Lags between Activities).
The seman-
tics of time pattern TP1 can be defined using Formula (1) by applying the
following restrictions to eX,eY, and valid
p
σ, ϕ, ψ
q
:
(a)
Depending on the kind of relation a time lag represents (i.e., Start-Start,
Start-End, End-Start, or End-End; cf. Design Choice E), event
eX
either
corresponds to the start or end event of the source activity. Likewise,
eY
corresponds to the start or end event of the time lag’s target activity.
(b)
The two activities or more precisely their events must either belong to the
same or an adjacent iteration, i.e., the first or last iteration of an inner
loop.4Consequently, it holds:
valid
p
σ, ϕ, ψ
qp
iter
p
σ, ϕ
q
iter
p
σ, ψ
qq _ p
iter
p
σ, ϕ
q
kiter
p
σ, ψ
qq
Restriction (a) expresses, for example, that for an End-Start relation between
two activities (e.g.,
A3
and
A6
in Fig. 8),
eX
corresponds to the end event of
the source and
eY
to the start event of the target activity, i.e., the constraint
restricts the time lag between the end event of the source and the start event of
the target activity.
In turn, restriction (b) expresses that the two activities (i.e, respective event
occurrences) must either belong to the same or to an adjacent iteration. The
second part of (b) can then be interpreted as follows: The definition of the pattern
semantics needs to be valid in connection with loops as well. As illustrated in
Fig. 8, considering time lags between two activities (TP1) of which one resides
inside a loop and the other one outside this loop (e.g., a time lag between activities
A1
and
A3
in Fig. 8) is a challenging task due to the unclear semantics of such
scenario. This becomes even more complicated when considering nested loops as
well. For example, consider a time lag between activities
A1
and
A6
in Fig. 8.
There exist several possible semantics for such a time lag. First, time lags whose
source activity is contained in one loop and whose target activity is inside a
nested loop (cf. Fig. 8) might only apply to the first or last iteration of the nested
loop. Second, such “inbound” time lag may be applied to all iterations of the
inner loop as well (effectively leading to different semantics for minimum and
4Note that the adjacency operator khas been defined in Table 2
20 Andreas Lanz, Manfred Reichert, and Barbara Weber
maximum time lags). Third, the time lag may be augmented by meta information
describing the iteration or iterations it applies to. Note that the same holds for
time lags whose source activity is inside a nested loop and whose target activity
is outside that loop (cf. Fig. 8). To resolve this issue, the current definition of the
semantics of pattern TP1 restricts the application of such a time lag to adjacent
iterations of respective loops, i.e., it restricts an “inbound” time lag to the first
iteration of a loop and an “outbound” time lag to the last iteration of a loop. If
necessary, this can be extended to specific iterations of the respective loops.
A1e2
e0A3
A6
A7
e4e9
A10 e11
e13
A12
e5e8
loop
loop
Fig. 8. Time lags and loops
Example 8 (Pattern Semantics 1).
We illustrate Pattern Semantics 1 for
the process schema depicted in Fig. 9. This schema contains a minimum time lag
of 10 between the end of activity
A1
and the start of activity
A6
, and a maximum
time lag of 7 between the start of
A3
and the start of
A7
. Based on this process
schema, for example, traces σ1-σ3may be produced.
σ1
h
p
e0,0
q
,
p
eA1S,1
q
,
p
eA1E,3
q
,
p
e2,4
q
,
p
eA3S,10
q
,
p
eA3E,12
q
,
p
e5,13
q
,
p
eA6S,14
q
,
p
eA6E,15
q
,
p
eA7S,17
q
,
p
eA7E,19
q
,
p
e8,20
q
i
σ2
h
p
e0,0
q
,
p
eA1S,2
q
,
p
eA1E,5
q
,
p
e2,6
q
,
p
eA4S,8
q
,
p
eA4E,10
q
,
p
e5,11
q
,
p
eA6S,13
q
,
p
eA6E,19
q
,
p
eA7S,25
q
,
p
eA7E,27
q
,
p
e8,28
q
i
σ3
h
p
e0,0
q
,
p
eA1S,4
q
,
p
eA1E,7
q
,
p
e2,8
q
,
p
eA3S,10
q
,
p
eA3E,18
q
,
p
e5,19
q
,
p
eA6S,20
q
,
p
eA6E,22
q
,
p
eA7S,23
q
,
p
eA7E,29
q
,
p
e8,30
q
i
Trace
σ1
is compliant with the set of temporal constraints defined on the
process schema. For example, the time lag between A1and A6is observed as
ϕt
eA1E
min
p
distance
p
σ, eA1S, eA6E, ϕt
eA6E
qq
3
10
13
¤
ϕt
eA6S
14
and the time lag between A3and A7as
ϕt
eA7S
17
¤
ϕt
eA3S
max
p
distance
p
σ, eA3S, eA7S, ϕt
eA7S
qq
10
7
17.
In turn, trace
σ2
is not compliant with the temporal constraints defined by the
process schema. Although the time lag between
A3
and
A7
is fulfilled, as activity
A3is not executed, the one between A1and A6is not fulfilled:
Formal Semantics of Time Patterns 21
ϕt
eA1E
min
p
distance
p
σ, eA1S, eA6E, ϕt
eA6E
qq
5
10
15
¦
ϕt
eA6S
13.
Finally, trace
σ3
is not compliant with the process schema. This time the time
lag between
A1
and
A6
is observed, but the time lag between
A3
and
A7
is not,
because it holds
ϕt
eA7S
23
¦
ϕt
eA3S
max
p
distance
p
σ, eA3S, eA7S, ϕt
eA7S
qq
10
7
17.
A1
e0
A3
A4
A6e8
A7
e2e5
end-start time lag
minimum 10 start-start time lag
maximum 7
Fig. 9. Illustration of Pattern Semantics 1
We next consider the semantics of time pattern TP3. Remember that TP3
restricts the time lag between two arbitrary events.
Pattern Semantics 2 (TP3: Time Lags between Arbitrary Events).
The semantics of TP3 can be expressed based on Formula (1) and applying the
following restrictions to eX,eY, and valid
p
σ, ϕ, ψ
q
:
(a) Both eXand eYconstitute arbitrary events.
(b)
As for Pattern Semantics 1, respective events have to belong either to the
same or an adjacent iteration. Hence, it holds:5
valid
p
σ, ϕ, ψ
qp
iter
p
σ, ϕ
q
iter
p
σ, ψ
qq _ p
iter
p
σ, ϕ
q
kiter
p
σ, ψ
qq
As can be seen in the context of Pattern Semantics 2, TP3 constitutes a
generalization of TP1 [
19
], effectively removing restriction (a) as specified for
Pattern Semantics 1.
Time pattern TP9 restricts the time lag between activities
A
and
B
across
iterations.
6
As discussed in [
19
], time pattern TP9 is a variant of time pattern
TP1. However, instead of enforcing the two activity instances to be inside the
same or adjacent iterations of a loop, we require the instance of the target activity
to be contained in an iteration succeeding the one to which the source activity
belongs.
5
For the sake of simplicity we assume same restrictions as for TP1. We are aware that
this might not always be desired. However, it is no problem to adapt this definition
for cases where other relations between iterations are required.
6Note that Aand Bmay represent the same activity.
22 Andreas Lanz, Manfred Reichert, and Barbara Weber
Pattern Semantics 3 (TP9: Cyclic Elements).
The semantics of time pat-
tern TP9 can be expressed based on Formula (1) and by applying the following
restrictions to eX,eY, and valid
p
σ, ϕ, ψ
q
:
(a) For eXand eY, the same restrictions as for Pattern Semantics 1 apply.
(b)
The activities and corresponding events of a cyclic element must either
belong to directly succeeding iterations or to arbitrary, but succeeding
iterations (Design Choice K). Hence, it holds:
valid
p
σ, ϕ, ψ
q
$
'
'
'
'
&
'
'
'
'
%
succ
p
iter
p
σ, ϕ
qq
iter
p
σ, ψ
q
if directly succeeding
iterations (DC K[a])
p
iter
p
σ, ϕ
q
iter
p
σ, ψ
qq^
pE
ω
P
occur
p
σ, ϕe
q Y
occur
p
σ, ψe
q
:
iter
p
σ, ϕ
q
iter
p
σ, ω
q
iter
p
σ, ψ
qq
if arbitrary, but suc-
ceeding iterations (DC
K[b])
Restriction (b) can be interpreted as follows: Depending on design choice
K, the target event must either occur in the directly succeeding iteration of
the source event (Design Choice K[a]) or in an arbitrary iteration succeeding
the iteration of the source event (Design Choice K[b]). In the first case, the
succeeding iteration of the source event (i.e.,
succ
p
iter
p
σ, ϕ
qq
) corresponds to the
iteration of the target event. In the second case, the target event must belong
to an iteration succeeding the one of the first event (i.e., iter
p
σ, ϕ
q
iter
p
σ, ψ
q
).
However, there may not be any occurrence of either the source
ϕe
or the target
ψeevent inbetween these two iterations.
Time pattern TP2 allows expressing that a particular activity, activity set,
process, or set of process instances must obey a duration restriction. Its semantics
is quite similar to Pattern Semantics 1-3 since it considers the relative time
distance between events as well.
Pattern Semantics 4 (TP2: Durations).
For an activity or process (Design
Choice C[a] and C[c]), respectively, the semantics of TP2 is defined based on
Formula (1) by applying the following restrictions to
eX
,
eY
, and
valid
p
σ, ϕ, ψ
q
(a)
Depending on the chosen granularity (i.e., activity or process) to which
the pattern is applied
eX
(
eY
) corresponds to the start (end) event of the
activity or process, respectively.
(b)
Both events of a valid pair must belong to the same activity (process)
instance and therefore the same iteration, i.e,
valid
p
σ, ϕ, ψ
qp
iter
p
σ, ϕ
q
iter
p
σ, ψ
qq
In turn, for an activity set
A
A
(Design Choice C[b]) Formula (1) needs
to be extended to consider sets of events as well. Let
EX
represent the set
of start events and
EY
the set of end events of all activities from
A
. Further,
function
duration
:
Q
2
A
C
Ñ
2
D
represents the parameter values of the
corresponding pattern on Aas it is effective at time t.
Formal Semantics of Time Patterns 23
–
For a minimum duration (Design Choice D[a]), it must hold that for each
valid pair of occurrences of events
eX
P
EX
and
eY
P
EY
, there exists at least
one pair of event occurrences within the same iteration which satisfies the
respective minimum duration:
@
a
P
A:
@p
ϕS, ϕE
q P
occur
p
τ, a
q ñ
D
eX
P
EX,
D
eY
P
EY:
D
µ
P
occur
p
σ, eX
q
,
D
ν
P
occur
p
σ, eY
q
:
valid
p
σ, µ, ν
q ^
iter
p
σ, ϕS
q
iter
p
σ, µ
q
ñ
µt
min
p
duration
p
σ, A, νt
qq ¤
νt
(2)
Each iteration may have several valid event pairs. However, only one of these
pairs must obey the given minimum duration. In this context, note that the
duration of the activity set corresponds the maximum time distance between
any events of the set.
–
A maximum duration (Design Choice D[b]) must be met by all valid pairs of
event occurrences eX
P
EXand eY
P
EY
@
eX
P
EX,
@
eY
P
EY:
@
ϕ
P
occur
p
σ, eX
q
,
@
ψ
P
occur
p
σ, eY
q
:
valid
p
σ, ϕ, ψ
q ñ
ψt
¤
ϕt
max
p
duration
p
σ, A, ψt
qq
(3)
–
For a time interval (DC D[c]), both Formula (2) and Formula (3) must be
satisfied.
For handling a set of process instances (DC C[b]), the above formulas must be
extended to consider different process instances. In this case
EX
(
EY
) represents
the start (end) events of all process instances of the set. For the sake of brevity,
we omit respective formulas here.
Regarding Pattern Semantics 1-4, it is noteworthy that none of the described
formalizations requires that all referred events are present in a temporal execution
trace; e.g., a maximum time lag between two activities is trivially fulfilled if the
target activity is never executed within the respective process instance.
As another set of time patterns with similar foundations we consider patterns
TP4 (Fixed Date Element) and TP7 (Validity Period). Both patterns refer
to absolute points in time and may be applied to either an activity or process
(Design Choice C). Finally, they can restrict the earliest start, latest start, earliest
completion, or latest completion date of the activity or process, respectively
(Design Choice F).
Definition 10 (Absolute time point of an event). Let Cbe the total set of
absolute time points. Compliance of a given trace σwith an absolute time point
for event
e
is defined as follows: All occurrences
ϕ
p
e,
q
of the event must
satisfy the absolute time point as it is effective at the time the event occurred.
Thereby, function
date
:
Q
E
C
Ñ
C
represents the parameter value of the
pattern occurrence as it is effective at time
t
. Finally, whether an event occurrence
24 Andreas Lanz, Manfred Reichert, and Barbara Weber
ϕ
satisfies an absolute time point depends on the kind of date (i.e., earliest/latest
start date, earliest/latest completion date) restricted by the respective constraint
(Design Choice F) and is expressed by function
compareA : C
C
Ñ
Boolean
with
compareA
p
ϕt, t
q
#
t
¤
ϕtif earliest start or completion date (DC F[a] or F[c])
ϕt
¤
tif latest start or completion date (DC F[b] or F[d])
Both patterns TP4 and TP7 can be formalized using Formula (4) by applying
different functions for date
p
σ, e, t
q
.
@
ϕ
P
occur
p
σ, e
q
: compareA
p
ϕt,date
p
σ, e, ϕt
qq
(4)
Depending on the kind of process element (i.e., activity or process; Design Choice
C) and the kind of date restricted by the constraint (i.e., earliest/latest start,
earliest/latest completion; Design Choice F), event
e
either corresponds to the
start or end event of the activity (process). ♦
Time pattern TP4 allows expressing that a particular activity (process)
instance must be executed in relation to a particular date.
Pattern Semantics 5 (TP4: Fixed Date Element).
The semantics of time
pattern TP4 can be expressed using Formula (4). In this context,
date
p
σ, e, ϕt
q
corresponds to a function returning the parameter value of the pattern occurrence
as it is effective for process instance
σ
at the time of event occurrence
ϕ
p
e, t
q
.
Example 9 (Pattern Semantics 5).
We illustrate Pattern Semantics 5 along
the process from Fig. 10. It contains a fixed date constraining the latest end date
of activity
A2
. In turn, the parameter value of the fixed date (i.e., the value of
function date) is determined by activity A1and may be modified by activity A3.
Traces σ1and σ2may be produced based on this process schema.
σ1
D
p
e0,0
q
,
p
eA1S,2
q
,
p
eA1E,4
q
t
date
p
σ,eA2E,t
¥
4
qÐ
7
u
,
p
eA2S,5
q
,
p
eA3S,6
q
,
p
eA2E,7
q
,
p
eA3E,10
q
t
date
p
σ,eA2E,t
¥
10
qÐ
12
u
,
p
e4,12
q
E
σ2
D
p
e0,0
q
,
p
eA1S,2
q
,
p
eA1E,4
q
t
date
p
σ,eA2E,t
¥
4
qÐ
12
u
,
p
eA3S,5
q
,
p
eA3E,6
q
t
date
p
σ,eA2E,t
¥
6
qÐ
8
u
,
p
eA2S,7
q
,
p
eA2E,9
q
,
p
e4,12
q
E
Thereby,
p
eA1E,
4
q
t
date
p
σ,eA2E,t
¥
4
qÐ
7
u
, for example, indicates that after the oc-
currence of event
eA1E
the value of
date
p
σ, eA2E,
q
is changed to 7, i.e.,
@
t
¥
4 : date
p
σ, eA2E, t
q
7(cf. trace σ1).
Formal Semantics of Time Patterns 25
σ1
complies with the fixed date constraining activity
A2
as the parameter value
of this fixed date is set to 7by
A1
and not modified by
A3
before completing
A2
.
Hence, for the completion event of A2it holds
ϕt
A2E
7
¤
date
p
σ, eA2E, ϕt
A2E
q
7.
In turn,
σ2
is not compliant with the fixed date constraining
A2
. Initially, the
parameter value of this fixed date element is set to 12 by activity
A1
. However,
before completing
A2
, activity
A3
is executed. Further,
A3
changes the parameter
value of the fixed date element to 8. Hence, for the completion of A2it holds
ϕt
A2E
9
¦
date
p
σ, eA2E, ϕt
A2E
q
8.
fixed date on
latest completion
A1
e0e4
A2
parameter value
A3
fixed
date
Fig. 10. Illustration of Pattern Semantics 5
Time pattern TP7 allows restricting the life time of an activity (or process)
to a certain validity period.
Pattern Semantics 6 (TP7: Validity Period).
The semantics of TP7 can
be expressed based on Formula (4). Thereby, the value of
date
p
σ, e, t
q
is indepen-
dent of both the current process instance
σ
and time
t
, i.e.,
date
p
, e,
q
const.
Note that Pattern Semantics 5 and 6 are quite similar. As only difference,
for Pattern Semantics 6 the value of function
date
p
, e,
q
is independent of the
particular process instance and the current time. In turn, for Pattern Semantics 5
the actual return value of
date
p
σ, e, t
q
may be different for each process instance
and time point. Nevertheless, the impact the respective time patterns (i.e., TP4
and TP7) have on process execution is quite different; e.g., TP7 should be verified
prior to creation of any process instance, whereas TP4 may only be verified
during run-time. Consequently, semantics of time patterns TP4 an TP7 (i.e.,
Pattern Semantics 5 and 6) are defined separately.
We now consider the semantics of time pattern TP5 (Schedule Restricted
Elements). As discussed in [
19
], TP5 allows restricting the possible execution
times of an activity (or process) through a schedule. In turn, a schedule constitutes
an abstract representation of a possibly infinite set of time slots described in
26 Andreas Lanz, Manfred Reichert, and Barbara Weber
terms of a finite expression. Since we do not want to restrict the representation
of such a schedule (e.g., [
49
,
50
]), we require that it can be materialized as a set
of subsets of the absolute time points C(i.e., as a set of time slot).
Definition 11 (Schedule).
A schedule
s
is a possibly infinite set of continuous
subsets (i.e., intervals / time slots) of the absolute time points C. Formally:
s
tr
tmin, tmax
s|r
tmin, tmax
s
C
u
2C
♦
Based on Definition 11, the semantics of time pattern TP5 (Schedule Restricted
Element) can be defined:
Pattern Semantics 7 (TP5: Schedule Restricted Elements).
Trace
σ
is
compliant with a schedule
s
for event
e
of an activity if for all event occurrences
ϕ
p
e,
q
the respective time stamp
ϕt
is contained within one of the time slots
of the schedule. Thereby, function
schedule
:
Q
E
C
Ñ
2
C
represents the
parameter value (i.e., the schedule) of the pattern occurrence as it is effective
at time t. Formally:
@
ϕ
P
occur
p
σ, e
q
:
Dr
tmin, tmax
s P
schedule
p
σ, e, ϕt
q
:tmin
¤
ϕt
¤
tmax (5)
Depending on the kind of process element (Design Choice C) and the kind of
date restricted by the constraint (Design Choice F), event
e
either corresponds
to the start or end event of the activity (process).
Example 10 (Pattern Semantics 7).
Fig. 11 illustrate Pattern Semantics 7.
It shows a simple process with a schedule restricting the start of activity
A1
.
Thereby, the schedule is given by expression
s
tr
5
10
i,
9
10
i
s|
i
¥
0
u
tr
5,9
s
,
r
15,19
s
,
r
25,29
s
, . . .
u
.
Traces σ1and σ2may be produced based on this process schema.
σ1
h
p
e0,0
q
,
p
eA1S,2
q
,
p
eA1E,9
q
,
p
e2,10
q
i
σ2
h
p
e0,0
q
,
p
eA1S,6
q
,
p
eA1E,11
q
,
p
e2,12
q
i
σ1is not compliant with the respective schedule restriction on A1as
ϕt
A1S
2
R
s
tr
5,9
s
,
r
15,19
s
,
r
25,29
s
, . . .
u
.
In turn, σ2is compliant with the schedule restriction:
ϕt
A1S
6
P
s
tr
5,9
s
,
r
15,19
s
,
r
25,29
s
, . . .
u
.
Time-based Restrictions (TP6) allow us to restrict the number of executions
of an activity, a set of activities, a process, or a set of process instances (Design
Formal Semantics of Time Patterns 27
Schedule restriction on start
s = { [5+10*i, 9+10*i] | i≥0 }
A1
e0e2
Fig. 11. Illustration of Pattern Semantics 7
Choice G) within a given time frame; e.g., a particular activity must not be
executed more than once per day. This can be formalized by comparing the
number of executions of the respective activities (processes) within the particular
time frame on one side with a given minimum or maximum number of executions
(Design Choice H ) on the other.
When considering the semantics of pattern TP6, a subtle difference between
the different pattern variants can be observed, which has not been covered by
the original design choices yet [
19
]. To be able to completely define the semantics
of time pattern TP6, Design Choice U must be considered as well (cf. Fig. 12).
Based on this, the number of executions of a particular activity within a time
frame can be defined.
Definition 12 (Executions per time frame).
Let
σS
be a temporal trace on
process schema S
P
PS.
Function
compareT
expresses whether the execution time frame
r
ϕt
S, ϕt
E
s
of
an activity occurrence
p
ϕS, ϕE
q
and the given time frame
r
tmin, tmax
s
fulfil the
restriction set out by Design Choice U. Formally:
compareT : 2C
2C
Ñ
Boolean
with
compareT
pr
tmin, tmax
s
,
r
ϕt
S, ϕt
E
sq
$
'
'
'
'
'
'
'
'
'
&
'
'
'
'
'
'
'
'
'
%
r
tmin, tmax
s X r
ϕt
S, ϕt
E
sH
Overlapping time frames (DC U[a])
r
ϕt
S, ϕt
E
sr
tmin, tmax
s
Execution time frame contained in
given time frame (DC U[b])
ϕt
S
P r
tmin, tmax
s
Start of execution within given time
frame (DC U[c])
ϕt
E
P r
tmin, tmax
s
End of execution within given time
frame (DC U[d])
Function
executions
returns the number of occurrences of an activity
a
P
AS
within a given time frame
r
tmin, tmax
s
. Formally:
executions : QS
AS
2C
ÞÑ
N
with
executions
p
σS, a,
r
tmin, tmax
sq
p
ϕS, ϕE
q P
occur
p
σS, a
q |
compareT
pr
tmin, tmax
s
,
r
ϕt
S, ϕt
E
sq
true
(
♦
28 Andreas Lanz, Manfred Reichert, and Barbara Weber
Design Choice U
U)
Execution time frame of the activity (process) and the given time
frame may be compared in different ways.
a) Overlapping time frames
b) Execution time frame contained in given time frame
c) Start of execution within given time frame
d) End of execution within given time frame
Fig. 12. Design Choice U for time pattern TP6
Based on Definition 12, the semantics of time pattern TP6 (Time Based
Restrictions) can be defined:
Pattern Semantics 8 (TP6: Time-based Restrictions).
For the sake of
simplicity, we assume that a time-based restriction is applied to a set of activities
A
A
related to the same process instance (DC G[a]). In this case, compliance
of a given trace σwith a Time-Based Restriction on Ais defined as follows:
–
A temporal trace
σ
is compliant with a maximum number
n
of concurrent
executions (Design Choices H[b], I[a]) of activities A
A, iff
@
a
P
A:
@p
ϕS, ϕE
q P
occur
p
σ, a
q
:
¸
a
1
P
A
executions
p
σ, a
1
,
r
ϕt
S, ϕt
E
sq
¤
n
For a minimum number of concurrent executions (Design Choice H[a]), the
same formula applies, if using “
¥
n” at the end.
–
In case of a time-based restriction on the number of executions per time period
(Design Choice I[b]), respective time periods may be represented as a schedule
s
tr
tmin, tmax
s|r
tmin, tmax
s
C
u
(cf. Def. 11). Then: A temporal trace
σ
is
compliant with a maximum number
n
of executions (Design Choice H[a]) of
activities A
Aper element of schedule siff:
@r
tmin, tmax
s P
s:
¸
a
P
A
executions
p
σ, a,
r
tmin, tmax
sq
¤
n
For a minimum number of executions per time period (Design Choice H[b]),
the same formula applies, if using “
¥
n” at the end.
For a set of activities belonging to different process instances (Design Choice
G[b]) or a set of process instances (Design Choice G[c]), these sums must
be calculated considering the set of temporal traces. For the sake of brevity,
respective formulas are omitted here.
The first part of Pattern Semantics 8 calculates the execution numbers of activ-
ities from set
A
within execution time frame
r
ϕt
S, ϕt
E
s
of any occurrence
p
ϕS, ϕE
q
Formal Semantics of Time Patterns 29
related to an activity
a
P
A
. For each activity occurrence, this number is then
compared with the given maximum number of concurrent executions. The second
part of Patterns Semantics 8 calculates the execution numbers of activities
a
P
A
for each time slot of schedule
s
. It then compares this number with the given
maximum number of executions per time period. The same applies to a minimum
number of executions.
Time pattern TP8 (Time-dependent Variability) allows varying the control
flow depending on time aspects. Thus, it restricts the set of events a compliant
temporal execution trace may contain; i.e., events belonging to a selected path
must occur within the trace, whereas events related to a deselected path must
not occur within the respective trace (cf. Example 3).7
Each instance of the pattern is triggered by a decision point represented by a
specific event
ed
(e.g., an XOR-split; cf. event
e2
in Fig. 9). To formalize time
pattern TP8 and to abstract from a concrete system implementation we define
function
eval
. It allows evaluating the condition at the time the decision event
ed
occurs for each of the possible paths
%
. Thereby, the current iteration
I
and the
current process instance σare considered.
Definition 13 (Evaluate).
Function
eval
evaluates the condition associated
with a path %
P
Pat time tthe decision point edoccurs. Formally:
eval : Q
P
E
C
ÞÑ
Boolean
♦
The concrete implementation of function
eval
depends on the formalism used
to describe the conditions for path selection. Depending on the outcome of
function
eval
, the sub-traces of the respective path (i.e., the traces producible by
this path) must or must not occur within the trace. Based on Definition 13, the
semantics of TP8 is defined as follows:
Pattern Semantics 9 (TP8: Time-dependent Variability).
A temporal
trace
σ
is compliant with a time-dependent XOR or a time-dependent late
binding (Design Choice J[a]) iff for all paths
%
, affected by the time-dependent
variability, the following condition is met:
@
µ
P
occur
p
σ, ed
q
:
r
eval
p
σ, %, ed, µt
q
true
ñ
E%
H _ D
e
P
E%:
D
ϕ
P
occur
p
σ, e
q
: iter
p
σ, ϕ
q
iter
p
σ, µ
qs
(i)
^
r
eval
p
σ, %, ed, µt
q
false
ñ @
e
P
E%:
@
ϕ
P
occur
p
σ, e
q
: iter
p
σ, ϕ
q
iter
p
σ, µ
qs
(ii)
7
In case of late binding a path only consists of a single activity representing the service
chosen in this path.
30 Andreas Lanz, Manfred Reichert, and Barbara Weber
In turn, the semantics of a time-dependent deferred choice (Design Choice J[b])
can be defined based on Patterns Semantics 1, i.e., this semantics is the same
as for the a time lag between two activities plus the semantics of the deferred
choice workflow pattern [
10
]. For sake of brevity, the respective definition is
omitted here.
Pattern Semantics 9 can be interpreted as follows: For each occurrence of the
decision event and for each outgoing path
%
, it is checked whether the condition
is fulfilled. In case this condition evaluates to
true
either the path must be empty
or at least one of its events must occur in the trace with the same iteration as
the occurrence of the decision event (i). Otherwise, none of the events of the
deselected path may occur within the same iteration as the occurrence of the
decision event (ii).
As discussed in [
19
], a
Periodicity
(Time Pattern TP10) can be realized
during run-time by using suitable combinations of time patterns TP1-6, TP8, and
TP9. As example consider the periodicity depicted in Fig. 13 and its potential
realization shown inside the activity. The semantics of pattern TP10 can be
defined based on the one of the patterns used for realizing the periodicity during
run-time. Therefore, no explicit semantics is provided for this pattern.
TP10: Periodicity
Drug A at ~ 8am, 1pm and 6pm
Drug B every ~2h
A
B
Schedule Restricted Element
s = { 8-9 am, 1-2 pm, 6-7 pm }
cyclic element; end-start
interval [1:45h, 2:15h]
Time-based Restriction
3 times per day
cyclic element; end-start
min 4h
Fig. 13. Illustration of Periodicity and possible realization
4.3 Conclusion
Based on Pattern Semantics 1-9 we are able to check whether a given tempo-
ral execution trace is compliant with all temporal constraints defined on the
corresponding process schema. In this context, there is no particular restriction
regarding the time patterns a process schema may contain, i.e., a single process
schema may contain several occurrences of all pattern variants. However, it must
be ensured that for each possible path that may be selected during process
execution, there exists at least one execution trace that is compliant with all
Formal Semantics of Time Patterns 31
temporal constraints defined. Otherwise, the temporal perspective of the process
schema is inconsistent since it contains conflicting temporal constraints, i.e., the
process schema contains a path that cannot be executed without violating at
least one of the temporal constraints. Formally:
Definition 14 (Consistency).
A process schema
S
P
PS
is consistent with
the set of temporal constraints defined on
S
, if for each possible path
%
P
PS
there exists at least one temporal execution trace
σS
P
QS
that is compliant (cf.
Definition 8) with the set of temporal constraints defined on S.♦
Example 11 (Consistency).
Consider the process depicted in Fig. 14. Now
assume that at XOR-split
e3
the lower path is chosen. In this case a possible
execution trace is
σ
t
e3
Ñ
lower
u
h
p
e0,0
q
,
p
eA1S,1
q
,
p
eA1E,4
q
,
p
e2,5
q
,
p
e3,6
q
,
p
eA8S,9
q
,
p
eA8E,15
q
,
p
eA9S,18
q
,
p
eA5S,20
q
,
p
eA9E,25
q
,
p
eA10S,28
q
,
p
eA5E,35
q
,
p
e6,36
q
,
p
eA7S,37
q
,
p
eA10E,40
q
,
p
eA7E,45
q
,
p
e11,46
q
,
p
eA12S,48
q
,
p
eA12E,58
q
,
p
e13,59
q
i
This particular execution trace complies with all temporal constraints on the
process schema. For example, maximum process duration is satisfied as
ϕt
e13
ϕt
e0
59
¤
60. Moreover, all duration constraints are observed. Finally, the two
time lags between
A1
and
A10
as well as between
A9
and
A12
, which are active
for this trace, are satisfied as ϕt
eA1E
25
¥
ϕt
eA10Sand ϕt
eA9S
35
¥
ϕt
eA12S.
However, in case the upper path is chosen at XOR-split
e3
, no valid execution
traces exists that is compliant with all temporal constraint on the process schema.
In particular, the path determining the shortest time to complete the process (i.e.,
the critical path) is given by
e0, A1, e2, e3, A4, e6, A7, e11, A12,
and
e13
; this sums
up to a minimum process duration of 72. In turn, this violates the maximum
process duration of 60. Consequently, the process schema is inconsistent, as there
exists an execution path for which no valid trace can be found.
Furthermore, the time lags between
A1
and
A4
,
A1
and
A10
, and
A4
and
A10
, as well as the activity duration constraints defined for activities
A4
and
A10
cannot be completely satisfied at the same time. The earliest possible time, activity
A4
may be completed after completing
A1
corresponds to
ϕt
eA1E
20
30. In turn,
the latest possible time
A10
may be completed after completing
A1
corresponds
to
ϕt
eA1E
25
10. Hence,
p
ϕt
eA1E
25
10
qp
ϕt
eA1E
20
30
q
35
50
15
R r
10
,
10
s
holds. Consequently, these constraints will never be completely
satisfied at the same time.
Example 11 indicates the complexity for verifying the consistency of a process
schema in respect to its temporal constraints [
24
,
25
]. Things become even more
complicated due to the fact that not all time patterns can be verified at build-
time [
19
]. For example, the fixed date element of an activity cannot be verified
at build-time since not all parameter values are known [
19
]; i.e., generally the
particular date of this element is set during run-time.
32 Andreas Lanz, Manfred Reichert, and Barbara Weber
A1A12
A9A10
A7
A8
A4
A5
e2
e3
e6
e11
e0e13
fixed date on
latest completion
[1; 5]
[5; 15] [5; 15] [5; 10]
[5; 15]
[30; 40]
[5; 15]
[10; 30]
[1; 60]
end-end
[-10; 10]
end-start
min 20
end-start
max 25 end-start
max 35
Fig. 14. Process containing different time patterns
Overall, the formal semantics of time patterns as presented in this paper may
serve as a solid and sound framework for verifying the consistency of a process
schema containing temporal constraints during build-time. Moreover, it may
serve as basis for verifying and monitoring the consistency of process instances
during run-time.
5 Validation
This section discusses how we validated the described formal semantics of the
time patterns against approaches from academia. The goal of this validation is to
evaluate how well the described formal semantics matches the semantics inherent
to these approaches. In particular, we consider the well-known proposals made by
Bettini [
24
,
51
], Combi [
5
,
25
], Eder [
7
,
52
], and Zhuge [
53
,
54
]. These approaches
were selected based on a systematic literature review (see [
19
] for details). In
particular, they provide the broadest support of the time patterns, i.e., each of
them considers at least 4 of the presented time patterns. Further, they provide
an implementation for some of the time patterns.
For each approach we determine the impact an occurrence of a specific pattern
variant has on the traces producible by a process instance that is compliant with
the pattern according to the respective formalism. We then compare this impact
with the defined formal semantics to determine to what degree they harmonize
with each other.
5.1 Bettini et al.
Bettini et al. [
24
,
51
] use simple temporal problems (STP), a special variant of
temporal constraint networks [
46
], as basic formalism for verifying the consistency
of the temporal perspective of a process schema. Simply spoken, a STP is a
directed graph whose vertices represent variables and whose arcs correspond
Formal Semantics of Time Patterns 33
to constraints between these variables. Each variable has an assigned domain
represented by an interval on the positive integers. In turn, each arc represents a
(temporal) constraint between the two variables it connects, which is described
by an interval on the integers. A STP is denoted as consistent if the graph has
a solution, i.e., there exist values for the variables from the associated domains
such that all constraints are satisfied [
46
]. A process schema is now translated
into a set of STPs by decomposing the process schema along its XOR-splits, i.e.,
each resulting STP corresponds one possible execution path (cf. Fig. 15). When
transforming an execution path into a STP, each activity is decomposed into its
start and end event. For each of these events a variable is added to the set of
vertices. For each activity, the variables of its start and end event are connected
by an arc. Further, for each control edge an arc is added between the variables
corresponding to the two events connected by it. Initially, the domains of all
variables as well as temporal constraints of the arcs are left undefined, i.e., the
assigned interval covers the domain of all positive integers. As example for this
translation consider the process depicted in the upper part of Fig. 15 and the
two corresponding STPs in the lower part of the figure. Finally, loops and the
dynamic setting of the parameter value of a pattern occurrence at run-time are
not considered by this approach.
Regarding time patterns, the proposal made by Bettini et al. [
24
] considers
patterns Time Lags between two Activities (TP1) (called “temporal distance”),
and Durations of activities (TP2, design choice C[a]). Further, Fixed Date El-
ements for activities (TP4, design choice C[a]) (called “deadline constraint”),
and Schedule Restricted Elements for activities (TP5, design choice C[a]) are
discussed, although no details on the implementation are provided.
A
time lag between two activities
(TP1) in a process schema is translated
to the STP by adding an arc between the two variables representing the events
corresponding to the two activities. The temporal constraint of the arc is then
set to the parameter value of the time lag (cf. Fig. 15); i.e., in case of a minimum
value the lower bound of the interval is set to the respective value, whereas for
a maximum value the upper bound of the interval is set. The other bound is
left unrestricted (i.e., it is set to
8
). For an interval value, both bounds of the
temporal constraint are set to the respective values. According to [
46
], an arc
i
Ñ
j
from variable
i
to
j
labeled with an interval
d
represents the constraint
min
p
d
q ¤
Xj
Xi
¤
max
p
d
q
;
Xi, Xj
P
N
represent the values assigned to
variable
i
and
j
respectively. Note that this corresponds to
Xi
min
p
d
q ¤
Xj
¤
Xi
max
p
d
q
, which, in turn, is equal to function
compareR
(cf. Definition 9).
8
Since the approach does not consider loops, only one pair of event occurrences
exists. Therefore, this semantics of a time lag between activities corresponds to
Pattern Semantics 1.
Similarly, an activity
duration
(TP2, design choice C[a]) in a process schema
is translated to the STP by setting the parameter value of the pattern as temporal
constraint for the arc between the variables representing the start and end event
of the activity (cf. Fig. 15). Consequently, this semantics is equivalent to the one
8
Using
max
p
d
q 8
and
min
p
d
q 8
for minimal and maximal value, respectively.
34 Andreas Lanz, Manfred Reichert, and Barbara Weber
A1
e0
A3
A4
A6A7
e2e5
e8
end-start time lag
minimum 10
start-start time lag
maximum 35
[1; 7]
[3; 5]
[2; 9] [5; 8]
[12; 17]
Process
STPs
process duration
maximum 60
e0e2e5e8
A1SA1E
[1, 7] A6SA6E
[2, 9] A7SA7E
[5, 8]
A3SA3E
[3, 5]
[0, ∞] [0, ∞]
[10, ∞]
[-∞, 35]
[0, ∞] [0, ∞]
[0, ∞] [0, ∞] [0, ∞]
[-∞, 60]
e0e2e5e8
A1SA1E
[1, 7] A6SA6E
[2, 9] A7SA7E
[5, 8]
A4SA4E
[12, 17]
[0, ∞] [0, ∞]
[-∞, 35]
[0, ∞] [0, ∞]
[0, ∞] [0, ∞] [0, ∞]
[-∞, 60]
Fig. 15. A Process schema and its corresponding STPs
of Pattern Semantics 5. Other kinds of duration (i.e., activity set, process, set of
process instances) are not discussed. Nevertheless, it is possible to translate the
duration of a process (TP2, design choice C[c]) to a constraint between the first
and last variable of the STP (similar to a time lag between activities). Again,
this translation yields the same semantics as defined by Pattern Semantics 5 for
this pattern variant.
An implementation of
fixed date elements
for activities (TP4, design
choice C[a]) is not presented by [
24
], although the authors claim that they
provide a way to assign a deadline to an activity. In our understanding, it is
possible to implement a fixed date element by restricting the domain of the
variable representing the start or end event of the activity (depending on the date
restricted by the pattern occurrence, i.e., design choice F). In turn, this results in
a constraint
Xi
P
domi
, where
Xi
represents the value of variable
i
and
domi
the
domain of this variable. Since
domi
is an interval, this constraint can be rewritten
as
min
p
domi
q ¤
Xi
¤
max
p
domi
q
. Consequently, this semantics corresponds to
the one of Pattern Semantics 5 (assuming that for an earliest/latest date only the
minimum/maximum of the domain is set to the respective value of the pattern
and the other part is left at
8
).
Support of
schedule restricted elements
for activities (TP5, design choice
C[a]) is claimed, but no implementation is described. We are not aware of any
Formal Semantics of Time Patterns 35
straightforward approach to implement such a constraint based on STPs. There-
fore, it is not possible to compare the semantics of the respective implementation
with our formal semantics.
Time lags between events
(TP3) are not considered, but may be translated
to the STP the same way as TP1 (assuming that all events of the process schema
are translated to variables in the STP). Again the resulting semantics corresponds
to the one of Pattern Semantics 2. Finally, since dynamic changes of the parameter
value of a time pattern during run-time are not considered, a
validity period
(TP7) can be implemented the same way as a fixed date element. Therefore, its
semantics is equivalent to Pattern Semantics 6.
5.2 Combi et al.
The approach suggested by Combi et al. [
5
,
25
] also uses simple temporal problems
(STP) as formalism for verifying the consistency of the temporal perspective of
a process schema. However, unary constraints (i.e., domains of variables) are
represented by an arc between a special origin variable (representing time point
0) and the respective variable having the corresponding domain as temporal
constraint. Again, a process schema is decomposed along its XOR-splits into
a set of STPs, such that each STP represents one possible execution path (cf.
Fig. 15). In particular, the transformation process is similar to the one used
by Bettini et al. (cf. Sec. 5.1). Additionally, well-nested loops are considered.
Thereby, each loop is associated either with a minimum and maximum number
of iterations or a maximum duration for completing all iterations of the loop.
Based on this, a loop can be transformed into a consecutive set of XOR-splits
for deciding whether the next iteration shall be executed or remaining iterations
shall be skipped (cf. Fig. 16). In turn, this can be translated into a STP the same
way normal XOR-splits are handled. Furthermore, the dependencies between
resulting STPs are considered, i.e., implicit constraints discovered in the STP
of one execution path are propagated to the STPs of all other execution paths
containing the involved variables. Finally, changing the parameter value of a
pattern occurrences during run-time is not considered.
B
min iteration: 2
max iteration: 4
repeat
exit B B‘ B‘‘ B‘‘‘
repeatrepeat
exit
exit
1. Iteration 2. Iteration 3. Iteration 4. Iteration
Fig. 16. Converting a Loop to a Set of Consecutive XOR-splits
In terms of the time patterns Combi et al. [
5
,
25
] consider Time Lags between
Activities (TP1) and Durations of activities (TP2, design choice C[a]). Further,
Fixed Date Elements for the earliest start and the latest completion of activities
(TP4, design choices C[a], F[a,d]) are considered. Finally, [
5
] mentions Schedule
36 Andreas Lanz, Manfred Reichert, and Barbara Weber
Restricted Elements related the start of activities (TP5, design choices C[a], F[a])
and Periodicity (TP10). However, no implementation details are provided.
[
25
] discusses two different ways of defining a
time lag between two activ-
ities
(TP1): delays and relative temporal constraints. A delay corresponds to an
end-start time lag between two directly succeeding activities, i.e., it represents
“the duration at disposal [of the PAIS] for managing the start of the successor(s)
after the end of the predecessor(s)” [
25
, p. 7]. In turn, a “relative [temporal]
constraint limits the time distance [...] between the starting/ending instants
[(i.e., events)] of two nonconsecutive [...] nodes” [
25
, p. 8]. Therefore, it corre-
sponds to a time lag between two activities. Both (i.e., delay and relative tempo-
ral constraint) are represented by an interval
r
MinDuration, MaxDuration
s
and translated to the STP by adding an arc with a corresponding tempo-
ral constraint between the respective events. Again, this results in constraint
MinDuration
¤
Xj
Xi
¤
MaxDuration
, which is equivalent to function
compareR
(see Definition 9). For time lags in connection with loops, [
25
, p. 9] de-
fines that “tasks [(i.e., activities)] within a cycle [(i.e., loop)] may be constrained
only with respect to other tasks of the same cycle and these constraints are
verified each iteration of the cycle” [
25
, p. 9]. Therefore, inbound and outbound
time lags of a loop are excluded. For all other cases, this definition yields the
same semantics as defined by Pattern Semantics 1.
A
duration
of an activity (TP2, design choice C[a]) is specified in terms of
an interval
r
MinDuration, MaxDuration
s
and translated to the STP by adding
a constraint
MinDuration
¤
AE
AS
¤
MaxDuration
, where
AS
and
AE
correspond to the start and end event of the activity. Consequently, this semantics
is equivalent to the respective variant of pattern semantics 4. Other kinds of
durations (i.e., activity set, process, set of process instances) are not discussed.
Again, it is possible to translate the duration of a process to the STP yielding
the same semantics as Pattern Semantics 4 (cf. Sec. 5.1).
According to [
25
, p. 9] an “absolute constraint represents a time interval
during which an activity can be performed”, i.e., it represents a
fixed date
element
for the earliest start and latest completion of the activity (TP4, design
choices C[a], F[a,d]). When creating a process instance, this fixed date element is
converted “into bounds that are dependent from the staring instant [(i.e., event)]
of the [process] instance” [
25
, p. 13]. This is achieved by subtracting the starting
time of the process from the interval bounds and by adding a pair of arcs to
the STP: one between the start event of the process and the start event of the
activity, the other one between the start event of the process and the end event
of the activity. Both arcs have the same converted interval as temporal constraint
[
25
, p. 13]. Thus, an absolute constraint
r
tstart, tcompletion
s
is transformed to
the following two constraints:
tstart
XS
¤
XAS
XS
¤
tcompletion
XS
and
tstart
XS
¤
XAE
XS
¤
tcompletion
XS
, where
XS
is the variable representing
the start event of the process instance and
XAS
, and
XAE
correspond to the
variables representing the start/end event of the activity. Since we know that
XAS
XAE
holds this inequations can be rewritten to
tstart
¤
XAS
XAE
¤
tcompletion
. The latter is equivalent with the combination of the semantics of a
Formal Semantics of Time Patterns 37
fixed date element for the earliest start and a fixed date element for the latest
completion of the activity as defined by Pattern Semantics 5 for the respective
pattern variant. Thus, this semantics of an absolute constraint corresponds to the
one of a restricted variant of pattern fixed date element (cf. Pattern Semantics 5).
“A periodic constraint represents a periodic time interval during which an
activity can be started” [
5
, p. 7]. This is similar to a
schedule restricted
element
for the earliest and latest start of an activity (TP5, design choices
C[a], F[a,b]). However, no implementation details are provided by [
5
]. We are
unaware of any straightforward approach to implement such a constraint based
on STPs. Therefore, it is not possible to compare the semantics of the respective
implementation to our formal semantics.
Likewise periodic activities, which are similar to the
periodicity
pattern
(TP10), are mentioned by [
5
]. However, no details on the implementation are
provided. Again, we are not aware of any straightforward way to implement this
pattern using STP. Therefore, the semantics cannot be compared.
Time lags between events
(TP3) are not considered, but again may be
translated to the STP the same way as TP1. Again the resulting semantics
corresponds to the one of Pattern Semantics 2. As discussed, a
validity period
for an activity (TP7, design choice C[a]) may be implemented based on a fixed
date element. Therefore, the same statements as for fixed date elements apply.
Consequently, the semantics would be the same as defined by Pattern Semantics 6.
5.3 Eder et al.
The approach suggested by Eder et al. [
7
,
52
] uses a timed workflow graph,
which constitutes an extension of the Critical Path Method (CPM) [
55
]—a well
known project planning method—as basic formalism. In turn, CPM uses activity-
on-node diagrams to represent and plan projects (cf. Fig. 17). Essentially, a
timed workflow graph is the same as the workflow graph. Each activity of the
process has a fixed duration and is augmented by two values for its earliest
and latest completion time. In particular, activity durations are considered to
be deterministic, i.e., activities are assumed to have the same duration for all
process instances. Consequently, the time of the activity start event can be
calculated based on the one of activity end event (and vice versa). Hence, the
approach only considers activity end events. To handle XOR-splits and -joins, the
timed workflow graph is extended in [
52
] by splitting up the earliest and latest
completion time into the earliest/latest completion of the best/worst case (cf.
Fig. 17). These four values are calculated for each activity by using a modified
version of the CPM algorithm. Finally, loops and the dynamic setting of the
parameter value of a pattern occurrences during run-time is not considered by
this approach.
Regarding time patterns, this approach considers patterns Time Lags between
two Activities (TP1) (called “upper and lower bound constraints”), fixed Durations
of activities (TP2, design choice C[a]), Fixed Date Elements (called “deadlines”)
for the latest completion of activities and processes (TP4, design choices C[a,c] and
38 Andreas Lanz, Manfred Reichert, and Barbara Weber
duration
Activity Name
Earliest
Completion Time
Best Case
Earliest
Completion Time
Worst Case
Latest
Completion Time
Best Case
Latest
Completion Time
Worst Case
A1
7
7
7
7
7
A3
5
22
22
22
22 A6
9
31
33
37
37
A7
8
39
42
60
60
A4
17
24
24
24
24 upper bound constraint ubc(A1, A6, 35 -7+9)
lower bound constraint lbc(A1, A3, 10 +5)
lower bound constraint
maximum process duration
upper bound constraint
Fig. 17. Timed Workflow Graph (of the process depicted in Fig. 15)
F[d]), and Schedule Restricted Elements for the earliest completion of activities
(TP5, design choices C[a] and F[c]) (called “fixed-date constraints”).
A lower bound constraint, i.e., a minimum
time lag between two activities
(TP1, design choices D[a] and E[d]) is defined as follows: “The duration between
[activity end] events
A
and
B
must be greater than or equal to
δ
” [
7
, p. 3].
Taking our notation this results in formula
ψt
BE
ϕt
AE
¥
δ
with
ϕt
AE
and
ψt
BE
being the time of occurrence of events
A
and
B
respectively. Further,
δ
min
p
distance
p
, eAE, eBE,
qq
corresponds to the minimum time distance
between the two events, which is independent of the particular trace
τ
and the
particular time point. In turn, an upper bound constraint, i.e., a maximum
time lag between two activities (TP1, design choices D[b] and E[d]) is defined
as follows: “The time distance between [activity end] events
A
and
B
must be
smaller than or equal to
δ
”[
7
, p. 3]. Again, in our notation this results in formula
ψt
BE
ϕt
AE
¤
δ
max
p
distance
p
, eAE, eBE,
qq
. Accordingly, this semantics of a
time lag between activities corresponds to the one of the respective variant of
Pattern Semantics 1. Since durations of activities are assumed to be the same
for all process instances (i.e., deterministic), start-start, start-end, and end-start
time lags may be also defined by adding the duration value of activity
A
or
B
or both to the respective lower or upper bound constraint. Again, under the
given assumptions this results in a similar semantics as defined by Patterns
Semantics 1.
Eder et al. “assume that activity durations are deterministic” [
7
, p. 2], i.e., the
duration
of an activity (TP2, design choices C[a]) is assumed to be the same for
all process instances. This results in formula
ϕt
AS
dA
ψt
AE
, where
ϕt
AS
and
ψt
AE
correspond to the time of occurrence of the start/end event of activity
A
, and
dA
to the duration of
A
. In turn, this can be interpreted as an interval duration
of an activity–according to pattern semantics 4–with
min
p
duration
p
, A,
qq
dA
max
p
duration
p
, A,
qq
. Accordingly, this semantics may be considered a
restricted variant of Pattern Semantics 4.
Formal Semantics of Time Patterns 39
Fixed date elements
for the latest completion date of activities (TP4,
design choice C[a] and F[d]) (called “deadlines”) are realized by ensuring that
the latest completion time of the respective activity is before or equal to the
corresponding deadline [
7
]. This results in condition
ϕt
AE
¤
deadline
for the
time of occurrence
ϕt
AE
of the end event of the activity. In turn, this yields same
semantics as Patterns Semantics 5 for this pattern variant. Again, since activity
durations are assumed to be deterministic, a fixed date for the latest start of an
activity can be specified by adding the duration of the activity to the respective
fixed date. This value is then used as deadline for the latest completion of the
activity. Again, this results in a restricted, but similar semantics as defined by
Pattern Semantics 5.
Schedule restricted elements
for the completion of activities (TP5, design
choice C[a] and F[c,d]) are implemented using a so-called “fixed-date object”.
The latter represents “an abstraction that generalizes a typically infinite set of
dates (i.e. ’every other Monday’ [...])” [
52
, p. 7]. A fixed-date object is similar
to a schedule as set out by Definition 11. Further, it has two basic methods
T.next
p
D
q
and
T.prev
p
D
q
which return the next and previous valid date of an
arbitrary date
D
according to the fixed-date object, i.e., the start/end of the
next/previous time slot. During run-time, a schedule restricted element is then
implemented by setting the earliest completion time of the activity to the next
date valid according to the fixed-date object. Likewise, the latest completion date
is set to the previous valid date. This is similar to Patterns Semantics 8, but not
completely equal as gaps between different valid dates (i.e., between the first and
last valid time slot) are not fully considered. Therefore, our semantics is more
complete and accurate.
As discussed, the
validity period
of an activity (TP7, design choice C[a]) can
be implemented based on a fixed date element. Therefore, the same statements
as for fixed date elements apply. Consequently, the semantics would be the same
as defined by Pattern Semantics 6.
5.4 Zhuge et al.
Zhuge et al. [
54
,
53
] do not use any specific formalism. Instead, temporal con-
straints are defined in terms of restrictions for start and completion times of
activities. In turn, this is similar to the way our semantics is defined. Moreover,
different time zones are considered when defining temporal constraints. However,
actually, this is not necessary: on one hand, temporal constraints are gener-
ally specified with respect to a reference time zone, on the other the temporal
constraints can be converted from one time zone to another (as implicitly demon-
strated by [
53
]). Finally, neither loops nor dynamic changes of the parameter
value of a pattern occurrences during run-time are considered.
Regarding the time patterns, Zhuge et al. consider patterns Time Lags between
two activities (TP1), Durations of activities and processes (TP2, design choice
C[a, c]), and Fixed Date Elements for activities (TP4, design choice C[a]) (called
“fixed-point constraints”).
40 Andreas Lanz, Manfred Reichert, and Barbara Weber
Two different ways of specifying a
time lag between two activities
(TP1)
are discussed: flow duration and duration constraint on the time between activities.
Aflow duration specifies the minimum and maximum time for passing control
from activity
Ai
to
Aj
. However, it is unclear whether activities
Ai
and
Aj
must directly succeed each other. A flow duration is similar to an end-start time
lag (TP1, design choice D[c] and E[c]), yet not completely equal. Note that in
general, it cannot be ensured that the second activity is started immediately
after receiving control. Nevertheless, its semantics is defined similarly to the
interval variant of Pattern Semantics 1, i.e., a flow duration between activities
Ai
and
Aj
is defined as [
53
, p. 233]:
d
p
Fij
q ¤
S
p
Aj
q
E
p
Ai
q ¤
D
p
Fij
q
where
E
p
Ai
q
is the time of the end event of activity Ai,S
p
Aj
q
is the time of the start
event of activity
Aj
, and
d
p
Fij
q
and
D
p
Fij
q
are the minimum and maximum flow
duration, respectively. In turn, a duration constraint restricts the maximum time
between the start event of activity
Ai
and the end event of activity
Aj
. Therefore,
it is similar to a start-end maximum time lag between the two activities (TP1,
design choice D[b] and E[b]). It is defined by formula
E
p
Aj
q
S
p
Ai
q ¤
pj
, where
S
p
Ai
q
corresponds to the start of activity
Ai
, and
E
p
Aj
q
to the end of activity
Aj
. Further,
pj
p
max
p
distance
p
, eAiS, eAjE,
qqq
corresponds to the respective
duration constraint. In turn, this is similar to a maximum start-end time lag
according to Pattern Semantics 1. Consequently, the semantics of time lags
between two activities considered by [
53
] is equal to the respective variant of our
pattern semantics.
The
duration
of an activity
A
(TP2, design choice C[a]) is specified by a
minimum value
d
p
A
q
and a maximum value
D
p
A
q
. Furthermore, durations are
defined by formula
d
p
A
q ¤
E
p
A
q
S
p
A
q ¤
D
p
A
q
, with
S
p
A
q
/
E
p
A
q
being the
time of the start/end event of activity
A
. Consequently, this semantics corresponds
to the respective variant of Pattern Semantics 4. Moreover, a minimum process
duration is defined as
d
¤
d
p
WfS
q
and a maximum one as
D
p
WfL
q ¤
D
(TP2,
design choice C[c]). Thereby,
d
(
D
) corresponds to the minimum (maximum)
process duration. In turn,
d
p
WfS
q
is the minimally possible duration of the
shortest process instance
WfS
. Likewise,
D
p
WfL
q
is the maximally possible
duration of the longest possible process instance
WfL
. Hence, this semantics
does not match the one of time pattern TP2 (cf. Pattern Semantics 4). However,
the semantics defined by Zhuge et al. does not meet the intended semantics of a
process duration. In particular, it factors the actual duration of a process instance
out, but only considers the duration of the overall best/worst case, i.e., it only
considers process instances where all activities require their minimum/maximum
duration. Yet, this (almost) never happens. Consequently, the semantics defined
by Zhuge et al. is too strict. Hence, we are convinced that Patterns Semantics 4
meets the intended semantics of this pattern variant.
A
fixed date element
(TP4) for the latest start of activity
Ai
is defined by
formula
S
p
Ai
q ¤
pi
, with
S
p
Ai
q
being the time of the start event of activity
Ai
and
pi
being the respective date. Other variants of pattern fixed date elements
(i.e., earliest start, or earliest latest completion) are defined analogously. Therefore,
Formal Semantics of Time Patterns 41
this semantics is a limited variant of Pattern Semantics 5 as it does not consider
changing the date value during run-time.
Again, a
validity period
for an activity (TP7, design choice C[a]) may be
implemented based on a fixed date element. Therefore, same statements as for
fixed date elements hold. Consequently, the semantics would be the same as
defined by Pattern Semantics 6.
5.5 Summary
Our validation has proven that in most cases our pattern semantics covers the
semantics of the evaluated approaches. It has further shown that the pattern
semantics we defined is the most general as it covers all special cases considered
by other approaches. In cases our pattern semantics differs from the one of the
described approaches, we could show, that ours is more precise, meeting the
intended semantics of the respective time pattern best. Finally, the introduced
pattern semantics is the only one addressing the impact of dynamic changes of
the parameter values of a pattern occurrence during run-time, which is important
when considering run-time support.
6 Discussion
Defining a formal semantics of time patterns provides significant benefits.
First, it gives the opportunity to uncover crucial aspects that might have
been neglected when only having an informal description.
Example 12 (Time Lags between Activities & Loops).
As discussed in
Sec. 4.2, any semantics of the time patterns needs to be valid in connection
with loops as well. Especially, this applies to time pattern TP1 (Time Lags
between Activities). When formalizing this time pattern we discovered that the
semantics of a time lag between two activities (TP1) of which one resides inside
a loop and the other one outside that loop is unclear. Actually, there exist three
different semantics (cf. Sec. 4.2). Regarding our definition of the semantics for
this time pattern, we decided to use the one most obvious to process experts and
not introducing any other ambiguity (cf. Sec. 4.2).
Example 13 (Time-based Restrictions & Comparison of intervals).
When
specifying the formal semantics of the time-based restrictions pattern (TP6), we
had to define how many executions of an activity exist within a given time frame.
Therefore, it became necessary to compare two different time intervals (i.e., the
execution interval of the activity and the given time frame). However, there exist
different ways to accomplish this task (e.g., subset, intersection), which is not
considered by the original design choices of this time pattern. To correctly define
the semantics of TP6 we added Design Choice U (cf. Fig. 12).
If such issues are not made explicit and resolved through the definition of a precise,
formal semantics, interpretations by users (e.g., system or process engineers)
42 Andreas Lanz, Manfred Reichert, and Barbara Weber
might be different resulting in misunderstandings, ambiguities, and erroneous
process implementations. However, we do not claim to provide the right semantics
for all cases. As some time patterns carry an inherent ambiguity under certain
circumstances, decisions had to be made regarding the definition of the formal
semantics, which may not suit all possible scenarios (cf. Example 12). In any
case, we have exposed these decisions. Additionally, due to the validation process
taken, we are convinced that our semantics is the one expected by most process
engineers and domain experts.
Second, the formal semantics enables us to precisely answer open questions
regarding the interpretation of certain constellations of process elements. For
example, if the parameter value of a time pattern may be modified during run-
time, it might be unclear which of these values must be considered for a particular
pattern instance (especially so in connection with concurrency and loops). By
utilizing the defined pattern semantics, such questions can now be precisely
answered.
Third, it becomes possible to compare and evaluate process modeling lan-
guages and PAIS according to formally defined criteria. This is additionally
fostered by the fact that the provided formal semantics is independent of any
particular process modeling language or paradigm. Therefore, it becomes possible
to compare different systems and languages with respect to their support of the
temporal perspective, e.g., to identify the one most suitable in a given application
context. Furthermore, any formal semantics provides a foundation for reasoning
about modeling language specifications and for deriving consequences from them.
In turn, the latter is an important aid in validating and evaluating proposed
implementations. Formal semantics also provides a view of modeling languages
that abstract from unimportant details of syntax and presentation. In particular,
this view makes it possible to compare languages, and to identify additionally
required language elements.
Furthermore, having a precise and formal semantics allows implementing
techniques for checking conformance of process instances in respect to a process
schema and its time constructs, i.e., answering the question “Do the log of the
process instance and the model conform to each other?” [
23
]. Again, this is
fostered by the fact that the formal pattern semantics we provide is defined based
on temporal execution traces, which are closely related to process instance logs.
Hence, it is possible to implement conformance checking algorithms based on the
defined formal semantics of the time patterns.
Similarly, a precise, formal semantics of time patterns is a key requirement for
the formal verification of the temporal perspective of processes during build-time
as well as for its verification and monitoring during run-time. In particular, a
formal semantics allows us to address some open issues that need to be solved
before developing comprehensive verification procedures (cf. Example 12). This is
especially true for more complex time patterns as well as for the link between time
patterns and loops. Up to now, these issues have been avoided by excluding both
complex time patterns and loops from respective considerations. However, without
these constructs no complete specification of the temporal perspective is possible.
Formal Semantics of Time Patterns 43
In turn, without a formal basis no universally valid verification of the temporal
perspective is possible due to ambiguities and unclear semantics. Consequently,
existing approaches may benefit from the formal semantics presented in this
paper.
What has not been discussed in this paper is the run-time support of the
temporal perspective. When executing process instances containing temporal
constraints, challenging issues emerge, e.g., “How can temporal constraints be
enforced?” or “What happens in case a temporal constraint is in danger of being
violated or has already been violated?”. Further, during run-time, one must
differentiate between temporal constraints to be met in any case (e.g., delivery
deadlines) and the ones that merely represent a recommendation and hence may
be ignored if desired (e.g., most duration constraints). Such issues are out of
scope of this paper. Yet, we are convinced that the presented formal semantics
of the time patterns serves as a good basis for investigating these issues. To the
best of our knowledge, it is the first attempt to precisely and formally define the
semantics of the time patterns.
7 Related Work
Time patterns have been (informally) introduced in [
18
,
19
] and evaluated in
[
19
] (cf. Sec. 2.2 and 3.1). Barba et al. [
56
] applies them in the context of
scheduling support for declarative workflows. However, no formal semantics has
been provided so far, even though this is crucial for implementing and comparing
time-aware PAISs. This paper closes this gap.
The general idea of using patterns to compare PAISs has been proposed by the
workflow patterns project [
10
]. Based on respective patterns, the expressiveness
of different process meta models and process modeling tools can be compared.
Further patterns were introduced including data flow patterns [
11
], resource
patterns [
12
], exception handling patterns [
15
], activity patterns [
14
], user interface
transformation patterns [
57
,
58
], and process change patterns [
16
,
13
,
17
]. Most
of them come along with a formal semantics, for example, based on languages
such as petri nets [10] or pi-calculus [42].
Existing approaches dealing with the temporal perspective in PAISs largely
focus on specific time features like the verification of temporal constraints [5, 6,
7
,
24
,
25
,
53
] (cf. Sec. 5), escalation management [
59
], and scheduling support
[
56
,
60
,
61
]. [
62
] investigates the mutual dependencies between different temporal
constraints and derives inference rules for their verification and monitoring.
Additionally, time support features like process monitoring [
63
], process mining
[
64
], and the effect of ad-hoc changes on temporal constraints [
65
] have been
studied. A systematic elaboration of the requirements for time support as well as
respective formal semantics has been missing so far.
A topic not considered in this paper concerns time granularities and their
application in the context of the time patterns. Reasoning about relative temporal
constraints and time granularities has been extensively discussed in literature
[
66
,
67
,
68
,
69
]. Especially, it becomes relevant when verifying the consistency
44 Andreas Lanz, Manfred Reichert, and Barbara Weber
and satisfiability of the temporal constraints of a process schema at build-time.
It can be shown that it is an NP-hard problem to decide whether an arbitrary
set of temporal constraints with granularities is consistent [
67
]. For defining
the time pattern semantics, however, this poses no problem. Since respective
pattern semantics is defined based on temporal execution traces, the absolute
time points of all events are known. Thus, only these absolute time points have
to be compared with the respective relative time distance. In particular, no
comparison between different relative time distances is required. For this reason,
time granularities were not considered in this paper.
8 Summary and Outlook
We have specified the formal semantics of the time patterns introduced in [
18
,
19
].
Their initial introduction complemented existing workflow patterns. In particular,
time patterns allow for a more meaningful evaluation of existing PAISs in case
temporal constraints are crucial. In combination with workflow patterns, time
patterns enable PAIS engineers to choose the PAIS-enabling technology meeting
their requirements best. The formal semantics presented in this paper provides the
basis for implementing the patterns in PAISs as well as for comparing PAISs with
respect to their support of the temporal perspective. For each pattern, its formal
semantics has been specified based on traces in a language-independent manner.
Our future work will include time patterns for aspects other than control flow (e.g.,
data or process changes). Furthermore, we will conduct a comprehensive study
on time support features, e.g., enabling the verification of temporal constraints,
escalation management, and advanced scheduling support. We will consider the
resource dimension in this context as well. Finally, we will evaluate the impact
process changes have on the time patterns and respective temporal specifications
of business processes.
References
1.
Reichert, M., Weber, B.: Enabling Flexibility in Process-aware Information Systems:
Challenges, Methods, Technologies. Springer Berlin / Heidelberg (2012)
2.
Weber, B., Reichert, M., Wild, W., Rinderle-Ma, S.: Providing integrated life cycle
support in process-aware information systems. International Journal of Cooperative
Information Systems 18(1) (March 2009) 115–165
3.
Lenz, R., Reichert, M.: It support for healthcare processes - premises, challenges,
perspectives. Data & Knowledge Engineering 61(1) (April 2007) 39–58
4.
Müller, D., Herbst, J., Hammori, M., Reichert, M.: IT support for release manage-
ment processes in the automotive industry. In Dustdar, S., Fiadeiro, J.L., Sheth,
A., eds.: Proceedings of the 4th International Conference on Business Process Man-
agement (BPM’06). Volume 4102 of Lecture Notes in Computer Science., Vienna,
Austria, Springer Berlin / Heidelberg (September 2006) 368–377
5.
Combi, C., Gozzi, M., Juarez, J.M., Oliboni, B., Pozzi, G.: Conceptual modeling
of temporal clinical workflows. In Goranko, V., Wang, X.S., eds.: Proceedings of
Formal Semantics of Time Patterns 45
the 14th International Symposium on Temporal Representation and Reasoning
(TIME’07), Alicante, Spain, IEEE Computer Society Press (June 2007) 70–81
6.
Marjanovic, O., Orlowska, M.E.: On modeling and verification of temporal con-
straints in production workflows. Knowledge and Information Systems
1
(2) (1999)
157–192
7.
Eder, J., Panagos, E., Rabinovich, M.: Time constraints in workflow systems. In
Jarke, M., Oberweis, A., eds.: Proceedings of the 11th International Conference on
Advanced Information Systems Engineering (CAiSE’99). Volume 1626 of Lecture
Notes in Computer Science., Heidelberg, Germany, Springer Berlin / Heidelberg
(June 1999) 286–300
8.
Dadam, P., Reichert, M., Kuhn, K.: Clinical workflows - the killer application
for process-oriented information systems. In: Proceedings of the 4th International
Conference on Business Information Systems (BIS’00). (2000) 36–59
9.
Mutschler, B., Weber, B., Reichert, M.: Workflow management versus case handling:
results from a controlled software experiment. In: Proceedings of the 2008 ACM
symposium on Applied computing (SAC’08), New York, NY, USA, ACM Press
(2008) 82–89
10.
van der Aalst, W.M.P., ter Hofstede, A.H.M., Kiepuszewski, B., Barros, A.P.:
Workflow patterns. Distributed and Parallel Databases 14(1) (2003) 5–51
11.
Russell, N.C., ter Hofstede, A.H.M., Edmond, D., van der Aalst, W.M.P.: Workflow
data patterns: Identification, representation and tool support. In Delcambre, L.,
Kop, C., Mayr, H.C., Mylopoulos, J., Pastor, O., eds.: Proceedings of the 24th
International Conference on Conceptual Modeling (ER’05). Volume 3716 of Lecture
Notes in Computer Science., Springer Berlin / Heidelberg (2005) 353–368
12.
Russell, N., van der Aalst, W.M.P., ter Hofstede, A.H.M., Edmond, D.: Workflow
resource patterns: Identification, representation and tool support. In Pastor, O.,
e Cunha, J.F., eds.: Proceedings of the 17th International Conference on Advanced
Information Systems Engineering (CAiSE’05). Volume 3520 of Lecture Notes in
Computer Science., Springer Berlin / Heidelberg (2005) 216–232
13.
Weber, B., Reichert, M., Rinderle-Ma, S.: Change patterns and change support
features - enhancing flexibility in process-aware information systems. Data &
Knowledge Engineering 66(3) (2008) 438–466
14.
Thom, L., Reichert, M., Iochpe, C.: Activity patterns in process-aware information
systems: Basic concepts and empirical evidence. International Journal of Business
Process Integration and Management 4(2) (2009) 93–110
15.
Russell, N., van der Aalst, W.M.P., ter Hofstede, A.H.M.: Exception handling
patterns in process-aware information systems. Technical report, BPMCenter.org
(2006)
16.
Weber, B., Rinderle, S., Reichert, M.: Change patterns and change support features
in process-aware information systems. In Krogstie, J., Opdahl, A.L., Guttorm, S.,
eds.: Proceedings of the 19th International Conference on Advanced Information
Systems Engineering (CAiSE’07). Volume 4495 of Lecture Notes in Computer
Science., Springer Berlin / Heidelberg (June 2007) 574–588
17.
Rinderle-Ma, S., Reichert, M., Weber, B.: On the formal semantics of change
patterns in process-aware information systems. In Li, Q., Spaccapietra, S., Yu, E.,
Olivé, A., eds.: Proceedings of the 27th International Conference on Conceptual
Modeling (ER’08). Volume 5231 of Lecture Notes in Computer Science., Springer
Berlin / Heidelberg (2008) 279–293
18.
Lanz, A., Weber, B., Reichert, M.: Workflow time patterns for process-aware
information systems. In Bider, I., Halpin, T., Krogstie, J., Nurcan, S., Proper,
46 Andreas Lanz, Manfred Reichert, and Barbara Weber
E., Schmidt, R., Ukor, R., eds.: Proceedings of the 11th International Workshop,
BPMDS 2010, and 15th International Conference, EMMSAD 2010. Volume 50 of
Lecture Notes in Business Information Processing., Hammamet, Tunesia, Springer
Berlin / Heidelberg (June 2010) 94–107
19.
Lanz, A., Weber, B., Reichert, M.: Time patterns for process-aware information
systems. Requirements Engineering (2012) (online first).
20.
www.timepatterns.org: Time patterns for process-aware information systems (Last
access 20.12.2012).
21.
Russell, N., ter Hofstede, A.H.M., van der Aalst, W.M.P., Mulyar, N.: Workflow
control-flow patterns: A revised view. Technical Report BPM-06-22, BPMCenter.org
(2006)
22.
van Glabbeek, R., Goltz, U.: Refinement of actions and equivalence notions for
concurrent systems. Acta Informatica 37 (2001) 229–327
23.
Rozinat, A., van der Aalst, W.M.P.: Conformance checking of processes based on
monitoring real behavior. Information Systems 33(1) (2008) 64–95
24.
Bettini, C., Wang, X.S., Jajodia, S.: Temporal reasoning in workflow systems.
Distributed and Parallel Databases 11(3) (2002) 269–306
25.
Combi, C., Gozzi, M., Posenato, R., Pozzi, G.: Conceptual modeling of flexible
temporal workflows. ACM Transactions on Autonomous and Adaptive Systems
7(2) (July 2012) 19:1–19:29
26.
Reichert, M., Dadam, P.: Towards process-oriented hospital information systems:
Some insights into requirements, technical challenges and possible solutions. In:
Proceedings of the 43. Jahrestagung der GMDS. (1998) 175–180
27.
Schultheiß, B., Meyer, J., Mangold, R., Zemmler, T., Reichert, M.: Prozessen-
twurf für den ablauf einer stationären chemotherapie. Technical Report DBIS-5,
Universität Ulm (1996) (in german).
28.
Schultheiß, B., Meyer, J., Mangold, R., Zemmler, T., Reichert, M.: Prozessentwurf
am beispiel eines ablaufs einer op. Technical report, Universität Ulm (1996) (in
german).
29.
Käfer, R.: Medical information processing in the hospital - current status, problems
and perspectives by the example of the medical university clinic ulm. Diploma
thesis, Heidelberg University (1993)
30.
Kuhn, K., Reichert, M., Käfer, R., Köhler, C.: Situations- und Schwachstellenanal-
yse der Informationsverarbeitung in einer Universitätsklinik. In: Proceedings 39.
Jahrestagung der GMDS. (1994)
31.
Li, C.: Mining Process Model Variants: Challenges, Techniques, Examples. Phd
thesis, University of Twente, The Netherlands (2010)
32.
Li, C., Reichert, M., Wombacher, A.: The MinAdept clustering approach for
discovering reference process models out of process variants. International Journal
of Cooperative Information Systems 19(3 & 4) (2010) 159–203
33.
Li, C., Reichert, M., Wombacher, A.: Mining business process variants: Challenges,
scenarios, algorithms. Data & Knowledge Engineering 70(5) (May 2011) 409–434
34.
Bobrik, R.: Konfigurierbare Visualisierung komplexer Prozessmodelle. PhD thesis,
University of Ulm (2008)
35.
German Association of the Automotive Industry (VDA): Engineering change
management. part 1: Engineering change request (ECR) (2005)
36.
Federal Aviation Administration: Aviation maintenance technician handbook, chap-
ter 8. inspection fundamental.
http://www.faa.gov/library/manuals/aircraft/
amt\_handbook/media/FAA-8083-30\_Ch08.pdf (2008) (accessed 29.04.2011).
Formal Semantics of Time Patterns 47
37.
IACA (International Air Carrier Association): Subpart Q - flight and duty time
limitations and rest requirements.
http://www.iaca.be/iaca/library/q15922\
_3.pdf (2004) (accessed 29.04.2011).
38.
Stoicsics, M.: Evaluation des Konzeptes eines Catering-, Steuerungs- und Con-
trollingsystems am Vergleichsbeispiel des Endmontageprozesses der Fertigung
von hochisolierenden Lager- und Transportbehältern für das Luftfahrt-Catering.
Diploma thesis, University of Ulm (November 2011)
39.
Steinle, M.: Use of workflow engines for efficient adaptation of standardized
industry software to different customer requirements (in german). Masters thesis,
Ulm University (2005)
40.
Grambow, G., Oberhauser, R., Reichert, M.: Event-driven exception handling
for software engineering processes. In Daniel, F., Barkaoui, K., Dustdar, S., eds.:
Proceedings of the 5th International Workshop on event-driven Business Process
Management (edBPM’11). Volume 99 of Lecture Notes in Business Information
Processing., Clermont-Ferrand, France, Springer Berlin / Heidelberg (August 2012)
414–426
41.
Hallerbach, A.: Management von Prozessvarianten. Phd thesis, University of Ulm
(2010)
42.
Puhlmann, F., Weske, M.: Using the pi-calculus for formalizing workflow patterns.
In van der Aalst, W.M.P., Benatallah, B., Casati, F., Curbera, F., eds.: Proceedings
of the 3rd International Conference on Business Process Management (BPM’05).
Volume 3649 of Lecture Notes in Computer Science., Nancy, France, Springer Berlin
/ Heidelberg (September 2005) 153–168
43.
Huth, M., Ryan, M.: Logic in Computer Science - modelling and reasoning about
systems. Cambridge University Press (2004)
44.
Cerone, A., Maggiolo-Schettini, A.: Time-based expressivity of time petri nets for
system specification. Theoretical Computer Science 216(1-2) (1999) 1 – 53
45.
Alur, R., Dill, D.: A theory of timed automata. Theoretical Computer Science
126(2) (1994) 183 – 235
46.
Dechter, R., Meiri, I., Pearl, J.: Temporal constraint networks. Artificial Intelligence
49 (1991) 61–95
47.
Lockyer, K.G., Gordon, J.: Project Management and Project Network Techniques.
Prentice Hall (2005)
48.
Vanhatalo, J., Völzer, H., Leymann, F.: Faster and more focused control-flow
analysis for business process models through sese decomposition. In Krämer, B.,
Lin, K.J., Narasimhan, P., eds.: Proceedings of the 5th International Conference
on Service-Oriented Computing (ICSOC’07). Volume 4749 of Lecture Notes in
Computer Science., Springer Berlin / Heidelberg (2007) 43–55
49.
Terenziani, P.: Integrating calendar dates and qualitative temporal constraints
in the treatment of periodic events. IEEE Transactions on Knowledge and Data
Engineering 9(5) (September 1997) 763–783
50.
Anselma, L.: Recursive representation of periodicity and temporal reasoning. In
Combi, C., Ligozat, G., eds.: Proceedings of the 11th International Symposium on
Temporal Representation and Reasoning (TIME’04), Tatihou, Normandie, France,
IEEE Computer Society Press (July 2004) 52–59
51.
Bettini, C., Wang, X.S., Jajodia, S.: Free schedules for free agents in workflow
systems. In: Proceedings of the 7th International Workshop on Temporal Represen-
tation and Reasoning (TIME’00). (2000)
52.
Eder, J., Panagos, E.: Managing time in workflow systems. In Fischer, L., ed.:
Workflow Handbook 2001. Future Strategies Inc. (2000) 109–132
48 Andreas Lanz, Manfred Reichert, and Barbara Weber
53.
Zhuge, H., Cheung, T.Y., Pung, H.K.: A timed workflow process model. Journal of
Systems and Software 55(3) (2001) 231–243
54.
Zhuge, H., Pung, H.K., Cheung, T.Y.: Timed workflow: Concept, model, and method.
In Zhou, X., Fong, J., Jia, X., Kambayashi, Y., Zhang, Y., eds.: Proceedings of the
1st International Conference on Web Information Systems Engineering. Volume 1.,
IEEE (2000) 183–189
55.
Philipose, S.: Operations Research - A Practical Approach. Tata McGraw-Hill
(1986)
56.
Barba, I., Lanz, A., Weber, B., Reichert, M., Valle, C.D.: Optimized time manage-
ment for declarative workflows. In Bider, I., Halpin, T., Krogstie, J., Nurcan, S.,
Proper, E., Schmidt, R., Soffer, P., Wrycza, S., eds.: Proceedings of the 13th Inter-
national Conference BPMDS 2012, 17th International Conference EMMSAD 2012,
and 5th EuroSymposium. Volume 113 of Lecture Notes in Business Information
Processing., Springer Berlin / Heidelberg (June 2012) 195–210
57.
Kolb, J., Hübner, P., Reichert, M.: Automatically generating and updating user
interface components in process-aware information systems. In: 20th International
Conference on Cooperative Information Systems. Number 7565 in Lecture Notes in
Computer Science, Springer (September 2012) 444–454
58.
Kolb, J., Hübner, P., Reichert, M.: Model-driven user interface generation and
adaptation in process-aware information systems. Technical Report UIB-2012-04,
University of Ulm, Ulm (July 2012)
59.
van der Aalst, W.M.P., Rosemann, M., Dumas, M.: Deadline-based escalation in
process-aware information systems. Decision Support Systems
43
(2) (2007) 492–511
60.
Combi, C., Pozzi, G.: Task scheduling for a temporal workflow management
system. In Pustajovsky, J., Revesz, P., eds.: Proceedings of the 13th International
Symposium on Temporal Representation and Reasoning (TIME’06), Budapest,
Hungary, IEEE Computer Society Press (June 2006) 61–68
61.
Eder, J., Pichler, H., Gruber, W., Ninaus, M.: Personal schedules for workflow sys-
tems. In van der Aalst, W.M.P., ter Hofstede, A.H.M., Weske, M., eds.: Proceedings
of the 1st International Conference on Business Process Management (BPM’03).
Volume 2678 of Lecture Notes in Computer Science., Eindhoven, The Netherlands,
Springer Berlin / Heidelberg (June 2003) 216–231
62.
Chen, J., Yang, Y.: Temporal dependency based checkpoint selection for dynamic
verification of temporal constraints in scientific workflow systems. ACM Transactions
on Software Engineering and Methodology 20(3) (2011) 9:1–9:23
63.
Sayal, M., Casati, F., Dayal, U., Shan, M.C.: Business process cockpit. In: Proceed-
ings of the 28th International Conference on Very Large Data Bases (VLDB’02),
VLDB Endowment (2002) 880–883
64.
van der Aalst, W.M.P., Pesic, M., Song, M.: Beyond process mining: From the past
to present and future. In Pernici, B., ed.: Proceedings of the 22nd International
Conference on Advanced Information Systems Engineering (CAiSE’10). Volume
6051 of Lecture Notes in Computer Science., Hammamet, Tunesia, Springer Berlin
/ Heidelberg (June 2010) 38–52
65.
Sadiq, S.W., Marjanovic, O., Orlowska, M.E.: Managing change and time in
dynamic workflow processes. International Journal of Cooperative Information
Systems 9(1-2) (2000) 93–116
66.
Bettini, C., Mascetti, S., Pupillo, V.: A system prototype for solving multi-
granularity temporal csp. In Faltings, B., Petcu, A., Fages, F., Rossi, F., eds.:
Recent Advances in Constraints. Volume 3419 of Lecture Notes in Computer Science.
Springer Berlin / Heidelberg (2005) 142–156
Formal Semantics of Time Patterns 49
67.
Bettini, C., Wang, X.S., Jajodia, S.: A general framework for time granularity
and its application to temporal reasoning. Annals of Mathematics and Artificial
Intelligence 22(1-2) (1998) 29–58
68.
Bettini, C., Wang, X.S., Jajodia, S.: Solving multi-granularity temporal constraint
networks. Artificial Intelligence 140(1-2) (2002) 107–152
69.
Combi, C., Franceschet, M., Peron, A.: Representing and reasoning about temporal
granularities. Journal of Logic and Computation 14(1) (2004) 51–77
