Unification With Lazy Non-Redundant Copying

UNIFICATION WITH LAZY NON-REDUNDANT COPYING Martin C. Emele* Project Polygloss University of Stuttgart IMS-CL/IfLAIS, KeplerstraBe 17 D 7000 Stuttgart 1, FRG emele~informatik.uni-stut tgaxt .de Abstract This paper presents a unification pro- cedure which eliminates the redundant copying of structures by using a lazy in- cremental copying appr0a~:h to achieve structure sharing. Copying of structures accounts for a considerable amount of the total processing time. Several meth- ods have been proposed to minimize the amount of necessary copying. Lazy In- cremental Copying (LIC) is presented as a new solution to the copying problem. It synthesizes ideas of lazy copying with the notion of chronological dereferencing for achieving a high amount of structure sharing. Introduction Many modern linguistic theories are using fea- ture structures (FS) to describe linguistic objects representing phonological, syntactic, and semantic properties. These feature structures are specified in terms of constraints which they must satisfy. It seems to be useful to maintain the distinction between the constraint language in which feature structure constraints are expressed, and the struc- tures that satisfy these constraints. Unification is the primary operation for determining the satisfia- bility of conjunctions of equality constraints. The efficiency of this operation is thus crucial for the overall efficiency of any system that uses feature structures. Typed Feature Structure Unification In unification-based grammar formalisms, unifica- tion is the meet operation on the meet semi-lattice formed by partially ordering the set of feature structures by a subsumption relation [Shieber 86]. Following ideas presented by [Ait-Kaci 84] and introduced, for example, in the unification-based formMism underlying HPSG [Pollard and Sag 87], first-order unification is extended to the sorted case using an order-sorted signature instead of a flat one. In most existing implementations, descriptions of feature structure constraints are not directly used as models that satisfy these constraints; in- stead, they are represented by directed graphs (DG) serving as satisfying models. In particular, in the case where we are dealing only with con- junctions of equality constraints, efficient graph unification algorithms exist. The graph unifica- tion algorithm presented by Ait-Kaci is a node • merging process using the UNION/FIND method (originMly used for testing the equivalence of fi- nite automata [Hopcroft/Karp 71]). It has its analogue in the unification algorithm for rational terms based on a fast procedure for congruence closure [Huet 76]. Node merging is a destructive operation Since actual merging of nodes to build new node equivalence classes modifies the argument DGs, they must be copied before unification is in- voked if the argument DGs need to be preserved. For example, during parsing there are two kinds of representations that must be preserved: first, lexi- cal entries and rules must be preserved. They need to be copied first before a destructive unification operation can be applied to combine categories to form new ones; and second, nondeterminism in parsing requires the preservation of intermediate representations that might be used later when the parser comes back to a choice point to try some yet unexplored options. *Research reported in this paper …

Content truncated to 500 words