Highly Constrained Unification Grammars

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 1089–1096, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Highly constrained unification grammars Daniel Feinstein Department of Computer Science University of Haifa 31905 Haifa, Israel daniel@cs.haifa.ac.il Shuly Wintner Department of Computer Science University of Haifa 31905 Haifa, Israel shuly@cs.haifa.ac.il Abstract 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 classes of languages. 1 Introduction Unification grammars (UG) (Shieber, 1986; Shieber, 1992; Carpenter, 1992) have originated as an extension of context-free grammars, the ba- sic idea being to augment the context-free rules with non context-free annotations (feature struc- tures) in order to express additional information. They can describe phonological, morphological, syntactic and semantic properties of languages si- multaneously and are thus linguistically suitable for modeling natural languages. Several formula- tions of unification grammars have been proposed, and they are used extensively by computational linguists to describe the structure of a variety of natural languages. Unification grammars are Turing equivalent: determining whether a given string is generated by a given grammar is as hard as deciding whether a Turing machine halts on the empty input (John- son, 1988). Therefore, the recognition problem for unification grammars is undecidable in the general case. To ensure its decidability, several constraints on unification grammars, commonly known as the off-line parsability (OLP) constraints, were sug- gested, such that the recognition problem is decid- able for off-line parsable grammars (Jaeger et al., 2005). The idea behind all the OLP definitions is to rule out grammars which license trees in which unbounded amount of material is generated with- out expanding the frontier word. This can happen due to two kinds of rules: ϵ-rules (whose bodies are empty) and unit rules (whose bodies consist of a single element). However, even for unifica- tion grammars with no such rules the recognition problem is NP-hard (Barton et al., 1987). In order for a grammar formalism to make pre- dictions about the structure of natural language its generative capacity must be constrained. It is now generally accepted that Context-free Gram- mars (CFGs) lack the generative power needed for this purpose (Savitch et al., 1987), due to natu- ral language constructions such as reduplication, multiple agreement and crossed agreement. Sev- eral linguistic formalisms have been proposed as capable of modeling these phenomena, including Linear Indexed Grammars (LIG) (Gazdar, 1988), Head Grammars (Pollard, 1984), …

Content truncated to 500 words