Two algorithms in search of a type system

Details Two algorithms in search of a type system Two algorithms in search of a type system

2007-10-03

arxiv.org/abs/0710.0824v2

Computer Science

Logic in Computer Science

30 pages. Final version to appear in Theory of Computing Systems

Scientific paper

The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are ATR-definable (ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper's main work is in refining the original time-complexity semantics for ATR to show that these new recursion schemes do not lead out of the realm of feasibility.

Affiliated with

Also associated with

No associations

Rating

Two algorithms in search of a type system 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 Two algorithms in search of a type system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two algorithms in search of a type system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-285993