Paper: Modularizing Contexted Constraints

ACL ID C96-1076
Title Modularizing Contexted Constraints
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1996

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.