Paper: Highly Constrained Unification Grammars

ACL ID P06-1137
Title Highly Constrained Unification Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2006

Unification grammars are widely accepted as an expressive means for describing the structure of natural languages. In gen- eral, the recognition problem is undecid- able for unification grammars. Even with restricted variants of the formalism, off- line parsable grammars, the problem is computationally hard. We present two nat- ural constraints on unification grammars which limit their expressivity. We first show that non-reentrant unification gram- mars generate exactly the class of context- free languages. We then relax the con- straint and show that one-reentrant unifi- cation grammars generate exactly the class of tree-adjoining languages. We thus re- late the commonly used and linguistically motivated formalism of unification gram- mars to more restricted, computationally tractable cl...