On Quasi-Interpretations, Blind Abstractions and Implicit Complexity

Details On Quasi-Interpretations, Blind Abstractions and Implicit Complexity On Quasi-Interpretations, Blind Abstractions and Implicit Complexity

2006-08-06

arxiv.org/abs/cs/0608030v1

Computer Science

Programming Languages

18 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Quasi-Interpretations, Blind Abstractions and Implicit Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Quasi-Interpretations, Blind Abstractions and Implicit Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Quasi-Interpretations, Blind Abstractions and Implicit Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-394241