Constraint Projection: An Efficient Treatment of Disjunctive Feature Descriptions

CONSTRAINT PROJECTION: AN EFFICIENT TREATMENT OF DISJUNCTIVE FEATURE DESCRIPTIONS Mikio Nakano NTT Basic Research Laboratories 3-9-11 Midori-cho, Musashino-shi, Tokyo 180 JAPAN e-mail: nakano@atom.ntt.jp Abstract Unification of disjunctive feature descriptions is important for efficient unification-based pars- ing. This paper presents constraint projection, a new method for unification of disjunctive fea- ture structures represented by logical constraints. Constraint projection is a generalization of con- straint unification, and is more efficient because constraint projection has a mechanism for aban- doning information irrelevant to a goal specified by a list of variables. 1 Introduction Unification is a central operation in recent com- putational linguistic research. Much work on syntactic theory and natural language parsing is based on unification because unification-based approaches have many advantages over other syn- tactic and computational theories. Unification- based formalisms make it easy to write a gram- mar. In particular, they allow rules and lexicon to be written declaratively and do not need trans- formations. Some problems remain, however. One of the main problems is the computational inefficiency of the unification of disjunctive feature struc- tures. Functional unification grammar (FUG) (Kay 1985) uses disjunctive feature structures for economical representation of lexical items. Using disjunctive feature structures reduces the num- ber of lexical items. However, if disjunctive fea- ture structures were expanded to disjunctive nor- mal form (DNF) 1 as in definite clause grammar (Pereira and Warren 1980) and Kay's parser (Kay 1985), unification would take exponential time in the number of disjuncts. Avoiding unnecessary expansion of disjunction is important for efficient disjunctive unification. Kasper (1987) and Eisele and DSrre (1988) have tackled this problem and proposed unification methods for disjunctive fea- ture descriptions. ~DNF has a form ¢bt Vq~ V¢3 V.-. Vq~n, where ¢i includes no disjunctions. These works are based on graph unification rather than on term unification. Graph unifica- tion has the advantage that the number of argu- ments is free and arguments are selected by la- bels so that it is easy to write a grammar and lexicon. Graph unification, however, has two dis- advantages: it takes excessive time to search for a specified feature and it requires much copying. We adopt term unification for these reasons. Although Eisele and DSrre (1988) have men- tioned that their algorithm is applicable to term unification as well as graph unification, this method would lose term unification's advantage of not requiring so much copying. On the con- trary, constraint unification (CU) (Hasida 1986, Tuda et al. 1989), a disjunctive unification method, makes full use of term unification ad- vantages. In CU, disjunctive feature structures are represented by logical constraints, particu- larly by Horn clauses, and unification is regarded as a constraint satisfaction problem. Further- more, solving a constraint satisfaction problem is identical to transforming a constraint into an equivalent and satisfiable constraint. CU unifies feature structures by transforming the constraints on them. The basic idea of CU is to transform constraints in a demand-driven way; that is, to transform only those constraints which may not be satisfiable. This is why …

Content truncated to 500 words