PaperlayerView exact revision on arXiv

Source-linked AI summary

From Doyle to AGM: A Survey and an Implementation Roadmap for Belief Change

Yuri Almeida, Arthur Casals

arXiv:2608.14567v1cs.AIcs.LO

TL;DR

Systematic empirical comparison of AGM, pre-AGM, and hybrid belief-revision implementations remains lacking. This targeted narrative review maps the field’s computational and theoretical evolution, finding that deployed applications synthesize pre-AGM efficiency with AGM rigor.

  • Problem

    Systematic empirical comparison of AGM, pre-AGM, and hybrid belief-revision implementations remains lacking, limiting evaluation of their practical characteristics.

  • Method

    The paper conducts a targeted narrative review that maps Doyle and London’s taxonomy onto pre-AGM computational approaches, AGM theory, and contemporary implementations.

  • Results

    Deployed applications demonstrate synthesis of pre-AGM computational efficiency with AGM theoretical rigor, while iterated revision and the frame problem remain open engineering concerns.

  • Takeaways & Limitations

    The review provides a historical and theoretical baseline for systematic implementation analysis and engineering-focused belief-revision research.

  • Takeaways & Limitations

    The original Doyle and London taxonomy may underrepresent social epistemology, emotional factors, and some multi-agent belief-revision research.

Abstract

from arXiv · show

This paper presents a targeted narrative review establishing the historical and theoretical foundations for computational belief change implementation. Seeded by Doyle and London's foundational 1980 taxonomy, we trace the evolution of belief revision from computational origins through the theoretical transformation of the AGM framework to contemporary approaches. Our analysis demonstrates how pre-AGM computational pragmatism relates to AGM theoretical constructs, revealing both continuities and transformations across this evolution. We analyze how each taxonomical category evolved in the post-AGM era, identifying the theoretical foundations and historical precedents that inform contemporary implementation challenges. This foundation enables subsequent research into robust computational blueprints that synthesize historical insights with formal guarantees, providing the baseline for systematic implementation analysis and engineering-focused belief change research.

1 Introduction

Belief revision enables AI systems to update beliefs, resolve contradictions, and maintain coherent knowledge in changing environments. This paper frames the implementation challenge through a targeted narrative review connecting pre-AGM computational approaches with AGM theory and contemporary research.

  • Foundations: Belief revision updates an agent’s beliefs when new information conflicts with its current knowledge state.It determines which beliefs to abandon, which information to accept, and how to preserve consistency and coherence.
  • The Core Problem: When new information creates inconsistency, belief revision theories address which existing beliefs to discard and why.The problem arises because conflicting statements cannot all be retained as true.
  • Importance for AI: Belief revision is crucial for AI systems operating with incomplete, contradictory, and changing information.It supports adaptive reasoning, learning and reasoning integration, human-like reasoning, and consistency maintenance in knowledge systems.
  • Implementation Challenge: AGM provides rigorous normative principles for belief change, but its operations are co-NP-complete in the worst case, complicating exact large-scale implementation.Practical systems may therefore require approximations that can compromise the theoretical guarantees.
  • Research Motivation: The paper revisits pre-AGM algorithms because their focus on tractability, incremental processing, and deployment constraints may inform contemporary implementations.It compares pre-AGM algorithms with post-AGM developments to evaluate how earlier models relate to AGM theory and can be adapted.
  • Approach and Contribution: The study uses a targeted narrative review grounded in Doyle and London to trace belief revision from computational origins through theoretical formalization to contemporary implementations.It establishes a historical and theoretical baseline for systematic research on computational blueprints and engineering-focused implementation.

2 Related Work

