Highly Constrained Unification Grammars |
| |
Authors: | Daniel Feinstein Shuly Wintner |
| |
Affiliation: | (1) Department of Computer Science, University of Haifa, 31905 Haifa, Israel |
| |
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, 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. |
| |
Keywords: | Unification grammars Linear indexed grammars Mildly context- sensitive languages Generative capacity |
本文献已被 SpringerLink 等数据库收录! |