{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:03Z","timestamp":1750309143137,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T00:00:00Z","timestamp":1713398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"EPSRC Centre for Doctoral Training in High Performance Embedded and Distributed Systems HiPEDS","award":["EP\/L016796\/1"],"award-info":[{"award-number":["EP\/L016796\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2024,5,31]]},"abstract":"<jats:p>Models such as finite state automata are widely used to abstract the behavior of software systems by capturing the sequences of events observable during their execution. Nevertheless, models rarely exist in practice and, when they do, get easily outdated; moreover, manually building and maintaining models is costly and error-prone. As a result, a variety of model inference methods that automatically construct models from execution traces have been proposed to address these issues.<\/jats:p>\n          <jats:p>However, performing a systematic and reliable accuracy assessment of inferred models remains an open problem. Even when a reference model is given, most existing model accuracy assessment methods may return misleading and biased results. This is mainly due to their reliance on statistical estimators over a finite number of randomly generated traces, introducing avoidable uncertainty about the estimation and being sensitive to the parameters of the random trace generative process.<\/jats:p>\n          <jats:p>This article addresses this problem by developing a systematic approach based on analytic combinatorics that minimizes bias and uncertainty in model accuracy assessment by replacing statistical estimation with deterministic accuracy measures. We experimentally demonstrate the consistency and applicability of our approach by assessing the accuracy of models inferred by state-of-the-art inference tools against reference models from established specification mining benchmarks.<\/jats:p>","DOI":"10.1145\/3640332","type":"journal-article","created":{"date-parts":[[2024,1,16]],"date-time":"2024-01-16T12:01:59Z","timestamp":1705406519000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Rigorous Assessment of Model Inference Accuracy using Language Cardinality"],"prefix":"10.1145","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5190-8957","authenticated-orcid":false,"given":"Donato","family":"Clun","sequence":"first","affiliation":[{"name":"Imperial College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0840-6449","authenticated-orcid":false,"given":"Donghwan","family":"Shin","sequence":"additional","affiliation":[{"name":"University of Sheffield, Sheffield, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9646-646X","authenticated-orcid":false,"given":"Antonio","family":"Filieri","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4854-685X","authenticated-orcid":false,"given":"Domenico","family":"Bianculli","sequence":"additional","affiliation":[{"name":"University of Luxembourg, Luxembourg, Luxembourg"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,4,18]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_15"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236064"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025151"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5009015"},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-540-24698-5_30","volume-title":"LATIN 2004: Theoretical Informatics","author":"Bodirsky Manuel","year":"2004","unstructured":"Manuel Bodirsky, Tobias G\u00e4rtner, Timo von Oertzen, and Jan Schwinghammer. 2004. Efficiently computing the density of regular languages. In LATIN 2004: Theoretical Informatics, Mart\u00edn Farach-Colton (Ed.). Springer Berlin, 262\u2013270."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SEFM.2008.17"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1963.263416"},{"key":"e_1_3_3_9_2","first-page":"82","volume-title":"Proceedings of the Vision Interface","volume":"2000","author":"Bunke Horst","year":"2000","unstructured":"Horst Bunke. 2000. Graph matching: Theoretical foundations, algorithms, and applications. In Proceedings of the Vision Interface, Vol. 2000. 82\u201388."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2019.00087"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/3-540-45006-8_9","volume-title":"Proceedings of the Case-Based Reasoning Research and Development","author":"Champin Pierre-Antoine","year":"2003","unstructured":"Pierre-Antoine Champin and Christine Solnon. 2003. Measuring the similarity of labeled graphs. In Proceedings of the Case-Based Reasoning Research and Development, Kevin D. Ashley and Derek G. Bridge (Eds.). Springer Berlin, 80\u201395."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231496"},{"key":"e_1_3_3_13_2","volume-title":"Model Checking","author":"Jr Edmund M. Clarke","year":"2018","unstructured":"Edmund M. Clarke Jr, Orna Grumberg, Daniel Kroening, Doron Peled, and Helmut Veith. 2018. Model Checking. MIT press, Cambridge, MA, USA."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/287000.287001"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.040"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998975"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196883"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1007\/978-3-319-04921-2_29","volume-title":"Proceedings of the International Conference on Language and Automata Theory and Applications","author":"Finkbeiner Bernd","year":"2014","unstructured":"Bernd Finkbeiner and Hazem Torfah. 2014. Counting models of linear-time temporal logic. In Proceedings of the International Conference on Language and Automata Theory and Applications, Adrian-Horia Dediu, Carlos Mart\u00edn-Vide, Jos\u00e9-Luis Sierra-Rodr\u00edguez, and Bianca Truthe (Eds.). Springer International Publishing, Cham, 360\u2013371."},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/978-3-319-68167-2_10","volume-title":"Proceedings of the International Symposium on Automated Technology for Verification and Analysis","author":"Finkbeiner Bernd","year":"2017","unstructured":"Bernd Finkbeiner and Hazem Torfah. 2017. The density of linear-time properties. In Proceedings of the International Symposium on Automated Technology for Verification and Analysis, Deepak D\u2019Souza and K. Narayan Kumar (Eds.). Springer International Publishing, Cham, 139\u2013155."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2012.110"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.87284"},{"key":"e_1_3_3_23_2","volume-title":"Mathematica","author":"Inc. Wolfram Research,","year":"2022","unstructured":"Wolfram Research, Inc.2022. Mathematica. Retrieved from https:\/\/www.wolfram.com\/mathematica"},{"key":"e_1_3_3_24_2","first-page":"551","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Kannan Sampath","year":"1995","unstructured":"Sampath Kannan, Z. Sweedyk, and Steve Mahaney. 1995. Counting and random generation of strings in regular languages. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms . Society for Industrial and Applied Mathematics, USA, 551\u2013557."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005027"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2635868.2635890"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2015.83"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/WCRE.2006.47"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1181775.1181808"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1595696.1595761"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2012.04.001"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594331"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1808885.1808891"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2016.2623623"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2017.3"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3387909"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSM.2010.5609576"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139058520"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aci.2018.08.003"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_12"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63390-9_21"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2430545.2430549"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88009-7_20"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-012-9210-3"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-015-9367-7"},{"key":"e_1_3_3_47_2","volume-title":"Maple","author":"Inc.. Waterloo Maple,","year":"2022","unstructured":"Waterloo Maple, Inc..2022. Maple. Retrieved from https:\/\/www.maplesoft.com\/products\/maple\/"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.25596\/jalc-2001-221"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3640332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3640332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:26Z","timestamp":1750287026000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3640332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,18]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5,31]]}},"alternative-id":["10.1145\/3640332"],"URL":"https:\/\/doi.org\/10.1145\/3640332","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"type":"print","value":"1049-331X"},{"type":"electronic","value":"1557-7392"}],"subject":[],"published":{"date-parts":[[2024,4,18]]},"assertion":[{"value":"2022-11-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}