Abstract

Title: Nonminimal Derivations in Unification-based Parsing
Published: May 1998
Authors: Steven L. Lytinen, Noriko Tomuro
Abstract: Many algorithms for parsing unification grammars are extensions of well-known context-free parsing techniques, such as chart parsing. An example is Shieber's abstract parsing algorithm (Shieber, 1992), which can be viewed as an extension of Earley's algorithm. In this paper, we discuss a difficulty that exists in these algorithms in general, and in Shieber's algorithm in particular. The difficulty is that these algorithms produce what we call "nonminimal derivations". Nonminimal derivations are parse trees which contain more information (i.e., features) than they absolutely have to. We show examples of nonminimal derivations produced by Shieber's algorithm, and enumerate the situations in which such derivations are produced. We then suggest several possible ways to modify to the algorithm to address this problem.
Full Paper: [postscript]