Because of the ease of their implementation, attribute-value based theories of grammar are becoming increasingly popular in theoretical linguistics as an alternative to transformational accounts and in computational linguistics. This book provides a formal analysis of attribute-value structures, their use in a theory of grammar and the representation of grammatical relations in such theories of grammar. It provides a classical treatment of disjunction and negation, and explores the linguistic implications of different representations of grammatical relations. Mark Johnson is assistant professor (...) in cognitive and linguistic sciences at Brown University. He was a Fairchild postdoctoral fellow at the Massachusetts Institute of Technology during the 1987-88 academic year. (shrink)

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In general, the recognition problem is undecidable for unification grammars. Even with restricted variants of the formalism, off-line parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity and allow for efficient processing. We first show that non-reentrant unification grammars generate exactly the class of context-free languages. We then relax the constraint and show that one-reentrant (...) unification grammars generate exactly the class of mildly context-sensitive languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars to more restricted, computationally tractable classes of languages. (shrink)