Abstract
Access-Limited Logic (ALL) provides a computationally tractable framework for automated reasoning by restricting inference to "reachable" paths within a network-structured knowledge base. This paper extends the original ALL framework to $ALL_{neg}$, incorporating classical negation and proof by contradiction (reductio ad absurdum). We introduce the concept of "Socratic Completeness," where the system can derive any logical consequence given an appropriate sequence of queries and assumptions. Our analysis shows that the complexity of $ALL_{neg}$ scales polynomially with the size of the knowledge base for a fixed depth of nested assumptions, offering a powerful tool for broad but shallow common-sense reasoning.
Introduction
A fundamental challenge in Knowledge Representation (KR) is the tradeoff between the expressiveness of a logical language and the efficiency of its deductive procedures. While First-Order Logic (FOL) is highly expressive, global search methods like resolution are often computationally intractable for large-scale systems. Access-Limited Logic (ALL) addresses this by mimicking human-like network-centric retrieval, where reasoning is confined to assertions reachable through specific access paths in a frame-based architecture.
However, early iterations of ALL lacked support for negation and disjunction, limiting their utility in complex reasoning scenarios. This work introduces $ALL_{neg}$, which integrates these features while maintaining the efficiency that makes ALL attractive for large-scale AI applications.
The $ALL_{neg}$ Framework
Access Paths and Frame Representation
The core of $ALL_{neg}$ is the restriction of inference to predefined access paths. Unlike standard FOL, where any assertion can be retrieved at any time, $ALL_{neg}$ requires that queries follow existing links between "frames" (objects). For example, instead of a global search for siblings, the system must navigate from a specific individual to their relatives.
As shown in the figure above, a logical relation $r(a,b)$ is represented within the frame system as a value $b$ stored under the slot $r$ of frame $a$. This structure ensures that reasoning remains localized and computationally bounded.
Negation and Proof by Contradiction
$ALL_{neg}$ treats negation as a first-class citizen, distinct from "negation as failure." The system explicitly tracks inconsistent states using a stack-based knowledge base structure. When an assumption is made, it is pushed onto the stack. If the system derives a contradiction (e.g., both $P$ and $\neg P$), it performs reductio ad absurdum: the stack is popped, the assumption is retracted, and its negation is asserted as a verified fact in the parent context.
Socratic Completeness and Complexity
A key theoretical contribution of this work is the definition of Socratic Completeness. Rather than attempting to find every possible deduction automatically—which would lead back to NP-completeness—$ALL_{neg}$ guarantees that if a fact is a logical consequence of the knowledge base, there exists a sequence of external queries and assumptions that will lead the system to it.
The computational "difficulty" in this framework is measured not by the length of a proof, but by the depth of nested assumptions. The authors prove that for a knowledge base of size $m$ and a maximum nesting depth $n$, the inference process is bounded by $O(m^n)$. This is particularly relevant for common-sense reasoning, which often involves vast amounts of data but rarely requires deeply convoluted chains of nested "what-if" scenarios.
Implementation and Practical Application
The principles of $ALL_{neg}$ were implemented in Algernon, a Lisp-based reasoning system. Algernon has been successfully applied to solve logic puzzles and build qualitative model builders (such as QPC). In these applications, "obvious" deductions—those following from simple rule chaining—are computed in a single operation, providing a responsive interface for complex domain modeling.
Limitations and Conclusion
While $ALL_{neg}$ significantly enhances the expressive power of access-limited reasoning, it currently lacks support for mixed existential and universal quantification (e.g., "Every person has a father"). Unrestricted creation of new frames during inference could lead to infinite loops or memory exhaustion. Future work will focus on controlling frame creation to allow for fuller quantification and integrating these methods with default reasoning systems.
By bounding complexity through assumption depth rather than proof length, $ALL_{neg}$ provides a scalable path forward for AI systems requiring broad, common-sense knowledge.
Summary updated