Quasi-friendly sup-interpretations
| dc.creator | Marion, Jean-Yves | |
| dc.creator | Pechoux, Romain | |
| dc.date | 2006-08-03 | |
| dc.date.accessioned | 2026-07-07T07:19:57Z | |
| dc.date.available | 2026-07-07T07:19:57Z | |
| dc.description | In a previous paper, the sup-interpretation method was proposed as a new tool to control memory resources of first order functional programs with pattern matching by static analysis. Basically, a sup-interpretation provides an upper bound on the size of function outputs. In this former work, a criterion, which can be applied to terminating as well as non-terminating programs, was developed in order to bound polynomially the stack frame size. In this paper, we suggest a new criterion which captures more algorithms computing values polynomially bounded in the size of the inputs. Since this work is related to quasi-interpretations, we compare the two notions obtaining two main features. The first one is that, given a program, we have heuristics for finding a sup-interpretation when we consider polynomials of bounded degree. The other one consists in the characterizations of the set of function computable in polynomial time and in polynomial space. | |
| dc.identifier | https://arxiv.org/abs/cs/0608020 | |
| dc.identifier | http://arxiv.org/abs/cs/0608020 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/114817 | |
| dc.subject | Computational Complexity | |
| dc.title | Quasi-friendly sup-interpretations | |
| dc.type | text |