|M.Sc Student||Jaeger Efrat|
|Subject||Unification Grammars and Off-Line Parsability|
|Department||Department of Computer Science||Supervisors||Professor Emeritus Nissim Francez|
|Dr. Shalom Wintner|
Context-free grammars are considered to lack the expressive power needed for modeling natural languages. Unification grammars have originated as an extension of context-free grammars, the basic idea being to augment the context-free rules with feature structures in order to express additional information. Unification grammars are known to be Turing-equivalent; given a grammar G and a word w, it is undecidable whether there exists a derivation tree for w admitted by G. In order to ensure the decidability of the membership problem, several constraints on grammars, commonly known as the off-line parsability constraint (OLP) were suggested. The membership problem is decidable for grammars which satisfy OLP. An open question is whether it is decidable if a given grammar satisfies OLP.
In this thesis we investigate various definitions of OLP and discuss their inter-relations. As some of the OLP variants were suggested without recognizing the existence of all other variants, we make a comparative analysis of the several different OLP variants for the first time. Some of the OLP variants were conjectured to be undecidable (it is undecidable whether a grammar satisfies the constraint), although no proof has ever been provided. There exist some variants of OLP for which decidability holds, but these conditions are too restrictive: there is a large class of non-OLP grammars for which parsing termination is guaranteed. Also these variants are limited only to a specific kind of unification grammar formalisms.
Our main contribution is proofs of undecidability for three of the undecidable OLP variants and a novel OLP constraint, along with an algorithm for deciding whether a grammar satisfies it. Our constraint is applicable to all unification grammar formalisms. It is more liberal than the existing decidable constraints, yet it can be tested efficiently.