A Unification Method for Disjunctive Feature Descriptions

A Unification Method for Disjunctive Feature Descriptions Robert T. Kasper USC/Information Sciences Institute 4676 Admiralty Way, Suite 1001 Marina del Rey, CA 90292 and Electrical Engineering and Computer Science Department University of Michigan Abstract Although disjunction has been used in several unification- based grammar formalisms, existing methods of unification have been unsatisfactory for descriptions containing large quantities of disjunction, because they require exponential time. This paper describes a method of unification by succes- sive approximation, resulting in better average performance. 1 Introduction Disjunction has been used in severM unlfication-based gram- mar formalisms to represent alternative structures in descrip- tions of constituents. Disjunction is an essential component of grammatical descriptions in Kay's Functional Unification Grammar [6], and it has been proposed by Karttunen as a Linguistically motivated extension to PATR-II [2]. In previous work two methods have been used to handle disjunctive descriptions in parsing and other computational applications. The first method requires expanding descriptions to dis- ]unctl've normal form (DNF) so that the entire description can be interpreted as a set of structures, each of which con- tains no disjunction. This method is exemplified by Definite Clause Grammar [8], which eliminates disjunctive terms by expanding each rule containing disjunction into alternative rules. It is also the method used by Kay [7] in parsing FUG. This method works reasonably well for small grammars, but it is clearly unsatisfactory for descriptions containing more than a small number of disjunctions, because the DNF ex- pansion requires an amount of space which is exponential in the number of disjunctions. The second method, developed by Karttunen [2], uses con- straints on dlsjuncts which must be checked whenever a die- junct is modified. Karttunen's method is only applicable to value disjunctions (i.e. those disjunctions used to specify the value of a single feature), and it becomes complicated and in- efficient when disjuncts contain non-local dependencies (i.e. values specified by path expressions denoting another fea- ture). In previous research [4,5] we have shown how descriptions of feature structures can be represented by a certain type of logical formula, and that the consistency problem for dis- junctive descriptions is NP-complete. This result indicates, according to the widely accepted mathematical assumption that P ~ NP, that any complete unification algorithm for disjunctive descriptions wiU require exponential time in the worst case. However, this result does not preclude algorithms with better average performance, such as the method de- scribed in the remainder of this paper. This method over- comes the shortcomings of previously existing methods, and has the following desirable properties: 1. It appUes to descriptions containing general disjunction and non-local path expressions; 2. It delays expansion to DNF; 3. It can take advantage of fast unification algorithms for non-disjunctive directed graph structures. 2 Data Structures The most common unification methods for non-disjunctive feature structures use a directed graph (DG) representation, in which arcs are labeled by names of features, and nodes correspond to values of features. For an introduction to these methods, the reader is referred to Shieber's survey …

Content truncated to 500 words