The tree-generative capacity of combinatory categorial grammars (Q2051866)

Combinatory categorial grammars, originally introduced by \textit{M. Steedman} [``Dependency and coördination in the grammar of Dutch and English'', Language 61, No. 3, 523--568 (1985)] as a linguistically motivated formalism, are now relatively well understood as generating mechanisms for languages of finite words. It is known that they always generate mild context-sensitive languages, and the model has been proved equivalent to several other widely used formalisms such as linear indexed grammars and tree-adjoining grammars [\textit{K. Vijay-Shanker} and \textit{D. J. Weir}, Math. Syst. Theory 27, No. 6, 511--546 (1994; Zbl 0813.68129)]. The authors of the article consider combinatory categorial grammars as generators of tree languages over suitable ranked alphabets. More precisely, a combinatory categorial grammar \(G\) is said to generate a tree language if this can be obtained from the tree language of all derivation trees of \(G\) via a relabelling of some specific sort. This implies in particular that all trees generated by combinatory categorial grammars are binary. The results obtained in the article thus only apply to trees of this kind, and the usual classes of tree languages are restricted accordingly. The class of tree languages generated by combinatory categorial grammars is shown to be included in the class of tree languages generated by the so-called simple monadic context-free tree grammars. This inclusion is shown to be strict for a class of \textit{pure} combinatory categorial grammars by showing that grammars from this subclass cannot even generate all derivation tree languages of context-free grammars, which are specific regular tree languages. In addition, the authors study the generative power of combinatory categorial grammars with limited rule degrees. They show that the grammars in which all rules are required to be of degree \(0\) generate a proper subclass of regular tree languages, while the grammars with rule degrees limited by \(1\) generate precisely the regular tree languages.