Computational Complexity of Alignments
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918373017780224 |
|---|---|
| author | Schwanen, Christopher T. Pakusa, Wied van der Aalst, Wil M. P. |
| author_facet | Schwanen, Christopher T. Pakusa, Wied van der Aalst, Wil M. P. |
| contents | In process mining, alignments quantify the degree of deviation between an observed event trace and a business process model and constitute the most important conformance checking technique. We study the algorithmic complexity of computing alignments over important classes of Petri nets. First, we show that the alignment problem is PSPACE-complete on the class of safe Petri nets and also on the class of safe and sound workflow nets. For live, bounded, free-choice systems, we prove the existence of optimal alignments of polynomial length which positions the alignment problem in NP for this class. We further show that computing alignments is NP-complete even on basic subclasses such as process trees and T-systems. We establish NP-completeness on several related classes as well, including acyclic systems. Finally, we demonstrate that on live, safe S-systems the alignment problem is solvable in P and that both assumptions (liveness and safeness) are crucial for this result. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05331 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computational Complexity of Alignments Schwanen, Christopher T. Pakusa, Wied van der Aalst, Wil M. P. Formal Languages and Automata Theory In process mining, alignments quantify the degree of deviation between an observed event trace and a business process model and constitute the most important conformance checking technique. We study the algorithmic complexity of computing alignments over important classes of Petri nets. First, we show that the alignment problem is PSPACE-complete on the class of safe Petri nets and also on the class of safe and sound workflow nets. For live, bounded, free-choice systems, we prove the existence of optimal alignments of polynomial length which positions the alignment problem in NP for this class. We further show that computing alignments is NP-complete even on basic subclasses such as process trees and T-systems. We establish NP-completeness on several related classes as well, including acyclic systems. Finally, we demonstrate that on live, safe S-systems the alignment problem is solvable in P and that both assumptions (liveness and safeness) are crucial for this result. |
| title | Computational Complexity of Alignments |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2603.05331 |