Data-Driven Runtime Complexity Analysis
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.
Experimental Results
Runtime Complexity: TRS
Runtime Complexity: TRS Innermost
Changelog
2025-02-21: v1.0
First Version
Contact
The tool is currently under development by:
- Manuel Meitinger
- Samuel Frontull
- Georg Moser