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.