M.Sc Thesis

M.Sc StudentJaeger Efrat
SubjectUnification Grammars and Off-Line Parsability
DepartmentDepartment 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.