Adjustment Strategies for Non-Compliant Process Instances [original]

Ulmer Informatik Berichte | Universität Ulm | Fakultät für Ingenieurwissenschaften und Informatik

Adjustment Strategies for

Non-Compliant Process Instances

Stefanie Rinderle-Ma, Manfred Reichert

Ulmer Informatik-Berichte

Nr. 2009-06

März 2009

Adjustment Strategies for Non-Compliant

Process Instances

Stefanie Rinderle-Ma and Manfred Reichert

1Ulm University, Germany, {stefanie.rinderle, manfred.reichert}@uni-ulm.de

Abstract. Enabling changes at both process type and process instance

level is an essential requirement for any adaptive process-aware infor-

mation system (PAIS). Particularly, it should be possible to migrate a

(long-)running process instance to a new type schema version, even if

this instance has been individually modiﬁed before. Further instance mi-

gration must not violate soundness; i.e., structural and behavorial con-

sistency need to be preserved. Compliance has been introduced as basic

notion to ensure that instances, whose state has progressed too far, are

prohibited from being migrated. However, this also excludes them from

further process optimizations, which is not tolerable in many practical

settings. This paper introduces a number of strategies for coping with

non-compliant instances in the context of process change such that they

can beneﬁt from future process type changes on the one hand, but do

not run into soundness problems on the other hand. We show, for ex-

ample, how to automatically adjust process type changes at instance

level to enable the migration of a higher number of instances. The dif-

ferent strategies are compared and discussed along existing approaches.

Altogether, adequate treatment of non-compliant process instances con-

tributes to full process lifecycle support in adaptive PAIS.

1 Introduction

The ability to eﬀectively deal with change has been identiﬁed as key functional-

ity for any process-aware information systems (PAIS). Through the separation

of process logic from application code, PAIS facilitate process changes signif-

icantly. In the context of long-running processes (e.g., medical treatment [1]),

PAIS must additionally allow for the propagation of respective changes to ongo-

ing process instances. Regarding the support of such dynamic process changes,

PAIS robustness is fundamental; i.e., dynamic changes must not violate sound-

ness of the running process instances. In response to these challenges adaptive

PAIS have emerged, which allow for dynamic process changes at diﬀerent levels

[2–6]. Most approaches apply a speciﬁc correctness notion to ensure that only

those process instances may migrate to a modiﬁed process schema for which

soundness can be ensured afterwards. One of the most prominent criteria used

in this context is compliance [2, 7]. According to it, an instance may migrate to

schema Sif it is compliant with S; i.e., current instance trace can be produced

on Sas well. Based on compliance it is ensured that instances, whose state has

progressed too far, are prohibited from being migrated.

Consider Fig. 1: Based on process schema Sprocess instances I1, ..., Inare

running. Then Sis transformed into new schema version Sby applying process

change ΔS. Assume that it can be decided that I1, ..., Ikmay migrate to Swith-

out violating soundness (i.e., they are compliant with S), whereas Ik+1, ..., In

have already progressed too far (i.e., they are not compliant with S).1As sug-

gested by most approaches Ik+1, ..., Inthen remain running on S.Assumethat

a further optimization of the new schema version Stakes place captured by

process change ΔSresulting in new type schema version S.ThenI1, ..., Ik

may also beneﬁt from ΔSif they are compliant with S.However,Ik+1, ..., In

are excluded from migration to S anyway since they are not running on S.This

is not tolerable in many practical settings. Think, for example, of a patient who

is excluded from a new optimized examination because his particular treatment

instance cannot be migrated to the changed process type schema. In these cases,

it is crucial to ﬁnd strategies to treat non-compliant instances such that they

can beneﬁt from further process optimizations as well (cf. Fig. 1).

SS‘S‘‘

ΔSΔS‘ ΔS‘‘

I1, …, IkI1, …, Ik-j I1, …, Ik-j-i

Ik+1, …, InIk-j+1, …, IkIk-j-i+1, …, Ik-j

migrate

compliant

non-compliant

migrate

adjustment Æmigrate adjustment Æmigrate

Fig. 1. Migrating Compliant Instances and Treating Non-compliant Ones

In this paper, we introduce a number of strategies for coping with non-

compliant instances in the context of process change such that they can beneﬁt

from future process changes on the one hand, but do not run into soundness

problems on the other hand. We show, for example, how to automatically ad-

just process type changes at instance level to enable the migration of a higher

number of instances. In particular, we do not only consider process instances

which are still running according to the process type schema version they were

startedon(denotedasunbiased process instances), but we elaborate adjustment

strategies in the context of biased process instances as well; i.e., instances which

have been already individually modiﬁed and thus their instance-speciﬁc schema

deviates from the original process type schema version. The diﬀerent strategies

are compared and discussed along existing approaches. Altogether the adequate

treatment of non-compliant process instances contributes to full lifecycle support

1We assume that instances are clustered along their state.

of business processes in adaptive PAIS. Section 2 introduces background infor-

mation. Section 3 presents diﬀerent strategies for dealing with non-compliant

instances. In Section 4, we discuss metrics for measuring the distance between

process schemas which is needed for evaluating the diﬀerent strategies presented

in Section 3. Sections 5 and 6 show how non-compliant process instances can be

adjusted regardless whether they are unbiased or biased. Section 7 provides an

evaluation for applying the diﬀerent strategies. Section 8 discussed related work

and Section 9 closes with a summary and outlook.

2 Backgrounds

2.1 Basic Concepts

In this section we summarize basic concepts and notions used in this paper. For

each business process to be supported a process type T represented by a process

schema S has to be deﬁned. For a particular type several process schemas may

exist, representing the diﬀerent versions and evolution of this type over time. In

the following, a single process schema is represented as directed graph, which

comprises a set of nodes – representing activities or control connectors (e.g.,

XOR-Split, AND-Join) – and a set of control edges (i.e., precedence relations)

between them. In the following we assume block-structured process schemas

(like in BPEL). In order to relax strict block structure, we provide additional

sync links for setting up order relations between activities belonging to parallel

branches (similar to the link concept suggested in BPEL). In addition, a process

schema comprises sets of data elements and data edges. A data edge links an

activity with a data element and represents a read or write access of this activity

to the respective data element. Altogether, a process schema Sis represented

by a tuple S:= (N,CtrlE,SyncE,D,DataE,...)whereNdenotes the set of

activities, CtrlE the set of control egdes, SyncE the set of sync edges, Dthe set

of data elements, and DataE the set of data edges.

Based on process schema Sat run-time new process instances can be cre-

ated and executed. For an instance Irunning on S, start and/or completion

events of corresponding activities are recorded in execution trace σS

I. A compact

representation of trace σS

Iis given by instance marking NSIwhich assigns to

each activity of Iits current state. Possible activity states include NotActivated,

Activated, Running, Completed, and Skipped [7].

Adaptive process management systems are characterized by their ability to

correctly and eﬃciently deal with (dynamic) process changes [8]. Before dis-

cussing diﬀerent levels of change, we give a deﬁnition on the topology of change.

Deﬁnition 1 (Process Change). Let PS be the set of all process schemas and

let S, S∈PS. Let further Δ=<op1,...,op

n>denote a process change which applies

change operations opi(i=1,. . . ,n) sequentially. Then:

1. S[Δ> Sif and only if Δis correctly applicable to S and Sis the process schema

resulting from the application of Δto S (i.e., S≡S+Δ)

2. S[Δ>Sif and only if there are process schemas S1,S

2,...,S

n+1 ∈PSwith S =

S1, S=S

n+1 and for 1 ≤i≤n: Si[Δi>Si+1 with Δi=(opi)

In general, we assume that change Δis applied to a sound (i.e., correct)

process schema S [9]; i.e., S obeys the correctness constraints set out by the

particular process meta model (e.g., block structuring) . This property is also

denoted as structural soundness.Furthermore,weclaimthatSmust obey be-

havorial soundness (i.e., any instance on Smust not run into deadlocks or

livelocks). This can be achieved in two ways: either Δitself preserves soundness

by formal pre-/post-conditions (e.g., ADEPT [3]) or Δis applied and soundness

of Sis checked afterwards (e.g., by reachability analysis).

Basically, changes can be triggered and performed at the process type and

process instance level. ChangesofaprocesstypeTmay become necessary to

cover the evolution of the business processes captured in process schemas of this

type [5, 7, 6]. Generally, process engineers can accomplish process type changes

by applying a set of change operations to the current schema version S of type

T [10]. This results in new schema version Sof T. Execution of future process

instances is usually based on S. In addition, for long-running instances, it is

often desired to migrate them to the new schema Sin a controlled and eﬃcient

manner [7, 8]. By contrast, changes of individual process instances are usually

performed by end users and become necessary to react to exceptional situations

[3]. In particular, eﬀects of such changes must be kept local, i.e., they must

not aﬀect other instances of same type. Thus for each individually modiﬁed

instance Ian instance-speciﬁc schema SIis maintained. The diﬀerence between

SIand original schema Sis captured by the so called instance-speciﬁc bias of

I; i.e., ΔI(S). Speciﬁcally ΔI(S) captures all change operations applied to Sat

instance level in order to obtain instance-speciﬁc schema SI. Instances which

have not been individually modiﬁed are denoted as unbiased instances.

In the context of process type and process instance changes, structural and

behavorial soundness have to be preserved. In our ADEPT approach, structural

soundness is achieved based on well-deﬁned pre- and post-conditions for the

diﬀerent change operations [3]. Behavorial soundness, in turn, refers to correct

instance states [7]. If, for example, an activity is started before all its predecessor

activities are completed, this activity will not necessarily be supplied with all

required input data. Behavorial soundness is accomplished by behavorial correct-

ness criteria. In the context of change one prominent example is the compliance

criterion [2] which is used in the remainder of this paper (a detailed comparison

of compliance and other correctness criteria can be found in [8]). Informally,

compliance checks whether execution trace σS

Iof instance Ion schema Scould

also be produced by an instance on Sin the same order as set out by σS

2.2 Overall Change Framework

Assume that at process type level schema Sevolves to schema Sand that

we want to migrate instances on Sto Sif they are compliant. Out focus is

on how to deal with non-compliant instances in this context. Speciﬁcally, we

Change operation Δon S opType subject paramList inverseOp

insert(S, X, A, B)ainsert X S, A, B delete(S, X)

Eﬀects on S: inserts activity S between activities A and B.

delete(S, X) delete X S insert(S, X, pred(S,X), succ(S,X))b

Eﬀects on S: deletes activities from S

move (S, X, A, B) move X A, B move(S, X, pred(S,X), succ(S,X))

Eﬀects on S: moves activity S from its original position in S to another position betweena ctivity

sets A and B

aBasically, insertion between activities A and B can be generalized to insertion between activity sets

A,B. Additionally, for conditional insert an optional parameter [sc] can be included for representing

a conditional insert (details see [10]).

bpred(S,X) / succ(S,X) denotes the direct predecessor(s) / successor(s) of X in S.

Table 1. Selection of Change Operations on Process Schemas

want to ﬁnd strategies to cope with non-compliant instances (i.e., to migrate

them to Swithout violating soundness) regardless whether they are unbiased

or biased. Due to their instance-speciﬁc bias, the treatment of non-compliant

biased instances poses additional challenges when compared to the treatment of

unbiased ones. In order to tackle these challenges in a systematic way, we base

following considerations on the classiﬁcation for biased instances as proposed in

[11, 12]. This classiﬁcation uses the degree of overlap betweentypechangeand

instance-speciﬁc bias. Overlapping changes occur if at instance level some or all

of the subsequent type changes are anticipated. If ΔIcompletely anticipates ΔS

(i.e., SI=S), we denote the changes as equivalent. In this case Ican be always

migrated to Swithout any further check. Changes can also subsume each other.

ΔIsubsumes ΔS(denoted by ΔIΔS) if all change operations captured by ΔS

are contained within ΔI,butΔIalso captures additional change operations. In

this case, Iis compliant with Sas well. However, new bias Δ

I:= ΔI\ΔSfor Ion

Shastobecalculated.Inturn,ifΔSsubsumes ΔI(denoted by ΔSΔI)ithas

to be checked whether the changes of ΔSnot present for Iso far (i.e., ΔS\ΔI)

can correctly applied to I. Finally, ΔIand ΔSpartially overlap if they have

some change operations ”in common”, but each of them also captures additional

changes. In this case, it has to be checked whether the changes in ΔS\ΔIcan

be correctly applied to I,andnewbiasΔI\ΔShas to be calculated for Ion S.

3 Strategies for Coping with Non-compliant Instances

In this section, we discuss novel strategies for coping with non-compliant in-

stances. The basic idea behind is to conduct certain kinds of adjustment (cf.

Fig. 3) to also enable non-compliant instances to migrate to the new schema

version; i.e., to be relinked to the new type schema. One of the possible ad-

justments is to ”simulate” an instance-speciﬁc bias such that the eﬀects of the

type change for which the instance has progressed too far (non-compliant) are

”neutralized”. This enables migration or – more precisely – ”re-linking” of the

respective instance to the new type schema version. Consequently, this instance

can beneﬁt from further schema optimization. In the following we present two

Set of running instances on S

Unbiased instances Biased instances

Compliant Non-Compliant

Disjoint Bias Overlapping Bias

Partially

Equivalent Bias

Subsumption

Equivalent Bias

Equivalent

Bias

Structural Conflicts

Compliant

> Δ

Compliant

Fig. 2. Overview on Instance Cases along Change Overlap

strategies for this bias-based adjustment (cf. Fig. 3). Other adjustments adapt

of instance execution traces or even the type change itself.

3.1 Biased-based Local Adjustment

Strategy 1 (Always-Migrate): Basically, any non-compliant instance can

be migrated (i.e., relinked) to the modiﬁed type schema version. The idea is

as follows: Let Sbe a process schema which is transformed into Sby change

ΔS.LetfurtherIbe an instance on S. So far, ΔSis propagated to Iwhen

migrating Ito S(i.e., Ireﬂects ΔSafter its migration to S). However, if Iis

not compliant with S,ΔSmust not be applied to I; i.e., execution of Ishould be

continued on its old schema. However, this eﬀect can be also ”simulated” when

Local Adjustment

Global Adjustment

History-based

Strategy 1

Strategy 2

Strategy 1

Strategy 2

Bias-based

Strategy 3

Strategy 4

Adjustments for Coping with

Non-compliant Instances

Strategy 1

Strategies 2/4

+ Strategy 3

Strategy 1

Strategy 3

Strategy 1

Strategy 2

Strategy 4

MOVEDELETEINSERT

Strategies along Change Types

Fig. 3. Overview on Possible Strategies for Coping with Non-Compliant Instances

re-linking Ito Sby ”neutralizing” type change ΔS. ”Neutralizing” means to

introduce an artiﬁcial bias ΔIbased on Swhich reverses the eﬀects of ΔSfor

this particular instance. Consider Fig. 4. At type level new activity Xis inserted

between activities Aand B. Then instance I(cf. Fig. 4b) is not compliant with

S’ since Bis already completed. However, Ican still be migrated to to Sby not

applying type change ΔS. The invalid change ΔSfor Ion Scan be ”healed”

by creating an instance-speciﬁc bias ΔI(S)forIon S; i.e., ΔI(S) reﬂects

the deviations between Sand instance-speciﬁc schema SI. Speciﬁcally, ΔI(S)

constitutes the ”inverse” change operation of ΔS. In our example, insertion of

Xinto Scan be reversed by deleting Xfrom S.

a) Process type schema S:

Modified process type schema S`:



‘

CXA B C

S= <insert(S,X,A,B),>

A B



b) Unbiased instance I on S:

migrate

Biased instance I on S‘:

I:A B C

migrate

A B C Activity States:

Completed

Activity:

Ati td

I(S‘) = <delete(S‘,X)>

I non-compliant with S‘

Fig. 4. Strategy 1: Always-Migrate (Example)

Strategy 1 can be applied for any kind of change operation. The challenge is to

determine the ”inverse” change to be maintained for the migrated instance. Tab.

1 shows the inverse changes for insert, delete, and move operations. Alternatively,

we can directly determine schema ”diﬀerence” between type schema Sand

instance-speciﬁc schema. Here, already existing approaches can be used. [13], for

example, presentw an approach to compare two schemas S1and S2in terms of

high-level change operations (cf. Tab. 1) needed to transform S1into S2.

Strategy 2 (Instance-Speciﬁc Adjustment) The idea behind Strategy 2 is

to conduct instance-speciﬁc adjustments of type changes in order to be able to

relink non-compliant instances to the new type schema version. For this pur-

pose we exploit speciﬁc semantics of the applied change operation [10]: When

applying an insert operation, for example, the user has to specify the position

where to insert the new activities (cf. Tab. 1). Thus the insert operation is a can-

didate for instance-speciﬁc adjustments since such position parameters can be

easily adapted; e.g., by inserting an activtiy ”later” than originally intended. In

the following, instance-speciﬁc adjustment is elaborated in the context of insert

operations. Section 5 also provides a discussion for adjusting move operations.

Consider the example depicted in Fig. 5. Instance I(cf. Fig. 5b) is not com-

pliant with new type schema Ssince Bis already in state Running. Basically,

if no semantic constraints are violated, at instance level Xcan be inserted at

other positions as well, speciﬁcally at those positions within the instance-speciﬁc

schema, where Ibecomes compliant again. Assuming that we keep Aas the ”left

anchor” for the insert operation, possible ”right anchors” for the insertion are C

and Drespectively. Consider ﬁrst insertion of Xbetween Aand C(x): When

applying change Δ1

I(S)toIas instance-speciﬁc adjustment, we obtain instance

schema S1

I. The bias between S1

Iand Sis then captured by Δ1

I(S) and reﬂects

an insertion with ”relaxed” insertion position.2Schema S2

Iresulting from the

insertion of Xbetween Aand Dis depicted in Fig. 5b (y). Obviously, the ques-

tion is which of the two schemas we shall prefer. The premise of this paper is

to enable migration of non-compliant instances such that they can beneﬁt from

further optimizations. In general, the application of further modiﬁcations at type

level will be supported best by keeping the instance-speciﬁc schemas ”as close

as possible” to the type schema version they are migrated to. Here, intuitively,

Iis ”closer” to Swhen compared to S2

I. In order to formally deﬁne ”as close

as possible” a distance metric between process schemas is needed (cf. Section 4).

Basically, it is also possible to use ”left anchors” other than Afor realizing

instance-speciﬁc adjustments. Consider Fig. 5b(z): When compared to Sthe

order between Xand Bhas been reversed for Fig. 5b(z), whereas for Fig. 5b(x)

Xand Bare ordered in parallel. Thus for Fig. 5b(x), still Xcan be started before

Bis ﬁnished, what is not possible in Fig. 5b(z). Hence, the instance schema from

Fig. 5b(x) is ”closest” to S. – Altogether, from the above discussion two basic

research questions can be derived:

1. How to measure the distance between process type and instance schemas?

2. How to determine instance-speciﬁc adjustments ΔI(S) such that I

–is compliant with SIwhere S[ΔI(S)>S

–and the distance between instance schema SIand modiﬁed type schema

Sbecomes minimal?

For the ﬁrst question diﬀerent approaches exist. We discuss them

in Section 4. The second question is targeted in Sections 5 and 6.

3.2 Strategy 3: History-Based Adjustment

History-based adjustment is mainly applied for delete operations (e.g., an in-

stance is not compliant if the activity to be deleted is already running or com-

pleted). Basically, deletion of activities ”in the past” of process instances can be

enabled by adjusting instance traces. Assume, for example, that activity Xis to

be deleted from schema Sresulting in schema S. Regarding instance Ion S,

Xhas been already completed and respective start and end events for Xwere

logged in σS

I.ThusσS

Icannot be ”replayed” on Sand compliance for Ion S

2i.e., Xis not inserted between Aand B, but between Aand the ﬁrst ”possible”

successor of B.

a) Process type schema S:

Modified process type schema S`:



insert

(SXAB



‘

CXA B C



insert

)

A B DD



b) Unbiased instance I on S: Biased instance I on S‘:



A B C D

I non

compliant

ith

S‘

1I(S‘) = <move(S, X, A, C)>

non

compliant

ith

S‘



XS2I



CBA X D

A B C

+ + D

3I(S‘) = <move(S, X, B, C)>



2I(S‘) = <move(S, X, A, D)>

Completed

Activity +AND-Split/Join



4I(S‘) = <move(S, X, B, C)>

XBA C D

Running S4I

Fig. 5. Strategy 1: Instance-Speciﬁc Adjustment (Example)

is not fulﬁlled. However, when discarding the respective trace entries of Xfrom

σS

I, the modiﬁed trace can be replayed on Sand thus Ican be migrated. Entries

of deleted activities are not physically deleted from the exeuction traces, but are

only ﬂagged within the trace in order to preserve traceability. As shown in [14]

Strategy 3 does not harm soundness of the aﬀected instances.

3.3 Strategy 4: Global-Adjustment

Basically, adjusting schema changes may be done at both, the process type and

the process instance level. Assume that process type schema Sis transformed

into another type schema Sby change ΔS.LetfurtherIbe an instance on

Swhich is not compliant with S.IfΔSis adjusted to Δ

Sat type level (i.e.,

transforming Sinto S instead of S), more instances running on Smay becomes

compliant with S afterwards. Generally, more instances will become compliant

with a changed type schema, if added activities are inserted ”as late as possible”.

Most important, all data dependencies (or additionally, semantics constraints)

imposed by the process type schema and the intended change must be fulﬁlled.

For the given example this implies that activities X and Y can be inserted ”later

in the type schema” (i.e., as ”close” to the process end as possible) as long as

the data dependency between them is still fulﬁlled. Since a process type schema

might contain more than one process end node, the formalization of ”later in a

process graph” should not be based on structural properties; i.e., we aim at being

independent of a particular process meta model. As for the compliance criterion,

we use process traces in this context. Due to lack of space we omit a formalization

here. Finally, when inserting two or more data-dependent activities, additional

constraints must hold. More precisely, it cannot be allowed to move the insertion

position of the writing activity ”behind” the reading activity since the resulting

schema would not be correct anymore.

4 Metrics on Process Schemas

As discussed in the context of Strategy 2, measuring the distance between type

and instance schema is an important task. Basically, there exist diﬀerent ap-

proaches for this, ranging from activity coverage [15] over ﬁtness functions (e.g.,

in connection with genetic process mining [16]), to process similarity as deﬁned

in [15]. Activity coverage quantiﬁes the distance between two process schemas

S1and S2in terms of the diﬀerence between their activity sets.

Regarding the examples depicted in Fig. 5, activity coverage is 100% for all

schemas. However, there are structural diﬀerences between instance schemas Sj

(j= 1, .., 4) and S. First of all, for each Sj

IabiasΔj

Ibetween Sj

Iand Sarises.

According to the process similarity notion introduced in [15], for example, the

distance between two process schemas can be determined as number of high-level

change operations (i.e., insert, move, and delete operations) needed to transform

the one schema into the other. Regarding our scenario from Fig. 5, for each

Iexactly one high-level change, speciﬁcally a move operation, is required to

capture the diﬀerence between Sand Sj

I. Using this measure, therefore, the

similarity to Swould be the same for all Sj

I(j=1,...,4).Thus,weneed

an additional measurement in terms of control relations between the diﬀerent

activities. Intuitively, such structural ﬁtness can be expressed considering the

number of control relations diﬀerent for Sand Sj

I. This number should be

minimized in order to enable propagation of subsequent schema changes.

Deﬁnition 2 (Structural Distance). Let S = (N, CtrlE, SyncE, ...) and S’ =

(N, CtrlE’, SyncE’, ...) (cf. Section 2) be two (block-structured) process schemas

having equal activity set (i.e., activity coverage of 100%, cf. Section 7). Let fur-

ther succ*(S, n) denote the set of all direct or indirect successors of activity n

in S3,formally:

succ*: S×N→ 2Nwith

succ*(S, n) = {n∗∈N|n∗∈succ(S, n)∨∃n∗∗ ∈succ(S, n):n∗∈succ∗(S, n∗∗))}