Existing belief-revision surveys span foundational taxonomy, formal AGM theory, computational implementation, application domains, and philosophical or multi-agent perspectives. This review distinguishes itself by tracing pre-AGM computational approaches through AGM to contemporary implementations while integrating historical, theoretical, and practical analysis.

  • Foundational surveys: Doyle and London’s 1980 bibliography established the taxonomical foundation, while Gärdenfors and Makinson developed comprehensive theoretical and formal foundations for belief revision.Doyle and London’s work was primarily descriptive; Makinson focused on contraction operations and their formal properties, complementing Gärdenfors’ philosophical treatment.
  • Foundational surveys: Mid-1990s handbook treatments synthesized post-AGM research by covering AGM postulates, construction methods, representation theorems, criticisms, and limitations.Gärdenfors and Rott’s chapter established an authoritative, canonical presentation of AGM theory and its extensions.
  • Scope of existing surveys: Later surveys examined theoretical connections, formal constructions, belief-base and kernel methods, implementation, complexity, approximation, ontology change, belief merging, and resource-bounded revision.These works generally emphasize theoretical development, computational constraints, specific logical frameworks, or multi-source information rather than the historical evolution central to this review.
  • This review’s contribution: Unlike primarily post-AGM, theoretical, or computational surveys, this review traces pre-AGM computational approaches through AGM to contemporary implementations and integrates theory with practice.It uses Doyle and London’s taxonomy to maintain historical continuity and examines how practical concerns influenced theory and theoretical insights informed practice.

3 Background and Foundations

This section traces belief revision from philosophical and computational foundations through Newell’s knowledge-level perspective to the AGM framework. It positions the survey as a bridge connecting pre-AGM computational approaches with AGM’s unified theoretical account.

  • Knowledge-Level Foundations: Newell’s knowledge-level perspective framed belief revision as rational, goal-directed behavior independent of specific symbolic representations or implementation mechanisms.It distinguished ideal competence from computational performance, motivating both normative theories and implementation-oriented computational theories.
  • Early Computational Foundations: Early AI architectures operationalized principled belief revision by tracking belief justifications and dependencies through truth maintenance and assumption-based reasoning systems.These approaches included Doyle’s truth maintenance systems and De Kleer’s assumption-based reasoning frameworks.
  • Pre-AGM Belief Revision: Pre-AGM research developed application-specific and syntactic belief-change models, leaving unresolved how revision could be described independently of belief representation.Doyle and London’s 1980 survey documented about 250 related papers, while later work exposed the limitations of representation-dependent formulations.
  • The AGM Framework: The AGM framework unified expansion, contraction, and revision through rationality postulates and representation theorems linking abstract principles to concrete constructions.The survey uses Doyle’s taxonomy to connect the practice-oriented pre-AGM era with AGM and identify both continuities and innovations in that transformation.
  • Survey Contribution: The survey bridges pre-AGM computational practice and AGM theory by using Doyle’s taxonomy to organize their correspondence and transformation.Its correspondence analysis identifies both continuities and innovations across the transition to the AGM theoretical umbrella.

4 The AGM Model

The AGM framework supplied principled logical foundations for belief revision through closed belief sets, formal operations, and rationality postulates. Its logical omniscience and deductive closure, however, create implementation difficulties for bounded agents, motivating belief-base and non-prioritized approaches.

  • Origins: AGM emerged in the mid-1980s to provide systematic theoretical foundations and evaluation criteria for rational belief revision systems.It applied rigorous logical and set-theoretic methods to belief revision.
  • Formal Foundations: AGM represents beliefs as logically closed sets under a consequence operator, assuming standard properties including monotonicity, deduction, and compactness.Logical closure embodies logical omniscience because agents are treated as aware of all consequences of their beliefs.
  • Belief-Change Operations: The model defines expansion, contraction, and revision, with revision adding information while modifying existing beliefs as needed to preserve consistency.Contraction removes beliefs while minimizing change, whereas expansion may produce inconsistency.
  • Implementation Limitations: Logical omniscience and deductive closure make standard AGM belief sets infeasible for bounded agents because nontrivial bases generate infinite sets and obscure belief provenance.These limitations motivate finite belief bases and more realistic non-prioritized revision frameworks.

5 Pre-AGM Belief Revision

