Belief Revision & TMS

This topic sits at the intersection of formal epistemology and reasoning-systems engineering. On the theoretical side, it covers the AGM framework for rational belief change, including its postulates, the relationships between revision and contraction, the limits imposed by triviality theorems, and the computational and representational costs of carrying out revision. On the engineering side, it covers Truth Maintenance Systems (TMS) as the practical machinery that tracks which beliefs are justified, which assumptions underlie them, and what to do when contradictions arise. Together these two strands matter because any system that reasons over a large, evolving knowledge base must decide how to incorporate new information without silently corrupting the old, and the AGM literature provides the normative criteria while TMS provides the operational substrate.

The AGM core is defined by exactly eight postulates: the first six (Closure, Success, Inclusion, Vacuity, Consistency, Extensionality) are the "basic" set, while Superexpansion and Subexpansion are the two "higher-order" postulates attributed to Darwiche and Pearl (agm-postulates-8-specific-postulates, agm-eight-postulates-names). Within this framework, the Levi and Harper identities give exact mathematical bridges between revision and contraction operators, ensuring that an AGM-compliant revision maps to a contraction satisfying all eight contraction postulates including Recovery (levi-harper-identities-link-revision-contraction). Several concrete revision operators are characterized: Full meet revision satisfies all eight postulates but is deemed too conservative because it discards the entire old knowledge base upon inconsistency (full-meet-revision-satisfies-all-agm-postulates); Dalal revision selects models of the new information at minimal Hamming distance from the old, requiring no auxiliary structure (dalal-revision-hamming-distance); and WIDTIO retains only formulae present in every maximal consistent subset intersected with the new information (widtio-intersection-maximal-consistent-subsets). A key limitation is Gärdenfors' triviality theorem, which shows that no non-trivial revision operator can satisfy all AGM postulates while also honoring the Ramsey test for counterfactual conditionals in the object language (gardenfors-triviality-theorem, gardenfors-triviality-revision-counterfactuals). Operationally, revision applies when old and new beliefs describe the same situation and the agent must discard old beliefs, whereas update applies when old beliefs describe the past and new information describes the present, governed by a principle of inertia (revision-vs-update-temporal-distinction). The computational cost is substantial: query answering and model checking for most revision operators land at the second level of the polynomial hierarchy rather than in P or NP (belief-revision-complexity-second-level-ph), and revision can cause representational blow-up where the output is exponentially larger than the inputs (belief-revision-representational-blow-up).

The TMS side introduces the engineering architecture and the distinctions that make belief tracking tractable. A TMS uses a two-component design: a domain reasoner performs inferences while the TMS tracks justifications and consistency, and the TMS itself does no domain reasoning (tms-two-component-architecture). Within the TMS, exactly two justification types are supported—Support Lists and Conditional Proofs (tms-two-justification-types). A critical structural distinction separates base facts, which are preconditions that can later be rejected, from derived facts that depend on them; this contrasts with AGM belief revision, which treats all formulae in the belief set as equally important (tms-base-facts-vs-derived-facts). Premises, or fundamental assumptions, require no justification at all, whereas every non-premise node must carry at least one valid justification to remain in the belief set (tms-premises-require-no-justification). Historically, the original TMS was published by Doyle in 1979, de Kleer extended it to the Assumption-Based TMS in 1986, and the first multi-agent versions appeared with Mason and Johnson (1989) and Bridgeland and Huhns (1990) (doyle-1979-original-tms-dekleer-1986-atms, first-multi-agent-tms-mason-johnson-1989). Single-context TMS enforces classical consistency across all stored facts, while multi-context TMS achieves paraconsistency by scoping consistency to tagged subsets with inference history (tms-single-vs-multi-context-paraconsistency). This paraconsistent stance is fundamentally different from revision itself: revision removes old inconsistent beliefs to make room for new ones, whereas paraconsistent logic retains everything and simply tolerates the contradiction (belief-revision-removes-vs-paraconsistent-tolerates).

All beliefs in this group are currently IN; none have been retracted. This means the knowledge base holds a consistent, mutually compatible picture of the AGM theoretical landscape and the TMS engineering landscape, with no prior claims having been withdrawn or contradicted by newer inferences. The coexistence of both the normative AGM results and the operational TMS mechanisms under a single IN status indicates that the system treats them as complementary rather than competing accounts of belief management.