with succ(S, n) denoting the set of all direct successors of n in S, i.e., regarding

control and sync edges

3At this point we assume acyclic process structures. However, in general cyclic struc-

tures can contribute to a treatment of non-compliant instances. A sketch of the so

called delayed migration using loop backward jumps is provided in Section 8.

The structural ﬁtness between S and S’ can then be quantiﬁed by function

sD(S, S’) which sums up the cardinalities of the diﬀerence sets between the suc-

cessor sets for all activities contained in S and S’.

sD: S×S→ Nwith

sD(S,S’) = |

n∈N(succ∗(S, n)\succ∗(S,n)) ∪(succ∗(S,n)\succ∗(S, n)|

Fig. 6 summarizes and compares the respective successor sets for the diﬀerent

schemas from Fig. 5. As can be seen instance-speciﬁc schema S1

Ihas minimal

structural distance to S. Hence, deciding for an instance-speciﬁc adjustment in

order to ”make” Icompliant with S(cf. Fig. 5b), change Δ1

Iwould be considered

as optimal instance-speciﬁc adjustment.

A XBCD XBCD XBCD XBCD XBCD

BCD

BCD CD CD XCD

XCD

CDDDDXD

∅∅∅∅∅

Fig. 6. Successor Sets and Structural Distances for the Scenario from Fig. 5

5 Instance-Speciﬁc Adjustment of Unbiased Instances

Bias-based strategies as introduced in Section 3.1 are promising approaches for

treating non-compliant instances. Assume that instance Ion Sis not compliant

with modiﬁed type schema version S(S[ΔS>S

). However, if type change ΔS

can be locally adjusted to ΔI(S)suchthatIbecomes compliant with instance

schema S|ΔI(S)>S

I,IcanberelinkedtoSusing bias ΔI(S) (Strategy 2). As

motivated by Fig. 5, diﬀerent adjustments of ΔSare conceivable. However, we are

particularly interested in the adjustment which results in the lowest structural

distance sD(S,S

I) between instance schema SIand type schema S(cf. Def.

2). In this section we show how to automatically derive such optimal instance-

speciﬁc adjustment for unbiased process instances. In the example from Fig. 5,

optimal instance-speciﬁc adjustment for operation ”insert activity Xbetween A

and B”isachievedifXis inserted between Aand the next possible successor

of Awhich has not been started yet. Theorem 1 captures this aspect:

Theorem 1 (Optimal Instance-speciﬁc Adjustment). LetS,S’betwo

process schemas and let ΔS=<insert(S,X,A,B)>be an insert operation

which transforms S into S’; i.e., S[ΔS>S

. Let further I ∈I(Idenotes the set

of all instances) be an instance running on S for which NSI(B)∈{Running,

Completed}holds for the state of activity B (cf. Section 2); i.e., I is not compli-

ant with S’. We deﬁne instance-speciﬁc adjustment ΔI(S)as follows:

ΔI(S)= move(S’,X,A,C) with C ∈nextNonStartedSucc(S’,I,B)4where

nextNonStartedSucc: S×I×N→ 2N

nextNotStartedSucc(S’,I,n) =

{n∈succ*(S’,X) |NSI(n)∈{Running, Completed}

∧( ∃ n’: NSI(n)∈{Running, Completed}∧n∈succ*(S’,n’) }

Then: Iis compliant with SIwhere S[ΔI(S)>SIand

dS(S’,SI)=min{dS(S’, ˜

SI)|S[˜

ΔI(S)>˜

SIwith I compliant with ˜

SI}

A proof of Theorem 1 can be cound in Appendix A.

For each insert operation applied to process schema Sa corresponding move

operation is generated based on Theorem 1 if necessary; i.e., if I is not compliant

regarding this particular insert operation. As example consider Fig. 7: instance

Iis not compliant with S. Hence for both insert operations (i.e., of Xand Y)

two corresponding move operations are applied to realize an instance-speciﬁc

adjustment (bias).

So far, insert and delete operations have been discussed. Regarding insert

operations instance-speciﬁc adjustments can be applied (cf. Strategy 2) whereas

for delete operations, adjustment of the execution history of the aﬀected instance

might relax compliance issues (cf. Strategy 3). What about move operations?

First of all, moving an activity can be seen as combination of a delete and

insert operation. Second, regarding compliance, an activity cannot be moved if

it has been already started or completed. Furthermore it cannot be moved before

an activity which has been already started or completed. Thus we distinguish

between the following cases: if an activity shall be moved, which has been already

started or completed, we apply history-based adjustment (Strategy 3). If the

activity is to be moved before an already started or completed activity, we apply

instance-speciﬁc adjustment (Strategy 2).

6 Instance-Speciﬁc Adjustment of Biased Instances

Fig.2hasalreadygivenanoverviewonthediﬀerentclassesofoverlapbetween

schema changes at the process type and the process instance level. In this sec-

tion we investigate whether and – if yes – how the strategies for dealing with

non-compliant instances (cf. Section 3) can be applied in the context of biased

instances as well. First of all, one can observe that instances with equivalent bias

and instances having subsumption equivalent bias (i.e., ΔIΔS)arealways

compliant with the changed schema (cf. Section 2). Consequently, for these two

4In connection with parallel or alternative branchings more than one successor of B

can be the ”next non-started activity”. In this case one of them is chosen arbitrarily

or the user is asked to make a choice.

a) Process Type Schema S: Process Type Schema Sb:

S= < insert(S,X,C,E).

insert

(S Y A B)>

insert

B)>

A B

X X A B

X X

Instances

on Schema S:



insert

(SXCF)>

Instances

on Schema S:



insert

F)>

(S‘)

(SXCF)

(S Y A D)

A B X X

(S‘)

move

, move



I(S)= <>

Activity

XXOR-Split/Join

Control edge



Activity States: Completed

ync e

sD(S‘, S‘I) = 5

Skipped



Activated

Fig. 7. Instance-speciﬁc Adjustment (Example)

classes no additional reasoning on treatment of non-compliant instances becomes

necessary. From the remaining overlap classes, we ﬁrst focus on instances with

disjoint bias; i.e., changes at type level and instance level which are completely

diﬀerent. An example is depicted in Fig. 8. Regarding instance I, activity Yhas

been inserted between Band C(captured by instance-speciﬁc bias ΔI(S)). Then

at type level, schema change ΔSinserts Xbetween Aand B. Obviously, ΔSand

ΔIare disjoint and Iis not compliant with S(since Bis already completed).

Transferring the instance-speciﬁc adjustment as presented in Theorem 1 to this

scenario, ﬁrst of all next successor of Bin SIwhichhasnotbeenstartedyet

is determined; i.e., activity Y. Thus, the instance-speciﬁc adjustment of ΔSat

instance level yields move operation move(S’, X, A, Y). Since ΔSand ΔI(S)are

disjoint, the instance-speciﬁc adjustment does not conﬂict with the original bias.

Thus, new bias ΔI(S) turns out as concatenation of the bias before migration

and the instance-speciﬁc adjustment; i.e., ΔI(S) as shown in Fig. 8. Due to lack

of space we omit formal details and proofs here.

If type schema change ΔSsubsumes instance change ΔI(i.e., ΔsuccΔI)

instance-speciﬁc adjustment has to be carried out for all insert operations in ΔS\

ΔIfor which Ihas progressed too far. How to determine diﬀerence sets between

changes is outside the scope of this paper. For all adjusted insert operations the

corresponding move operation can be determined based on Theorem 1. These

a) Process schema S:

Modified process schema S`:

CXA B C

S= <insert(S,X,A,B),>

A B

b) Biased instance I on S: migrate Biased instance

IonS

‘

CBA

Activity:

Disjoint bias I(S) = <insert(S, Y, B, C)>

I(S‘) = <insert(S‘, Y, B, C), move(S‘, X, A, Y)>

Activity States: Completed

Fig. 8. Instance-speciﬁc Adjustment for Instances with Disjoint Bias

move operations have to be stored as instance-speciﬁc bias on Safter migration.

Fig. 9 shows an example.

a) Process schema S:

Modified process schema S`:

BXA B C

S= <insert(S,X,A,B), insert(S, Y, X, B),>

A C

b) Biased instance I on S: Biased instance I on S‘:

migrate

CXA B

I(S) = <insert(S, X, A, B)>

I(S‘) = <move(S‘, Y, X, C)>

s/I(S) = <insert(S, Y, X, B)>

Fig. 9. Instance-speciﬁc Adjustment of Instances with Subsumption Equivalent Bias

7 Strategy Evaluation

Assume that instances IS:= {I1, ..., In}are running on type schema Swhich

is then transformed into schema S(S[ΔS>S’). Assume further that a subset of

the running instances is not compliant with S’. In this section we want to eval-

uate the quality of the diﬀerent strategies introduced in Section 3 for treating

non-compliant instances. On the one hand, the quality of a strategy is based

on the number of instances which can be migrated additionally to the number

of compliant instances (i.e., instances without applying any strategy). On the

other hand, we also have to consider the ”price” to be paid for each additionally

migrated instance I. The latter is reﬂected by the distance between instance

schema SIand Safter migration. One metric for measuring the structural dis-

tance between process schemas SI:= (NI,CtrlE

I, ...)andS=(N,CtrlE, ...)

is provided in Def. 2. However, this metrics can be only applied if SIand Shave

the same activity sets; i.e., there exists a bijective mapping between NIand N

or – in other words – activity coverage between SIand Sis 100%. Actually,

activity coverage can be also used to compare process schemas, for example, in

the context of Strategy 1 (cf. Section 3), which leads to NI=Nin most cases.

Finally, process schemas SIand Scan be also compared based on the number

of high-level operations necessary to transform SIinto S(denoted as process

similarity [15]). For a deﬁnition of all three metrics see Tab. 2:

Metric M Formula Preconditions

Process Similarity PS(SI,S’):= #ops

|NI|+|N|−|NI∩N|

Activity Coverage AC(SI,S’):= |NI∩N|

|NI|+|N|−|NI∩N|

Structural Distance SD(SI,S’):= sD(SI,S)

|NI|AC(SI,S’) = 100%

aops denotes the high-level operations applied for transforming SIinto S.

Table 2. Diﬀerent Metrics for Comparing Process schemas

Below Formula (1) enables evaluation of the quality of Strategies 1 to 4.

Speciﬁcally, #mIsdenotes the number of migratable instances when applying

strategy s. Note that we can compare the application of a strategy with the

case of applying no strategy. Then #mIsreﬂects the number of instances, which

are compliant with modiﬁed type schema version Sanyway. The remainder of

the formula quantiﬁes the side-eﬀects when applying one of the strategies. If

we do not apply any strategy, the formula yields SC(”none”, S’, IS)=#mIs

|IS|;

i.e., the number of compliant instances divided by the number of all instances.

For Strategy 1, for example, which enables migration of all instances (”always-

migrate”), #mIs=|IS|holds.

SC(s, S,IS):= #mIs−

I∈ISPS(SI,S

)−

I∈ISAC(SI,S

)−

I∈ISsD(SI,S

)

|IS|(1)

Consider the scenario depicted in Fig. 10. Type schema Sis transformed

into Sby inserting activity Xbetween Aand Band by deleting C.Assume

that 500 instances are running based on Sand that they are clustered along

their current instance state. Assume further that for instances I1, ..., I100,activ-

ity Ais completed and Bis activated, for instances I101, ..., I200 Aand Bare

completed and Cis activated, and for I201, ..., I500 activities, A,B,andCare

completed whereas Dis either activated or running. Then instances I1, ..., I100

are compliant with S,whereasI101, ..., I500 have progressed too far; i.e., they

are non-compliant with S. Without any further treatment of the non-compliant

instances the quality turns out as SC(”none”,S’,IS)=0.2.

The result of applying our four strategies is illustrated by Fig. 10. First, Strat-

egy 1 (Always-Migrate) is applied to instances I101, ..., I500.InstancesI101, ..., I200

are not compliant with respect to the insertion of X, but they are compliant with

respect to the deletion of C. Hence, when applying Strategy 1 to I101, ..., I200,

the insert operation has to be neutralized, which can be expressed by a delete

operation on S(i.e., to delete Xon S). Contrary, instances I201, ..., I500 are not

compliant with respect to both changes. Hence also the deletion of Chas to be

neutralized by a respective insert operation (cf. Fig. 10).

As summarized in Fig. 3, some of the strategies are applicable in the context

of certain change operations; i.e., Strategy 2 for insert operations and Strategy

3 for delete operations. Type schema change ΔScaptures an insert as well as a

delete operation. Hence, we have to combine Strategies 2 and 3 in order to ade-

quately treat non-compliant instances by bias-based local adjustment. Regard-

ing instances I101, ..., I200, the delete operation can be applied (no history-based

adjustment). However the insert operation has to be adjusted to a move oper-

ation as depicted in Fig. 10. Regarding instances I201, ..., I500 we have to apply

history-based adjustment for the deletion of Cas well (i.e., logically discarding

the entries of Cin traces of I201, ..., I500). Finally, Fig. 10 shows an example for

the application of Strategy 4 (Global Adjustment); i.e., by inserting activity X

between Cand DinsteadofbetweenAand Ball instances, for which Dhas

not been started yet become compliant with S (e.g., I1, ..., I450). Altogether,

we obtain the following quality estimations for Strategies 1, 2, and 4 as depicted

in Fig. 10:

•Strategy 1: S(s1, S’, {I1,...,I

500})=500−(100∗0.25+300∗0.4)+(100∗0.75+300∗0.6)

500 =1.31

•Strategy 2: S(s2, S’, {I1,...,I

500})=500−500∗0.25+500−500∗0.25

500 =1.5

•Strategy 4: S(s3, S’, {I1,...,I

500})=450+500

500 =1.9

8 Related Work

There is a plethora of approaches dealing with correctness issues in adaptive

PAIS [5, 17, 6, 7, 4]. The kind of applied correctness criterion often depends on

the used process meta model. A discussion and comparison of the particular

correctness criteria is given in [8]. Aside from the applied correctness criteria,

mostly, these approaches do neither address the question of how to increase the

number of migratable instances nor how to deal with non-compliant instances.

Most approaches which treat non-compliant instances are based on partial roll-

back [4, 18] (cf. Sect. 4). An alternative approach supporting delayed migrations

of non-compliant instances is oﬀered by Flow Nets [17].EvenifinstanceIon Sis

a) Process Schema S: S`:

S= < insert(S,X,A,B), delete(S,C)>

Strategy 1: Always Migrate



delete

‘

,X)

101, …, 200

A B C D A X B D

SC(1,S‘,

)=1.31

I101, …, 200 A B D



delete

(S ,X) ,

101,

…,

200

A B C D

I201, …, 500 A B C D

Ij = <delete(S‘,X), insert(S, C, B, D)>, j = 201, …, 500

A B C D

Strategy 2: Local Adjustment

XSC(2,S‘,

)=1.5

101, …, 500



= <move

(

S‘

)

= 101

…

500

A B D

+ +

A B C D

( ,,,),

j,,

Strategy 4: Global Adjustment ‘S= < insert(S,X,C,D), delete(S,C)>

SC(4,S‘,

)=1.9

Fig. 10. Application of Diﬀerent Strategies

not compliant with Swithin the actual iteration of a loop, a delayed migration

of Ito the new change region is possible when another loop iteration takes place.

Frameworks for process ﬂexibility have been presented in [19, 10]. In [19],

diﬀerent paradigms for process ﬂexibility and related technologies are described.

[10] provides change patterns and evaluates diﬀerent approaches based on them.

However, [19, 10] do not address the treatment of non-compliant instances.

For treating non-compliant instances, partial rollback has been suggested [4,

18]. Applying this policy for instances which have already progressed too far

results in a compliant state. Generally, instance rollback is accomplished by

compensating activities [4]. An obvious drawback is that it is not always pos-

sible to ﬁnd compensating activities, i.e., to adequately rollback non-compliant

instances. Apart from this, rollback is mostly connected with loss of work and

thus not well accepted by users.

9 Summary and Outlook

So far, non-compliant process instances have been excluced from being migrated

to the new process type schema version in order to preserve soundness. Con-

sequently, these instances are also excluded from any future process optimiza-

tions. Thus, in this paper we provided four strategies to cope with non-compliant

process instances. Speciﬁcally, the strategies are based on adjustments either of

process changes at type schema level or instance level. Alternatively, adjustments

of the instance traces are helpful in some cases. All strategies preserve soundness

of the running instances after relinking them to the new type schema version.

In particular, we elaborated the migration of instances by locally adjusting the

type schema change at instance level; e.g., moving the insertion position such

that the instances become compliant with the resulting instance-speciﬁc schema.

How respective adjustments can be determined such that the distance between

instance-speciﬁc schema and modiﬁed type schema version becomes minimal has

been shown as well. Finally, all strategies were evaluated along an example. In

future work, we aim at implementing the diﬀerent strategies together with our

framework on relaxing compliance notions within the ADEPT2 system. Further-

more, we plan to investigate the interplay between relaxing compliance, treating

non-compliant instances, and ensuring semantic process constraints.

References

1. Lenz, R., Reichert, M.: IT support for healthcare processes – premises, challenges,

perspectives. Data and Knowledge Eng. 61 (2007) 39–58

2. Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workﬂow evolution. Data and Knowledge

Engineering 24 (1998) 211–238

3. Reichert, M., Dadam, P.: ADEPTflex - supporting dynamic changes of workﬂows

without losing control. J of Intelligent Information Systems 10 (1998) 93–129

4. Sadiq, S., Marjanovic, O., Orlowska, M.: Managing change and time in dynamic

workﬂow processes. IJCIS 9(2000) 93–116

5. van der Aalst, W., Basten, T.: Inheritance of workﬂows: An approach to tackling

problems related to change. Theoret. Comp. Science 270 (2002) 125–203

6. Weske, M.: Business Process Management: Concepts, Languages, Architectures.

Springer (2007)

7. Rinderle, S., Reichert, M., Dadam, P.: Flexible support of team processes by

adaptive workﬂow systems. Distributed and Parallel Databases 16 (2004) 91–116

8. Rinderle, S., Reichert, M., Dadam, P.: Correctness criteria for dynamic changes in

workﬂow systems – a survey. Data and Knowledge Eng. 50 (2004) 9–34

9. Dehnert, J., Zimmermann, A.: On the suitability of correctness criteria for business

process models. In: Int’l Conference Business Process Management. (2005) 386–391

10. Weber, B., Reichert, M., Rinderle-Ma, S.: Change patterns and change support

features - enhancing ﬂexibility in process-aware information systems. Data and

Knowledge Engineering 66 (2008) 438–466

11. Rinderle, S., Reichert, M., Dadam, P.: On dealing with structural conﬂicts between

process type and instance changes. In: Int’l Conf. on Business Process Management.

(2004) 274–289

12. Rinderle, S.: Schema Evolution in Process Management Systems. PhD thesis, Ulm

University (2004)

13. Li, C., Reichert, M., Wombacher, A.: On measuring process model similarity based

on high-level change operations. In: 27th Int’l Conf. on Conceptual Modeling

(ER’08). (2008) 248–264

14. Rinderle-Ma, S., Reichert, M., Weber, B.: Relaxed compliance notions in adaptive

process management systems. In: Int’l Conf. on Conceptual Modeling (ER’08).

(2008) 232–247

15. Li, C., Reichert, M., Wombacher, A.: Discovering reference process models by

mining process variants. In: Int’l Conf. on Web Services. (2008)

16. Alves de Medeiros, A., Weijters, A., van der Aalst, W.: Genetic process mining: An

experimental evaluation. Data Mining and Knowl. Discovery 14 (2007) 245–304

17. Ellis, C., Keddara, K., Rozenberg, G.: Dynamic change within workﬂow systems.

In: ACM Conf. on Organizational Computing Systems. (1995) 10–21

18. Reichert, M., Dadam, P., Bauer, T.: Dealing with forward and backward jumps in

workﬂow management systems. Software and Syst. Modeling 2(2003) 37–58

19. Mulyar, N., Schonenberg, M., Mans, R., Russell, N., van der Aalst, W.: Towards a

taxonomy of process ﬂexibility (extended version). Technical Report BPM-07-11,

Brisbane/Eindhoven: BPMcenter.org (2007)

20. Rinderle, S., Reichert, M., Jurisch, M., Kreher, U.: On representing, purging, and

utilizing change logs in process management systems. In: Proc. of 4the Int’l Conf.

on Business Process Management, September, Vienna, Austria. (2006) 241–256

A Proofs

Theorem 1 (Optimal Instance-speciﬁc Adjustment). LetS,S’betwo

process schemas and let ΔS=<insert(S,X,A,B)>be an insert operation

which transforms S into S’; i.e., S[ΔS>S

. Let further I ∈I(Idenotes the set

of all instances) be an instance running on S for which NSI(B)∈{Running,

Completed}holds for the state of activity B (cf. Section 2); i.e., I is not compli-

ant with S’. We deﬁne instance-speciﬁc adjustment ΔI(S)as follows:

ΔI(S)= move(S’,X,A,C) with C ∈nextNonStartedSucc(S’,I,B)5where

nextNonStartedSucc: S×I×N→ 2N

nextNotStartedSucc(S’,I,n) =

{n∈succ*(S’,X) |NSI(n)∈{Running, Completed}

∧( ∃ n’: NSI(n)∈{Running, Completed}∧n∈succ*(S’,n’) }

Then: Iis compliant with SIwhere S[ΔI(S)>SIand

dS(S’,SI)=min{dS(S’, ˜

SI)|S[˜

ΔI(S)>˜

SIwith I compliant with ˜

SI}

ForprooﬁngTheorem1,weusethefollowingtwoLemmata:Lemma1pro-

vides an estimation for the structural diﬀerence between a modifed type schema

version and an instance-speciﬁc schema, if the assumption of Theorem ?? hold.

Again under the assumptions of Theorem 1, Lemma 2 gives an estimation for the

structural diﬀerence when the instance-speciﬁc change is modiﬁed by choosing

another left anchor for the move operation at instance level as suggested for the

instance-speciﬁc change with minimal structural diﬀerence.

Lemma 1 (Structural Distance for Instance-Speciﬁc Adjustment (1)).

Let the assumptions be as deﬁned for Theorem 1. Then:

sD(SI,S’) = |succ∗(S,A)∩pred∗(S,C)|-1

5In connection with parallel or alternative branchings more than one successor of B

can be the ”next non-started activity”. In this case one of them is chosen arbitrarily

or the user is asked to make a choice.

Proof of Lemma 1: For illustration see Fig. 11.

TheonlyactivitywithinSIwhich is aﬀected by ΔIin terms of changes of

its successor set is Xwhen compared to S. Reason is that for ”left anchor” A

(and all its predecessors) the set of successors remains the same (i.e., Xis only

inserted at a diﬀerent position). Symmetrically, for ”right anchor” C(and all

its successors) their successor sets are not aﬀected by ΔI(S)atall.Thus,the

possibly aﬀected activities are within set succ∗(SI,A)∩pred∗(SI,C).

When digging deeper we obtain the following results: For activities in set

(succ∗(SI,A)∩pred∗(SI,X)) their successor sets remain equal as well when com-

pared to S. Note that Xis actually present in their successor sets and the exact

position does not matter. For all activities in succ∗(SI,X)∩pred∗(SI,C), Xis

inserted in parallel. Assume that Aand Bare direct successors in Sand Xis in-

serted serially between Aand Bresulting in S.SinceBhas been already started

for I,Xis moved between Aand a successor of B. Thus, this always results in

inserting Xat least parallel to B. Altogether, for succ∗(SI,X)∩pred∗(SI,C)

there is also no change in their successor sets when compared to Ssince no new

order relations are introduced for these activities.

In summary, only the successor set of XisaﬀectedwhencomparingSIand

S.Asarguedbefore,Xis moved parallel to the activities which are in set

succ∗(S,A)∩pred ∗(S,C) except Xitself. Thus, for all these activites (except

X)X”looses” one successor when comparing Sand SI. Out of this statement

Lemma 1 can be directly concluded. 

Process Schema S: S= < insert(S,X,A,B)>

S`:

Fig. 11. Illustration of Lemmata 1 and 2

Lemma 2 (Structural Distance for Instance-Speciﬁc Adjustments (2)).

Let the assumptions be as deﬁned for Theorem 1. Then for ΔI= move(S’,X,Y,C)

with Y ∈succ*(S’,A) (with S’[ΔI> SI,Icompliant with SI):

sD(SI,S’) = |succ∗(S,A)∩pred∗(S,C)|−1+|succ∗(S,A)∩pred∗(S,Y)|

ProofSketchofLemma2:

The basic consideration behind Lemma 1 is that change ΔI(S)canbe

”mapped” to change ΔI(S) as described in Theorem 1. This can be done as

follows: Consider Fig. 11: Xcan be inserted between Aand E; i.e., by change

ΔI(S) = move(S’,X,A,E). According to Lemma 1 for each activity Xis moved

parallel to, X”looses” one successor. Shifting the left anchor from Atowards E

can be expressed by inserting a sync edge between new anchor Yand X; e.g.,

if we chose Bas left anchor (i.e., ΔI(S) = move(S’,X,B,E)). By doing so, B

”receives” new successor X. If, for example, Dis chosen as left anchor, B,C,

and Dhave new successor X. Thus, for all activities ”between” Aand Yone

new successor occurs. 

Proof of Theorem 1:

Preconditions:

1. ΔS=<insert(S,X,A,B)>

2. S[ΔS>S



3. I∈Ion S

4. NSI(B)∈{Running, Completed}

5. ΔI(S) = move(S’,X,A,C) with

C∈nextNonStartedSucc(S’,I,B) =⇒NSI(C)∈{NotActivated, Activated}

6. S’[ΔI(S)>S

Statement:

(1)IcompliantwithSI

∧

(2) dS(S’,SI)=min{dS(S’, ˜

SI)|S[˜

ΔI(S)>˜

SIwith I compliant with ˜

SI}

We proof Theorem 1 by contradiction.

Contradicton Assumption:

¬((1) ∧(2)) ≡¬(1) ∨¬(2) ≡

¬((1)IcompliantwithSI∧

(2) dS(S’,SI)=min{dS(S’, ˜

SI)|S[˜

ΔI(S)>˜

with I compliant with ˜

SI})≡

(¬1) I is not compliant with SI∨

(¬2) ∃ΔI(S)withdS(S’,SI)≥dS(S’, SI)with

S’[ΔI(S)> SI

Preliminaries for Case (¬1): Basically, compliance is deﬁned based on execution

traces [2, 7]; i.e., instance Iis compliant with changed type schema version S

if trace σS

Iof Ion Scould have been also produced on S. As discussed in [7],

for example, checking compliance based on generating and replaying execution

traces can be quite expensive. Thus, comparable to serializability in database

systems, for example, we have stated precise compliance conditions (cf. [7, 8, 12,

20], based on which compliance can be quickly checked. The idea is to exploit

the semantics of the applied change operation (e.g., an insert or move operation)

and to evaluate the node states NSIof ”critical” activities; i.e., activities which

constitute the change region of the the particular activity. For deletion, for exam-

ple,thechangeregionisbuiltbytheactivitytobedeleted(changesemantics).

It can be shown that compliance is ensured if the activity to be deleted is in

state NotActivated or Activated. In the context of Theorem 1 we are interested

in move operations.

The compliance conditions for move operation move(S’,X,A,C) are as follows:

NSI(X)∈{NotActivated, Activated}∧NSI(C)∈{Running, Completed}

Case ¬(1): I is not compliant with SI=⇒

ΔI(S) violates the compliance condition for move operations, i.e.,

NSI(X)∈{NotActivated, Activated}

∨NSI(C)∈{NotActivated, Activated}=⇒Contradiction 

since NSI(X) = NotActivated since X is newly inserted at type schema level

and NSI(C)∈{NotActivated, Activated}according to Precondition (5)

Case ¬(2): ∃ΔI(S)withdS(S’,SI)≥dS(S’, SI) with S’[ΔI(S)> SI

Pre-Considerations:

We assume implicitly that dS(S’,SI)anddS(S’,SI) are deﬁned =⇒

N’ = N

I=NI

for S’= (N’, CtrlE, ...), SI=(NI,CtrlE

I, ...), and SI=(NI,CtrlEI, ...).

From this assumption we can conclude that opType(ΔI(S))=move(cf.Table

Since we assume further that Iis compliant with SI, subject((ΔI(S)) = S

follows (cf. Table 1); i.e., altogether ΔI(S) = move(S’,X,Y,Z).

Consequently, ΔI(S)andΔI(S) diﬀer in their parameter list. Here we can

distinguish the following cases:

Case A: Y = A, Z = C; i.e., maintaining ”left anchor” A

With Lemma 1 we obtain:

sD(SI,S’) = |succ∗(S,A)∩pred∗(S,Y)|−1!

<|succ∗(S,A)∩pred∗(S,C)|-1

Under the assumption that ΔIis a valid change (i.e., Y ∈succ*(SI,A)) and

compliance conditions hold for ΔI(S) (i.e., NSI(Y)∈{Running, Completed})

a contradiction to the preconditions results, since in this case Ccannot be one

of the next non-started successor of A in S’ 

Case B: Y=A,Z=C;i.e.,maintaining”rightanchor”C

Case B1: Y∈succ*(S’,A)

With Lemma 1 and Lemma 2 we obtain:

sD(SI,S’) = |succ∗(S,A)∩pred∗(S,C)|-1 + |succ∗(S,A)∩pred∗(S,Y)|!

|succ∗(S,A)∩succ∗(S,C)|-1 =⇒Contradiction 

Case B2: Y∈pred*(S’,A)

Intuitively clear. If we move Xbetween a predecessor of Aand C,Xis

moved parallel to A.ThusatleastA”looses” Xas successor and we obtain

sD(SI,S’) ≥sD(SI,S’) + 1

Case C: Y=A,Z==⇒follows from Case A and Case B 

Liste der bisher erschienenen Ulmer Informatik-Berichte

Einige davon sind per FTP von ftp.informatik.uni-ulm.de erhältlich

Die mit * markierten Berichte sind vergriffen

List of technical reports published by the University of Ulm

Some of them are available by FTP from ftp.informatik.uni-ulm.de

Reports marked with * are out of print

91-01 Ker-I Ko, P. Orponen, U. Schöning, O. Watanabe

Instance Complexity

91-02* K. Gladitz, H. Fassbender, H. Vogler

Compiler-Based Implementation of Syntax-Directed Functional Programming

91-03* Alfons Geser

Relative Termination

91-04* J. Köbler, U. Schöning, J. Toran

Graph Isomorphism is low for PP

91-05 Johannes Köbler, Thomas Thierauf

Complexity Restricted Advice Functions

91-06* Uwe Schöning

Recent Highlights in Structural Complexity Theory

91-07* F. Green, J. Köbler, J. Toran

The Power of Middle Bit

91-08* V.Arvind, Y. Han, L. Hamachandra, J. Köbler, A. Lozano, M. Mundhenk, A. Ogiwara,

U. Schöning, R. Silvestri, T. Thierauf

Reductions for Sets of Low Information Content

92-01* Vikraman Arvind, Johannes Köbler, Martin Mundhenk

On Bounded Truth-Table and Conjunctive Reductions to Sparse and Tally Sets

92-02* Thomas Noll, Heiko Vogler

Top-down Parsing with Simulataneous Evaluation of Noncircular Attribute Grammars

92-03 Fakultät für Informatik

17. Workshop über Komplexitätstheorie, effiziente Algorithmen und Datenstrukturen

92-04* V. Arvind, J. Köbler, M. Mundhenk

Lowness and the Complexity of Sparse and Tally Descriptions

92-05* Johannes Köbler

Locating P/poly Optimally in the Extended Low Hierarchy

92-06* Armin Kühnemann, Heiko Vogler

Synthesized and inherited functions -a new computational model for syntax-directed

semantics

92-07* Heinz Fassbender, Heiko Vogler

A Universal Unification Algorithm Based on Unification-Driven Leftmost Outermost

Narrowing

92-08* Uwe Schöning

On Random Reductions from Sparse Sets to Tally Sets

92-09* Hermann von Hasseln, Laura Martignon

Consistency in Stochastic Network

92-10 Michael Schmitt

A Slightly Improved Upper Bound on the Size of Weights Sufficient to Represent Any

Linearly Separable Boolean Function

92-11 Johannes Köbler, Seinosuke Toda

On the Power of Generalized MOD-Classes

92-12 V. Arvind, J. Köbler, M. Mundhenk

Reliable Reductions, High Sets and Low Sets

92-13 Alfons Geser

On a monotonic semantic path ordering

92-14* Joost Engelfriet, Heiko Vogler

The Translation Power of Top-Down Tree-To-Graph Transducers

93-01 Alfred Lupper, Konrad Froitzheim

AppleTalk Link Access Protocol basierend auf dem Abstract Personal

Communications Manager

93-02 M.H. Scholl, C. Laasch, C. Rich, H.-J. Schek, M. Tresch

The COCOON Object Model

93-03 Thomas Thierauf, Seinosuke Toda, Osamu Watanabe

On Sets Bounded Truth-Table Reducible to P-selective Sets

93-04 Jin-Yi Cai, Frederic Green, Thomas Thierauf

On the Correlation of Symmetric Functions

93-05 K.Kuhn, M.Reichert, M. Nathe, T. Beuter, C. Heinlein, P. Dadam

A Conceptual Approach to an Open Hospital Information System

93-06 Klaus Gaßner

Rechnerunterstützung für die konzeptuelle Modellierung

93-07 Ullrich Keßler, Peter Dadam

Towards Customizable, Flexible Storage Structures for Complex Objects

94-01 Michael Schmitt

On the Complexity of Consistency Problems for Neurons with Binary Weights

94-02 Armin Kühnemann, Heiko Vogler

A Pumping Lemma for Output Languages of Attributed Tree Transducers

94-03 Harry Buhrman, Jim Kadin, Thomas Thierauf

On Functions Computable with Nonadaptive Queries to NP

94-04 Heinz Faßbender, Heiko Vogler, Andrea Wedel

Implementation of a Deterministic Partial E-Unification Algorithm for Macro Tree

Transducers

94-05 V. Arvind, J. Köbler, R. Schuler

On Helping and Interactive Proof Systems

94-06 Christian Kalus, Peter Dadam

Incorporating record subtyping into a relational data model

94-07 Markus Tresch, Marc H. Scholl

A Classification of Multi-Database Languages

94-08 Friedrich von Henke, Harald Rueß

Arbeitstreffen Typtheorie: Zusammenfassung der Beiträge

94-09 F.W. von Henke, A. Dold, H. Rueß, D. Schwier, M. Strecker

Construction and Deduction Methods for the Formal Development of Software

94-10 Axel Dold

Formalisierung schematischer Algorithmen

94-11 Johannes Köbler, Osamu Watanabe

New Collapse Consequences of NP Having Small Circuits

94-12 Rainer Schuler

On Average Polynomial Time

94-13 Rainer Schuler, Osamu Watanabe

Towards Average-Case Complexity Analysis of NP Optimization Problems

94-14 Wolfram Schulte, Ton Vullinghs

Linking Reactive Software to the X-Window System

94-15 Alfred Lupper

Namensverwaltung und Adressierung in Distributed Shared Memory-Systemen

94-16 Robert Regn

Verteilte Unix-Betriebssysteme

94-17 Helmuth Partsch

Again on Recognition and Parsing of Context-Free Grammars:

Two Exercises in Transformational Programming

94-18 Helmuth Partsch

Transformational Development of Data-Parallel Algorithms: an Example

95-01 Oleg Verbitsky

On the Largest Common Subgraph Problem

95-02 Uwe Schöning

Complexity of Presburger Arithmetic with Fixed Quantifier Dimension

95-03 Harry Buhrman,Thomas Thierauf

The Complexity of Generating and Checking Proofs of Membership

95-04 Rainer Schuler, Tomoyuki Yamakami

Structural Average Case Complexity

95-05 Klaus Achatz, Wolfram Schulte

Architecture Indepentent Massive Parallelization of Divide-And-Conquer Algorithms

95-06 Christoph Karg, Rainer Schuler

Structure in Average Case Complexity

95-07 P. Dadam, K. Kuhn, M. Reichert, T. Beuter, M. Nathe

ADEPT: Ein integrierender Ansatz zur Entwicklung flexibler, zuverlässiger

kooperierender Assistenzsysteme in klinischen Anwendungsumgebungen

95-08 Jürgen Kehrer, Peter Schulthess

Aufbereitung von gescannten Röntgenbildern zur filmlosen Diagnostik

95-09 Hans-Jörg Burtschick, Wolfgang Lindner

On Sets Turing Reducible to P-Selective Sets

95-10 Boris Hartmann

Berücksichtigung lokaler Randbedingung bei globaler Zieloptimierung mit neuronalen

Netzen am Beispiel Truck Backer-Upper

95-12 Klaus Achatz, Wolfram Schulte

Massive Parallelization of Divide-and-Conquer Algorithms over Powerlists

95-13 Andrea Mößle, Heiko Vogler

Efficient Call-by-value Evaluation Strategy of Primitive Recursive Program Schemes

95-14 Axel Dold, Friedrich W. von Henke, Holger Pfeifer, Harald Rueß

A Generic Specification for Verifying Peephole Optimizations

96-01 Ercüment Canver, Jan-Tecker Gayen, Adam Moik

Formale Entwicklung der Steuerungssoftware für eine elektrisch ortsbediente Weiche

mit VSE

96-02 Bernhard Nebel

Solving Hard Qualitative Temporal Reasoning Problems: Evaluating the Efficiency of

Using the ORD-Horn Class

96-03 Ton Vullinghs, Wolfram Schulte, Thilo Schwinn

An Introduction to TkGofer

96-04 Thomas Beuter, Peter Dadam

Anwendungsspezifische Anforderungen an Workflow-Mangement-Systeme am

Beispiel der Domäne Concurrent-Engineering

96-05 Gerhard Schellhorn, Wolfgang Ahrendt

Verification of a Prolog Compiler - First Steps with KIV

96-06 Manindra Agrawal, Thomas Thierauf

Satisfiability Problems

96-07 Vikraman Arvind, Jacobo Torán

A nonadaptive NC Checker for Permutation Group Intersection

96-08 David Cyrluk, Oliver Möller, Harald Rueß

An Efficient Decision Procedure for a Theory of Fix-Sized Bitvectors with

Composition and Extraction

96-09 Bernd Biechele, Dietmar Ernst, Frank Houdek, Joachim Schmid, Wolfram Schulte

Erfahrungen bei der Modellierung eingebetteter Systeme mit verschiedenen SA/RT–

Ansätzen

96-10 Falk Bartels, Axel Dold, Friedrich W. von Henke, Holger Pfeifer, Harald Rueß

Formalizing Fixed-Point Theory in PVS

96-11 Axel Dold, Friedrich W. von Henke, Holger Pfeifer, Harald Rueß

Mechanized Semantics of Simple Imperative Programming Constructs

96-12 Axel Dold, Friedrich W. von Henke, Holger Pfeifer, Harald Rueß

Generic Compilation Schemes for Simple Programming Constructs

96-13 Klaus Achatz, Helmuth Partsch

From Descriptive Specifications to Operational ones: A Powerful Transformation

Rule, its Applications and Variants

97-01 Jochen Messner

Pattern Matching in Trace Monoids

97-02 Wolfgang Lindner, Rainer Schuler

A Small Span Theorem within P

97-03 Thomas Bauer, Peter Dadam

A Distributed Execution Environment for Large-Scale Workflow Management

Systems with Subnets and Server Migration

97-04 Christian Heinlein, Peter Dadam

Interaction Expressions - A Powerful Formalism for Describing Inter-Workflow

Dependencies

97-05 Vikraman Arvind, Johannes Köbler

On Pseudorandomness and Resource-Bounded Measure

97-06 Gerhard Partsch

Punkt-zu-Punkt- und Mehrpunkt-basierende LAN-Integrationsstrategien für den

digitalen Mobilfunkstandard DECT

97-07 Manfred Reichert, Peter Dadam

ADEPTflex - Supporting Dynamic Changes of Workflows Without Loosing Control

97-08 Hans Braxmeier, Dietmar Ernst, Andrea Mößle, Heiko Vogler

The Project NoName - A functional programming language with its development

environment

97-09 Christian Heinlein

Grundlagen von Interaktionsausdrücken

97-10 Christian Heinlein

Graphische Repräsentation von Interaktionsausdrücken

97-11 Christian Heinlein

Sprachtheoretische Semantik von Interaktionsausdrücken

97-12 Gerhard Schellhorn, Wolfgang Reif

Proving Properties of Finite Enumerations: A Problem Set for Automated Theorem

Provers

97-13 Dietmar Ernst, Frank Houdek, Wolfram Schulte, Thilo Schwinn

Experimenteller Vergleich statischer und dynamischer Softwareprüfung für

eingebettete Systeme

97-14 Wolfgang Reif, Gerhard Schellhorn

Theorem Proving in Large Theories

97-15 Thomas Wennekers

Asymptotik rekurrenter neuronaler Netze mit zufälligen Kopplungen

97-16 Peter Dadam, Klaus Kuhn, Manfred Reichert

Clinical Workflows - The Killer Application for Process-oriented Information

Systems?

97-17 Mohammad Ali Livani, Jörg Kaiser

EDF Consensus on CAN Bus Access in Dynamic Real-Time Applications

97-18 Johannes Köbler,Rainer Schuler

Using Efficient Average-Case Algorithms to Collapse Worst-Case Complexity

Classes

98-01 Daniela Damm, Lutz Claes, Friedrich W. von Henke, Alexander Seitz, Adelinde

Uhrmacher, Steffen Wolf

Ein fallbasiertes System für die Interpretation von Literatur zur Knochenheilung

98-02 Thomas Bauer, Peter Dadam

Architekturen für skalierbare Workflow-Management-Systeme - Klassifikation und

Analyse

98-03 Marko Luther, Martin Strecker

A guided tour through Typelab

98-04 Heiko Neumann, Luiz Pessoa

Visual Filling-in and Surface Property Reconstruction

98-05 Ercüment Canver

Formal Verification of a Coordinated Atomic Action Based Design

98-06 Andreas Küchler

On the Correspondence between Neural Folding Architectures and Tree Automata

98-07 Heiko Neumann, Thorsten Hansen, Luiz Pessoa

Interaction of ON and OFF Pathways for Visual Contrast Measurement

98-08 Thomas Wennekers

Synfire Graphs: From Spike Patterns to Automata of Spiking Neurons

98-09 Thomas Bauer, Peter Dadam

Variable Migration von Workflows in ADEPT

98-10 Heiko Neumann, Wolfgang Sepp

Recurrent V1 – V2 Interaction in Early Visual Boundary Processing

98-11 Frank Houdek, Dietmar Ernst, Thilo Schwinn

Prüfen von C–Code und Statmate/Matlab–Spezifikationen: Ein Experiment

98-12 Gerhard Schellhorn

Proving Properties of Directed Graphs: A Problem Set for Automated Theorem

Provers

98-13 Gerhard Schellhorn, Wolfgang Reif

Theorems from Compiler Verification: A Problem Set for Automated Theorem

Provers

98-14 Mohammad Ali Livani

SHARE: A Transparent Mechanism for Reliable Broadcast Delivery in CAN

98-15 Mohammad Ali Livani, Jörg Kaiser

Predictable Atomic Multicast in the Controller Area Network (CAN)

99-01 Susanne Boll, Wolfgang Klas, Utz Westermann

A Comparison of Multimedia Document Models Concerning Advanced Requirements

99-02 Thomas Bauer, Peter Dadam

Verteilungsmodelle für Workflow-Management-Systeme - Klassifikation und

Simulation

99-03 Uwe Schöning

On the Complexity of Constraint Satisfaction

99-04 Ercument Canver

Model-Checking zur Analyse von Message Sequence Charts über Statecharts

99-05 Johannes Köbler, Wolfgang Lindner, Rainer Schuler

Derandomizing RP if Boolean Circuits are not Learnable

99-06 Utz Westermann, Wolfgang Klas

Architecture of a DataBlade Module for the Integrated Management of Multimedia

Assets

99-07 Peter Dadam, Manfred Reichert

Enterprise-wide and Cross-enterprise Workflow Management: Concepts, Systems,

Applications. Paderborn, Germany, October 6, 1999, GI–Workshop Proceedings,

Informatik ’99

99-08 Vikraman Arvind, Johannes Köbler

Graph Isomorphism is Low for ZPPNP and other Lowness results

99-09 Thomas Bauer, Peter Dadam

Efficient Distributed Workflow Management Based on Variable Server Assignments

2000-02 Thomas Bauer, Peter Dadam

Variable Serverzuordnungen und komplexe Bearbeiterzuordnungen im Workflow-

Management-System ADEPT

2000-03 Gregory Baratoff, Christian Toepfer, Heiko Neumann

Combined space-variant maps for optical flow based navigation

2000-04 Wolfgang Gehring

Ein Rahmenwerk zur Einführung von Leistungspunktsystemen

2000-05 Susanne Boll, Christian Heinlein, Wolfgang Klas, Jochen Wandel

Intelligent Prefetching and Buffering for Interactive Streaming of MPEG Videos

2000-06 Wolfgang Reif, Gerhard Schellhorn, Andreas Thums

Fehlersuche in Formalen Spezifikationen

2000-07 Gerhard Schellhorn, Wolfgang Reif (eds.)

FM-Tools 2000: The 4th Workshop on Tools for System Design and Verification

2000-08 Thomas Bauer, Manfred Reichert, Peter Dadam

Effiziente Durchführung von Prozessmigrationen in verteilten Workflow-

Management-Systemen

2000-09 Thomas Bauer, Peter Dadam

Vermeidung von Überlastsituationen durch Replikation von Workflow-Servern in

ADEPT

2000-10 Thomas Bauer, Manfred Reichert, Peter Dadam

Adaptives und verteiltes Workflow-Management

2000-11 Christian Heinlein

Workflow and Process Synchronization with Interaction Expressions and Graphs

2001-01 Hubert Hug, Rainer Schuler

DNA-based parallel computation of simple arithmetic

2001-02 Friedhelm Schwenker, Hans A. Kestler, Günther Palm

3-D Visual Object Classification with Hierarchical Radial Basis Function Networks

2001-03 Hans A. Kestler, Friedhelm Schwenker, Günther Palm

RBF network classification of ECGs as a potential marker for sudden cardiac death

2001-04 Christian Dietrich, Friedhelm Schwenker, Klaus Riede, Günther Palm

Classification of Bioacoustic Time Series Utilizing Pulse Detection, Time and

Frequency Features and Data Fusion

2002-01 Stefanie Rinderle, Manfred Reichert, Peter Dadam

Effiziente Verträglichkeitsprüfung und automatische Migration von Workflow-

Instanzen bei der Evolution von Workflow-Schemata

2002-02 Walter Guttmann

Deriving an Applicative Heapsort Algorithm

2002-03 Axel Dold, Friedrich W. von Henke, Vincent Vialard, Wolfgang Goerigk

A Mechanically Verified Compiling Specification for a Realistic Compiler

2003-01 Manfred Reichert, Stefanie Rinderle, Peter Dadam

A Formal Framework for Workflow Type and Instance Changes Under Correctness

Checks

2003-02 Stefanie Rinderle, Manfred Reichert, Peter Dadam

Supporting Workflow Schema Evolution By Efficient Compliance Checks

2003-03 Christian Heinlein

Safely Extending Procedure Types to Allow Nested Procedures as Values

2003-04 Stefanie Rinderle, Manfred Reichert, Peter Dadam

On Dealing With Semantically Conflicting Business Process Changes.

2003-05 Christian Heinlein

Dynamic Class Methods in Java

2003-06 Christian Heinlein

Vertical, Horizontal, and Behavioural Extensibility of Software Systems

2003-07 Christian Heinlein

Safely Extending Procedure Types to Allow Nested Procedures as Values

(Corrected Version)

2003-08 Changling Liu, Jörg Kaiser

Survey of Mobile Ad Hoc Network Routing Protocols)

2004-01 Thom Frühwirth, Marc Meister (eds.)

First Workshop on Constraint Handling Rules

2004-02 Christian Heinlein

Concept and Implementation of C+++, an Extension of C++ to Support User-Defined

Operator Symbols and Control Structures

2004-03 Susanne Biundo, Thom Frühwirth, Günther Palm(eds.)

Poster Proceedings of the 27th Annual German Conference on Artificial Intelligence

2005-01 Armin Wolf, Thom Frühwirth, Marc Meister (eds.)

19th Workshop on (Constraint) Logic Programming

2005-02 Wolfgang Lindner (Hg.), Universität Ulm , Christopher Wolf (Hg.) KU Leuven

2. Krypto-Tag – Workshop über Kryptographie, Universität Ulm

2005-03 Walter Guttmann, Markus Maucher

Constrained Ordering

2006-01 Stefan Sarstedt

Model-Driven Development with ACTIVECHARTS, Tutorial

2006-02 Alexander Raschke, Ramin Tavakoli Kolagari

Ein experimenteller Vergleich zwischen einer plan-getriebenen und einer

leichtgewichtigen Entwicklungsmethode zur Spezifikation von eingebetteten

Systemen

2006-03 Jens Kohlmeyer, Alexander Raschke, Ramin Tavakoli Kolagari

Eine qualitative Untersuchung zur Produktlinien-Integration über

Organisationsgrenzen hinweg

2006-04 Thorsten Liebig

Reasoning with OWL - System Support and Insights –

2008-01 H.A. Kestler, J. Messner, A. Müller, R. Schuler

On the complexity of intersecting multiple circles for graphical display

2008-02 Manfred Reichert, Peter Dadam, Martin Jurisch,l Ulrich Kreher, Kevin Göser,

Markus Lauer

Architectural Design of Flexible Process Management Technology

2008-03 Frank Raiser

Semi-Automatic Generation of CHR Solvers from Global Constraint Automata

2008-04 Ramin Tavakoli Kolagari, Alexander Raschke, Matthias Schneiderhan, Ian Alexander

Entscheidungsdokumentation bei der Entwicklung innovativer Systeme für

produktlinien-basierte Entwicklungsprozesse

2008-05 Markus Kalb, Claudia Dittrich, Peter Dadam

Support of Relationships Among Moving Objects on Networks

2008-06 Matthias Frank, Frank Kargl, Burkhard Stiller (Hg.)

WMAN 2008 – KuVS Fachgespräch über Mobile Ad-hoc Netzwerke

2008-07 M. Maucher, U. Schöning, H.A. Kestler

An empirical assessment of local and population based search methods with different

degrees of pseudorandomness

2008-08 Henning Wunderlich

Covers have structure

2008-09 Karl-Heinz Niggl, Henning Wunderlich

Implicit characterization of FPTIME and NC revisited

2008-10 Henning Wunderlich

On span-P and related classes in structural communication complexity

2008-11 M. Maucher, U. Schöning, H.A. Kestler

On the different notions of pseudorandomness

2008-12 Henning Wunderlich

On Toda’s Theorem in structural communication complexity

2008-13 Manfred Reichert, Peter Dadam

Realizing Adaptive Process-aware Information Systems with ADEPT2

2009-01 Peter Dadam, Manfred Reichert

The ADEPT Project: A Decade of Research and Development for Robust and Fexible

Process Support

Challenges and Achievements

2009-02 Peter Dadam, Manfred Reichert, Stefanie Rinderle-Ma, Kevin Göser, Ulrich Kreher,

Martin Jurisch

Von ADEPT zur AristaFlow® BPM Suite – Eine Vision wird Realität “Correctness by

Construction” und flexible, robuste Ausführung von Unternehmensprozessen

2009-03 Alena Hallerbach, Thomas Bauer, Manfred Reichert

Correct Configuration of Process Variants in Provop

2009-04 Martin Bader

On Reversal and Transposition Medians

2009-05 Barbara Weber, Andreas Lanz, Manfred Reichert

Time Patterns for Process-aware Information Systems: A Pattern-based Analysis

2009-06 Stefanie Rinderle-Ma, Manfred Reichert

Adjustment Strategies for Non-Compliant Process Instances

Ulmer Informatik-Berichte

ISSN 0939-5091

Herausgeber:

Universität Ulm

Fakultät für Ingenieurwissenschaften und Informatik

89069 Ulm