Title:	Efficient Lazy Unification
Authors:	Noriko Tomuro, Steven L. Lytinen
Abstract:	Parsing with unification grammars is inefficient due to the intractable complexity of the algorithm. In implemented systems, performance suffers even more by additional overhead of processing large feature-value structures (FSs) as the base data structure. In particular, copying and unification of FSs has been identified to be the most expensive operation. In this paper, we present an algorithm which copies FSs efficiently. The algorithm is a version of lazy unification, an optimization technique for unification-based systems. The algorithm utilizes a data structure called environment for bookkeeping, and it is relatively simple. The algorithm attains efficiency by lazy evaluation, in which FSs are copied only when necessary, and structure sharing, in which only the necessary portion of the FSs are copied. We present empirical testing which shows a marked effect by our algorithm in achieving a linear average case parsing performance.
Full Paper:	[postscript]