P-time Completeness of Light Linear Logic and its Nondeterministic Extension

Details P-time Completeness of Light Linear Logic and its Nondeterministic Extension P-time Completeness of Light Linear Logic and its Nondeterministic Extension

2004-10-15

arxiv.org/abs/cs/0410034v2

Computer Science

Logic in Computer Science

Scientific paper

In CSL'99 Roversi pointed out that the Turing machine encoding of Girard's seminal paper "Light Linear Logic" has a flaw. Moreover he presented a working version of the encoding in Light Affine Logic, but not in Light Linear Logic. In this paper we present a working version of the encoding in Light Linear Logic. The idea of the encoding is based on a remark of Girard's tutorial paper on Linear Logic. The encoding is also an example which shows usefulness of additive connectives. Moreover we also consider a nondeterministic extension of Light Linear Logic. We show that the extended system is NP-complete in the same meaning as P-completeness of Light Linear Logic.

Affiliated with

Also associated with

No associations

Rating

P-time Completeness of Light Linear Logic and its Nondeterministic Extension 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 P-time Completeness of Light Linear Logic and its Nondeterministic Extension, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and P-time Completeness of Light Linear Logic and its Nondeterministic Extension will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-289845