Optimized SAT encoding of conformance checking artefacts
Visualitza/Obre
Cita com:
hdl:2117/331252
Tipus de documentArticle
Data publicació2021-01
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
ProjecteMODELOS Y METODOS BASADOS EN GRAFOS PARA LA COMPUTACION EN GRAN ESCALA (AEI-TIN2017-86727-C2-1-R)
Abstract
Conformance checking is a growing discipline that aims at assisting organizations in monitoring their processes. On its core, conformance checking relies on the computation of particular artefacts which enable reasoning on the relation between observed and modeled behavior. It is widely acknowledge that the computation of these artifacts is the lion’s share of conformance checking techniques. This paper shows how important conformance artefacts like alignments, anti-alignments or multi-alignments, defined over the Levenshtein edit distance, can be efficiently computed by encoding the problem as an optimized SAT instance. From a general perspective, the work advocates for a unified family of techniques that can compute conformance artefacts in the same way. The implementation of the techniques presented in this paper show capabilities for dealing with both synthetic and real-life instances, which may open the door for a fresh way of applying conformance checking in the near future.
CitacióBoltenhagen, M.; Chatain, T.; Carmona, J. Optimized SAT encoding of conformance checking artefacts. "Computing", Gener 2021, vol. 103, p. 29-50.
ISSN0010-485X
Versió de l'editorhttps://link.springer.com/article/10.1007%2Fs00607-020-00831-8
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
Boltenhagen et al.pdf | 365,5Kb | Visualitza/Obre |