Pre-AGM belief revision emerged from AI efforts to manage uncertain and changing information, emphasizing practical implementation over theoretical foundations. Doyle and London’s 1980 taxonomy organized this computational landscape and anticipated later theoretical developments while revealing its emphasis on tractability.

  • Taxonomical method: Doyle and London organized the field empirically by identifying recurring change tasks, representational devices, and inference regimes, then assigning multiple labels to each entry.The categories were not mutually exclusive: one system could combine representations, procedures, inference styles, and applications.
  • Taxonomical scope: The taxonomy covered global issues, representations, procedures, non-monotonic and inexact inference, theoretical issues, applications, and related issues.Its scope ranged from dependency-based revision and default reasoning to probabilistic, fuzzy, temporal, modal, and situational approaches.
  • Computational priorities: Pre-AGM approaches addressed updating world models, reconciling inconsistent hypotheses, and absorbing new information with minimal disruption.These pressures corresponded to the taxonomy’s Global Issues, Representations, and Procedures categories.
  • Limitations and deployment: Pre-AGM implementations often used efficient but logically informal updating heuristics, while probability-based models faced scalability and applicability difficulties.Most systems were demonstrated on toy or small-scale domains, with notable deployments including DART and GDE.
  • Algorithmic contributions: Pre-AGM systems introduced dependency tracking, non-chronological backtracking, multi-context reasoning, uncertainty quantification, and frameworks for incomplete information.These innovations came from TMS, ATMS, probabilistic networks, and default reasoning systems, respectively.
  • Distribution of research: 47% of papers focused on procedural approaches, 77% on representational innovations, 70% on applications, and 48% on theoretical issues.The distribution demonstrates the field’s primary emphasis on computational tractability and practical aspects of belief revision.

6 Re-examining Pre-AGM Systems Through Post-AGM Theory

The section re-examines pre-AGM computational belief-revision systems through AGM’s axiomatic framework, linking empirical practices to formal postulates and tracing their subsequent evolution. It combines historical taxonomy reconstruction with theoretical correspondence analysis while acknowledging classification limitations and scope boundaries.

  • Theoretical Re-examination: AGM theory provided rigorous axiomatic foundations that were absent in the pre-AGM era, enabling systematic reinterpretation of earlier computational systems.The section frames this reinterpretation as both an opportunity and a methodological challenge.
  • Analytical Framework: Taxonomical mapping reconstructs Doyle and London’s categories to identify influential computational innovations and patterns of research emphasis.The analysis maps computational approaches to taxonomy categories and examines their empirical structure.
  • Analytical Framework: Postulate correspondence analysis relates each pre-AGM approach to specific AGM postulates, revealing how computational insights anticipated later theoretical formalization.The comparison considers both direct correspondences and cases where computational practice preceded theory.
  • Analytical Framework: Evolution tracing follows each Doyle taxonomy category through post-AGM developments, showing how computational insights were formalized, extended, or superseded.The tracing identifies theoretical developments, seminal papers, and transformation patterns across categories.
  • Limitations and Scope: Doyle’s multi-labeling and heterogeneous granularity complicate structured classification, while social and multi-agent dimensions remain outside the taxonomy’s AGM-focused scope.These limitations motivate AGM-aware refinements, and the scope excludes contemporary social dimensions not anticipated in the pre-AGM era.

7 Taxonomical Evolution in the Post-AGM Era

