Soft lambda-calculus: a language for polynomial time computation

Details Soft lambda-calculus: a language for polynomial time computation Soft lambda-calculus: a language for polynomial time computation

2003-12-07

arxiv.org/abs/cs/0312015v1

Computer Science

Logic in Computer Science

20 pages

Scientific paper

Soft linear logic ([Lafont02]) is a subsystem of linear logic characterizing the class PTIME. We introduce Soft lambda-calculus as a calculus typable in the intuitionistic and affine variant of this logic. We prove that the (untyped) terms of this calculus are reducible in polynomial time. We then extend the type system of Soft logic with recursive types. This allows us to consider non-standard types for representing lists. Using these datatypes we examine the concrete expressivity of Soft lambda-calculus with the example of the insertion sort algorithm.

Affiliated with

Also associated with

No associations

Rating

Soft lambda-calculus: a language for polynomial time computation 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 Soft lambda-calculus: a language for polynomial time computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Soft lambda-calculus: a language for polynomial time computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-252512