h t t p s : / / w w w . d e k l e e r . o r g / P u b l i c a t i o n s / A n % 2 0 A s s u m p t i o n - B a s e d % 2 0 T M S . p d f

Ingest: An Assumption-based TMS

Type: kb/sources/types/ingest-report.md

Classification

This is a scientific paper that defines an assumption-based truth maintenance system, gives its formal properties and algorithms, and discusses implementation choices and motivating applications. Author: Johan de Kleer, then at Xerox PARC's Intelligent Systems Laboratory, developed the ATMS and situates it against earlier truth maintenance systems and his own qualitative-reasoning systems.

Summary

An ATMS records each derived datum with a minimal label of consistent assumption sets under which it holds. Justifications propagate these labels, while contradictions produce minimal “nogood” assumption sets whose supersets are excluded. This lets a problem solver retain mutually incompatible possibilities in one database, reuse conclusions across contexts by subset tests, and avoid most retraction and backtracking. The paper specifies consistency, soundness, completeness, and minimality requirements for labels, describes an incremental update algorithm, and explains implementation optimizations. Its guarantees are relative to the supplied assumptions and justifications: the ATMS maintains what follows in which consistent environments, but it does not decide whether the assumptions, inference rules, or conclusions are true or empirically warranted.

Quotes

No source quotes have been retained yet.

Connections Found

The paper is a technical basis for comparing explicit assumption dependencies with Commonplace's checker-relative source dependencies in A note is an atomic step relative to the check that reads it: both make a conclusion's usable support conditions inspectable, although they operate over different objects and checks. It also supplies a formal counterpoint to A claim's warrant does not determine its fit in a working theory: an ATMS can establish derivability and consistency relative to an assumption environment without establishing the independent warrant or theory fit of any member.

Learning Claims (our opinion)

The paper calls the ATMS an intelligent cache or primitive learning scheme because it accumulates justifications and contradictions, transfers derivations across contexts, and avoids repeating work. This is learning only in that restricted operational sense. It is not theory refinement: empirical cases do not revise a tentative theory, and the ATMS supplies no operator for judging or repairing the assumptions and domain rules that determine its consequences. Instead, it incrementally compiles problem-solver-supplied structure into labels and nogoods. The source therefore sharpens a useful boundary for Commonplace: retaining dependency structure can improve reuse and localize inconsistency without providing evidence that the retained theory became better. The paper's formal analysis supports that mechanism, but it does not empirically establish improved learning outcomes.

Extractable Value

  1. Separate conditional validity from warrant. An explicit dependency structure can determine that a conclusion follows under a consistent assumption set without showing that the assumptions or inference rules deserve belief. This directly answers the occasion's “what it does not establish” boundary. [quick-win]
  2. Represent support as minimal environments. A conclusion can carry several minimal assumption sets, with every consistent superset inheriting it; contradictions can likewise be stored as minimal nogoods that invalidate all supersets. This is a reusable formal model for maintaining conclusions across alternative contexts. [deep-dive]
  3. Keep content inference separate from dependency maintenance. The problem solver supplies assumptions, data, and justifications, while the ATMS computes where their consequences hold. The separation clarifies that provenance machinery can preserve and propagate a dependency relation without choosing the claims or validating their content. [quick-win]
  4. Treat inconsistency as scoped by dependency. A contradiction invalidates environments containing its supporting assumptions rather than forcing global retraction, allowing unaffected conclusions to remain usable. This offers a precise comparison point for localizing conflicts in a knowledge base. [experiment]
  5. Account for combinatorial cost. Minimal labels avoid enumerating every context, but worst-case labels and nogoods can still be exponential in the number of assumptions; explicit dependency maintenance is therefore an architectural tradeoff, not a free guarantee of scalable context management. [just-a-reference]

Limitations (our opinion)

The paper establishes the ATMS's formal label properties relative to supplied assumptions and justifications, but it does not test whether those inputs are correct or whether the resulting conclusions match an external world. Its efficiency discussion relies on algorithmic analysis, implementation experience, and motivating examples rather than a systematic benchmark against alternatives; the author also acknowledges exponential worst cases and expensive justification retraction. The framework therefore supports claims about conditional derivability and scoped inconsistency more strongly than broad claims about practical efficiency, learning quality, or epistemic reliability. Its assumptions are symbolic and explicitly enumerated, so transfer to natural-language KB claims also requires a separate account of how assumptions and dependency edges are identified and checked.

Write a note titled “Dependency tracking preserves conditional support, not warrant” that states the boundary, uses the ATMS as its formal case, and distinguishes dependency maintenance from claim validation and theory refinement.