In the early 1980s, Knowledge Representation (KR) was dominated by "semantic networks"—graphical structures where nodes represent concepts and edges represent relationships. While these networks were intuitive for representing strict taxonomies, they struggled with the nuances of real-world knowledge, specifically defaults and exceptions. David Etherington and Raymond Reiter’s 1983 paper, "On Inheritance Hierarchies With Exceptions," provided a landmark formalization of these systems using Default Logic.
The Problem: Beyond Strict Taxonomies
Early AI researchers favored inheritance hierarchies for their simplicity. In a strict taxonomy, properties are inherited without question: if a Poodle is a Dog, and a Dog is a Mammal, then a Poodle is a Mammal.
However, common-sense reasoning is rarely so rigid. We often rely on "defaults"—rules that are generally true but allow for exceptions. For instance, "Birds normally fly," but "Penguins are birds that do not fly." Standard first-order logic collapses under such contradictions; asserting both that all birds fly and that some birds do not leads to a logical explosion where anything can be proven.
Early systems like NETL attempted to handle exceptions using a "shortest path" heuristic, where the "closest" information in the graph takes precedence. Etherington and Reiter demonstrated that this approach was mathematically unstable and often led to incorrect or ambiguous conclusions.
Formalizing Defaults with Logic
To provide a rigorous foundation, the authors mapped inheritance networks to Default Logic. A default rule is structured as: "If X is true, and it is consistent to assume Y, then conclude Z."
They categorized network links into five types, translating each into logical formulae:
- Strict IS-A/ISN'T-A: Standard logical implications (e.g., $A \implies B$).
- Default IS-A/ISN'T-A: Rules that hold unless evidence suggests otherwise.
- Exception Links: Specific "blockers" that prevent a default rule from firing (e.g., "Don't apply the 'Birds fly' rule if the subject is a Penguin").
By using "semi-normal" defaults, the authors created a system that explicitly checks for these blockers before drawing a conclusion. They proposed a relaxation-style constraint propagation algorithm to iteratively build an "extension"—a maximal set of consistent beliefs derived from the network.
Key Insights: The Nautilus Problem and Locality
One of the paper's most significant contributions is the critique of local inference. The authors argued that determining if a property is inherited is a non-local problem. In complex networks, a "blocker" or exception might be located many nodes away from the concept being evaluated.
This insight had profound implications for the "marker-passing" hardware popular at the time. If inference requires checking distant parts of a graph to ensure consistency, simple parallel algorithms where nodes only communicate with immediate neighbors are insufficient. The "Nautilus" problem (depicted above) serves as a classic example of how overlapping paths and exceptions can lead to "inter-extension interference," where different valid sets of beliefs might emerge.
Results and Legacy
Etherington and Reiter proved that acyclic networks are "coherent," meaning they are guaranteed to have at least one consistent extension. While they acknowledged the "Ambiguity Problem"—where a network might support multiple valid but conflicting extensions—their work provided the first formal semantics for inheritance with exceptions.
The paper ended on a cautionary note regarding massively parallel architectures. The authors demonstrated that for unrestricted hierarchies, a single-pass parallel algorithm under purely local control is likely impossible. This shifted the focus of the field toward identifying specific "natural classes" of hierarchies that allow for efficient, perhaps parallel, inference without sacrificing the expressive power needed for common-sense reasoning.
Summary updated