Post-AGM work transformed Doyle’s empirical taxonomy into a normative, postulate-based theory of rational belief change while preserving computational concerns about choice, minimal disruption, and implementation. This evolution separated revision from update, formalized iterated change and computational feasibility, and supported practical systems that combine AGM semantics with dependency-aware, modular repair strategies.

  • From empirical taxonomy to normative theory: AGM transformed Doyle’s empirical taxonomy into a normative framework for rational belief change governed by postulates and representation theorems.The framework includes closure, success, inclusion, consistency preservation, vacuity, extensionality, and constraints for iterated revision.
  • Revision and update: Post-AGM theory separated belief revision, which incorporates new information through minimal change, from belief update, which accommodates changes in the world.Revision uses faithful assignments, systems of spheres, and distance-based minimization, whereas update uses possible-model and persistence principles.
  • Choice and minimal change: Doyle’s themes of alternative choice and minimal disruption became formal mechanisms using selection functions, preference orderings, sphere semantics, distance metrics, and partial-meet constructions.These constructions select among maximal consistent subsets or minimize change across possible worlds or logical theories.
  • Change over time: Iterated revision extended AGM beyond single change episodes by imposing rationality constraints on belief sequences and developing natural, lexicographic, restrained, priority-based, and ordinal-ranking policies.The Darwiche-Pearl postulates motivated systematic study of how successive inputs should interact over time.
  • Implementation synthesis: Contemporary implementations combine AGM’s formal repair semantics with dependency tracking, incremental processing, modular repair, kernel methods, and complexity-guided strategies to support scalable knowledge management.Ontology repair demonstrates adaptation beyond propositional logic, while complexity results provide precise bounds for implementation planning.

8 Synthesis and Analysis

The synthesis presents AGM as a unifying source of formal rigor and design templates, while preserving pre-AGM computational pragmatism and identifying persistent theoretical gaps. It also shows that Doyle’s taxonomy remains historically informative for contemporary symbolic, probabilistic, neural-symbolic, distributed, and implementation challenges, subject to stated scope limitations.

  • AGM’s Theoretical Contribution: AGM unified heterogeneous pre-AGM proposals through common rationality postulates, enabling systematic comparison, mathematical precision, and proof-oriented analysis.Its postulates, construction methods, and representation theorems connect abstract criteria to implementable operators and generated research on limitations, extensions, and computable realizations.
  • Complementary Traditions: Pre-AGM practice contributes implementable algorithms, incremental processing, efficient data structures, bounded-memory awareness, and real-time responsiveness.AGM complements these strengths with auditable rationality postulates, mathematical precision, conceptual unification, and representation theorems linking principles to operators.
  • Persistent Challenges: The frame problem and underspecified preference elicitation remain persistent challenges for efficient revision in dynamic, partially observed settings.Naively recomputing closure is untenable, while AGM provides limited operational guidance for inferring entrenchment orderings or selection functions from users, logs, or latent models.
  • Taxonomical Correspondence: Doyle’s Non-Monotonic Inference and Inexact Inferential Techniques categories do not map directly onto AGM postulates, exposing theoretical gaps involving default reasoning and numerical uncertainty.Non-monotonic inference derives tentative conclusions from incomplete information, whereas AGM concerns incorporating information; probabilistic and fuzzy approaches address uncertainty that AGM abstracts away from.
  • Historical Synthesis: The post-AGM evolution transforms empirical observations of computational practice into normative frameworks, validating Doyle’s taxonomy as a guide to enduring structural features and cross-era integration.This synthesis provides a foundation for identifying opportunities to combine historical insights across theoretical sophistication and computational implementation.
  • Contemporary Relevance: Contemporary systems require revision across symbolic and subsymbolic representations while reconciling statistical inference, logical consistency, concurrency, trust, scalability, efficiency, and modularity.These requirements extend concerns addressed by probabilistic networks and de Kleer’s ATMS, while amplifying pre-AGM computational demands through scale and real-time constraints.

9 Discussion

The review traces belief revision from Doyle and London’s pre-AGM computational practice through AGM theory to contemporary implementations, finding that effective systems combine computational pragmatism with formal rigor. It establishes a foundation for implementation research while identifying unresolved engineering challenges and the need for systematic empirical comparison.

  • Historical Evolution: The field evolved from ad hoc computational techniques into a theoretically rigorous discipline with practical applications.The review frames this development from Doyle and London’s 1980 bibliography onward.
  • Theory-Practice Synthesis: Deployed applications demonstrate that pre-AGM computational efficiency and AGM theoretical rigor can be synthesized in practice.Examples include ontology debugging and repair, belief merging with distance-based optimization and SAT compilation, and ontology repair using kernel-style operators.
  • Core Findings: Pre-AGM methods supplied implementable, modular techniques with explicit computational costs, while AGM introduced rationality postulates, representation theorems, and a comparative language.Contemporary implementations operationalize selected AGM-style operators through incremental algorithms and approximations under practical constraints.
  • Design Implications: The review proposes using AGM as specification and pre-AGM as implementation, supplemented by learned preferences and resource-aware execution, while labeling this a design hypothesis.Preference elicitation remains largely ad hoc, and iterated revision and the frame problem remain open engineering concerns.
  • Research Agenda: The resulting historical and theoretical baseline supports architectural design, gap analysis, empirical validation, and engineering-focused research, but systematic empirical comparison of AGM, pre-AGM, and hybrid approaches remains lacking.Future work is directed toward practical, theoretically sound, computationally efficient belief revision systems and unified synthesis frameworks.

