Eliminating Circular Justifications in Knowledge Representation

127 concepts82 papers2 proposals

Imagine you ask a system why it believes statement $A$, and it responds, "Because $B$ is true." When you ask why it believes $B$, it responds, "Because $A$ is true."

In classical propositional logic, this kind of circularity is perfectly acceptable. If we have the rules $A \leftarrow B$ and $B \leftarrow A$, setting both $A$ and $B$ to true results in a perfectly valid, logically consistent model. However, in human commonsense reasoning and nonmonotonic paradigms like Answer Set Programming (ASP), this is a major failure. We intuitively expect that truths must be grounded—they must trace back to an external fact or an objective premise. Without a mechanism to prevent these self-supporting loops, automated reasoning systems can validate arbitrary, ungrounded conclusions.

To bridge the gap between classical logic solvers (like SAT solvers) and nonmonotonic semantics, researchers have developed formal techniques to detect, constrain, and eliminate circular justifications.

The Core Failure: Why Standard Completions Fall Short

The challenge of circularity became acute when researchers tried to use high-performance SAT solvers to find stable models for logic programs. A standard approach was Clark's completion, which transforms directional rules into classical bi-implications. For instance, the rules $A \leftarrow B$ and $B \leftarrow A$ complete to $A \leftrightarrow B$.

As noted in ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers, classical translations fail because they treat rules as undirected implications. A SAT solver looking at $A \leftrightarrow B$ can simply assign both variables to true. In ASP, however, this pair forms an unfounded set—a cluster of rules that mutually justify each other in a vacuum without any external support. To enforce true nonmonotonic semantics, the system must force these ungrounded loops to be false unless an independent derivation path exists.

The Mechanism of Loop Formulas

To solve this problem without abandoning the speed of classical SAT solvers, Lin et al. introduced the concept of loop formulas in ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers.

The intuition behind a loop formula is simple: it breaks the self-supporting nature of a cycle by explicitly demanding an exit route. For any cyclic dependency graph (a "loop"), the loop formula states that if any atom within that loop is true, then at least one rule outside the loop must be true to initiate the chain of justification.

Mathematically, if a set of atoms $L$ forms a loop, its loop formula might look like:

$$\bigvee L \implies \bigvee \text{ExternalSupport}(L)$$

If there is no external support, the formula simplifies to $\bigvee L \implies \text{false}$, forcing the SAT solver to set every atom in the loop to false.

This model-theoretic foundation was generalized by Joohyung Lee 0002 in A Model-Theoretic Counterpart of Loop Formulas, which formalized externally supported sets. This work proved that a model belongs to the stable semantics if and only if every subset of literals possesses a valid derivation originating entirely from outside that subset. The authors of Loop Formulas for Circumscription subsequently extended this mechanism to McCarthy's circumscription, demonstrating that circular dependency constraints are universally applicable across different nonmonotonic formalisms to maintain model minimality.

Breaking Symmetry with Orderings and Level Mappings

While loop formulas are mathematically elegant, a logic program can contain an exponential number of loops, making it computationally expensive to find and add every formula upfront. To bypass this bottleneck, researchers developed alternative strategies that eliminate circularity by tracking the chronology or order of derivations.

Index Variables and Partial Orderings

One prominent approach is to inject ordering constraints directly into the logical theory. In Default Logic, Propositional Logic, and Constraints, Ben-Eliyahu et al. demonstrated that cyclic theories can be safely mapped to standard propositional logic by introducing integer-valued index variables.

If a rule states that $B$ justifies $A$, the system enforces a strict inequality:

$$\text{Index}(A) > \text{Index}(B)$$

Because a finite set of integers cannot strictly decrease along a closed path, a cycle like $A \implies B \implies A$ would require $\text{Index}(A) > \text{Index}(B) > \text{Index}(A)$, which is a contradiction. The solver is thus mathematically blocked from satisfying circular loops with true values.

Ordered Completion

Lin et al. adapted this concept to first-order logic in Ordered Completion for First-Order Logic Programs on Finite Structures. By adding explicit derivation-order predicates to the classical theory, they ensured that well-foundedness could be evaluated dynamically by standard first-order reasoning engines, eliminating the need to explicitly enumerate loops.

Level Mappings

When dealing with complex logic programs that include non-monotonic aggregates or constraint atoms, traditional loop formulas can become unwieldy. To address this, Shen et al. proposed a level-mapping formalism in FLP Semantics Without Circular Justifications for General Logic Programs. By assigning a directional level to each semantic evaluation step, this framework ensures that rules cannot rely on their own consequences, preserving the directional nature of logical inference even when rules are evaluated using classical implication.

Historical and Epistemic Foundations

The modern focus on eliminating circular justifications in ASP is the continuation of a long-standing quest for structural integrity in knowledge representation.

In the domain of early AI architecture, Jon Doyle identified this exact hazard in The Ins and Outs of Reason Maintenance. He established that Reason Maintenance Systems (RMS) require finite grounding—a structural guarantee that every belief is supported by a non-cyclic chain of justifications rooted in external assumptions—to prevent the system from adopting arbitrary, self-justifying belief states.

Similarly, in modal and epistemic logics where agents reason about their own knowledge, self-referential loops can lead to paradoxes. To resolve this, Kurt Konolige introduced strongly grounded extensions in On the Relation Between Default Theories and Autoepistemic Logic. This constraint mandates that an agent's beliefs must be logically derived from objective, initial facts rather than allowing beliefs to be accepted merely because they support other beliefs in a self-fulfilling loop.

Whether through the explicit constraints of loop formulas, the mathematical asymmetry of level mappings, or the structural requirements of finite grounding, eliminating circular justifications ensures that automated reasoning remains anchored to reality.

Key Foundational Work

The Ins and Outs of Reason Maintenance (1983) — contributed 3 concept elements to this direction.
Semantical Considerations on Nonmonotonic Logic (1983) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 77 papers
  2. Version 1 · 2026-10-04 · 50 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_circular_justification_9bd2ac4d,
  title = {circular justification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/circular-justification/rdr_9bd2ac4d99664e93be2e19f415f09447},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_circular_justification_9bd2ac4d_v2,
  title = {circular justification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/circular-justification/rdr_9bd2ac4d99664e93be2e19f415f09447/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake