Conjunctive Categorial Grammars
Stepan Lvovich Kuznetsov, Alexander Okhotin · 2017
Basic categorial grammars are enriched with a conjunction operation, and it is proved that the formalism obtained in this way has the same expressive power as conjunctive grammars, that is, context-free grammars enhanced with conjunction.It is also shown that categorial grammars with conjunction can be naturally embedded into the Lambek calculus with conjunction and disjunction operations.This further implies that a certain NP-complete set can be defined in the Lambek calculus with conjunction.