On the semantics of EPCs - Efficient calculation and simulation

Authors

  • Nicolas Cuntz Computer Graphics and Multimedia Systems Group University of Siegen
  • Ekkart Kindler Software Engineering Group University of Paderborn

DOI:

https://doi.org/10.18417/emisa.1.1.2

Abstract

One of the most debatable features of Event driven Process Chains (EPCs) is their non-local semantics, which results in some difficulties when formalising their semantics. Recently, we have overcome these problems by using techniques from fixed-point theory for defining the semantics of an EPC, which consists of a pair of related transition relations. This fixed-point characterisation of the semantics of EPCs provides a mathematical characterisation of the semantics of EPCs only. For simulating an EPC based on this semantics, we need an efficient way for calculating the corresponding pair of transition relations. A naive implementation of the underlying fixed-point iteration for calculating the transition relations results in a practically useless algorithm.

In this paper, we show how to calculate the semantics of an EPC in a more efficient way by employing different techniques and optimisations from symbolic model checking. We also analysed all kinds of simplifications of EPCs to make the calculation of the semantics more efficient, but it turned out that most of these techniques are ineffective. Still, our algorithms are fast enough for simulating practical size EPCs.


In order to demonstrate the efficiency of our algorithms and data structures, we have started an open source project called EPC Tools, which could be a good starting point for an open source tool for the EPC community.

Downloads

Published

2015-12-07

Issue

Vol. 1 No. 1 (2005)

Section

Research Articles

License

Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal 'Enterprise Modelling and Information Systems Architectures - International Journal of Conceptual Modeling' and the Gesellschaft für Informatik e.V. (GI) the permission of first publication, and the non-exclusive, irrevocable and non-time limited publication permission for the submitted work including the permissions to store, copy, distribute and reproduce their work in printed and electronic form for the duration of the legal copyright. This includes the right of translation. Authors grant the journal 'Enterprise Modelling and Information Systems Architectures - International Journal of Conceptual Modeling' and the Gesellschaft für Informatik e.V. (GI) the permission to license their work under a Creative Commons BY-SA 4.0 license that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book) given an acknowledgement of its initial publication in this journal.

Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access). The submitting corresponding author on behalf of all co-authors asserts that she/he is entitled to the granting of the above mentioned permissions for the submitted work.