Tech Report CS-89-14

Skeptical Inheritance: Computing the Intersection of Credulous Extensions

Lynn Andrea Stein

February 1989


Ideally skeptical inheritance supports exactly those inferences true in every credulous extension of an inheritance hierarchy. We provide a formal definition of ideally skeptical inheritance. We then give a linear-time algorithm which computes a plausible approximation of ideally skeptical inheritance. However, we show that there are inheritance hierarchies for which this algorithm computes only a subset of the inferences sanctioned by ideally skeptical inheritance. Reasoning by cases is necessary to compute the complete set of inferences. Finally, we give an algorithm which computes ideally skeptical inheritance using a limited form of Boolean satisfiability. It is not known whether this problem is NP-complete.

(complete text in pdf)