On the generative capacity of multi-modal Categorial Grammars

In Moortgat 1996 the Lambek Calculus L (Lambek 1958) is extended by a pair of residuation modalities ◊ and □↓. Categorial Grammars based on the resulting logic L◊ are attractive for linguistic purposes since they offer a compromise between the strict constituent structures imposed by context free grammars and related formalisms on the one hand, and the complete absence of hierarchical information in Lambek grammars on the other hand. The paper contains some results on the generative capcity of Categorial Grammars based on L◊. First it is shown that adding residuation modalities does not extend the weak generative capacity. This is proved by extending the proof for the context freeness of L-grammars from Pentus 1993 to L◊. Second the strong generative capacity of L◊-grammars is compared to context free grammars. The results are mainly negative. The set of tree languages generated by L◊-grammars neither contains nor is contained in the class of context free tree languages.