An Efficient ATMS for Equivalence Relations

Caroline N. Koff, Nicholas S. Flann, Thomas G. DietterichAAAI 1988

Abstract

Reasoning about equality ($x = y$) across multiple contexts is a fundamental challenge in automated reasoning. Traditional Assumption-based Truth Maintenance Systems (ATMS) often struggle with the $O(n^3)$ complexity of transitive equality rules or the memory explosion of maintaining separate UNION-FIND structures for every context. This paper introduces a specialized ATMS for equivalence relations that utilizes a graph-based label-update algorithm. By treating equivalence classes as complete graphs with labeled edges and employing a disjoint union ($\oplus$) operation for updates, the proposed system achieves $O(n^2)$ complexity and eliminates redundant derivations.

Introduction

In the late 1980s, the Assumption-based Truth Maintenance System (ATMS) became a cornerstone for reasoning in multiple possible worlds or contexts. However, equality reasoning remained a significant bottleneck. Standard implementations either relied on inefficient axiomatic encodings of transitivity or memory-intensive context-specific data structures. This work proposes a "middle way" that combines the efficiency of UNION-FIND with the multi-context capabilities of an ATMS.

The Challenge of Equality Reasoning

Two primary methods existed for handling equality in an ATMS. The first, axiomatic encoding, involves providing the ATMS with transitivity rules ($x=y \land y=z \implies x=z$). Due to the symmetric and circular nature of these rules, the ATMS frequently re-derives the same equalities, leading to $O(n^3)$ complexity.

Standard ATMS justification links for transitivity, showing the overhead of explicit dependency tracking.

The second method, UNION-FIND, is highly efficient for single contexts but fails to scale when $2^k$ possible contexts must be tracked simultaneously, leading to an exponential explosion in memory usage.

A Specialized ATMS for Equivalence

The authors propose a specialized architecture that moves away from standard justification links for equality. Instead, they introduce "Weak Equivalence Classes," where terms are grouped if they are equal in any context.

The proposed graph-based representation where edges are labeled with assumption sets.

In this model, the equivalence class is treated as a complete graph. Each edge between nodes (terms) is labeled with the set of assumptions (environments) under which those terms are equal. This representation allows the system to calculate new labels directly through a mathematical operation called a disjoint union ($\oplus$), rather than searching through a complex dependency graph.

Key Insights and Implementation

The core insight is that the label of an equality $x=z$ is essentially the union of labels along the path from $x$ to $z$ in the graph. By exploiting the mathematical properties of transitivity, the system can maintain implicit dependencies within the labels themselves. To ensure logical consistency even when assumptions are not unique, the system assigns unique "equality tokens" to each piece of evidence, performing logic on these tokens before mapping them back to the original ATMS assumptions.

Results and Complexity

The specialized ATMS was implemented and tested as part of FORLOG, a forward-chaining logic programming language. Theoretical analysis and empirical testing demonstrated a reduction in label update complexity from $O(n^3)$ to $O(n^2)$. Furthermore, the elimination of explicit justification links for equalities resulted in significant space savings and the removal of redundant derivations that previously plagued ATMS implementations.

Conclusion and Future Work

While highly efficient for simple constants and Skolem constants, the current system does not yet handle compound terms or functions (which would require congruence closure). Future research aims to extend this specialized ATMS to perform full unification and improve performance in scenarios with a high number of contradictions (nogoods), where standard ATMS pruning might currently hold an advantage.

Summary updated

BibTeX
@inproceedings{koff1988efficient,
  author = {Caroline N. Koff and Nicholas S. Flann and Thomas G. Dietterich},
  title = {{An Efficient ATMS for Equivalence Relations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure