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.
Experimentelle Ergebnisse
Runtime Complexity: TRS
Runtime Complexity: TRS Innermost
Änderungsprotokoll
2025-02-21: v1.0
First Version
Kontakt
Das Tool wird derzeit entwickelt von:
- Manuel Meitinger
- Samuel Frontull
- Georg Moser