Data-Driven Runtime Complexity Analysis
Open Access
- 15 September 2025
- book chapter
- Published by Springer Nature
- p. 228-246
Abstract
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.Keywords
This publication has 28 references indexed in Scilit:
- Control-Flow Refinement for Complexity Analysis of Probabilistic Programs in KoAT (Short Paper)2024
- ATLAS: Automated Amortised Complexity Analysis of Self-adjusting Data Structures2021
- Runtime Complexity Analysis of Logically Constrained Rewriting2021
- TcT: Tyrolean Complexity Tool2016
- Amortised Resource Analysis and Typed Polynomial Interpretations2014
- Automated Complexity Analysis Based on the Dependency Pair MethodLecture Notes in Computer Science, 2007
- Introduction to Numerical Analysis2002
- Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms2001
- A new recursion-theoretic characterization of the polytime functionscomputational complexity, 1992
- Termination proofs and the length of derivationsLecture Notes in Computer Science, 1989