Linear Logic by Levels and Bounded Time Complexity

Details Linear Logic by Levels and Bounded Time Complexity Linear Logic by Levels and Bounded Time Complexity

2008-01-08

arxiv.org/abs/0801.1253v3

Computer Science

Logic in Computer Science

63 pages. To appear in Theoretical Computer Science. This version corrects minor fonts problems from v2

Scientific paper

We give a new characterization of elementary and deterministic polynomial time computation in linear logic through the proofs-as-programs correspondence. Girard's seminal results, concerning elementary and light linear logic, achieve this characterization by enforcing a stratification principle on proofs, using the notion of depth in proof nets. Here, we propose a more general form of stratification, based on inducing levels in proof nets by means of indexes, which allows us to extend Girard's systems while keeping the same complexity properties. In particular, it turns out that Girard's systems can be recovered by forcing depth and level to coincide. A consequence of the higher flexibility of levels with respect to depth is the absence of boxes for handling the paragraph modality. We use this fact to propose a variant of our polytime system in which the paragraph modality is only allowed on atoms, and which may thus serve as a basis for developing lambda-calculus type assignment systems with more efficient typing algorithms than existing ones.

Affiliated with

Also associated with

No associations

Rating

Linear Logic by Levels and Bounded Time 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 Linear Logic by Levels and Bounded Time Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Logic by Levels and Bounded Time Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-421508