This page is obsolete. The new page is here. You will be redirected presently.
Unification grammars and off-line parsability
Computational Linguistics Group, Department of Computer Science, University of Haifa
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, 2004. Accepted for publication.
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
Computational Linguistics Group, Department of Computer Science,
University of Haifa,
http://cl.haifa.ac.il/
Maintained by
shuly@cs.haifa.ac.il.
Last modified: Thu Mar 27 17:07:52 IST 2003