Abstract
Recursive logic rules, such as transitive relations in genealogy, historically posed significant challenges for automated inference systems, often leading to infinite loops or extreme redundancy. This paper presents a method for handling such rules by modeling inference as a network of "producer-consumer" processes. By utilizing an active connection graph that permits cycles and ensures data collectors never transmit duplicate results, the system achieves efficient, terminating recursive inference within the SNePS (Semantic Network Processing System) framework.
Introduction: The Challenge of Recursion
In early knowledge representation and symbolic AI, recursive rules—where a relation is defined in terms of itself—were a primary source of instability for theorem provers. A classic example is the "Ancestor" relation: if $A$ is the parent of $B$, and $B$ is an ancestor of $C$, then $A$ is an ancestor of $C$.
Standard "chaining" algorithms typically fail on these rules in two ways:
- Infinite Loops: The system may recursively apply a rule to its own output without a termination condition.
- Redundancy: Systems often build expansive tree structures that re-solve identical sub-problems, leading to computational inefficiency.
The authors aimed to develop an inference engine for SNePS that could handle these rules regardless of whether the underlying data was specific facts (extensional) or general rules (intensional).
Methodology: The Active Connection Graph
The proposed solution replaces static search trees with a dynamic AND/OR problem reduction graph composed of active processes. The architecture relies on four specialized process types:
- INFER: Matches queries against the database to find specific formula instances.
- CHAIN: Applies specific rules (e.g., "if $A$ and $B$, then $C$").
- SWITCH: Manages variable bindings, translating results between the context of a general rule and a specific query.
- FILTER: Regulates data flow when a general process provides results to a more specific request.
The core innovation is the producer-consumer model. When a sub-problem is identified, the system checks if a process is already addressing it. If so, the new "parent" process attaches itself as a "boss" to the existing process. This creates cycles in the process graph. Because these processes act as "data collectors" that store results and never transmit the same answer twice, the cycle naturally terminates once all unique answers are found.
Key Insights
Cycles as a Feature
While most systems attempt to detect and prune cycles to avoid loops, Shapiro and McKay argue that cycles are the natural representation of recursion. By managing data flow through these cycles rather than avoiding them, the system handles recursive logic elegantly.
Data Collectors and Loop Termination
By ensuring that INFER and CHAIN processes store their results and communicate only unique findings to their "bosses," the system prevents the "ping-pong" effect of recursive logic. Termination is guaranteed as long as the set of possible answers in the database is finite.
Context Independence and Uniformity
The system factors the "Most General Unifier" (MGU) into source and target bindings, allowing processes to operate in their original variable context. Furthermore, the system treats facts and rules identically within the semantic network, eliminating the distinction between base relations and defined relations.
Results and Performance
The SNePS inference system demonstrated several key capabilities:
- Recursive Stability: It handles transitive relations and circular definitions without specialized code.
- Efficiency: It avoids redundant work by sharing sub-processes across different parts of a query.
- Guaranteed Termination: The system terminates correctly even with rules that could theoretically apply infinitely, provided the database contains finite facts.
- Order Independence: Results are consistent regardless of the processing order of rules or antecedents.
Limitations
Despite its strengths, the system faces practical constraints. Termination is ultimately bounded by available resources, and managing these bounds in extremely complex networks remains a challenge. Additionally, the computational cost of the "match routine" for retrieving unifiable formulas is significant. Finally, in domains involving an infinite set of Skolem constants, the process only terminates if a finite number of answers is requested.
Summary updated