Logic in Computer Science (LICS 1995)

Paper: The Complexity of Neutrals in Linear Logic (at LICS 1995)

Authors: Max I. Kanovich

Abstract

The main result announced in this paper is the proof of the existence of strongly independent (free) sets of Linear Logic formulas that are built up of only neutrals. The motivating application is a uniform and transparent technique for obtaining the exact computational characterization of Constant-Only Fragments of Commutative and Non-Commutative Linear Logic. In particular, we prove the surprising results that - Multiplicative-Additive Fragments of Constant-Only Linear Logic are PSPACE-complete, - All partial recursive predicates are directly definable in the Full Constant-Only Linear Logic.

BibTeX

  @InProceedings{Kanovich-TheComplexityofNeut,
    author = 	 {Max I. Kanovich},
    title = 	 {The Complexity of Neutrals in Linear Logic},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1995},
    year =	 1995,
    editor =	 {Dexter Kozen},
    month =	 {June}, 
    pages =      {486-495},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }