The complexity of multiplicative-additive Lambek calculus: 25 years later
The Lambek calculus was introduced as a mathematical description of natural languages. The original Lambek calculus is NP-complete (Pentus), while its product-free fragment with only one implication is polynomially decidable (Savateev). We consider Lambek calculus with the additional connectives: conjunction and disjunction. It is known that this system is PSPACE-complete (Kanovich, Kanazawa). We prove, in contrast with the polynomial-time result for the product-free Lambek calculus with one implication, that the derivability problem is still PSPACE-complete even for a very small fragment (∖,∧), including one implication and conjunction only. PSPACE-completeness is also provided for the (∖,∨) fragment, which includes only one implication and disjunction. Categorial grammars based on the original Lambek calculus generate exactly the class of context-free languages (Gaifman, Pentus). The class of languages generated by Lambek grammars extended with conjunction is known to be closed under intersection (Kanazawa), and therefore includes all finite intersections of context-free languages and, moreover, images of such intersections under alphabetic homomorphisms. We show that the same closure under intersection holds for Lambek grammars extended with disjunction, even for our small (∖,∨) fragment.