A Theoretical Development Tracking Methodology

The methodology systematically snowballed from Doyle and London’s 1980 bibliography to trace how pre-AGM work contributed to the emergence of the AGM framework and its 1985 foundational paper.

  • Methodological Approach: The review began with pre-AGM papers catalogued in Doyle and London’s 1980 taxonomy.These papers provided the starting point for forward-citation tracing.
  • Methodological Approach: Forward citations were used to trace the emergence of the AGM framework from earlier computational research.The methodology specifically followed developments from the pre-AGM literature into AGM.
  • Methodological Approach: Early work on consistency maintenance, belief dependencies, and rational choice was traced to Alchourrón, Gärdenfors, and Makinson’s foundational 1985 paper.The methodology treated this AGM paper as the central theoretical cornerstone.

A.1 Detailed Methodology Explanation · A.1.1 Phase 1: Pre-AGM Foundation Analysis

The methodology began by systematically analyzing Doyle and London’s 1980 bibliography to map the pre-AGM computational landscape across its eight-point taxonomy. It then used backward citation analysis to trace the epistemological, philosophical, and logical roots informing later AGM theory.

  • A.1.1 Phase 1: Pre-AGM Foundation Analysis: The analysis examined Doyle and London’s 1980 bibliography of approximately 250 papers representing the pre-AGM computational landscape.The papers were systematically categorized according to the original eight-point taxonomy.
  • A.1.1 Phase 1: Pre-AGM Foundation Analysis: One taxonomical category covered consistency maintenance mechanisms, including Truth Maintenance Systems and dependency networks.
  • A.1.1 Phase 1: Pre-AGM Foundation Analysis: Another category addressed belief revision procedures such as backtracking, assumption management, and conflict resolution.
  • A.1.1 Phase 1: Pre-AGM Foundation Analysis: The taxonomy also included rational choice and preference modeling through decision theory applications and utility-based approaches.
  • A.1.1 Phase 1: Pre-AGM Foundation Analysis: Knowledge representation frameworks formed another category, encompassing semantic networks, frame systems, and production rules.
  • A.1.1 Phase 1: Pre-AGM Foundation Analysis: Backward citation analysis traced the theoretical and philosophical roots of these computational approaches through epistemology, philosophy of science, and formal logic.These connections were traced as influences that would later inform AGM theory.

A.1.2 Phase 2: AGM Emergence Tracking

Forward citation analysis tracked AGM’s emergence through papers formalizing and unifying pre-AGM computational approaches. It identified the 1985 foundational synthesis as connecting computational insights with rationality, logic, and theory-change traditions.

  • AGM emergence: Forward citation analysis identified papers that developed formal frameworks from multiple pre-AGM computational works.The analysis traced papers that cited multiple pre-AGM computational works while developing formal theoretical frameworks.
  • AGM emergence: These papers unified disparate computational approaches under common principles and introduced normative postulates for rational belief change.They also mathematically formalized concepts that had appeared algorithmically in pre-AGM work.
  • Foundational synthesis: The 1985 Alchourrón, Gärdenfors, and Makinson paper synthesized insights from Doyle’s Truth Maintenance Systems.The cited computational contributions included dependency tracking and conflict resolution.
  • Foundational synthesis: The synthesis also drew on decision theory, formal logic and model theory, and philosophy of science concerning rational choice, semantics, and theory change.These traditions contributed preference structures, consistency requirements, semantic approaches to belief change, and scientific rationality.

