{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T07:43:16Z","timestamp":1772696596755,"version":"3.50.1"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,6,1]],"date-time":"2015-06-01T00:00:00Z","timestamp":1433116800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Kurt G\u00f6del Research Fellowship"},{"name":"Kurt G\u00f6del Society"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p>\n            Process discovery has emerged as a powerful approach to support the analysis and the design of complex processes. It consists of analyzing a set of traces registering the sequence of tasks performed along several enactments of a transactional system, in order to build a process model that can explain all the episodes recorded over them. An approach to accomplish this task is presented that can benefit from the background knowledge that, in many cases, is available to the analysts taking care of the process (re-)design. The approach is based on encoding the information gathered from the log and the (possibly) given background knowledge in terms of\n            <jats:italic>precedence constraints<\/jats:italic>\n            , that is, of constraints over the topology of the resulting process models. Mining algorithms are eventually formulated in terms of reasoning problems over precedence constraints, and the computational complexity of such problems is thoroughly analyzed by tracing their tractability frontier. Solution algorithms are proposed and their properties analyzed. These algorithms have been implemented in a prototype system, and results of a thorough experimental activity are discussed.\n          <\/jats:p>","DOI":"10.1145\/2710020","type":"journal-article","created":{"date-parts":[[2015,6,2]],"date-time":"2015-06-02T15:13:25Z","timestamp":1433258005000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Process Discovery under Precedence Constraints"],"prefix":"10.1145","volume":"9","author":[{"given":"Gianluigi","family":"Greco","sequence":"first","affiliation":[{"name":"University of Calabria, Italy"}]},{"given":"Antonella","family":"Guzzo","sequence":"additional","affiliation":[{"name":"University of Calabria, Italy"}]},{"given":"Francesco","family":"Lupia","sequence":"additional","affiliation":[{"name":"University of Calabria, Italy"}]},{"given":"Luigi","family":"Pontieri","sequence":"additional","affiliation":[{"name":"ICAR, National Research Council (CNR), Italy"}]}],"member":"320","published-online":{"date-parts":[[2015,6]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/EDOC.2011.12"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645338.650397"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1380572.1380578"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2151688.2151700"},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Paul C. Attie Munindar P. Singh E. Allen Emerson Amit P. Sheth and Marek Rusinkiewicz. 1996. Scheduling workflows by enforcing intertask dependencies. Distributed Systems Engineering 3 (1996) 222--238.  Paul C. Attie Munindar P. Singh E. Allen Emerson Amit P. Sheth and Marek Rusinkiewicz. 1996. Scheduling workflows by enforcing intertask dependencies. Distributed Systems Engineering 3 (1996) 222--238.","DOI":"10.1088\/0967-1846\/3\/4\/003"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1885721.1885749"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.304005"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20511-8_20"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of the 4th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL\u201903)","author":"Kevin C.","unstructured":"Kevin C. W. Chen and David Y. Y. Yun. 2003. Discovering process models from execution history by graph matching . In Proceedings of the 4th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL\u201903) . 887--892. Kevin C. W. Chen and David Y. Y. Yun. 2003. Discovering process models from execution history by graph matching. In Proceedings of the 4th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL\u201903). 887--892."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00899-3_16"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2006.08.009"},{"key":"e_1_2_2_12_1","volume-title":"Process Mining: Extending the &alpha;-Algorithm to Mine Short Loops. Technical Report","author":"Alves de Medeiros Ana Karla","year":"2004","unstructured":"Ana Karla Alves de Medeiros , Boudewijn F. van Dongen , Wil M. P. van der Aalst , and A. J. M. M. Weijters . 2004 . Process Mining: Extending the &alpha;-Algorithm to Mine Short Loops. Technical Report . University of Technology , Eindhoven. Ana Karla Alves de Medeiros, Boudewijn F. van Dongen, Wil M. P. van der Aalst, and A. J. M. M. Weijters. 2004. Process Mining: Extending the &alpha;-Algorithm to Mine Short Loops. Technical Report. University of Technology, Eindhoven."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-006-0061-7"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401919"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CIDM.2011.5949428"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2012.02.004"},{"key":"e_1_2_2_17_1","volume-title":"Constraint networks. Encyclopedia of Artificial Intelligence","author":"Dechter Rina","year":"1992","unstructured":"Rina Dechter . 1992. Constraint networks. Encyclopedia of Artificial Intelligence ( 1992 ), 276--285. Rina Dechter. 1992. Constraint networks. Encyclopedia of Artificial Intelligence (1992), 276--285."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30359-3_2"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/240080.240252"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218843006001463"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1577069.1577113"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.4018\/jdwm.2007100106"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the 20th European Conference on Artificial Intelligence (ECAI\u201912)","author":"Greco Gianluigi","year":"2012","unstructured":"Gianluigi Greco , Antonella Guzzo , and Luigi Pontieri . 2012 . Process discovery via precedence constraints . In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI\u201912) . 366--371. Gianluigi Greco, Antonella Guzzo, and Luigi Pontieri. 2012. Process discovery via precedence constraints. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI\u201912). 366--371."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.123"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.05.002"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2005.02.006"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/1099-1174(200006)9:2<67::AID-ISAF186>3.0.CO;2-7"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compind.2003.10.002"},{"key":"e_1_2_2_29_1","first-page":"3113","article-title":"A novel approach for mining stochastic process model from workflow logs","volume":"7","author":"Hu Haiyang","year":"2011","unstructured":"Haiyang Hu , Jianen Xie , and Hua Hu . 2011 . A novel approach for mining stochastic process model from workflow logs . Journal of Computational Information Systems 7 , 9 (2011), 3113 -- 3126 . Haiyang Hu, Jianen Xie, and Hua Hu. 2011. A novel approach for mining stochastic process model from workflow logs. Journal of Computational Information Systems 7, 9 (2011), 3113--3126.","journal-title":"Journal of Computational Information Systems"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 12th International Conference on Advanced Information Systems Engineering (AOIS\u201900+CAiSE\u201900)","author":"Joeris Gregor","year":"2000","unstructured":"Gregor Joeris . 2000 . Decentralized and Flexible Workflow Enactment Based on Task Coordination Agents . In Proceedings of the 12th International Conference on Advanced Information Systems Engineering (AOIS\u201900+CAiSE\u201900) . 41--62. Gregor Joeris. 2000. Decentralized and Flexible Workflow Enactment Based on Task Coordination Agents. In Proceedings of the 12th International Conference on Advanced Information Systems Engineering (AOIS\u201900+CAiSE\u201900). 41--62."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020571"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of the 17th Australasian Database Conference (ADC\u201906)","author":"Lu Ruopeng","year":"2006","unstructured":"Ruopeng Lu , Shazia Sadiq , Vineet Padmanabhan , and Guido Governatori . 2006 . Using a temporal constraint network for business process execution . In Proceedings of the 17th Australasian Database Conference (ADC\u201906) . 157--166. Ruopeng Lu, Shazia Sadiq, Vineet Padmanabhan, and Guido Governatori. 2006. Using a temporal constraint network for business process execution. In Proceedings of the 17th Australasian Database Conference (ADC\u201906). 157--166."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31095-9_18"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40176-3_8"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the 2011 IEEE Symposium on Computational Intelligence and Data Mining (CIDM\u201911)","author":"Maggi Fabrizio Maria","unstructured":"Fabrizio Maria Maggi , Arjan J. Mooij , and Wil M. P . van der Aalst. 2011. User-guided discovery of declarative process models . In Proceedings of the 2011 IEEE Symposium on Computational Intelligence and Data Mining (CIDM\u201911) . 192--199. Fabrizio Maria Maggi, Arjan J. Mooij, and Wil M. P. van der Aalst. 2011. User-guided discovery of declarative process models. In Proceedings of the 2011 IEEE Symposium on Computational Intelligence and Data Mining (CIDM\u201911). 192--199."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557092"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the 17th International SPIN Conference on Model Checking Software (SPIN\u201910)","author":"Pesic Maja","unstructured":"Maja Pesic , Dragan Bosnacki , and Wil M. P . van der Aalst. 2010. Enacting declarative languages using LTL: Avoiding errors and improving performance . In Proceedings of the 17th International SPIN Conference on Model Checking Software (SPIN\u201910) . 146--161. Maja Pesic, Dragan Bosnacki, and Wil M. P. van der Aalst. 2010. Enacting declarative languages using LTL: Avoiding errors and improving performance. In Proceedings of the 17th International SPIN Conference on Model Checking Software (SPIN\u201910). 146--161."},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of the Business Process Management Demonstration Track (BPM\u201909)","author":"Pesic Maja","unstructured":"Maja Pesic , Helen Schonenberg , and Wil M. P . van der Aalst. 2009. DECLARE demo: A constraint-based workflow management system . In Proceedings of the Business Process Management Demonstration Track (BPM\u201909) (Demos). Maja Pesic, Helen Schonenberg, and Wil M. P. van der Aalst. 2009. DECLARE demo: A constraint-based workflow management system. In Proceedings of the Business Process Management Demonstration Track (BPM\u201909) (Demos)."},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 2007 OTM Confederated International Conference on On the Move to Meaningful Internet Systems: CoopIS, DOA, ODBASE, GADA, and IS\u2014Volume Part I (OTM\u201907)","author":"Pesic Maja","unstructured":"Maja Pesic , M. H. Schonenberg , Natalia Sidorova , and Wil M. P . van der Aalst. 2007. Constraint-Based Workflow Models: Change Made Easy . In Proceedings of the 2007 OTM Confederated International Conference on On the Move to Meaningful Internet Systems: CoopIS, DOA, ODBASE, GADA, and IS\u2014Volume Part I (OTM\u201907) . 77--94. Maja Pesic, M. H. Schonenberg, Natalia Sidorova, and Wil M. P. van der Aalst. 2007. Constraint-Based Workflow Models: Change Made Easy. In Proceedings of the 2007 OTM Confederated International Conference on On the Move to Meaningful Internet Systems: CoopIS, DOA, ODBASE, GADA, and IS\u2014Volume Part I (OTM\u201907). 77--94."},{"key":"e_1_2_2_40_1","volume-title":"Transactions on Petri Nets and Other Models of Concurrency II","author":"Reichert Manfred","unstructured":"Manfred Reichert , Stefanie Rinderle-Ma , and Peter Dadam . 2009. Transactions on Petri Nets and Other Models of Concurrency II . Springer-Verlag , Berlin , 115--135. Manfred Reichert, Stefanie Rinderle-Ma, and Peter Dadam. 2009. Transactions on Petri Nets and Other Models of Concurrency II. Springer-Verlag, Berlin, 115--135."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2007.07.001"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2004.05.002"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1761141.1761146"},{"key":"e_1_2_2_45_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases (VLDB\u201902)","author":"Senkul Pinar","unstructured":"Pinar Senkul , Michael Kifer , and Ismail H. Toroslu . 2002. A logical framework for scheduling workflows under resource allocation constraints . In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB\u201902) . 694--702. Pinar Senkul, Michael Kifer, and Ismail H. Toroslu. 2002. A logical framework for scheduling workflows under resource allocation constraints. In Proceedings of the 28th International Conference on Very Large Data Bases (VLDB\u201902). 694--702."},{"key":"e_1_2_2_46_1","volume-title":"Jan Vanthienen, and Bart Baesens.","author":"van den Broucke Seppe K. L. M.","year":"2013","unstructured":"Seppe K. L. M. van den Broucke , Jochen De Weerdt , Jan Vanthienen, and Bart Baesens. 2013 . A comprehensive benchmarking framework (CoBeFra) for conformance analysis between procedural process models and event logs in ProM. In Proceedings of 2013 IEEE Symposium on Computational Intelligence and Data Mining (CIDM\u2019 13). 254--261. Seppe K. L. M. van den Broucke, Jochen De Weerdt, Jan Vanthienen, and Bart Baesens. 2013. A comprehensive benchmarking framework (CoBeFra) for conformance analysis between procedural process models and event logs in ProM. In Proceedings of 2013 IEEE Symposium on Computational Intelligence and Data Mining (CIDM\u201913). 254--261."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126698000043"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19345-3"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31131-4_5"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1045"},{"key":"e_1_2_2_51_1","volume-title":"Proceedings of the 22nd International Conference on Concurrency Theory (CONCUR\u201911)","author":"Wil M.","unstructured":"Wil M. P. van der Aalst, Arya Adriansyah, and Boudewijn F. van Dongen. 2011. Causal nets: A modeling language tailored towards process discovery . In Proceedings of the 22nd International Conference on Concurrency Theory (CONCUR\u201911) . 28--42. Wil M. P. van der Aalst, Arya Adriansyah, and Boudewijn F. van Dongen. 2011. Causal nets: A modeling language tailored towards process discovery. In Proceedings of the 22nd International Conference on Concurrency Theory (CONCUR\u201911). 28--42."},{"key":"e_1_2_2_52_1","volume-title":"Proceedings of EPK\u201902","author":"Wil M.","unstructured":"Wil M. P. van der Aalst, J\u00f6rg Desel, and Ekkart Kindler. 2002. On the semantics of EPCs: A vicious circle . In Proceedings of EPK\u201902 . 71--80. Wil M. P. van der Aalst, J\u00f6rg Desel, and Ekkart Kindler. 2002. On the semantics of EPCs: A vicious circle. In Proceedings of EPK\u201902. 71--80."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00450-009-0057-9"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-023X(03)00066-1"},{"key":"e_1_2_2_55_1","volume-title":"van Hee","author":"van der Aalst Wil M. P.","year":"2002","unstructured":"Wil M. P. van der Aalst and Kees M . van Hee . 2002 . Workflow Management : Models, Methods, and Systems. MIT Press . Wil M. P. van der Aalst and Kees M. van Hee. 2002. Workflow Management: Models, Methods, and Systems. MIT Press."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.47"},{"key":"e_1_2_2_57_1","first-page":"3","article-title":"Process discovery using integer linear programming","volume":"94","author":"van der Werf Jan Martijn","year":"2009","unstructured":"Jan Martijn van der Werf , Boudewijn F. van Dongen , Cor A. J. Hurkens , and Alexander Serebrenik . 2009 . Process discovery using integer linear programming . Fundamenta Informaticae 94 , 3 -- 4 (2009), 387--412. Jan Martijn van der Werf, Boudewijn F. van Dongen, Cor A. J. Hurkens, and Alexander Serebrenik. 2009. Process discovery using integer linear programming. Fundamenta Informaticae 94, 3--4 (2009), 387--412.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/11494744_25"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39850-9_13"},{"key":"e_1_2_2_60_1","volume-title":"Proceedings of the Belgian\/Netherlands Artificial Intelligence Conference (BNAIC\u201901)","author":"A. J. M.","unstructured":"A. J. M. M. Weijters and Wil M. P. van der Aalst. 2001. Process mining: Discovering workflow models from event-based data . In Proceedings of the Belgian\/Netherlands Artificial Intelligence Conference (BNAIC\u201901) . 283--290. A. J. M. M. Weijters and Wil M. P. van der Aalst. 2001. Process mining: Discovering workflow models from event-based data. In Proceedings of the Belgian\/Netherlands Artificial Intelligence Conference (BNAIC\u201901). 283--290."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/1273320.1273325"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10844-007-0052-1"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2010.06.001"},{"key":"e_1_2_2_65_1","volume-title":"ter Hofstede, and Colin J. Fidge","author":"Wynn Moe Thandar","year":"2009","unstructured":"Moe Thandar Wynn , Chun Ouyang , Arthur H. M. ter Hofstede, and Colin J. Fidge . 2009 . Workflow Support for Product Recall Coordination. Technical Report. BPMcenter .org. Moe Thandar Wynn, Chun Ouyang, Arthur H. M. ter Hofstede, and Colin J. Fidge. 2009. Workflow Support for Product Recall Coordination. Technical Report. BPMcenter.org."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2710020","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2710020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:01:09Z","timestamp":1750276869000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2710020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1145\/2710020"],"URL":"https:\/\/doi.org\/10.1145\/2710020","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6]]},"assertion":[{"value":"2014-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}