David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 14 (2):199-234 (2005)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Anders Søgaard & Martin Lange (2009). Polyadic Dynamic Logics for Hpsg Parsing. Journal of Logic, Language and Information 18 (2):159-198.
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.
Added to index2009-01-28
Total downloads2 ( #500,207 of 1,696,550 )
Recent downloads (6 months)1 ( #343,026 of 1,696,550 )
How can I increase my downloads?