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 (grants 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.

• Efrat Jaeger. Unification Grammars and Off-line Parsability. MSc. Thesis, Department of Computer Science, The Technion. December 2002.

• Efrat Jaeger, Nissim Francez and Shuly Wintner. Guaranteeing parsing termination of unification grammars. In Proceedings of COLING-2002, Taipei, Taiwan, August 2002.