Modularizing Contexted Constraints

Modularizing Contexted Constraints John Griffith* Seminar fiir Sprachwissenschaft Universitgt 'Fiibingen K1. Wilhehnstr. 113, D-72074 Tiibingen, Germany griflith4~)sfknphil.uni-tuebingen.de Abstract This paper describes a nlethod for com- piling a constraint-based grammar into a potentially inore efficient form for pro- cessing. This method takes dependent disjunctions within a constraint formula and factors them into non-interacting groups whenever possibh; by determining their independence. When a group of de- pendent disjunctions is split into slnaller groups, an exponential amount of redun- dant information is reduced. At runtime, this ineans that all exponential alnount of processing can be saved as well. Since the performance of an algorithm ibr pro- cessing constraints with dependent dis- jmmtions is highly deterxnined by its in- put, the transformatioll presented in this paper should prove beneficial for all such algorithms. 1 Introduction There are two facts that conspire to make tile treatment of disjunction an important consider- ation when building a natural language process- ing (NLP) system. The first fact is that nat- ural languages are full of ambiguities, and in a grammar many of these ambiguities are de- scribed by disjunctions. The second fact is that the introduction of disjmmtion into a grammar causes processing tilne to increase exponentially in the number of disjunets. This means that a nearly linear-time operation, such as uififieation of Imrely conjunctive feature structures, becomes an exponential-time problem as soon as disjunctions are included, t Since disjunction is unlikely to dis- * This work was sponsored by Teilprojekt B4 "t~¥om Constraints to Rules: Compilation of lipS(;" of the Sonderforsehungsbereieh 340 of the Deutsche Forsehungsgemeinschaft. I would also like to thank Dale Gerdemann and Guido Minnen for helpfltl com- ments on the ideas presented here. All remaining er- rors are of course my own. tAssuming P # NIL appear from natur~fl language gralnlnars, control- ling its form (:all save exponential amounts of time. This paper introduces all etficient normal tbrm for processing dependent disjunctive constraints and an operation for compilation into this normal form. This ot)eration , modularization, can reduce exponential alnounts of redtmdant information in a grainmar and can consequently save correspond- ing alnounts of processing time. While this oper- ation is general enough to be applied to a wide variety of constraint systems, it; was originally de- signed to optimize processing of dependent dis- junctions in featm'e structure-based grammars. In particular, modular fea.tuie structures are more eflicient R)r unification than non-Inodulm' ones. Since ill many current NLP systems, a signiti- cant amount of tilne is spent performing unifica- tion, optimizing feature structures for unillcatioll shouhl increase the tmrtbrmance of these, syst;ems. Many algorithms for etticient mfitication of lea tare structures with dependent disjunctions have been propose.d (Maxwell and Kaplan, 1989; F, isele and DSrre, 1990; Gerdemann, 1991; StrSmbSek, 1992; Griflith, 1.996). However, all of these al- gorithms sutfer from a common problem: thc.ir performance is highly deternfined by their inputs. All of these algorithms will perform at their best when their dependent disjunctions interact as lit- tle as possible, but if all of the …

Content truncated to 500 words