Computational Linguistics Group
Department of Computer Science
University of Haifa

Home People Projects Publications Events

Unification grammars and off-line parsability

Project description

Objective: To define a decidable condition for guaranteeing parsing termination for unification grammars.
Researchers: Efrat Jaeger, Nissim Francez (Department of Computer Science, Technion) and Shuly Wintner
Status: Complete
Funding: Israeli Science Foundation (grant 136/01)

Abstract

Unification grammars are known to be Turing-equivalent; given a grammar G and a word w, it is undecidable whether w is in 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 work we investigate various definitions of OLP and discuss their inter-relations, proving that some of the OLP variants are indeed undecidable. Finally, we present a novel, decidable, OLP constraint which is more liberal than the existing decidable ones.

Resources

None.

Publications

Efrat Jaeger, Nissim Francez and Shuly Wintner. Unification Grammars and Off-Line Parsability. Journal of Logic, Language and Information, 14:299-234, 2005. PDF.
Efrat Jaeger. Unification Grammars and Off-line Parsability. MSc. Thesis, Department of Computer Science, The Technion. December 2002. PDF.
Efrat Jaeger, Nissim Francez and Shuly Wintner. Guaranteeing parsing termination of unification grammars. In Proceedings of COLING-2002, Taipei, Taiwan, August 2002. PDF.

Contact

Mailing address	Shuly Wintner Department of Computer Science University of Haifa 31905 Haifa, Israel.
Phone	+972-4-8288180
Fax	+972-4-8249331
E-mail	`shuly@cs.haifa.ac.il`

Computational Linguistics Group , http://cl.haifa.ac.il/
Department of Computer Science , University of Haifa
Maintained by shuly@cs.haifa.ac.il, modified Sunday November 24, 2013.