A Non-Well-Founded Approach to Terminological Cycles

Robert Dionne, Eric Mays, Frank J. OlesAAAI 1992

Abstract

Traditional set-theoretic semantics for terminological knowledge representation languages often struggle with circular definitions. This paper introduces concept algebras, a formal framework that employs intensional semantics and non-well-founded set theory to provide a rigorous mathematical foundation for handling terminological cycles. By treating concepts as descriptions rather than mere sets of objects, the authors align formal theory with the practical behavior of AI classifiers.

Introduction: The Challenge of Terminological Cycles

In Knowledge Representation (KR), specifically within term subsumption languages, concepts are defined by their properties. A classic example is defining a "Parent" as a "Human who has a child who is a Human." However, when definitions become mutually recursive—for instance, if Human is also defined in terms of Parent—traditional logic-based systems encounter "terminological cycles."

Historically, these cycles were either prohibited or handled through ad-hoc "hacks" because standard extensional semantics (based on sets of individuals) often lead to infinite recursion or counter-intuitive results. This paper addresses the gap between formal semantics and the practical implementations of classifiers, such as the K-REP system, which must reason about these circularities consistently.

Concept Algebras and Intensional Semantics

The authors propose a shift from extensional to intensional semantics. In an extensional view, two concepts are identical if they denote the same set of individuals. In an intensional view, concepts are distinct if their descriptions differ, even if they happen to refer to the same entities in a particular world.

To formalize this, the paper introduces concept algebras. These algebras define a signature of allowed operations, such as primitive concepts, roles (attributes), and conjunction.

Figure 1: Syntax and semantics of the concept forming operators and terminological axioms.

The core of this approach lies in establishing a set of axioms that these algebras must satisfy, ensuring they behave predictably under operations like "and" (conjunction).

Figure 2: Algebraic axioms defining the structure of concept algebras.

Handling Cycles with Non-Well-Founded Sets

To resolve the problem of infinite recursion in cyclic definitions, the authors leverage Peter Aczel’s theory of non-well-founded sets. Unlike standard Zermelo-Fraenkel set theory, non-well-founded set theory allows for sets that can contain themselves.

By treating a Knowledge Base (KB) as a system of equations, cycles are modeled as the greatest fixed point of these equations. Aczel’s "Solution Lemma" guarantees that such systems have unique solutions in the domain of non-well-founded sets. This mathematical framework allows circular concepts to be treated as well-defined descriptions rather than errors.

Key Results and Algorithmic Foundations

The paper establishes several critical theoretical results:

  • Subsumption Hierarchy: The authors define "descriptive subsumption" algebraically and "structural subsumption" using a Universal Concept Algebra. They prove that descriptive subsumption implies structural subsumption, providing a more refined lens for analyzing concept relationships.
  • Graph Simulation: A significant practical contribution is the demonstration that checking subsumption in a cyclic environment is equivalent to finding a "simulation relation" between two directed graphs (Accessible Pointed Graphs).
  • Formal Correctness: This mapping provides a formal proof of correctness for the recursive classification algorithms used in practical systems like K-REP.

Limitations and Future Directions

While the current model provides a robust foundation for a subset of KR languages (including primitives, conjunctions, and value restrictions), it does not yet account for disjunctions (OR) or negations (NOT). The authors suggest that disjunctions might be modeled using finite power sets of the concept algebra. Additionally, the inclusion of "role value maps"—which compare results across different attribute paths—remains a complex area for future investigation.

Summary updated

BibTeX
@inproceedings{dionne1992non,
  author = {Robert Dionne and Eric Mays and Frank J. Oles},
  title = {{A Non-Well-Founded Approach to Terminological Cycles}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure