Strong polynomial bound for light linear logic by levels

Details Strong polynomial bound for light linear logic by levels Strong polynomial bound for light linear logic by levels

2012-01-13

arxiv.org/abs/1201.2956v1

Computer Science

Logic in Computer Science

Scientific paper

Girard's LLL characterized Ptime in the proof-as-program paradigm with a complexity bound on cut elimination. This logic relied on a stratification principle which Baillot and Mazza generalized by defining two variants L^4 and L^4_0 referred to as light linear logic by levels. However, for L^4, a polynomial bound was given on cut elimination only for a specific reduction strategy. L^4_0 only enjoyed a complexity soundness result without an explicit bound on cut elimination. These limitations are a problem for defining a proper type system out of theses logics. In this paper we overcome these problems by proving a polynomial time bound for cut elimination under any strategy(strong bound) both for L^4 and L^4_0. The proof is based on an extension of Dal Lago's context semantics, illustrating once again the usefullness of this tool.

Affiliated with

Also associated with

No associations

Rating

Strong polynomial bound for light linear logic by levels 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 Strong polynomial bound for light linear logic by levels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong polynomial bound for light linear logic by levels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-693310