An introduction to mildly context sensitive grammar formalisms

Gerhard Jäger and Jens Michaelis

[revised and updated August 16, 2004 ]


Summary: While there is conclusive proof that not all natural languages can be described by context-free grammars, all available evidence suggests that a very cautious extension of this complexity class is sufficient to accommodate all linguistic phenomena. Research on this issue has led to the notion of "mild context-sensitivity". A range of corresponding formalisms is well-established (e.g. Tree Adjoining Grammars, Linear Indexed Grammars, Combinatory Categorial Grammars, Head Grammars, and also Stabler's Minimalist Grammars). The first part of the course aims to recapitulate the motivations for employing non-context-free devices in formal linguistics. We will show that certain stronger-than-context-free means are not only more appropriate for reasons of weak generative power, but also permit theoretically more elegant and satisfactory structural descriptions (e.g. pertaining to non-local dependencies). In the second part of the course, the most common mildly context-sensitive devices - Tree Adjoining Grammars and Combinatory Categorial Grammars - will be introduced formally, and their usefulness for working linguists as well as their applications in language technology methods will be demonstrated. Finally we will briefly outline how most of the MCSG-formalisms become comparable in terms of "linear context-free rewriting systems".


Downloadable Reader