{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T20:14:21Z","timestamp":1758053661170,"version":"3.44.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032041661","type":"print"},{"value":"9783032041678","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,15]],"date-time":"2025-09-15T00:00:00Z","timestamp":1757894400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,15]],"date-time":"2025-09-15T00:00:00Z","timestamp":1757894400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We establish a data-driven method for the assessment of the runtime complexity of first-order term rewrite systems (TRSs for short). The fully automated complexity analysis of TRSs has a long tradition in rewriting and numerous sophisticated static analysis methods have been developed. The recent success in machine learning motivates the quest for data-driven analysis techniques, which, while unsound in principle, can potentially return insightful upper bounds on the runtime complexity where traditional (static) techniques fail. We present the first such technique based on bottom-up rule unfolding, akin to a variant of backward narrowing. Further, we employ a dedicated notion of data fitting that is fine-tuned to the estimation of asymptotic complexities. We provide ample experimental data indicating the viability of the approach.<\/jats:p>","DOI":"10.1007\/978-3-032-04167-8_13","type":"book-chapter","created":{"date-parts":[[2025,9,14]],"date-time":"2025-09-14T22:04:08Z","timestamp":1757887448000},"page":"228-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Data-Driven Runtime Complexity Analysis"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1230-4666","authenticated-orcid":false,"given":"Samuel","family":"Frontull","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6555-0060","authenticated-orcid":false,"given":"Manuel","family":"Meitinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9240-6128","authenticated-orcid":false,"given":"Georg","family":"Moser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,9,15]]},"reference":[{"issue":"1\u20132","key":"13_CR1","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/S0304-3975(99)00207-8","volume":"236","author":"T Arts","year":"2000","unstructured":"Arts, T., Giesl, J.: Termination of term rewriting using dependency pairs. Theor. Comput. Sci. 236(1\u20132), 133\u2013178 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(99)00207-8","journal-title":"Theor. Comput. Sci."},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Avanzini, M., Lago, U.D., Moser, G.: Analysing the complexity of functional programs: higher-order meets first-order. In: Proceedings of 20th ICFP, pp. 152\u2013164. ACM (2015). https:\/\/doi.org\/10.1145\/2784731.2784753","DOI":"10.1145\/2784731.2784753"},{"key":"13_CR3","doi-asserted-by":"publisher","unstructured":"Avanzini, M., Moser, G.: Complexity of Acyclic Term Graph Rewriting. In: Proceedings of 1st FSCD. LIPIcs, vol.\u00a052, pp. 10:1\u201310:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPICS.FSCD.2016.10","DOI":"10.4230\/LIPICS.FSCD.2016.10"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-662-49674-9_24","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"M Avanzini","year":"2016","unstructured":"Avanzini, M., Moser, G., Schaper, M.: TcT: Tyrolean Complexity Tool. In: Chechik, M., Raskin, J.-F. (eds.) TACAS 2016. LNCS, vol. 9636, pp. 407\u2013423. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49674-9_24"},{"key":"13_CR5","doi-asserted-by":"publisher","unstructured":"Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998). https:\/\/doi.org\/10.1017\/CBO9781139172752","DOI":"10.1017\/CBO9781139172752"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01201998","volume":"2","author":"SJ Bellantoni","year":"1992","unstructured":"Bellantoni, S.J., Cook, S.A.: A new recursion-theoretic characterization of the polytime functions. Comput. Complex. 2, 97\u2013110 (1992). https:\/\/doi.org\/10.1007\/BF01201998","journal-title":"Comput. Complex."},{"key":"13_CR7","doi-asserted-by":"publisher","unstructured":"Bishop, C.: Pattern Recognition and Machine Learning. Information Science and Statistics, Springer, New York (2006). https:\/\/doi.org\/10.5555\/1162264","DOI":"10.5555\/1162264"},{"issue":"3","key":"13_CR8","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1109\/MS.2020.3016773","volume":"38","author":"M Boehme","year":"2021","unstructured":"Boehme, M., Cadar, C., Roychoudhury, A.: Fuzzing: Challenges and Reflections. IEEE Softw. 38(3), 79\u201386 (2021). https:\/\/doi.org\/10.1109\/MS.2020.3016773","journal-title":"IEEE Softw."},{"issue":"1","key":"13_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/S10817-016-9397-X","volume":"59","author":"F Frohn","year":"2017","unstructured":"Frohn, F., Giesl, J., Hensel, J., Aschermann, C., Str\u00f6der, T.: Lower bounds for runtime complexity of term rewriting. J. Autom. Reason. 59(1), 121\u2013163 (2017). https:\/\/doi.org\/10.1007\/S10817-016-9397-X","journal-title":"J. Autom. Reason."},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/S10817-016-9388-Y","volume":"58","author":"J Giesl","year":"2017","unstructured":"Giesl, J., et al.: Analyzing Program Termination and Complexity Automatically with AProVE. J. Autom. Reason. 58(1), 3\u201331 (2017). https:\/\/doi.org\/10.1007\/S10817-016-9388-Y","journal-title":"J. Autom. Reason."},{"issue":"20","key":"13_CR11","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/0743-1066(94)90034-5","volume":"19","author":"M Hanus","year":"1994","unstructured":"Hanus, M.: The integration of functions into logic programming: From theory to practice. J. Log. Program. 19(20), 583\u2013628 (1994). https:\/\/doi.org\/10.1016\/0743-1066(94)90034-5","journal-title":"J. Log. Program."},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-540-71070-7_32","volume-title":"Automated Reasoning","author":"N Hirokawa","year":"2008","unstructured":"Hirokawa, N., Moser, G.: Automated Complexity Analysis Based on the Dependency Pair Method. In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol. 5195, pp. 364\u2013379. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-71070-7_32"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/3-540-51081-8_107","volume-title":"Rewriting Techniques and Applications","author":"D Hofbauer","year":"1989","unstructured":"Hofbauer, D., Lautemann, C.: Termination proofs and the length of derivations. In: Dershowitz, N. (ed.) RTA 1989. LNCS, vol. 355, pp. 167\u2013177. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/3-540-51081-8_107"},{"key":"13_CR14","doi-asserted-by":"publisher","unstructured":"Hoffmann, J., Das, A., Weng, S.: Towards automatic resource bound analysis for OCaml. In: Proceedings of 44th POPL, pp. 359\u2013373. ACM (2017). https:\/\/doi.org\/10.1145\/3009837.3009842","DOI":"10.1145\/3009837.3009842"},{"issue":"6","key":"13_CR15","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1017\/S0960129521000487","volume":"32","author":"J Hoffmann","year":"2022","unstructured":"Hoffmann, J., Jost, S.: Two decades of automatic amortized resource analysis. Math. Struct. Comput. Sci. 32(6), 729\u2013759 (2022). https:\/\/doi.org\/10.1017\/S0960129521000487","journal-title":"Math. Struct. Comput. Sci."},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/978-3-319-08918-8_19","volume-title":"Rewriting and Typed Lambda Calculi","author":"M Hofmann","year":"2014","unstructured":"Hofmann, M., Moser, G.: Amortised Resource Analysis and Typed Polynomial Interpretations. In: Dowek, G. (ed.) RTA 2014. LNCS, vol. 8560, pp. 272\u2013286. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-08918-8_19"},{"issue":"6","key":"13_CR17","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1017\/S0960129521000232","volume":"32","author":"M Hofmann","year":"2022","unstructured":"Hofmann, M., Leutgeb, L., Obwaller, D., Moser, G., Zuleger, F.: Type-based analysis of logarithmic amortised complexity. Math. Struct. Comput. Sci. 32(6), 794\u2013826 (2022). https:\/\/doi.org\/10.1017\/S0960129521000232","journal-title":"Math. Struct. Comput. Sci."},{"key":"13_CR18","doi-asserted-by":"publisher","unstructured":"Hofmann, M., Moser, G.: Multivariate amortised resource analysis for term rewrite systems. In: Proceedings of 13th TLCA. LIPIcs, vol.\u00a038, pp. 241\u2013256. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015). https:\/\/doi.org\/10.4230\/LIPICS.TLCA.2015.241","DOI":"10.4230\/LIPICS.TLCA.2015.241"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-030-81688-9_5","volume-title":"Computer Aided Verification","author":"L Leutgeb","year":"2021","unstructured":"Leutgeb, L., Moser, G., Zuleger, F.: ATLAS: Automated Amortised Complexity Analysis of Self-adjusting Data Structures. In: Silva, A., Leino, K.R.M. (eds.) CAV 2021. LNCS, vol. 12760, pp. 99\u2013122. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-81688-9_5"},{"key":"13_CR20","doi-asserted-by":"publisher","unstructured":"Lommen, N., Meyer, \u00c9., Giesl, J.: Control-Flow Refinement for Complexity Analysis of Probabilistic Programs in KoAT (Short Paper). In: Proceedings of 12th IJCAR. LNCS, vol. 14739, pp. 233\u2013243 (2024). https:\/\/doi.org\/10.1007\/978-3-031-63498-7_14","DOI":"10.1007\/978-3-031-63498-7_14"},{"key":"13_CR21","doi-asserted-by":"publisher","unstructured":"McGeoch, C.C., Cohen, P.R.: How to find big-oh in your data set (and how not to). In: Madigan, D., Smyth, P. (eds.) Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol.\u00a0R1, pp. 347\u2013354. PMLR (1997). https:\/\/doi.org\/10.1007\/BFb0052828","DOI":"10.1007\/BFb0052828"},{"key":"13_CR22","unstructured":"Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of Machine Learning. Adaptive Computation and Machine Learning series, MIT Press, Cambridge (2012). https:\/\/dl.acm.org\/doi\/10.5555\/3360093"},{"key":"13_CR23","doi-asserted-by":"publisher","unstructured":"Moser, G., Schneckenreither, M.: Automated amortised resource analysis for term rewrite systems. Sci. Comput. Program. 185 (2020). https:\/\/doi.org\/10.1016\/J.SCICO.2019.102306","DOI":"10.1016\/J.SCICO.2019.102306"},{"key":"13_CR24","unstructured":"Murphy, K.: Machine Learning: A Probabilistic Perspective. Adaptive Computation and Machine Learning series, MIT Press, Cambridge (2012). https:\/\/dl.acm.org\/doi\/book\/10.5555\/2380985"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Noschinski, L., Emmes, F., Giesl, J.: Analyzing Innermost Runtime Complexity of Term Rewriting by Dependency Pairs. JAR 51(1), 27\u201356 (2013). https:\/\/doi.org\/10.1007\/s10817-013-9277-6","DOI":"10.1007\/s10817-013-9277-6"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Pham, L., Saad, F.A., Hoffmann, J.: Robust Resource Bounds with Static Analysis and Bayesian Inference. Proc. ACM Program. Lang. 8(PLDI) (2024). https:\/\/doi.org\/10.1145\/3656380","DOI":"10.1145\/3656380"},{"key":"13_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/3-540-44691-5_12","volume-title":"Algorithm Engineering","author":"P Sanders","year":"2001","unstructured":"Sanders, P., Fleischer, R.: Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms. In: N\u00e4her, S., Wagner, D. (eds.) WAE 2000. LNCS, vol. 1982, pp. 135\u2013146. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44691-5_12"},{"key":"13_CR28","doi-asserted-by":"publisher","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge (2014). https:\/\/doi.org\/10.1017\/CBO9781107298019","DOI":"10.1017\/CBO9781107298019"},{"key":"13_CR29","doi-asserted-by":"publisher","unstructured":"Stoer, J., Bulirsch, R., Bartels, R., Gautschi, W., Witzgall, C.: Introduction to Numerical Analysis, vol.\u00a01993. Springer, Heidelberg (1980). https:\/\/doi.org\/10.1007\/978-0-387-21738-3","DOI":"10.1007\/978-0-387-21738-3"},{"key":"13_CR30","doi-asserted-by":"publisher","unstructured":"TeReSe: Term Rewriting Systems, Cambridge Tracks in Theoretical Computer Science, vol.\u00a055. Cambridge University Press, Cambridge (2003). https:\/\/doi.org\/10.1017\/S095679680400526X","DOI":"10.1017\/S095679680400526X"},{"key":"13_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-030-68446-4_2","volume-title":"Logic-Based Program Synthesis and Transformation","author":"S Winkler","year":"2021","unstructured":"Winkler, S., Moser, G.: Runtime Complexity Analysis of Logically Constrained Rewriting. In: LOPSTR 2020. LNCS, vol. 12561, pp. 37\u201355. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-68446-4_2"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Combining Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04167-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,14]],"date-time":"2025-09-14T22:04:10Z","timestamp":1757887450000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04167-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,15]]},"ISBN":["9783032041661","9783032041678"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04167-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,15]]},"assertion":[{"value":"15 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FroCoS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Frontiers of Combining Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Reykjavik","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Iceland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 October 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"frocos2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/icetcs.github.io\/frocos-itp-tableaux25\/frocos\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}