=Paper=
{{Paper
|id=Vol-1293/paper12
|storemode=property
|title=From Declarative Processes to Imperative Models
|pdfUrl=https://ceur-ws.org/Vol-1293/paper12.pdf
|volume=Vol-1293
|dblpUrl=https://dblp.org/rec/conf/simpda/PrescherCM14
}}
==From Declarative Processes to Imperative Models==
https://ceur-ws.org/Vol-1293/paper12.pdf
From Declarative Processes
to Imperative Models
Johannes Prescher, Claudio Di Ciccio, and Jan Mendling?
Vienna University of Economics and Business, Vienna, Austria
{johannes.prescher,claudio.di.ciccio,jan.mendling}@wu.ac.at
Abstract. Nowadays organizations support their creation of value by explicitly
defining the processes to be carried out. Processes are specifically discussed from
the angle of simplicity, i.e., how compact and easy to understand they can be
represented. In most cases, organizations rely on imperative models which, how-
ever, become complex and cluttered when it comes to flexibility and optionality.
As an alternative, declarative modeling reveals to be effective under such cir-
cumstances. While both approaches are well known for themselves, there is still
not a deep understanding of their semantic interoperability. With this work, we
examine the latter and show how to obtain an imperative model out of a set of
declarative constraints. To this aim, we devise an approach leading from a De-
clare model to a behaviorally equivalent Petri net. Furthermore, we demonstrate
that any declarative control flow can be represented by means of a Petri net for
which the property of safety always holds true.
1 Introduction
The definition of valid behavior is at the core of every organization in order to support
the creation of value. Such behavior is in most cases modeled using an imperative con-
cept, e.g., by means of notations such as Petri nets [1] or BPMN [18]. They explicitly
describe the options to continue at each state. However, while imperative approaches
are a strong concept when it comes to well-defined processes, they lack clarity once
an observed behavior allows for flexible execution. In this case, models following a
declarative approach are able to describe the behavior in a more compact way [4].
Recent research, however, acknowledges that hardly any of the available represen-
tations would be superior in all circumstances. For instance, it was pointed out that
imperative and declarative models are favoring different types of comprehension tasks
[19, 31]. Therefore, approaches have been proposed to represent a mined process partly
as an imperative model and partly as a declarative model [35]. A problem in this con-
text is, however, to choose which parts would better be shown in either way. In order
to allow for an informed decision, a preliminary question has to be answered: is there a
possibility to represent the same behavior regardless of the notation?
In this paper, we start answering this research question by describing how to derive
an imperative model from a declarative one. We build upon existing work on transfor-
mations from Transition Systems to Petri nets by extending the approach to a tool chain
?
The research leading to these results has received funding from EU Seventh Framework Pro-
gramme (FP7) under grant agreement 318275 (GET Service).
that leads from a Declare model to a behaviorally equivalent Petri net. We implemented
and tested our approach using the logs of the BPI Challenge from 2013. Lastly, we show
that the imperative version always holds the property of safety.
The paper is structured as follows. Section 2 defines the background of our re-
search, namely preliminaries of different representations including automata, transition
systems, Petri nets, and Declare. Section 3 defines our transformation approach. Sec-
tion 4 demonstrates the feasibility of our approach using a prototypical implementation
applied to the BPI Challenge 2013. Section 5 discusses related work before Section 6
concludes the paper.
2 Background
In this section, we discuss Finite State Automata as generic, yet verbose representations
of behavior. Then, we revisit the essential concepts of Petri nets. Finally, we introduce
Declare as a representation based on behavioral constraints.
b d p+t
a s1 b a c
b d
p q r s t
s0 d q+r+t p+r+s
c d b
s2 a c c a
q + 2r + s
Fig. 1: A process be- Fig. 2: A Petri net P Fig. 3: The Reachability
havior as an FSA Graph of P
2.1 Finite State Automata
In general, a process can be described as a stateful artifact characterized by its conver-
sational behavior, i.e., its potential evolutions resulting from the interaction with some
external system, such as a client service. The finite set of possible interactions consti-
tutes the so-called process alphabet. The conversational behavior can be represented
as a Finite State Automaton (FSA). Its transitions are labeled by process activities, un-
der the assumption that each legal run of the system corresponds to a conversation
supported by the process. A process behavior is represented by a finite deterministic
Transition System S = hA, S, s0 , δ, S f i, where: A is the process alphabet; S is the fi-
nite non-empty set of states; s0 ∈ S is the initial state; δ : S × A → S is the transition
a
function (by s − → s0 we denote that, from state s, transition a leads to state s0 ); S f ⊆ S
is the set of final states.
The initial and final states respectively correspond to a legal initialization and ter-
mination of the process lifecycle. W.l.o.g., we assume that every state is reachable by
traversing the automaton, starting from the initial state. Thus, in Figure 1, the process
would admit the instance to either (i) perform activity a and then b an arbitrary number
of times, and finally d, then terminate, or (ii) perform c once and terminate. We can
consider FSAs to be for process modeling what Assembly is for computer program-
ming. FSAs are simple and valuable in terms of expressive power, but have problems
modeling concurrency succinctly. Suppose that there are n parallel activities, i.e., all n
activities need to be executed but any order is allowed. There are n! possible execution
sequences. The FSA thus requires 2n states and n × 2n − 1 transitions. This is an ex-
ample of the well-known “state explosion” problem. Concurrency is known to be well
handled by Petri nets.
2.2 Petri nets
Petri nets (PNs) originate from the Ph.D. thesis of Carl Adam Petri [30]. A PN is a
directed bipartite graph. Its vertices can be divided into two disjoint finite sets consisting
of places and transitions. Every arc of a PN connects a place to a transition or vice versa,
but neither two places nor two transitions can be directly connected. Formally, a Petri
net is a tuple P = hP, T, F i, where:
– P is a finite set of places;
– T is a finite set of transitions;
– F ⊆ (P × T ) ∪ (T × P ) is the flow relation.
Places in a PN may contain a discrete number of marks called tokens. Any distribution
of tokens over the places represents a configuration of the net called marking. For-
mally, a marking of a PN is a multiset of its places, i.e., a mapping M : P → N. We
say the marking assigns a number of tokens (graphically represented as black dots) to
each place; it represents a state of the system and can be regarded as a vector of non-
negative integers of length P . We thus denote a marking M as a linear combination
of places, where the linear factor corresponds to the number of tokens in the place.
In the following, we will adopt either the vectorial or the polynomial notation (e.g.,
M0 = (1, 0, 0, 0, 1) for states p, q, r, s, t in Figure 2, which we also denote as p + t)
to this extent. A transition t ∈ T of a PN may fire whenever there are sufficient tokens
at the start of all input arcs; when it fires, it consumes these tokens, and puts tokens
at the end of all output arcs. Thus, t leads from a marking M1 ∈ M to a marking
t
M2 ∈ M (M1 → − M2 ). In other words, M2 is reachable from M1 by means of t.
Firings are atomic, i.e., single non-interruptible steps. PNs are always associated to an
initial marking M0 , denoting the initial status of the described system. The set of all
markings reachable from M0 is called its reachability set. A PN with initial marking
M0 is k-bounded iff for every reachable marking M , no place contains more than k
tokens (k is the minimal number for which this holds). A 1-bounded net is called safe.
Figure 2 depicts a 2-bounded PN. A labeled Petri net is a PN with labeling function
λ : T → A, which puts into correspondence every transition of the net with a symbol
(called label) from the alphabet A. Henceforth, we will refer to labeled PNs simply as
PNs, for the sake of conciseness.
Thus, modeling a process in terms of a Petri net is rather straightforward: (i) activ-
ities are modeled by transitions; (ii) conditions are modeled by places; (iii) cases are
modeled by tokens. Figure 2 depicts the parallel evolution of two separate branches of
the execution, one involving a loop of c’s and d’s, the other involving loops of a’s and
b’s.
Constraint Regular expression Notation
Participation(a) [ˆa]*(a[ˆa]*)+[ˆa]*
Existence constraints AtMostOne(a) [ˆa]*(a)?[ˆa]*
Init(a) a.*
End(a) .*a
RespondedExistence(a, b) [ˆa]*((a.*b.*)|(b.*a.*))*[ˆa]*
Response(a, b) [ˆa]*(a.*b)*[ˆa]*
AlternateResponse(a, b) [ˆa]*(a[ˆa]*b[ˆa]*)*[ˆa]*
Relation constraints ChainResponse(a, b) [ˆa]*(ab[ˆa]*)*[ˆa]*
Precedence(a, b) [ˆb]*(a.*b)*[ˆb]*
AlternatePrecedence(a, b) [ˆb]*(a[ˆb]*b[ˆb]*)*[ˆb]*
ChainPrecedence(a, b) [ˆb]*(ab[ˆb]*)*[ˆb]*
CoExistence(a, b) [ˆab]*((a.*b.*)|(b.*a.*))*[ˆab]*
Mutual relation Succession(a, b) [ˆab]*(a.*b)*[ˆab]*
constraints
AlternateSuccession(a, b) [ˆab]*(a[ˆab]*b[ˆab]*)*[ˆab]*
ChainSuccession(a, b) [ˆab]*(ab[ˆab]*)*[ˆab]*
NotChainSuccession(a, b) [ˆa]*(aa*[ˆab][ˆa]*)*([ˆa]*|a)
Negative relation NotSuccession(a, b) [ˆa]*(a[ˆb]*)*[ˆab]*
constraints
NotCoExistence(a, b) [ˆab]*((a[ˆb]*)|(b[ˆa]*))?
Table 1: Semantics of Declare constraints as POSIX Regular Expressions [17]
Reachability Graph and Bisimulation The Reachability Graph (RG) of a PN is a
Transition System in which (i) the set of states is the reachability set (every state is
thus a reachable marking), (ii) the alphabet coincides with the one of the net, and
t
(iii) M1 →− M2 iff there exists a transition t in the net that leads from marking M1 to
M2 . Figure 3 depicts the Reachability Graph for the PN of Figure 2. With a slight abuse
of terminology, we will thus refer to the bisimulation [27] of a Petri net and a Transi-
tion System, meaning that the Reachability Graph of the PN and the Transition System
(TS) are bisimilar. We recall here that bisimulation relation is a behavioral equivalence
relation, which entails the impossibility for an external user to distinguish the behavior
of the two systems. As a consequence, the two systems are trace-equivalent (see [22]).
2.3 Declare Constraints
The need for flexibility in the definition of some types of process has lead to an al-
ternative to the classical “imperative” approach: the “declarative” one. The classical
approach is called “imperative” (or also “procedural”) because it explicitly represents
every step allowed by the process model at hand, by means of transitions (the possible
actions to do) among places/states (the legal situations where the process can wait or
terminate). This leads to the likely increase of graphical objects as the process allows
more alternative executions. The size of the model, though, has undesirable effects on
understandability and likelihood of errors – see for instance work on process modeling
c, b b, c
c a, c b a, c, b c
b
c a b
b, c a, b, c a, c a, b a, c
a a b a c a
(a) Participation(a) (b) Rspd.Exist.(a, b) (c) CoExistence(a, c) (d) NotCoExist.(a, b)
Fig. 4: FSAs accepting Declare constraints, on process alphabet A = {a, b, c}
guidelines [25]. In fact, larger models tend to be more difficult to understand [26], not to
mention the higher error probability from which they suffer, with respect to small mod-
els [24]. Rather than using a procedural language for expressing the allowed sequences
of activities, it is based on the description of workflows through the usage of constraints:
the idea is that every task can be performed, as long as its execution does not violate
any of the specified constraints [29]. Declare [4] is a language defining an extensible
set of templates for constraints. Declare constraint templates can be divided into two
main types: existence constraints CE , and relation constraints CR . The former consists
of constraint templates constraining single activities. As such, existence constraints can
be expressed as predicates over one variable (the constrained activity): CE (x). The lat-
ter comprises rules that are imposed on target activities, when activation tasks occur.
Relation constraints thus correspond to predicates of arity two: CR (x, y). Process al-
phabet A is the domain of interpretation for constraints. Given a (possibly empty) set
of existence constraints of size m > 0 (resp. relation constraints, of size n > 0) inter-
A A
preted over alphabet A, each denoted as CE i
(x) (resp. CRj
(x, y)), the declarative model
A A A A
consists of their conjunction: CE1 (x) ∧ . . . ∧ CEm (x) ∧ CR1 (x, y) ∧ . . . ∧ CR n
(x, y).
Participation(a) is an existence constraint, which requires the execution of a at
least once in every process instance. AtMostOne(a) is its dual, as it specifies that
a is not executed more than once in a process instance. End (a) requires that a oc-
curs in every case as the last activity carried out. RespondedExistence(a, b) is a re-
lation constraint. It imposes that if a is performed at least once during the enact-
ment of the process, b must be executed at least once as well, either in the future
or in the past, with respect to the time in which a is carried out. Response(a, b) en-
forces RespondedExistence(a, b) by specifying that b must occur eventually after-
wards. AlternateResponse(a, b) adds to Response(a, b) the condition that no other
a’s occur between an execution of a and a subsequent b. Two specializations of the
relation constraints are mutual relation constraints and negative relation constraints.
Mutual relation constraints are such that both constrained activities are activation and
target. For instance, CoExistence(a, c) is a mutual relation constraint requiring that if
a is executed, then c must be performed as well, and vice versa, in any order. Neg-
ative relation constraints are such that both constrained activities are activation and
target as well. However, the occurrence of one activity excludes the occurrence of the
other. For instance, NotCoExistence(a, b) is a negative relation constraint imposing
that if a is executed, then b cannot be performed at all in the trace, and vice versa.
Decl. Constraints Reg. Expressions Automaton Petri net
Petri net
synthesis
Fig. 5: Obtaining imperative processes as Petri nets from declarative constraints.
NotSuccession(a, b) is a looser constraint, because it requires that no b’s occur after
a (and therefore no a’s before b). NotChainSuccession(a, b) requires that the next ac-
tivity after a cannot be b. An example of graphical representation for a simple Declare
process model is drawn in Figure 6a.
The semantics of Declare templates have been expressed as formulations of several
formal languages: as Linear Temporal Logic over Finite Traces (LTLf ) formulas [14],
in [13]; as SCIFF integrity constraints [6], in [8]; as First Order Logic (FOL) formulas,
interpreted on finite traces, in [16], based on [14]; as Regular Expressions (REs) in
[17]. In particular, our work will build upon the last translation, as explained in the next
section. Table 1 reports the semantics of Declare constraints as REs. In the table, as
well as in the remainder of this paper, we adopt POSIX standard shortcuts for REs, for
the sake of brevity. Therefore, in addition to the known Kleene star (*), alternation (|)
and concatenation ( ) operators, we make use here of (i) the . and [ˆx] shortcuts for
respectively matching any character in the alphabet, or any character but x, (ii) the +
and ? operators for respectively matching from one to any, or none to one, occurrences
of the preceding expression. We will also utilize the intersection operator & for REs.
3 Conceptual Framework
In this section, we show an approach that describes how to compute a Petri net corre-
sponding to a Declare process model. This approach serves as a conceptual framework
for proving that there always exists a Petri net which is bisimilar to a Declare process
model. Furthermore, the returned PN is proven to be safe. The computation consists of
three main steps, as sketched in Figure 5.
Declarative constraints to Regular Expressions. We represent all declarative con-
straints as REs. Each constraint maps to a single RE, i.e., the mapping is one-to-one (cf.
Table 1). REs apply to characters. Owing to this, our approach identifies each activity
in the process alphabet with a character.
Regular Expressions to Finite State Automaton. The allowed behavior is given by
the conjunction of all Declare constraints. Hence, it maps to the intersection of the lan-
guages accepted by corresponding REs, i.e., the language accepted by the conjunction
of the REs (which is in turn a RE itself, being Regular Expressions close w.r.t. the con-
junction operation [21]). For the sake of conciseness, though, single REs are thought to
directly refer to those activities (characters). They are constrained by the corresponding
c
a, c
a
a, c, b b
c
a p2 c
b
p3 a
a p4 c
b a a
b b
p1
b, c
(a) Declare (b) FSA (c) PN
Fig. 6: A Declare model, consisting of constraints Participation(a),
RespondedExistence(a, b) and CoExistence(a, c), represented with the Declare
graphical notation, as a Finite State Automaton and as a Petri net
constraint, disregarding the rest of the process alphabet in their formulation. Consider,
for example, Participation(a), depicted in Table 1. The corresponding RE requires the
occurrence of a at least once, but also allows any other input beforehand and afterwards.
Therefore, we need to limit the set of allowed characters to those which identify activ-
ities in the process alphabet A (see Section 2). This is obtained by means of another
RE, which is put in conjunction with the constraint-related ones. This way, we can de-
fine the declarative process model described by N constraints by means of a Regular
Expression, derived from the conjunction of N + 1 REs.
As an example, we consider a process consisting of the following three constraints
and having process alphabet A = {a, b, c}:
– Participation(a), translating to [ˆa]*(a[ˆa]*)+[ˆa]*, referred to as
(re1),
– RespondedExistence(a, b), translating to [ˆa]*((a.*b.*)|(b.*a.*))*[ˆa]*,
referred to as (re2), and
– CoExistence(a, c), translating to [ˆaˆc]*((a.*c.*)|(c.*a.*))*[ˆaˆc]*,
referred to as (re3).
The mere conjunction of (re1), (re2) and (re3) would still allow not only
for the characters representing activities but also for any input character. In order to
limit input characters to those which identify activities in the process alphabet, we thus
conjunct the aforementioned three to the following: ([abc]*). As a result, the final
RE is: (re1) & (re2) & (re3) & ([abc]*).
Continuing with our computation, we transform the RE into the corresponding FSA.
We recall here indeed that regular grammars are recognizable through Regular Expres-
sions [9]. Figures 4a to 4c depict the FSAs accepting the languages of (re1), (re2)
and (re3), respectively. Figure 6b shows the FSA which results from the example
we provided. Aside of the transitions that do not change its state, the FSA allows two
different runs before reaching its final state, i.e. either ha, bi or hb, ai.
Finite State Automaton to Petri net. In the last step of our approach, we derive a Petri
net from the FSA. For this purpose, we rely on the theory of regions described in [12],
adopted to synthesize PNs from state-based models, such as Transition Systems (and
thus, a fortiori, FSAs). The rationale behind the theory of regions is to conglomerate
sets of places that share the same input and output transitions in common regions. The
regions translate to places in the derived PN. Input transitions lead to them, and output
transitions start from them. In particular, we adopt the approach described in [11], which
is proven to return a safe Petri net from a Transition System, ensuring the bisimilarity
between the two systems (see Section 2.2).
Figure 6c shows the Petri net stemming from the application of the technique of
Cortadella et al. [11] to the FSA of our example. Just as the FSA, it contains four places
(p1 , p2 , p3 , p4 ) and has the initial marking M = (1, 0, 1, 0), i.e., it contains a token
in p1 and p3 . However, the places of the Petri net do not correspond directly to the
states of the FSA. Instead (again, without considering the firings that do not change
the marking), just as the FSA, the PN allows two different runs (ha, bi and hb, ai).
As the final state of the FSA allows for the execution of any activity in the process
alphabet (any character of the input alphabet), the PN also allows for this behavior
when its marking is M = (0, 1, 0, 1). Please note that such marking is reachable only
by means of the sequence of firings that replicate the sequence of characters leading to
the accepting state of the FSA.
The reader can notice that the returned net presents multiple transitions labeled the
same, i.e., representing the same activity. This is due to the fact that label-splitting
can be avoided for derived safe PNs only if the Transition System has the property
of excitation closure for its transitions, i.e., only if the intersection of those states from
which the transitions start can be grouped in one single activating region [11]. However,
such property is not guaranteed from the FSAs that Declare processes translate to. Later
work of Carmona et al. [7] shows how to balance the trade-off between k-boundedness
of the returned Petri net and the number of splitted labels.
To sum up, applying the steps mentioned above, we derive an imperative model
from declarative constraints. Note that the operations we perform are transformations
that do not alter the behavior. Thus, not only the declarative constraints but also the
Regular Expression, the FSA and the PN represent the same behavioral characteris-
tics of the process. Furthermore, we have demonstrated by construction the following
theorem.
Theorem 1. Given any Declare process model PD consisting of n > 0 existence
Vmand Am > 0Vrelation
constraints constraints, expressed over process alphabet A,
n A
PD = C
i=1 Ei (x) ∧ C
j=1 Rj (x, y), there always exist a safe Petri net model
PN = hP, T, F i labeled by λ : T → A, which is bisimilar to PD and is safe.
4 Evaluation by Implementation
In this section, we present a feasibility evaluation of our proposed concepts based on
a prototypical implementation. We first describe the implementation. Then, we present
the results of its application on a Declare model generated from a log of the BPI Chal-
lenge 2013. Finally, we discuss insights from the case.
Completed
Completed
Accepted Completed
Accepted
Accepted Accepted
Unmatched
Completed
Completed
Completed
Queued
Completed
Accepted Queued
Accepted Queued Queued
Accepted
Completed Queued
Queued Accepted
Accepted
Accepted
Queued Accepted
Completed Completed
Completed
Queued Accepted
(a) Declare model (b) Finite State Automaton derived from the Declare model
Fig. 7: The process mined out of BPIC 2013 log [33], as Declare model and FSA
4.1 Implementation
In order to have the opportunity to analyze real-life declarative process models, we
have integrated our approach with a tool for the mining of declarative control flows
from event logs (see Figure 5), namely MINERful [15]. The MINERful framework
comes with an integrated support of a library called dk.bricks.automaton [28], for the
generation of FSAs out of Regular Expressions. We extended the integrated MINERful-
dk.bricks.automaton tool in order to make it capable of serializing FSAs into TSML-
encoded files. TSML (Transition System Markup Language) is indeed a format sup-
ported by ProM, the Process Mining Toolkit [3]. In this way, we have been able to ap-
ply the ProM plug-in by van Dongen (see [5]), capable of converting a TSML-encoded
Transition System into a Petri net, by using Petrify (see [10]).
4.2 Application to the BPI Challenge 2013
As a real-world data set for validating the approach, we selected the “BPI Challenge
2013, closed problems” log [33] as an application case. For the control-flow dis-
covery task, we have considered the activities’ names as their identifiers (Accepted,
Completed, Queued and Unmatched). We have set MINERful up in order to return
those constraints proven to be valid in every trace (support threshold equal to 1). The
discovered model consisted of the following 10 constraints:
Response(Queued, Accepted) End(Completed)
NotChainSuccession(Queued, Completed) NotSuccession(Completed, Unmatched)
Response(Queued, Completed) AtMostOne(Unmatched)
NotChainSuccession(Queued, Unmatched) RespondedExistence(Unmatched, Accepted)
Response(Accepted, Completed) AlternateResponse(Unmatched, Completed)
The graphical representation of the model is depicted in Figure 7a. Figure 7b draws
the Finite State Automaton derived from the Declare model, and Figure 8 shows the
final outcome, as a Petri net. What we can observe from the comparison of the Declare
model and the behavior-equivalent Petri net is the multiplication of various activities.
a
a a
q a
q q a
c
c a q q c c
q a
a
c c
a u
c a
a
c
c
c
q
q
Fig. 8: The Petri net derived from the Finite State Automaton representing the De-
clare model mined out of BPIC 2013 log [33]. Labels are abbreviated: a = “Accepted”,
c = “Completed”, u = “Unmatched”, q = “Queued”.
Although the Declare model seems to be more compact in terms of its nodes and edges,
it must be noted that the Petri net is presented as it was produced, i.e., it has not been
subject to any post-processing for reducing its complexity. However, the defined chain
of transformations provide us with the basis to study the trade-off between compactness
of the model and richness of the language in future experiments, conducted on behavior-
equivalent Petri nets and Declare models.
5 Related work
The stream of research on the comparison of declarative and imperative modeling ap-
proaches has been discussed considering different perspectives. In [32], Pichler et al.
investigate both imperative and declarative languages with respect to process model
understanding. The issue of maintainability for both languages is discussed in [20]. An
open problem for this experimental stream of research has been the question of what
a fair comparison is for declarative and imperative models. In this regard, the work of
[35] and [36] elaborates on mixed representations as a combination of both approaches
from a modeling perspective.
Furthermore, research on automatic process discovery techniques has been defined
based on different representations and different techniques of discovery beyond the
classical alpha miner [2]. Our selection is not meant to be exhaustive, but rather high-
lights those approaches that use constraints, automata or transition systems. Van der
Aalst et al. propose a two-step approach in [5] in order to discover transition systems
which are then synthesized to Petri nets using the “theory of regions”. As well as Van
der Aalst et al., Maruster et al. suggested an approach for process discovery in which
they deal with noise and imbalance in process logs ([23]). A tool manipulating concur-
rent specifications, synthesis and optimization of asynchronous controllers is presented
in [10]. In order to come up with a better understanding of the mutual strengths and
weaknesses of these approaches, De Weerdt et al. ([34]) provide an extensive, multi-
dimensional survey of existing process discovery algorithms using real-life event logs.
Different representations are, however, not discussed in this survey. In this way, our
work provides a basis for an extensive comparison in the future.
6 Conclusion
In this paper, we described an approach to derive imperative process models from
declarative process control-flows. To this extent, we utilize a sequence of steps, leading
from declarative constraints to Regular Expressions, then to a Finite State Automaton,
and finally to a Petri net. We implemented our integrative approach as part of the MIN-
ERful software package and evaluated it using the real world case of the BPI Challenge
2013. A remaining limitation is that we do not provide a sound solution for a transfor-
mation from an arbitrary imperative model into a declarative representation. In future
research, we will address this issue. Furthermore, we plan to utilize the transformation
in the design of experiments to study the mutual benefits of PNs and Declare models in
model comprehension tasks.
References
1. van der Aalst, W.M.P.: The application of petri nets to workflow management. Journal of
Circuits, Systems, and Computers 8(1), 21–66 (1998)
2. van der Aalst, W.M.P.: Process Mining: Discovery, Conformance and Enhancement of Busi-
ness Processes. Springer (2011)
3. van der Aalst, W.M.P., van Dongen, B.F., Günther, C.W., Rozinat, A., Verbeek, E., Weijters,
T.: ProM: The process mining toolkit. In: BPM (Demos) (2009)
4. van der Aalst, W.M.P., Pesic, M.: DecSerFlow: Towards a truly declarative service flow lan-
guage. In: WS-FM. pp. 1–23 (2006)
5. van der Aalst, W.M.P., Rubin, V., Verbeek, H.M.W., van Dongen, B.F., Kindler, E., Günther,
C.W.: Process mining: a two-step approach to balance between underfitting and overfitting.
Software and System Modeling 9(1), 87–111 (2010)
6. Alberti, M., Chesani, F., Gavanelli, M., Lamma, E., Mello, P., Torroni, P.: Verifiable agent
interaction in abductive logic programming: The sciff framework. ACM Trans. Comput. Log.
9(4), 29:1–29:43 (2008)
7. Carmona, J., Cortadella, J., Kishinevsky, M.: New region-based algorithms for deriving
bounded petri nets. IEEE Trans. Computers 59(3), 371–384 (2010)
8. Chesani, F., Lamma, E., Mello, P., Montali, M., Riguzzi, F., Storari, S.: Exploiting induc-
tive logic programming techniques for declarative process mining. T. Petri Nets and Other
Models of Concurrency 2, 278–295 (2009)
9. Chomsky, N., Miller, G.A.: Finite state languages. Information and Control 1(2), 91–112
(1958)
10. Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: a tool
for manipulating concurrent specifications and synthesis of asynchronous controllers. IEICE
Transactions 80(3), 315–325 (1997)
11. Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving petri nets from finite
transition systems. IEEE Trans. Comput. 47(8), 859–882 (1998)
12. Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Synthesizing petri nets from
state-based models. In: Proc. of ICCAD’95. pp. 164–171 (November 1995)
13. De Giacomo, G., De Masellis, R., Montali, M.: Reasoning on ltl on finite traces: Insensitivity
to infiniteness. In: AAAI (2014)
14. De Giacomo, G., Vardi, M.Y.: Linear temporal logic and linear dynamic logic on finite traces.
In: IJCAI (2013)
15. Di Ciccio, C., Mecella, M.: A two-step fast algorithm for the automated discovery of declar-
ative workflows. In: Proc. of CIDM, Singapore 2013. pp. 135–142. IEEE (2013)
16. Di Ciccio, C., Mecella, M.: On the discovery of declarative control flows for artful processes.
ACM Transactions on Management Information Systems (2014)
17. Di Ciccio, C., Mecella, M., Scannapieco, M., Zardetto, D., Catarci, T.: MailOfMine – an-
alyzing mail messages for mining artful collaborative processes. In: Data-Driven Process
Discovery and Analysis, vol. 116, pp. 55–81. Springer (2012)
18. Dumas, M., La Rosa, M., Mendling, J., Reijers, H.A.: Fundamentals of Business Process
Management. Springer (2013)
19. Fahland, D., Lübke, D., Mendling, J., Reijers, H.A., Weber, B., Weidlich, M., Zugal, S.:
Declarative versus imperative process modeling languages: The issue of understandability.
In: BMMDS/EMMSAD. pp. 353–366 (2009)
20. Fahland, D., Mendling, J., Reijers, H.A., Weber, B., Weidlich, M., Zugal, S.: Declarative
versus imperative process modeling languages: The issue of maintainability. In: Business
Process Management Workshops. pp. 477–488 (2009)
21. Gisburg, S., Rose, G.F.: Preservation of languages by transducers. Information and Control
9(2), 153 – 176 (1966)
22. van Glabbeek, R.J., Weijland, W.P.: Branching time and abstraction in bisimulation seman-
tics. J. ACM 43(3), 555–600 (1996)
23. Maruster, L., Weijters, A.J.M.M., van der Aalst, W.M.P., van den Bosch, A.: A rule-based
approach for process discovery: Dealing with noise and imbalance in process logs. Data Min.
Knowl. Discov. 13(1), 67–87 (2006)
24. Mendling, J., Neumann, G., van der Aalst, W.M.P.: Understanding the occurrence of errors
in process models based on metrics. In: OTM Conferences (1). pp. 113–130 (2007)
25. Mendling, J., Reijers, H.A., van der Aalst, W.M.P.: Seven process modeling guidelines
(7PMG). Information & Software Technology 52(2), 127–136 (2010)
26. Mendling, J., Reijers, H.A., Cardoso, J.: What makes process models understandable? In:
BPM. pp. 48–63 (2007)
27. Milner, R.: An algebraic definition of simulation between programs. In: IJCAI. pp. 481–489
(1971)
28. Møller, A.: dk.bricks.automaton (2011)
29. Pesic, M., Schonenberg, M.H., Sidorova, N., van der Aalst, W.M.P.: Constraint-based work-
flow models: Change made easy. In: OTM Conferences (1). pp. 77–94 (2007)
30. Petri, C.A.: Kommunikation mit Automaten. Ph.D. thesis, Institut für instrumentelle Mathe-
matik, Bonn (1962)
31. Pichler, P., Weber, B., Zugal, S., Pinggera, J., Mendling, J., Reijers, H.A.: Imperative versus
declarative process modeling languages: An empirical investigation. In: Business Process
Management Workshops (1). pp. 383–394 (2011)
32. Pichler, P., Weber, B., Zugal, S., Pinggera, J., Mendling, J., Reijers, H.A.: Imperative versus
declarative process modeling languages: An empirical investigation. In: Business Process
Management Workshops (1). pp. 383–394 (2011)
33. Steeman, W.: Real-life event logs – an incident management process: closed problems. Third
International Business Process Intelligence Challenge (BPIC’13) (2013)
34. Weerdt, J.D., Backer, M.D., Vanthienen, J., Baesens, B.: A multi-dimensional quality as-
sessment of state-of-the-art process discovery algorithms using real-life event logs. Inf. Syst.
37(7), 654–676 (2012)
35. Westergaard, M., Slaats, T.: Cpn tools 4: A process modeling tool combining declarative and
imperative paradigms. In: BPM (Demos) (2013)
36. Westergaard, M., Slaats, T.: Mixing paradigms for more comprehensible models. In: BPM.
pp. 283–290 (2013)