Introduction
In the late 1980s, the field of Knowledge Representation (KR) faced a fundamental dilemma known as the "Knowledge Representation Trade-off." Researchers were developing terminological logics—the precursors to the modern Web Ontology Language (OWL)—to formalize "frames," which are structured types used to represent categories of objects. The central challenge was balancing expressivity with computational efficiency. While adding features like "number restrictions" (e.g., defining a concept as having "at least three children") made the logic more useful for modeling the real world, it typically rendered the core reasoning task—subsumption—computationally intractable (NP-hard or worse) under standard Tarski-style, two-valued semantics.
In this foundational 1988 paper, Peter Patel-Schneider proposes a solution: by weakening the underlying logic from a standard two-valued system to a four-valued semantics, it is possible to include number restrictions while maintaining polynomial-time complexity for subsumption.
The Problem: The Cost of Expressivity
Subsumption is the process of determining if one concept is more general than another. For example, a reasoner must decide if the concept "Person with at least three children" subsumes "Parent of three lawyers." In standard two-valued logic (where every proposition is either True or False), computing these relationships becomes a combinatorial nightmare as the logic grows more expressive.
To keep systems responsive, developers often resorted to "sound but incomplete" algorithms. These systems were fast but unpredictable; they might fail to find a valid inference without a clear theoretical explanation as to why. Patel-Schneider’s goal was to provide a formal semantic foundation for these reasoners, ensuring that their "incompleteness" was principled and predictable rather than ad-hoc.
Methodology: Four-Valued Semantics
The author’s approach is rooted in the four-valued logic developed by Belnap and Levesque. Instead of the traditional {True, False}, this logic utilizes four truth values:
- {true}
- {false}
- {unknown} (neither true nor false)
- {contradictory} (both true and false)
This framework allows the system to handle incomplete or inconsistent information gracefully. By moving to four-valued semantics, the logic abandons the "Law of the Excluded Middle" (the principle that $A \lor \neg A$ must be true). While this makes the logic mathematically "weaker," it significantly reduces the computational burden because the reasoner does not need to explore every possible world-state to verify a contradiction.
Redefining Identity and Cardinality
The key technical innovation of the paper lies in how it handles identity and counting within this four-valued space.
Four-Valued Identity
In this logic, identity is not a binary state. Two individuals in a domain might be known to be identical, known to be distinct, neither, or both. Patel-Schneider treats elements of the domain as descriptions within an agent's belief space rather than actual, unique objects in the physical world. This "divorce of identity from equality" prevents the combinatorial explosion usually triggered by number restrictions.
Cardinality via Identity
Because identity is four-valued, a set does not have a single, fixed size. Instead, the author introduces two measures of cardinality:
- Minimum Cardinality: The size of the largest subset where all elements are known to be distinct.
- Maximum Cardinality: The size of the largest subset where no two elements are known to be identical.
By defining number restrictions in terms of these bounds, the logic can reason about quantities (e.g., "at least $n$" or "at most $m$") without falling into the complexity traps of standard equality.
Results and Computational Complexity
The paper demonstrates that the subsumption task for this logic is tractable. The author outlines a "structural subsumption" algorithm that involves converting concepts into a canonical form using structure sharing.
- Complexity: The subsumption test runs in time proportional to the product of the sizes of the two concepts, or $O(n \times m)$.
- Soundness: The logic is shown to be sound with respect to standard two-valued semantics. If the four-valued logic determines that concept A subsumes concept B, a standard two-valued logic would reach the same conclusion.
- Expressive Parity: This approach brought the expressive power of four-valued systems nearly to the level of then-dominant (but intractable) systems like KL-ONE and NIKL.
Conclusion and Limitations
While the four-valued approach offers a path to efficiency, it comes with trade-offs. The author acknowledges that four-valued identity is less intuitive than standard equality, leading to a "weaker" set of subsumption relationships that might miss certain inferences a human would naturally expect. Furthermore, the version of the logic presented here excludes certain constructs like "role-value maps," though the author suggests these could be integrated in future iterations.
Ultimately, Patel-Schneider’s work remains a landmark in KR, providing a rigorous way to build fast, predictable reasoning systems by intentionally limiting the logical strength of the underlying semantics.
Summary updated