Classification in Feature-Based Default Inheritance Hierarchies
Marc Light · 1993
. Increasingly, inheritance hierarchies are being used to reduce redundancy in natural language processing lexicons. Systems that utilize inheritance hierarchies need to be able to insert words under the optimal set of classes in these hierarchies. In this paper, we formalize this problem for feature-based default inheritance hierarchies. Since the problem turns out to be NP-complete, we present an approximation algorithm for it. We show that this algorithm is efficient and that it performs well with respect to a number of standard problems for default inheritance. A prototype implementation has been tested on lexical hierarchies and it has produced encouraging results. The work presented here is also relevant to other types of default hierarchies. Zusammenfassung. In zunehmendem Masse werden Erbschaftshierarchien zur kompakten Beschreibung von Worteigenschaften in Sprachverarbeitungslexica verwendet. Systeme, die Erbschaftshierarchien benutzen, mussen Worte in die optimale Klasse (ode...