Graduate studies at Western
Journal of Logic, Language and Information 17 (3):345-381 (2008)
|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|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Philippe de Groote & Sylvain Pogodalla (2004). On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms. [REVIEW] Journal of Logic, Language and Information 13 (4):421-438.
Theo Janssen, Gerard Kok & Lambert Meertens (1977). On Restrictions on Transformational Grammars Reducing the Generative Power. Linguistics and Philosophy 1 (1):111 - 118.
Nissim Francez & Michael Kaminski (2007). Commutation-Augmented Pregroup Grammars and Mildly Context-Sensitive Languages. Studia Logica 87 (2-3):295 - 321.
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Wojciech Buszkowski & Gerald Penn (1990). Categorial Grammars Determined From Linguistic Data by Unification. Studia Logica 49 (4):431 - 454.
Barbara Dziemidowicz-Gryz (2007). On Learnability of Restricted Classes of Categorial Grammars. Studia Logica 85 (2):153 - 169.
Efrat Jaeger, Nissim Francez & Shuly Wintner (2005). Unification Grammars and Off-Line Parsability. Journal of Logic, Language and Information 14 (2):199-234.
Added to index2009-01-28
Total downloads6 ( #154,860 of 739,345 )
Recent downloads (6 months)1 ( #61,538 of 739,345 )
How can I increase my downloads?