A.1.3 Phase 3: Post-AGM Extension Mapping

The post-AGM extension mapping used systematic forward snowballing to identify influential AGM-related work and classify its theoretical and computational extensions. Selected papers were also checked for intellectual lineage from pre-AGM insights, AGM constructs, or connections between both developments.

  • Selection criteria: The review selected papers with > 100 citations that explicitly reference AGM foundational work, using citation impact as an influence threshold.This criterion was intended to identify work indicating significant influence on the field’s development.
  • Theoretical Extension Categories: Theoretical extensions were categorized as constructive extensions, limitation addresses, representation theorems, and complexity analyses.These categories respectively addressed operationalization, problems in the original framework, computational procedures, and computational properties of AGM operations.
  • Lineage Verification: Each selected paper was verified to maintain a clear intellectual lineage from pre-AGM computational insights or AGM theoretical constructs.The verification examined how algorithmic innovations were formalized and how AGM extensions or refinements were developed.
  • Lineage Verification: The lineage verification also covered cross-connections between computational and theoretical development.This captured links between pre-AGM computational insights and AGM theoretical constructs.

A.1.4 Phase 4: Systematic Coverage Validation

The review validated comprehensive coverage through cross-reference checks spanning major surveys, publication venues, and AGM-adjacent theoretical paradigms. These checks addressed developments that snowballing or citation links might have missed.

  • Cross-reference validation: Cross-reference validation was used to ensure comprehensive coverage.The validation process included survey analysis, venue-based sampling, and paradigm boundary checking.
  • Cross-reference validation: Major belief revision surveys and AI venues were systematically reviewed to identify developments missed by snowballing or weak citation links.Surveys covered G¨ardenfors 1988, Hansson 1999, and Ferm´e & Hansson 2018; venues included IJCAI, AAAI, KR, AIJ, JLC, and JPL from 1985–2024.
  • Cross-reference validation: Paradigm boundary checking covered classical AGM theory, belief bases, iterated revision, computational complexity, approximation theory, and multi-agent extensions.The stated coverage also included dynamic belief change, belief-set relationships, and social choice extensions.

A.1.5 Phase 5: Temporal and Conceptual Organization · A.1.6 Quality Assurance and Validation

The review organized selected papers chronologically and conceptually to trace theoretical development, conceptual lineage, and cross-paradigm connections from 1985–2024. Quality assurance combined peer-review prioritization, replication and extension analysis, implementation attention, and expert validation.

  • A.1.5 Phase 5: Temporal and Conceptual Organization: The papers were organized chronologically and conceptually to trace developments across the 1985–2024 period.This organization addressed how theoretical insights emerged, matured, and influenced subsequent work.
  • A.1.5 Phase 5: Temporal and Conceptual Organization: The review traced how pre-AGM computational innovations, including dependency tracking in TMS, evolved into formal constructs such as epistemic entrenchment orderings.
  • A.1.5 Phase 5: Temporal and Conceptual Organization: It examined intersections between complexity theory, preference learning, multi-agent systems, and core AGM theory.
  • A.1.6 Quality Assurance and Validation: Quality assurance prioritized papers from top-tier, rigorously peer-reviewed venues to support theoretical quality and methodological soundness.
  • A.1.6 Quality Assurance and Validation: Replication and extension analysis tracked whether key theoretical results were replicated, extended, or challenged by subsequent work.This captured both stable contributions and evolving understanding.
  • A.1.6 Quality Assurance and Validation: The selection maintained explicit attention to theory–implementation bridges, keeping theoretical tracking connected to computational practice.
  • A.1.6 Quality Assurance and Validation: Expert cross-checking against major belief revision course reading lists and established researchers’ recommendations supported historical accuracy, comprehensive coverage, and pre-AGM/post-AGM continuity.
Loading 2608.14567v1…