2011 | OriginalPaper | Chapter
The Product-Free Lambek-Grishin Calculus Is NP-Complete
Author : Jeroen Bransen
Published in: Logical Aspects of Computational Linguistics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The Lambek-Grishin calculus
LG
is the symmetric extension of the non-associative Lambek calculus
NL
. In this paper we prove that the derivability problem for the product-free fragment of
LG
is NP-complete, thus improving on Bransen (2010) where this is shown for
LG
with product.