Affordable Access

Publisher Website

Lambek calculus is NP-complete

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
357
Identifiers
DOI: 10.1016/j.tcs.2006.03.018
Keywords
  • Lambek Calculus
  • Cyclic Linear Logic
  • Noncommutative Linear Logic
  • Complexity

Abstract

Abstract We prove that for both the Lambek calculus L and the Lambek calculus allowing empty premises L * the derivability problem is NP -complete. It follows that also for the multiplicative fragments of cyclic linear logic and noncommutative linear logic the derivability problem is NP -complete.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Product-free Lambek calculus is NP-complete

on Annals of Pure and Applied Log...

Models for the Lambek calculus

on Annals of Pure and Applied Log... Jan 01, 1995

Lambek vs. Lambek: Functorial vector space semanti...

on Annals of Pure and Applied Log...
More articles like this..