tailieunhanh - Báo cáo khoa học: "Highly constrained unification grammars"

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, offline parsable grammars, the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity. We first show that non-reentrant unification grammars generate exactly the class of contextfree languages. We then relax the constraint and show that one-reentrant unification grammars generate exactly the class of tree-adjoining languages. . | Highly constrained unification grammars Daniel Feinstein Department of Computer Science University of Haifa 31905 Haifa Israel daniel@ Shuly Wintner Department of Computer Science University of Haifa 31905 Haifa Israel shuly@ Abstract 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 offline parsable grammars the problem is computationally hard. We present two natural constraints on unification grammars which limit their expressivity. 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 tree-adjoining languages. We thus relate the commonly used and linguistically motivated formalism of unification grammars 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 basic idea being to augment the context-free rules with non context-free annotations feature structures in order to express additional information. They can describe phonological morphological syntactic and semantic properties of languages simultaneously and are thus linguistically suitable for modeling natural languages. Several formulations 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 Johnson 1988 . Therefore the recognition problem for unification grammars is undecidable in the general case.