tailieunhanh - Báo cáo khoa học: "CONSTRAINT PROJECTION: AN EFFICIENT TREATMENT DISJUNCTIVE FEATURE DESCRIPTIONS "

Unification of disjunctive feature descriptions is important for efficient unification-based parsing. This paper presents constraint projection, a new method for unification of disjunctive feature structures represented by logical constraints. Constraint projection is a generalization of constraint unification, and is more efficient because constraint projection has a mechanism for abandoning information irrelevant to a goal specified by a list of variables. These works are based on graph unification rather than on term unification. Graph unification has the advantage that the number of arguments is free and arguments are selected by labels so that it is easy to write a grammar. | 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@ Abstract Unification of disjunctive feature descriptions is important for efficient unification-based parsing. This paper presents constraint projection a new method for unification of disjunctive feature structures represented by logical constraints. Constraint projection is a generalization of constraint unification and is more efficient because constraint projection has a mechanism for abandoning information irrelevant to a goal specified by a list of variables. 1 Introduction Unification is a central operation in recent computational linguistic research. Much work on syntactic theory and natural language parsing is based on unification because unification-based approaches have many advantages over other syntactic and computational theories. Unificationbased formalisms make it easy to write a grammar. In particular they allow rules and lexicon to be written declaratively and do not need transformations. Some problems remain however. One of the main problems is the computational inefficiency of the unification of disjunctive feature structures. Functional unification grammar FUG Kay 1985 uses disjunctive feature structures for economical representation of lexical items. Using disjunctive feature structures reduces the number of lexical items. However if disjunctive feature structures were expanded to disjunctive normal 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 Dorre 1988 have tackled this problem and proposed unification methods for disjunctive feature descriptions. DNF has a form 1 V ộĩ V 03 V V fin where ỷ includes no .