Symbolically Aligning Observed and Modelled Behaviour

Vincent Bloemen, Jaco van de Pol, W.M.P. van der Aalst

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    11 Citations (Scopus)
    141 Downloads (Pure)


    Conformance checking is a branch of process mining that aims to assess to what degree a given set of log traces and a corresponding reference model conform to each other. The state-of-the-art approach in conformance checking is based on the concept of alignments. Alignments express the observed behaviour in terms of the reference model while minimizing the number of mismatches between the event data and the model. The currently known best algorithm for constructing alignments applies the A* shortest path algorithm for each trace of event data. In this work, we apply insights from the field of model checking to aid conformance checking. We investigate whether alignments can be computed efficiently via symbolic reachability with decision diagrams. We designed a symbolic algorithm for computing shortest-paths on graphs restricted to 0- and 1-cost edges (which is typical for alignments). We have implemented our approach in the LTSmin model checking toolset and compare its performance with the A* implementation supported by ProM. We generated more than 4000 experiments (Petri net model and log trace combinations) by setting various parameters, and analysed performance and related these to structural properties. Our empirical study shows that the symbolic technique is in general better suited for computing alignments on large models than the A* approach. Our approach is better performing in cases where the size of the state-space tends to blow up. Based on our experiments we conclude that the techniques are complementary, since there is a significant number of cases where A* outperforms the symbolic technique and vice versa.
    Original languageEnglish
    Title of host publication2018 18th International Conference on Application of Concurrency to System Design
    Subtitle of host publicationProceedings
    Number of pages10
    ISBN (Electronic)978-1-5386-7013-2
    ISBN (Print)978-1-5386-7013-2
    Publication statusPublished - 2018
    Event18th International Conference on Application of Concurrency to System Design 2018 - Bratislava, Slovakia
    Duration: 24 Jun 201829 Jun 2018
    Conference number: 18


    Conference18th International Conference on Application of Concurrency to System Design 2018
    Abbreviated titleACSD 2018
    Internet address


    • conformance checking
    • process mining
    • model checking
    • symbolic reachability
    • alignment
    • algorithm
    • graph search


    Dive into the research topics of 'Symbolically Aligning Observed and Modelled Behaviour'. Together they form a unique fingerprint.

    Cite this