Efficiently computing alignments: using the extended marking equation

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    11 Citations (Scopus)
    1 Downloads (Pure)


    Conformance checking is considered to be anything where observed behaviour needs to be related to already modelled behaviour. Fundamental to conformance checking are alignments which provide a precise relation between a sequence of activities observed in an event log and a execution sequence of a model. However, computing alignments is a complex task, both in time and memory, especially when models contain large amounts of parallelism. When computing alignments for Petri nets, (Integer) Linear Programming problems based on the marking equation are typically used to guide the search. Solving such problems is the main driver for the time complexity of alignments. In this paper, we adopt existing work in such a way that (a) the extended marking equation is used rather than the marking equation and (b) the number of linear problems that is solved is kept at a minimum. To do so, we exploit fundamental properties of the Petri nets and we show that we are able to compute optimal alignments for models for which this was previously infeasible. Furthermore, using a large collection of benchmark models, we empirically show that we improve on the state-of-the-art in terms of time and memory complexity.

    Original languageEnglish
    Title of host publicationBusiness Process Management - 16th International Conference, BPM 2018, Proceedings
    EditorsMarco Montali, Ingo Weber, Mathias Weske, Jan vom Brocke
    Place of PublicationCham
    Number of pages18
    ISBN (Electronic)978-3-319-98648-7
    ISBN (Print)978-3-319-98647-0
    Publication statusPublished - 1 Jan 2018
    Event16th International Conference on Business Process Management, BPM 2018 - Sydney, Australia
    Duration: 9 Sep 201814 Sep 2018

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume11080 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference16th International Conference on Business Process Management, BPM 2018


    • Alignments
    • Conformance checking
    • Process Mining

    Fingerprint Dive into the research topics of 'Efficiently computing alignments: using the extended marking equation'. Together they form a unique fingerprint.

    Cite this