Abstract
This paper addresses the challenge of non-uniqueness in autoepistemic logic (AEL) by introducing the concept of stratified autoepistemic theories. By partitioning theories into hierarchical layers, the author ensures the existence of a single, unique stable expansion. This framework provides a formal bridge between AEL and logic programming, demonstrating that "negation as failure" is a specific instance of autoepistemic reasoning.
Introduction
In the 1980s, the quest for formalizing non-monotonic reasoning—where conclusions can be retracted upon receiving new information—led to the development of several formalisms. Robert Moore’s autoepistemic logic (AEL) emerged as a prominent approach, utilizing a belief operator $L$ (where $Lf$ signifies "$f$ is believed") to represent an agent's self-knowledge. However, AEL suffered from a lack of "well-behavedness": a set of premises could lead to multiple conflicting stable expansions or no consistent set of beliefs at all. This ambiguity made it difficult to define what constitutes a "theorem" within the logic. Gelfond's work seeks to identify a specific structural class of these theories that ensures they are mathematically stable and computationally useful.
The Concept of Stratification
The author introduces stratification as a means of organizing autoepistemic theories into a hierarchy. The core principle involves partitioning a theory into layers ($T_0, T_1, \dots, T_n$) such that the definition of a proposition $p$ occurs in a lower layer than any belief operator $Lp$ referencing it.
By enforcing this hierarchy, the framework prevents circular definitions of belief—such as believing $A$ because one believes $B$, while simultaneously believing $B$ only because one believes $A$. These circularities are the primary cause of logical paradoxes and multiple stable expansions in standard AEL. The author provides a constructive proof for building the unique stable expansion of a stratified theory, starting from the base "objective" layer and progressing upward through the hierarchy.
Unifying Logic Programming and Autoepistemic Logic
A central contribution of the paper is the formal mapping $I$ between logic programs and autoepistemic formulas. Gelfond demonstrates that the "negation as failure" operator ($\neg p$) commonly used in programming languages like Prolog is semantically equivalent to the autoepistemic statement "it is not believed that $p$" ($\neg Lp$).
This insight suggests that the way logic programs handle negation is not merely a procedural trick but a rigorous form of autoepistemic reasoning. Under the condition of stratification, three major approaches to AI reasoning—Autoepistemic Logic, Negation as Failure, and Prioritized Circumscription—are shown to coincide, providing a unified theoretical foundation.
Key Results
The paper establishes several foundational theorems that validate the utility of stratified theories:
- Existence and Uniqueness (Theorems 2 & 3): Every consistent, stratified autoepistemic theory is guaranteed to possess exactly one stable expansion. This provides a clear, unambiguous definition of theoremhood.
- Logical Equivalence (Theorem 5): For stratified logic programs, a query is true if and only if its autoepistemic translation is a theorem in the corresponding unique expansion.
- Computational Feasibility: Because of the relationship between AEL and logic programming, the author proves that classical SLDNF resolution (the algorithm behind Prolog) can serve as the deductive engine for a broad class of autoepistemic theories.
Limitations and Future Directions
Despite its theoretical significance, the current framework is limited to propositional logic. For the approach to be fully applicable to complex AI systems, it must be extended to include quantification (the use of "for all" and "there exists").
Furthermore, stratification is a syntactic restriction. While it ensures well-behaved theories, there may be valid common-sense reasoning patterns that do not fit into a strict hierarchy. The author suggests that while stratification is a powerful tool, future research should investigate other syntactically described classes of theories that might also yield unique expansions while supporting different reasoning patterns.
Summary updated