Light Logics and Optimal Reduction: Completeness and Complexity

Details Light Logics and Optimal Reduction: Completeness and Complexity Light Logics and Optimal Reduction: Completeness and Complexity

2007-04-19

arxiv.org/abs/0704.2448v1

Computer Science

Logic in Computer Science

21 pages

Scientific paper

Typing of lambda-terms in Elementary and Light Affine Logic (EAL, LAL, resp.) has been studied for two different reasons: on the one hand the evaluation of typed terms using LAL (EAL, resp.) proof-nets admits a guaranteed polynomial (elementary, resp.) bound; on the other hand these terms can also be evaluated by optimal reduction using the abstract version of Lamping's algorithm. The first reduction is global while the second one is local and asynchronous. We prove that for LAL (EAL, resp.) typed terms, Lamping's abstract algorithm also admits a polynomial (elementary, resp.) bound. We also show its soundness and completeness (for EAL and LAL with type fixpoints), by using a simple geometry of interaction model (context semantics).

Affiliated with

Also associated with

No associations

Rating

Light Logics and Optimal Reduction: Completeness and 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 Light Logics and Optimal Reduction: Completeness and Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Light Logics and Optimal Reduction: Completeness and Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212454