# 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

## 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.