The generative power of categorial grammars and head-driven phrase structure grammars with lexical rules
Bob Carpenter · 1991
In this paper, it is shown that the addition of a simple and linguistically motivated form of lexical rules to grammatical theories based on subcategorization lists, such as categorial grammars (CG) or head-driven phrase structure grammars (HPSG) results in a system which can generate all and only the recursively enumerable languages. The proof of this result is carried out by means of a reduction of generalized rewriting systems. Two restrictions are considered, each of which constrains the generative power of the resulting system to context-free languages. 1 Introduction In recent grammatical theories, there has been an increasing trend toward the lexicalization of syntactic information. This is particularly evident in the case of categorial grammars (CG) and head-driven phrase structure grammars (HPSG), where a small number of highly schematic syntactic rules are assumed to apply universally. With this assumption of a universal syntax, the task of explaining the variations between ...