Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces

Axel Kjeld Fjelrad Christfort; Tijs Slaats

doi:10.1007/978-3-031-41620-0_1

Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces

Axel Kjeld Fjelrad Christfort^*, Tijs Slaats

^*Corresponding author af dette arbejde

Software, Data, People & Society

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

4 Citationer (Scopus)

3 Downloads (Pure)

Abstract

Dynamic Condition Response (DCR) Graphs is a popular declarative process modelling notation which is supported by commercial modelling tools and has seen significant industrial adoption. The problem of aligning traces with DCR Graphs, with it’s multitude of applications such as conformance checking and log repair, has surprisingly not been solved yet. In this paper we address this open gap in the research by developing an algorithm for efficiently computing the optimal alignment of a DCR Graph and a trace. We evaluate the algorithm on the PDC 2022 dataset, showing that even for large models and traces alignment problems can be solved within milliseconds, and present a case study based on test-driven modelling.

Originalsprog	Engelsk
Titel	Business Process Management - 21st International Conference, BPM 2023, Proceedings
Redaktører	Chiara Di Francescomarino, Andrea Burattin, Christian Janiesch, Shazia Sadiq
Antal sider	17
Forlag	Springer
Publikationsdato	2023
Sider	3-19
ISBN (Trykt)	9783031416194
DOI	https://doi.org/10.1007/978-3-031-41620-0_1
Status	Udgivet - 2023
Begivenhed	Proceedings of the 21st International Conference on Business Process Management , BPM 2023 - Utrecht, Holland Varighed: 11 sep. 2023 → 15 sep. 2023

Konference

Konference	Proceedings of the 21st International Conference on Business Process Management , BPM 2023
Land/Område	Holland
By	Utrecht
Periode	11/09/2023 → 15/09/2023

Navn	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind	14159 LNCS
ISSN	0302-9743

Bibliografisk note

Funding Information:
This work is supported by Digital Research Centre Denmark (DIREC). We acknowledge Søren Debois for sharing his Isabelle/HOL DCR Graph formalization.

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Adgang til dokumentet

10.1007/978-3-031-41620-0_1

FulltextIndsendt manuskript, 2,1 MBLicens: Ikke-specificeret

Citationsformater

Christfort, A. K. F., & Slaats, T. (2023). Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces. I C. Di Francescomarino, A. Burattin, C. Janiesch, & S. Sadiq (red.), Business Process Management - 21st International Conference, BPM 2023, Proceedings (s. 3-19). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Bind 14159 LNCS https://doi.org/10.1007/978-3-031-41620-0_1

Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces. / Christfort, Axel Kjeld Fjelrad ; Slaats, Tijs.

Business Process Management - 21st International Conference, BPM 2023, Proceedings. red. / Chiara Di Francescomarino; Andrea Burattin; Christian Janiesch; Shazia Sadiq. Springer, 2023. s. 3-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 14159 LNCS).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Christfort, AKF & Slaats, T 2023, Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces. i C Di Francescomarino, A Burattin, C Janiesch & S Sadiq (red), Business Process Management - 21st International Conference, BPM 2023, Proceedings. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), bind 14159 LNCS, s. 3-19, Proceedings of the 21st International Conference on Business Process Management , BPM 2023, Utrecht, Holland, 11/09/2023. https://doi.org/10.1007/978-3-031-41620-0_1

Christfort AKF , Slaats T. Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces. I Di Francescomarino C, Burattin A, Janiesch C, Sadiq S, red., Business Process Management - 21st International Conference, BPM 2023, Proceedings. Springer. 2023. s. 3-19. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 14159 LNCS). https://doi.org/10.1007/978-3-031-41620-0_1

Christfort, Axel Kjeld Fjelrad ; Slaats, Tijs. / Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces. Business Process Management - 21st International Conference, BPM 2023, Proceedings. red. / Chiara Di Francescomarino ; Andrea Burattin ; Christian Janiesch ; Shazia Sadiq. Springer, 2023. s. 3-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 14159 LNCS).

@inproceedings{b138f7c46aa240238e318192f7114509,

title = "Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces",

abstract = "Dynamic Condition Response (DCR) Graphs is a popular declarative process modelling notation which is supported by commercial modelling tools and has seen significant industrial adoption. The problem of aligning traces with DCR Graphs, with it{\textquoteright}s multitude of applications such as conformance checking and log repair, has surprisingly not been solved yet. In this paper we address this open gap in the research by developing an algorithm for efficiently computing the optimal alignment of a DCR Graph and a trace. We evaluate the algorithm on the PDC 2022 dataset, showing that even for large models and traces alignment problems can be solved within milliseconds, and present a case study based on test-driven modelling.",

keywords = "Conformance checking, DCR graphs, Declarative process models, Test-driven Modelling, Trace alignment",

author = "Christfort, {Axel Kjeld Fjelrad} and Tijs Slaats",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; Proceedings of the 21st International Conference on Business Process Management , BPM 2023 ; Conference date: 11-09-2023 Through 15-09-2023",

year = "2023",

doi = "10.1007/978-3-031-41620-0_1",

language = "English",

isbn = "9783031416194",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "3--19",

editor = "{Di Francescomarino}, Chiara and Andrea Burattin and Christian Janiesch and Shazia Sadiq",

booktitle = "Business Process Management - 21st International Conference, BPM 2023, Proceedings",

address = "Switzerland",

}

TY - GEN

T1 - Efficient Optimal Alignment Between Dynamic Condition Response Graphs and Traces

AU - Christfort, Axel Kjeld Fjelrad

AU - Slaats, Tijs

PY - 2023

Y1 - 2023

N2 - Dynamic Condition Response (DCR) Graphs is a popular declarative process modelling notation which is supported by commercial modelling tools and has seen significant industrial adoption. The problem of aligning traces with DCR Graphs, with it’s multitude of applications such as conformance checking and log repair, has surprisingly not been solved yet. In this paper we address this open gap in the research by developing an algorithm for efficiently computing the optimal alignment of a DCR Graph and a trace. We evaluate the algorithm on the PDC 2022 dataset, showing that even for large models and traces alignment problems can be solved within milliseconds, and present a case study based on test-driven modelling.

AB - Dynamic Condition Response (DCR) Graphs is a popular declarative process modelling notation which is supported by commercial modelling tools and has seen significant industrial adoption. The problem of aligning traces with DCR Graphs, with it’s multitude of applications such as conformance checking and log repair, has surprisingly not been solved yet. In this paper we address this open gap in the research by developing an algorithm for efficiently computing the optimal alignment of a DCR Graph and a trace. We evaluate the algorithm on the PDC 2022 dataset, showing that even for large models and traces alignment problems can be solved within milliseconds, and present a case study based on test-driven modelling.

KW - Conformance checking

KW - DCR graphs

KW - Declarative process models

KW - Test-driven Modelling

KW - Trace alignment

U2 - 10.1007/978-3-031-41620-0_1

DO - 10.1007/978-3-031-41620-0_1

M3 - Article in proceedings

AN - SCOPUS:85172235408

SN - 9783031416194

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 19

BT - Business Process Management - 21st International Conference, BPM 2023, Proceedings

A2 - Di Francescomarino, Chiara

A2 - Burattin, Andrea

A2 - Janiesch, Christian

A2 - Sadiq, Shazia

PB - Springer

T2 - Proceedings of the 21st International Conference on Business Process Management , BPM 2023

Y2 - 11 September 2023 through 15 September 2023

ER -