Accession Number:

ADA281503

Title:

Classification in Feature-Based Default Inheritance Hierarchies

Descriptive Note:

Technical rept.

Corporate Author:

ROCHESTER UNIV NY DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Light, Marc

Report Date:

1993-11-01

Pagination or Media Count:

32.0

Abstract:

When one works with a system that utilizes inheritance hierarchies the following problem often arises. A new object is introduced and it must be integrated into a hierarchy under which classes in the hierarchy should the new object be positioned In this paper, I formalize this problem for feature-based default inheritance hierarchies. Since it turns out to be NP-complete, I present an approximation algorithm for it. I show that this algorithms is efficient and look at some of the possible problematic situations for the algorithm. Although more analysis and experimentation are needed, these preliminary results show that the algorithm warrants such efforts.

Descriptors:

• *ALGORITHMS
• *HIERARCHIES
• *LINGUISTICS
• *NATURAL LANGUAGE
• EFFICIENCY
• PROBLEM SOLVING
• LEXICOGRAPHY
• SPEECH

Subject Categories:

• Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE