Modular Automatic Complexity Analysis of Recursive Integer Programs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908750069104640 |
|---|---|
| author | Lommen, Nils Giesl, Jürgen |
| author_facet | Lommen, Nils Giesl, Jürgen |
| contents | In earlier work, we developed a modular approach for automatic complexity analysis of integer programs. However, these integer programs do not allow non-tail recursive calls or subprocedures. In this paper, we consider integer programs with function calls and present a natural extension of our modular complexity analysis approach to the recursive setting based on a new form of ranking functions. Hence, our approach combines already existing powerful techniques on the "imperative" parts of the program and our novel ranking functions on the recursive parts. The strength of this combination is demonstrated by our implementation in the complexity analysis tool KoAT. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18851 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Modular Automatic Complexity Analysis of Recursive Integer Programs Lommen, Nils Giesl, Jürgen Logic in Computer Science In earlier work, we developed a modular approach for automatic complexity analysis of integer programs. However, these integer programs do not allow non-tail recursive calls or subprocedures. In this paper, we consider integer programs with function calls and present a natural extension of our modular complexity analysis approach to the recursive setting based on a new form of ranking functions. Hence, our approach combines already existing powerful techniques on the "imperative" parts of the program and our novel ranking functions on the recursive parts. The strength of this combination is demonstrated by our implementation in the complexity analysis tool KoAT. |
| title | Modular Automatic Complexity Analysis of Recursive Integer Programs |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2512.18851 |