tailieunhanh - Báo cáo khoa học: "UNIFICATION WITH LAZY NON-REDUNDANT COPYING"

This paper presents a unification procedure which eliminates the redundant copying of structures by using a lazy incremental copying appr0a~:h to achieve structure sharing. Copying of structures accounts for a considerable amount of the total processing time. Several methods have been proposed to minimize the amount of necessary copying. Lazy Incremental 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. . | UNIFICATION WITH LAZY NON-REDUNDANT COPYING Martin c. Emele Project Polygloss University of Stuttgart IMS-CL Ifl-AIS Keplerstrafie 17 D 7000 Stuttgart 1 FRG emele@ Abstract This paper presents a unification procedure which eliminates the redundant copying of structures by using a lazy incremental copying approach to achieve structure sharing. Copying of structures accounts for a considerable amount of the total processing time. Several methods have been proposed to minimize the amount of necessary copying. Lazy Incremental 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 feature 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 structures that satisfy these constraints. Unification is the primary operation for determining the satisfiability 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 unification 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 A it-Kaci 84 and introduced for example in the unification-based formalism 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