Quarterly (March, June, September, December)
160 pp. per issue
6 3/4 x 10
ISSN
0891-2017
E-ISSN
1530-9312
2014 Impact factor:
1.23

Computational Linguistics

Paola Merlo, Editor
June 2007, Vol. 33, No. 2, Pages 153-160
(doi: 10.1162/coli.2007.33.2.153)
© 2007 Massachusetts Institute of Technology
Maximal Consistent Subsets
Article PDF (127.85 KB)
Abstract

Default unification operations combine strict information with information from one or more defeasible feature structures. Many such operations require finding the maximal subsets of a set of atomic constraints that are consistent with each other and with the strict feature structure, where a subset is maximally consistent with respect to the subsumption ordering if no constraint can be added to it without creating an inconsistency. Although this problem is NP-complete, there are a number of heuristic optimizations that can be used to substantially reduce the size of the search space. In this article, we propose a novel optimization, leaf pruning, which in some cases yields an improvement in running time of several orders of magnitude over previously described algorithms. This makes default unification efficient enough to be practical for a wide range of problems and applications.