Graduate studies at Western
Journal of Logic, Language and Information 14 (2):199-234 (2005)
|Abstract||Unification grammars are known to be Turing-equivalent; given a grammar G and a word w, it is undecidable whether w L(G). In order to ensure decidability, several constraints on grammars, commonly known as off-line parsability (OLP), were suggested, such that the recognition problem is decidable for grammars which satisfy OLP. An open question is whether it is decidable if a given grammar satisfies OLP. In this paper we investigate various definitions of OLP and discuss their interrelations, proving that some of the OLP variants are indeed undecidable. We then present a novel, decidable OLP constraint which is more liberal than the existing decidable ones.|
|Keywords||off-line parsability parsing termination unification grammars|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Yael Sygal & Shuly Wintner (2009). Associative Grammar Combination Operators for Tree-Based Grammars. Journal of Logic, Language and Information 18 (3):293-316.
Christian Retoré & Sylvain Salvati (2010). A Faithful Representation of Non-Associative Lambek Grammars in Abstract Categorial Grammars. Journal of Logic, Language and Information 19 (2):185-200.
Barbara Dziemidowicz-Gryz (2007). On Learnability of Restricted Classes of Categorial Grammars. Studia Logica 85 (2):153 - 169.
Wojciech Buszkowski & Gerald Penn (1990). Categorial Grammars Determined From Linguistic Data by Unification. Studia Logica 49 (4):431 - 454.
Sylvain Salvati (2010). On the Membership Problem for Non-Linear Abstract Categorial Grammars. Journal of Logic, Language and Information 19 (2):163-183.
Nissim Francez & Michael Kaminski (2007). Commutation-Augmented Pregroup Grammars and Mildly Context-Sensitive Languages. Studia Logica 87 (2-3):295 - 321.
Shuly Wintner & Nissim Francez (1999). Off-Line Parsability and the Well-Foundedness of Subsumption. Journal of Logic, Language and Information 8 (1):1-16.
Daniel Feinstein & Shuly Wintner (2008). Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17 (3):345-381.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Recent downloads (6 months)0
How can I increase my downloads?