Introduction
In the development of artificial intelligence, a persistent tension exists between mathematical rigor and computational efficiency. During the 1980s, researchers were caught between nonmonotonic reasoning formalisms like Default Logic—which offered logical precision but were often computationally intractable—and inheritance reasoners (semantic networks), which were fast and intuitive but frequently ad hoc and logically inconsistent.
David Etherington’s work bridges this gap by demonstrating that Touretzky’s "inferential distance" algorithm—a graph-based method for handling inheritance with exceptions—is formally sound within the framework of Default Logic. This finding suggests that for specific structured problems, we can achieve both logical correctness and computational tractability.
The Challenge of Inheritance with Exceptions
The core problem addressed is "inheritance with exceptions," where general rules are overridden by more specific information. Consider the following hierarchy:
- Molluscs normally have shells.
- Cephalopods are molluscs, but normally don't have shells.
- A Nautilus is a cephalopod and does have a shell.
A naive "shortest-path" algorithm in a semantic network might reach conflicting conclusions depending on which path it traverses first. To resolve this, the "inferential distance" algorithm uses the topology of the network to prioritize more specific information over general superclasses.
Formalizing the Mapping
Etherington performs a formal mapping between two distinct systems:
- Touretzky’s Inheritance Language: A network representation using nodes for individuals or classes and four types of links (IS-A, ISN'T-A, RELATED, and UNRELATED).
- Reiter’s Default Logic: A formal system where "defaults" are rules of inference. A default rule typically states: "If $A$ is known and it is consistent to believe $B$, then assume $B$."
By translating network links into default logic formulas—for example, an IS-A link from class $A$ to $B$ becomes a default rule—the paper proves a significant theorem: the ground facts produced by the Inferential Distance algorithm are guaranteed to reside within a single "extension" (a consistent set of beliefs) of the corresponding Default Theory.
Handling Ambiguity: The Nixon Diamond
A critical test for any inheritance reasoner is how it handles genuine ambiguity. The classic example is the "Nixon Diamond": Richard Nixon is both a Quaker (who are typically pacifists) and a Republican (who are typically not pacifists).
In such cases, the algorithm correctly identifies that there is no logical basis to prefer one conclusion over the other. It remains neutral, returning the intersection of possible logical extensions—essentially concluding that the information is insufficient to decide.
Key Insights and Results
The paper provides several foundational insights for symbolic AI:
- Topology as Logic: The shape of a knowledge graph can perform the work of complex logical inference. By calculating "inferential distance," contradictions are resolved without the need for expensive, general-purpose theorem provers.
- Formal Adequacy: Touretzky’s algorithm is proven to be "formally adequate," meaning its results are logically valid conclusions within Default Logic, not just heuristic guesses.
- Computational Tractability: While general Default Logic is undecidable, this specific class of inheritance reasoning can be handled in polynomial time and space.
- Parallelism Constraints: While these networks are fast, implementing them on massively parallel hardware requires "conditioning" the network (adding redundant links), which introduces a computational cost of $O(N^2)$.
Limitations and Future Directions
Despite its success, the mapping has limitations. It does not yet cover "no-conclusion" links that block inheritance without providing alternatives, nor does it handle "strict" links (definitions without exceptions). Furthermore, while the algorithm is effective for ground facts (e.g., "Fred has a shell"), its application to normative statements remains preliminary. Finally, the "update problem"—the need to recondition the network whenever the knowledge base changes—remains a potential bottleneck for dynamic AI systems.
Summary updated