The generative power of categorial grammars and head-driven phrase structure grammars with lexical rules

Abstract

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 ...

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 39 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.