On Quasi-Interpretations, Blind Abstractions and Implicit Complexity
| dc.creator | Baillot, Patrick | |
| dc.creator | Lago, Ugo Dal | |
| dc.creator | Moyen, Jean-Yves | |
| dc.date | 2006-08-06 | |
| dc.date.accessioned | 2026-07-07T07:19:58Z | |
| dc.date.available | 2026-07-07T07:19:58Z | |
| dc.description | Quasi-interpretations are a technique to guarantee complexity bounds on first-order functional programs: with termination orderings they give in particular a sufficient condition for a program to be executable in polynomial time, called here the P-criterion. We study properties of the programs satisfying the P-criterion, in order to better understand its intensional expressive power. Given a program on binary lists, its blind abstraction is the nondeterministic program obtained by replacing lists by their lengths (natural numbers). A program is blindly polynomial if its blind abstraction terminates in polynomial time. We show that all programs satisfying a variant of the P-criterion are in fact blindly polynomial. Then we give two extensions of the P-criterion: one by relaxing the termination ordering condition, and the other one (the bounded value property) giving a necessary and sufficient condition for a program to be polynomial time executable, with memoisation. | |
| dc.description | 18 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0608030 | |
| dc.identifier | http://arxiv.org/abs/cs/0608030 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/114823 | |
| dc.subject | Programming Languages | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.title | On Quasi-Interpretations, Blind Abstractions and Implicit Complexity | |
| dc.type | text |