Mild context-sensitivity and tuple-based generalizations of context-free grammar
This paper classifies a family of grammar formalisms that extend context-free grammar by talking about tuples of terminal strings, rather than independently combining single terminal words into larger single phrases. These include a number of well-known formalisms, such as head grammar and linear context-free rewriting systems, but also a new formalism, (simple) literal movement grammar, which strictly extends the previously known formalisms, while preserving polynomial time recognizability. The descriptive capacity of simple literal movement grammars is illustrated both formally through a weak generative capacity argument and in a more practical sense by the description of conjunctive cross-serial relative clauses in Dutch. After sketching a complexity result and drawing a number of conclusions from the illustrations, it is then suggested that the notion of mild context-sensitivity currently in use, that depends on the rather loosely defined concept of constant growth, needs a modification to apply sensibly to the illustrated facts; an attempt at such a revision is proposed.
|MSC||Turing machines and related notions (msc 03D10), Complexity classes (hierarchies, relations among complexity classes, etc.) (msc 68Q15), Formal languages and automata (msc 68Q45), Theory of computing (msc 68Qxx), Theory of computing (msc 68Qxx), Natural language processing (msc 68T50)|
|Journal||Linguistics and Philosophy|
|Conference||Mathematics of Language|
Groenink, A.V. (1998). Mild context-sensitivity and tuple-based generalizations of context-free grammar. Linguistics and Philosophy, 20(6), 607–636.