Classification in Feature-Based Default Inheritance Hierarchies

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1993
Accession Number
ADA281503

Entities

People

  • Marc Light

Organizations

  • University of Rochester

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Cognitive Science
  • Computational Linguistics
  • Computer Science
  • Computers
  • Coverings
  • Dictionaries
  • Grammars
  • Language
  • Linguistics
  • Mathematics
  • Natural Languages
  • Phrase Structure Grammars
  • Polynomials
  • Prototypes
  • Syntax

Fields of Study

  • Computer science

Readers

  • Artificial Intelligence
  • Computer Vision.
  • Operations Research