{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:11:18Z","timestamp":1760710278024,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MINECO and FEDER","award":["TIN2017-86727-C2-1-R"],"award-info":[{"award-number":["TIN2017-86727-C2-1-R"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this article, a novel approach is presented to tackle the challenge of computing an alignment for large-problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further improvement is possible. The implementation of the presented technique reveals a magnificent reduction both in computation time and in memory usage. Moreover, although the proposed technique does not guarantee the derivation of an alignment with minimal cost, the experiments show that in practice the quality of the obtained solutions is close to optimal.<\/jats:p>","DOI":"10.1145\/3394056","type":"journal-article","created":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T16:19:41Z","timestamp":1591028381000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Computing Alignments of Well-Formed Process Models using Local Search"],"prefix":"10.1145","volume":"29","author":[{"given":"Farbod","family":"Taymouri","sequence":"first","affiliation":[{"name":"The University of Melbourne, Melbourne, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9656-254X","authenticated-orcid":false,"given":"Josep","family":"Carmona","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}]}],"member":"320","published-online":{"date-parts":[[2020,6]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2018. 4TU: Centre for Research Data. http:\/\/researchdata.4tu.nl\/hom  2018. 4TU: Centre for Research Data. http:\/\/researchdata.4tu.nl\/hom"},{"volume-title":"Proceedings of the BPM Demo Track 2016 Co-located with the 14th International Conference on Business Process Management (BPM 2016","year":"2016","author":"Burattin Andrea","key":"e_1_2_1_3_1"},{"volume-title":"Conformance Checking - Relating Processes and Models","author":"Carmona Josep","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2017.03.047"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"J. Desel and J. Esparza. 1993. Reachability in cyclic extended free-choice systems. TCS 114. Elsevier Science Publishers B.V. (1993).  J. Desel and J. Esparza. 1993. Reachability in cyclic extended free-choice systems. TCS 114. Elsevier Science Publishers B.V. (1993).","DOI":"10.1016\/0304-3975(93)90154-L"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"J. Desel and J. Esparza. 1995. Free Choice Petri Nets. Cambridge University Press Cambridge Great Britain.  J. Desel and J. Esparza. 1995. Free Choice Petri Nets. Cambridge University Press Cambridge Great Britain.","DOI":"10.1017\/CBO9780511526558"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008743212620"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2017.2668418"},{"key":"e_1_2_1_10_1","unstructured":"Gurobi Optimization Inc. 2016. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com.  Gurobi Optimization Inc. 2016. Gurobi Optimizer Reference Manual. http:\/\/www.gurobi.com."},{"volume-title":"Trace Alignment in Process Mining: Opportunities for Process Diagnostics","author":"Jagadeesh Chandra Bose R. P.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2008.08.005"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10270-016-0545-x"},{"volume-title":"Van Der Aalst","year":"2014","author":"Munoz-Gama Jorge","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.24143"},{"edition":"5","volume-title":"Foundations of Algorithms","author":"Neapolitan Richard","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980764"},{"volume-title":"Marcello La Rosa, and Abel Armas-Cervantes","year":"2017","author":"Rei\u00dfner Daniel","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2007.07.001"},{"volume-title":"Computer Science: Lectures on Petri Nets I: Basic Models","year":"1998","author":"Silva M.","key":"e_1_2_1_21_1"},{"volume-title":"ALI: Alignment for Large Instances. https:\/\/www.cs.upc.edu\/taymouri\/tool.html.","year":"2017","author":"Taymouri Farbod","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45348-4_12"},{"volume-title":"Proceedings of the 6th International Symposium on Data-driven Process Discovery and Analysis (SIMPDA 2016","year":"2016","author":"Taymouri Farbod","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7127-5"},{"volume-title":"Process Mining - Data Science in Action","author":"van der Aalst Wil M. P.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-010-0161-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59536-8_7"},{"volume-title":"Proceedings of the 16th International Conference on Business Process Management, (BPM 2018","year":"2018","author":"van Dongen Boudewijn F.","key":"e_1_2_1_29_1"},{"volume-title":"Proceedings of the 26th International Conference on Applications and Theory of Petri Nets (ICATPN\u201905)","author":"van Dongen B. F.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.130"},{"volume-title":"Merging Alignments for Decomposed Replay","author":"Verbeek H. M. W.","key":"e_1_2_1_32_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-39086-4_14"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394056","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3394056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:12Z","timestamp":1750193232000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3394056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3394056"],"URL":"https:\/\/doi.org\/10.1145\/3394056","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"type":"print","value":"1049-331X"},{"type":"electronic","value":"1557-7392"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}