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

Abstract

This article 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 Alchourrón, Gärdenfors, and Makinson (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 (BR) is the process by which an intelligent agent modifies its beliefs when confronted with new information that contradicts its current knowledge state (Gärdenfors, 1988). This fundamental cognitive and computational process involves determining which existing beliefs to abandon, which new beliefs to accept, and how to maintain consistency and coherence in the resulting belief system. Unlike simple belief addition, which merely incorporates new information, BR requires sophisticated mechanisms to handle conflicts, prioritize information sources, and preserve the most reliable or important beliefs while discarding those that have become untenable.

To illustrate the problem faced by BR, we adapt an example from Fermé and Hansson (2018, pp. 1–2). Suppose that the following statements are all true:

John was born in Portugal ( $\alpha$ )

Pedro was born in Massaguassú ( $\beta$ )

John and Pedro are compatriots ( $\gamma$ )

From these statements, we infer that Massaguassú is in Portugal. Now, assume that we received two new pieces of information:

Massaguassú is not a country ( $\delta$ )

Massaguassú is in Brazil ( $ϵ$ )

Since the five statements are inconsistent, it follows that it is not viable to accept all five as true. There are several different approaches to dealing with this problem. Should we forget some of our previous beliefs? If so, which are the ones we choose to forget? And why? These are just a few of the questions that BR theories try to answer.

The formal study of BR encompasses both normative theories that specify how rational agents should revise their beliefs and descriptive theories that model how BR actually occurs in natural and artificial systems. At its core, BR addresses three fundamental operations: expansion (adding new beliefs without removing old ones), contraction (removing beliefs to restore consistency), and revision (adding new beliefs while removing conflicting old ones to maintain consistency) (Alchourrón et al., 1985).

BR is crucial for artificial intelligence (AI), as real-world AI systems must operate in dynamic, uncertain environments where information is incomplete, potentially contradictory, and subject to change (Doyle, 1979). Unlike static knowledge bases that assume perfect and unchanging information, intelligent agents must continuously update their understanding based on new observations, sensor data, user inputs, and changing environmental conditions.

It also plays a pivotal role in simulating human-like reasoning (Harman, 1986). By modeling cognitive processes, AI systems can more effectively emulate human thought patterns, which is invaluable in developing intelligent assistants, educational tutors, and collaborative systems, to name a few examples. Furthermore, BR supports the integration of learning and reasoning in AI (Mitchell, 1997). As systems increasingly combine data-driven methods, such as machine learning, with symbolic reasoning, BR facilitates the reconciliation of learnt patterns with logical rules through approximate operators (Chopra et al., 2001) and anytime algorithms (Wassermann, 1999) that balance computational efficiency with theoretical soundness. This integration fosters the development of robust hybrid AI systems capable of excelling in complex tasks (Bengio et al., 2013; Russell & Norvig, 2010).

Finally, BR is indispensable for maintaining consistency in knowledge systems. Systems such as expert systems and knowledge graphs rely on consistent information to ensure accuracy and utility (Davis & Lenat, 1982). Updating these systems without introducing logical errors is a fundamental challenge that BR effectively addresses. By enabling these diverse capabilities, BR functions as a key mechanism to advance the adaptability, reliability, and intelligence of AI systems (Russell & Norvig, 2010).

In summary, the importance of BR in AI manifests itself in multiple dimensions:

Adaptive reasoning: AI systems must adapt their reasoning as new evidence emerges, requiring mechanisms to identify which beliefs are no longer supported and how to propagate changes throughout interconnected knowledge structures (Doyle, 1979).

Consistency maintenance: As agents acquire new information, conflicts inevitably arise with existing beliefs. BR provides principled methods for resolving these conflicts while preserving the coherence of the overall knowledge set (Alchourrón et al., 1985).

Learning and knowledge acquisition: Machine learning systems inherently involve BR as they update their models based on new training data, requiring sophisticated approaches to balance new evidence against established patterns (Mitchell, 1997).

Multi-agent systems: When multiple AI agents share information, BR becomes essential to incorporate the knowledge of other agents while maintaining individual epistemic autonomy (Stone & Veloso, 2000).

Human-AI interaction: AI systems that interact with humans must revise their beliefs based on user feedback, corrections, and changing preferences, necessitating robust BR mechanisms that can handle subjective and contextual information (Amershi et al., 2014).

Ontology repair and knowledge base maintenance: Modern AI systems increasingly rely on formal ontologies to structure domain knowledge, yet these ontologies must evolve as understanding deepens or inconsistencies emerge (Flouris & Plexousakis, 2005, 2006; Konstantinidis et al., 2007). Recent work has established formal connections between Alchourrón, Gärdenfors, and Makinson (AGM) BR and ontology repair, demonstrating that contraction operations can be adapted to description logic ontologies through optimal repair strategies that minimize information loss while restoring consistency (Baader & Wassermann, 2024; Flouris et al., 2006, 2013; Flouris & Plexousakis, 2006; Souza, 2024). This extension of classical BR to expressive logical frameworks provides principled methods for maintaining large-scale knowledge bases in semantic web technologies, knowledge graphs, and enterprise systems, making BR essential for the reliability of contemporary knowledge-centric AI applications.

1.1. Problem Statement and Motivation

The field of BR faces a fundamental challenge in bridging the gap between theoretical foundations and practical implementation (Fermé et al., 2025; Fermé & Hansson, 2018). While the AGM framework provides rigorous normative principles for rational belief change, these operations are computationally intractable in the worst case (co-NP-complete) (Nebel, 1998), making exact implementation infeasible for large-scale applications and often requiring approximations that may compromise theoretical guarantees (Chopra et al., 2001; Delgrande et al., 2013; Williams, 1997). In contrast, pre-AGM computational approaches demonstrated practical feasibility but lacked systematic theoretical foundations that could ensure rational behavior or provide principled evaluation criteria. This theory-practice gap manifests itself in several critical ways. Computational complexity: AGM revision operations are generally co-NP-complete, making exact implementation infeasible for large-scale applications, yet the relationship between approximation strategies and theoretical soundness remains poorly understood (Liberatore, 2023; Liberatore & Schaerf, 1996; Nebel, 1998). Preference specification: AGM theory requires preference structures such as epistemic entrenchment orderings or selection functions, but provides limited guidance on how to acquire these preferences from users, data, or domain expertise (Williams, 1994). Implementation strategies: Whereas AGM provides clear normative constraints, it offers little guidance on data structures, algorithms, or architectural decisions needed for practical systems (Delgrande et al., 2013; Williams, 1996).

The motivation for this research stems from the recognition that pre-AGM computational approaches, developed before theoretical foundations were established, may contain valuable implementation insights that have been overlooked by the post-AGM focus on theoretical development. These early systems were designed with explicit attention to computational tractability, incremental processing, and practical deployment constraints, concerns that remain central to contemporary AI applications but are often secondary in theoretical research.

Additionally, the proliferation of AI systems in dynamic, uncertain environments, from autonomous vehicles to conversational agents, has renewed interest in practical BR implementations that can operate under real-time constraints with limited computational resources. Understanding how pre-AGM approaches addressed these challenges, and how their insights can be integrated with AGM’s theoretical framework, is crucial for developing the next generation of intelligent systems.

To better understand progress in this field, it is essential to revisit the BR algorithms that preceded the influential AGM model, which has become the dominant approach. By comparing the state of pre-AGM algorithms with post-AGM developments, it is possible to understand how these models can be evaluated in the context of the AGM theory, and ultimately how they can be adapted for the implementation of BR in intelligent agents. We argue that the theory of belief change for belief bases has now matured to a stage where the next step, implementing BR in real-world agents, can be undertaken. This is due to advances within the research field itself, and also to the increased computational power of small devices over the past decades. With this understanding, we contend that the algorithms for BR proposed by the AI community in the 1970s and 1980s likely contain valuable insights into the implementation of BR mechanisms.

In this article, we analyze how the models proposed in the pre-AGM era can be evaluated in light of the AGM theory. We begin by analyzing pre-AGM BR algorithms, building on the classic article, ‘‘A Selected Descriptor-Indexed Bibliography to the Literature on Belief Revision” (Doyle & London, 1980). Doyle and London’s work provides a detailed overview of early research and pre-AGM approaches, offering a valuable framework for our analysis. We use this bibliography as a foundation for revisiting key contributions and outlining developments in the field of BR. Subsequently, we analyze how these contributions can be assessed in light of the AGM theory and ultimately how they can be adapted when implementing BR mechanisms in intelligent agents.

Rather than a systematic literature review, this article presents a targeted narrative review, grounded in Doyle and London’s work, which serves as a basis for tracing the evolution of BR research from its computational origins through theoretical formalization to contemporary implementations. This targeted narrative review establishes the historical and theoretical foundation for a systematic research program addressing computational BR implementation. By comprehensively analyzing the evolution from pre-AGM computational approaches through AGM theory to contemporary systems, we provide the baseline necessary for systematic implementation analysis and engineering-focused research. Subsequent work will build on this foundation to develop computational blueprints and implementation analysis frameworks that synthesize historical insights with formal guarantees.

1.2. Paper Organization

This article is organized as follows:

Section 2 presents a comprehensive review of related work, positioning our survey approach within the broader landscape of BR surveys and reviews. We compare our methodology and scope with existing literature reviews and identify the unique contributions of our historical-theoretical analysis.

Section 3 establishes the philosophical and theoretical foundations of BR research, tracing its emergence from epistemological inquiries and Newell’s knowledge level framework through the transition from computational practice to a theoretical foundation that sets the stage for our historical analysis.

Section 4 provides essential background on the AGM framework, including its theoretical foundations, postulates, construction methods, and criticisms. This section establishes the theoretical lens through which we analyze pre-AGM computational approaches and post-AGM developments.

Section 5 examines pre-AGM computational approaches to BR, with particular emphasis on systems identified in Doyle and London’s taxonomy. We analyze truth maintenance systems (TMSs), assumption-based truth maintenance systems (ATMSs), probabilistic belief networks, and other foundational computational approaches, documenting their algorithmic innovations and implementation strategies.

Section 6 presents our methodological framework for systematic correspondence analysis between pre-AGM computational approaches and AGM theoretical constructs. We detail our taxonomical mapping strategy, postulate correspondence analysis, and systematic approach to tracing theoretical evolution across Doyle’s categories, providing the analytical foundation for our historical-theoretical integration.

Section 7 provides a comprehensive analysis of how each category in Doyle’s taxonomy evolved in the post-AGM era. For each category, we examine key theoretical developments, identify seminal papers that drove transformation, and analyze how computational insights were formalized into theoretical frameworks.

Section 8 synthesizes our findings, examining the enduring value of Doyle’s classification, the lasting impact of the AGM revolution, and opportunities for integrating pre-AGM and post-AGM approaches. We discuss the contributions of key figures, including Doyle and McCarthy, and analyze patterns of theoretical development across the field.

Section 9 concludes with a summary of the findings, research contributions, and the identification of systematic research directions enabled by our foundational analysis. We establish the theoretical and historical baseline necessary for subsequent computational blueprint development while identifying strategic directions for engineering-focused implementation research.

2. Related Work

The field of BR has been the subject of numerous surveys, reviews, and comparative analyses over the past four decades. These works provide different perspectives on the field’s development, theoretical foundations, and practical applications. This section positions our survey within this broader landscape of literature reviews and identifies how our work extends and complements existing analyses.

2.1. Foundational Surveys and Reviews

In ‘‘A Selected Descriptor-Indexed Bibliography to the Literature on Belief Revision,” which is the earliest comprehensive survey of BR research (Doyle & London, 1980), the authors established the taxonomical framework that forms the foundation of our analysis. This work was primarily descriptive, cataloging existing approaches without systematic theoretical evaluation. In ‘‘Knowledge in Flux,” Gärdenfors (1988) provided the first comprehensive theoretical treatment of BR, focusing on the AGM framework and its philosophical foundations rather than computational implementation.

In ‘‘How to Give It Up,” Makinson (1985) offered an early systematic examination of formal aspects of belief change, providing mathematical foundations that complemented Gärdenfors’ more philosophical approach. This work focused primarily on contraction operations and their formal properties, establishing important theoretical results that informed subsequent AGM development.

The first comprehensive handbook treatments of BR appeared in the mid-1990s, providing systematic coverage that synthesized the first decade of post-AGM research. The handbook chapter by Gärdenfors and Rott (1995) offered the first authoritative survey of AGM theory and its extensions, covering the fundamental postulates, construction methods, and representation theorems while addressing early criticisms and limitations. This work established the canonical presentation of AGM theory that would influence subsequent textbook treatments and became the standard reference for researchers entering the field. A decade later, Peppas (2008) handbook chapter provided updated coverage that reflected the maturation of the field, including comprehensive treatment of iterated revision, belief base approaches, and computational complexity results that had emerged since the mid-1990s. These handbook chapters serve complementary roles to book-length treatments, providing authoritative surveys that capture the field’s consensus understanding at specific historical moments while remaining more accessible than comprehensive monographs.

2.2. Post-AGM Theoretical Surveys

Following the establishment of the AGM framework, several comprehensive surveys examined its extensions and applications. In ‘‘Change, Choice and Inference,” Rott (2001a) provides extensive coverage of connections between BR and non-monotonic reasoning, examining how AGM principles relate to default logic, conditional logic, and other approaches to uncertain reasoning. This work complements our analysis by focusing on theoretical connections rather than historical development.

In ‘‘A Textbook of Belief Dynamics,” Hansson (1999c) offers comprehensive coverage of BR theory with emphasis on formal constructions and their properties. In their more recent work, Fermé and Hansson (2018) provide updated coverage including belief base approaches, kernel methods, and contemporary extensions. These works focus primarily on theoretical development rather than the historical evolution that is central to our analysis. The authors further extend their coverage in a later publication, but focusing only on the AGM development (Fermé et al., 2025).

In his survey of BR implementations, Williams (1998) examined practical aspects of BR systems, focusing on computational approaches and their relationship to theoretical foundations.

2.3. Specialized Domain Surveys

Several surveys have examined BR within specific application domains. A survey of ontology change by Flouris et al. (2008) examines BR principles as applied to ontology evolution and maintenance, providing detailed coverage of description logic extensions and practical implementation strategies. This work demonstrates how AGM principles have been adapted for specific logical frameworks.

In their work on belief merging, Konieczny and Pino Pérez (2002) survey approaches to combining information from multiple sources, extending AGM principles to multi-agent settings.

A complexity survey by Liberatore and Schaerf (1996) provides comprehensive coverage of computational complexity results for BR operations, examining both theoretical bounds and practical approximation strategies. This work complements our analysis by providing detailed technical results.

2.4. Computational and Implementation Surveys

Several works have surveyed computational approaches to BR implementation. In her work on resource-bounded BR, Wassermann (1999) examines how computational limitations affect BR implementation, providing important insights into practical constraints that complement our historical analysis of pre-AGM computational approaches.

In their survey of approximation methods, Schaerf and Cadoli (1995) examine various approaches to approximate BR, including compilation methods, anytime algorithms, and heuristic approaches.

In their work on approximate BR, Chopra et al. (2001) provide a systematic account of approximation as an explicit response to computational constraints in belief change. Rather than treating approximation as an ad hoc compromise, they characterize families of approximation operators and analyze their trade-offs with respect to AGM postulates and rationality criteria. This work remains primarily situated within the AGM framework, and the implementation of the proposed system is marked as future work.

2.5. Philosophical and Cognitive Perspectives

Several surveys have examined BR from philosophical and cognitive perspectives. In his work on BR and reasoning, Harman (1986) examines connections between BR and human reasoning, providing insights into descriptive aspects of belief change that complement AGM’s normative framework.

A survey of defeasible reasoning by Pollock (1987) examines connections between BR and defeasible reasoning, addressing some of the non-monotonic aspects that Doyle’s taxonomy identified as adjacent to BR proper.

These philosophical surveys provide important context for understanding BR as both a computational and cognitive phenomenon.

2.6. Contemporary Multi-Agent and Social Perspectives

Recent surveys have addressed BR in multi-agent and social contexts. In their work on dynamic epistemic logic (DEL), Baltag and Smets (2008) survey formal approaches to knowledge and belief change in multi-agent settings, providing sophisticated logical frameworks that extend beyond the individual focus of classical AGM theory.

Dragoni (1994) examines early approaches to distributed BR with a survey of BR in multi-agent systems, providing important coverage of extensions beyond single-agent settings. This work complements our analysis by addressing multi-agent aspects, but does not provide the systematic historical perspective central to our approach.

2.7. Positioning of Our Work

Our review differs from existing surveys in several important ways:

Historical scope: Unlike surveys that focus primarily on post-AGM theoretical developments (Fermé & Hansson, 2018; Hansson, 1999c; Rott, 2001a), our work systematically examines pre-AGM computational approaches and traces their evolution through the AGM transformation to contemporary implementations.

Taxonomical framework: We use Doyle and London’s original taxonomy as an organizational framework, providing systematic coverage of all major aspects of BR research while maintaining historical continuity.

Theory-practice integration: Our analysis explicitly examines the relationship between theoretical development and computational implementation, identifying how practical concerns have influenced theoretical development and how theoretical insights have informed practical approaches. This distinguishes our work from purely theoretical surveys (Gärdenfors, 1988; Makinson, 1985) and purely computational surveys (Williams, 1998).

Methodological approach: We develop a correspondence analysis that maps pre-AGM computational techniques to AGM theoretical constructs, providing a methodological framework that could be applied to other areas of AI research.

While our work builds upon and complements existing surveys, it provides a unique perspective that combines historical analysis, theoretical evaluation, and practical implementation insights within a unified framework. This approach fills an important gap in the literature by analyzing how the field has evolved from its computational origins to its current theoretical sophistication.

3. Background and Foundations

The philosophical roots of BR theory stem from epistemological inquiries into knowledge acquisition and belief change. The formal study of BR emerged from the intersection of AI, philosophy of science, and cognitive psychology in the 1960s and 1970s. In his influential concept of the knowledge level, Newell (1982) provided a crucial theoretical foundation by distinguishing among different levels of analysis in cognitive systems: the biological level, the symbol level, and the knowledge level.

At the knowledge level, Newell argued, intelligent behavior can be understood in terms of the knowledge an agent possesses and the goals it pursues, independent of the specific symbolic representations or computational mechanisms used to implement that knowledge. This perspective was revolutionary because it suggested that BR could be studied as a rational process governed by the principles of coherence, consistency, and goal-directed behavior, rather than merely as a collection of ad hoc computational procedures.

Newell’s framework influenced early AI researchers to develop principled approaches to knowledge representation and reasoning that could support rational BR. This led to the development of truth maintenance systems (Doyle, 1979), assumption-based reasoning frameworks (De Kleer, 1986), and other computational architectures designed to track the justifications for beliefs and manage belief dependencies systematically (Doyle, 1979).

The knowledge level perspective also highlighted the importance of distinguishing between the competence level (what an ideal rational agent should do) and the performance level (what computationally bounded agents actually do). This distinction became central to BR research, leading to both normative theories that specify ideal BR behavior and computational theories that address the practical constraints of implementing BR in real systems (Newell, 1982).

Early contributions from philosophers such as James (1896) and Peirce (1877) emphasized the dynamic character of belief systems and the necessity of rational methods for updating them. These philosophical investigations established several key principles:

Minimal change principle: When incorporating new information, one should preserve as much of the existing belief system as possible while ensuring consistency.

Coherence: The resulting belief system should preserve internal consistency and logical soundness.

Epistemic entrenchment: Some beliefs are more fundamental or important than others, influencing which beliefs should be retained during revision.

Peirce and James are central to pragmatist ideas about belief and coherence, but the formal, systematic foundations of minimal change and entrenchment in BR were developed later by decision-theoretic and AGM-style authors (Levi; Alchourrón, Gärdenfors, Makinson) and by AI/logic researchers. Historical precursors such as Zimmerman (2022) and Hollingsworth (2022) also shaped the pragmatists’ views.

From the computational perspective, BR explores how intelligent systems (or agents) can update their beliefs in response to new information. This process is essential because, in real-world contexts, AI systems often need to handle dynamic, incomplete, or contradictory information. With a BR process in place, intelligent systems can maintain a consistent information base in the presence of new input, thereby supporting more accurate decision-making (Nebel, 1998; Wassermann, 1999).

The formal study of BR can be traced to early work in AI and philosophical logic during the 1960s and 1970s. However, the field was revolutionized by the seminal work of Alchourrón et al. (1985), which provided the first comprehensive formal framework for belief change operations.

Before the AGM framework, researchers developed various algorithmic approaches to BR, often developed for specific applications. In particular, the problem of how to revise a database or knowledge base appeared in the AI community during the 1970s. The survey article by Doyle and London (1980) provided a selected bibliography of about 250 papers related to this area. In its introduction, it states that “Belief Revision concentrates on the issue of revising systems of beliefs to reflect perceived changes in the environment or acquisition of new information.”

During the 1980s, several authors (Borgida, 1985; Dalal, 1988; Fagin et al., 1983; Katsuno & Mendelzon, 1991a, 1991b; Martins & Shapiro, 1988; Satoh, 1988; Winslett, 1988) proposed different models for performing belief change. However, these models were developed at the syntactic level, that is, with a commitment to the representation language. Therefore, as Nebel (1989) pointed out, ‘‘the question remains how belief revision can be described on an abstract level independent of how beliefs are represented and manipulated inside a machine.”

It remains unclear how to describe BR at the knowledge level, as Newell (1982) introduced in his seminal article ‘‘The knowledge level. In that work, he argued that ‘ $\cdots$ there exists a distinct computer system level, lying immediately above the symbol level, which is characterized by knowledge as the medium and the principle of rationality as the law of behavior’.” Newell further suggested that intelligent behavior could be understood in terms of an agent’s beliefs, goals, and rational action selection, abstracting away from implementation details.

These ideas later inspired the formal development of the belief–desire–intention (BDI) paradigm, in which agent behavior is explicitly modeled in terms of beliefs, desires, and intentions (Cohen & Levesque, 1990; Rao & Georgeff, 1995). While Newell did not propose a BDI architecture himself, his knowledge-level analysis provided a conceptual foundation that strongly influenced subsequent BDI models and agent-oriented reasoning frameworks. That paper exerted an enormous influence on the AI community, particularly on researchers in Knowledge Representation and Reasoning, including Brachman, Levesque, Moore, Halpern, Moses, Vardi, Fagin, Ullman, Shapiro, Borgida, and others.

3.1. The AGM Revolution

The AGM framework, developed by Alchourrón et al. (1985), Gärdenfors (1988), and Makinson (1985), represents the most influential normative theory of BR. Named after its creators’ initials, the AGM framework provides a set of postulates that specify how rational agents should revise their beliefs when confronted with new information. This work fundamentally transformed the field by:

Providing a unified theoretical framework for three types of belief change: expansion, contraction, and revision.

Establishing rationality postulates that any reasonable belief change operation should satisfy.

Introducing representation theorems that connected abstract postulates with concrete construction methods.

Creating formal relationships between different types of belief change operations.

In the AGM literature, representation theorems provide equivalent characterizations of the abstract postulates in terms of concrete constructions. For example, contraction operators satisfying the AGM postulates can be represented as partial meet contractions, obtained by selecting preferred remainder sets via a selection function (Alchourrón et al., 1985; Alchourrón & Makinson, 1982). Other representation theorems give equivalent formulations in terms of epistemic entrenchment orderings (Gärdenfors & Makinson, 1988), kernel contraction (Alchourrón & Makinson, 1986; Hansson, 1994a), and Grove’s system of spheres for revision (Grove, 1988).

The AGM model characterizes specific change operations that represent the modifications an agent can perform on its knowledge. Each of these operations is defined by a set of rationality postulates that determine its behavior independently of implementation details. These postulates allow us to conceive of the change operations as “black boxes,” that is, mechanisms whose behavior is specified separately from how they are implemented (Alchourrón & Makinson, 1985).

Additionally, by the end of the 1980s, four equivalent methods for constructing AGM functions were introduced, along with semantics for such operations: partial meet functions (Alchourrón et al., 1985; Alchourrón & Makinson, 1982), epistemic entrenchment (Gärdenfors & Makinson, 1988), safe/kernel contraction (Alchourrón & Makinson, 1986; Hansson, 1994a), and sphere-systems semantics (Grove, 1988). Together, these developments elevated the AGM to the status of a standard model. The influence of Newell’s paper and the AGM model led to the abandonment of syntactic approaches.

However, the AGM framework is defined for belief sets, that is, sets of sentences closed under logical consequence (usually infinite sets). Hence, resource-bounded agents cannot employ the AGM model without modifications (Wassermann, 1999).

During the 1990s and 2000s, the AGM model was extended to belief bases, that is, sets of sentences not closed under logical consequence (Falappa et al., 2006; Fermé et al., 2008; Hansson, 1991b, 1994a). Several works advocate the use of belief bases instead of belief sets to represent states of knowledge (Fermé, 1992; Fuhrmann, 1991a; Hansson, 1991a, 1992a, 1994b; Nebel, 1989; Rott, 1998; Wassermann, 1999).

While the AGM model played a pivotal role in formalizing BR, its practical application in real-world systems has faced challenges, primarily due to computational complexity and resource limitations. Despite these obstacles, AGM-based concepts have been adapted and extended to address the requirements of dynamic decision-making systems (Nebel, 1998; Wassermann, 1999).

3.2. Transition From Practice to Theory

Our survey serves as a bridge between the practice-oriented pre-AGM era documented in Section 5 and the theory-oriented AGM framework that we examine in the subsequent Section 4. Doyle’s taxonomy provides the organizational structure for understanding how diverse computational approaches to BR were unified under the AGM theoretical umbrella, while our correspondence analysis reveals both the continuities and innovations that characterize this theoretical transformation.

The pre-AGM period was rich in concrete computational mechanisms that addressed specific implementation challenges. Consider three exemplary cases that illustrate our methodological approach:

Operator descriptions in planning systems like STRIPS (Fikes & Nilsson, 1971) fall under Doyle’s Representations category and pair naturally with the operator application Procedures to implement model change. These systems directly addressed the frame problem by making explicit what changes and, implicitly, what remains constant during action execution. From an AGM perspective, these mechanisms anticipate the success and inclusion postulates, though they lack the systematic theoretical foundation that AGM provides.

Context layers and change-triggered procedures, including pattern-directed invocation mechanisms, capture consequential effects and localize revisions, key innovations under Doyle’s Representations category. These approaches operationalize a weak notion of causality through precondition/effect relationships and support sophisticated backtracking strategies under the Procedures category. AGM theory abstracts away from these implementation details, while preserving their essential insights about minimal change and preference-guided revision through selection functions and epistemic entrenchment orderings (Gärdenfors, 1988).

Logical data dependencies and TMSs explicitly record support relationships between beliefs and compute revised belief status through dependency-directed algorithms, representing perhaps the most direct pre-AGM bridge between computational practice and later AGM theory (Doyle, 1979). These systems map to dependency structures under Representations and dependency-based revision under Procedures, anticipating AGM’s kernel contraction methods (Hansson, 1994a) and belief base approaches that would emerge in the 1990s.

Non-monotonic techniques, including defaults, circumscription, and default logic, inhabit a separate taxonomical family precisely because they solve a different problem than AGM revision: how to license tentative commitments in the absence of complete proof, rather than how to minimally revise a belief corpus when definitive information arrives (McCarthy, 1980; Reiter, 1980). Doyle’s taxonomical segmentation acknowledges the frequent co-occurrence of these techniques in implemented systems without conflating their distinct purposes, a distinction that AGM theory would later formalize through its focus on categorical belief change rather than uncertain inference.

4. The AGM Model

The AGM framework emerged in the mid-1980s as a response to the need for principled normative foundations for BR (Alchourrón et al., 1985). Although pre-AGM approaches had developed sophisticated computational methods, they lacked systematic theoretical foundations that could guide the development of rational BR systems and provide criteria for evaluating different approaches.

The framework was developed through a series of influential papers by Carlos Alchourrón, Peter Gärdenfors, and David Makinson, culminating in the comprehensive treatment in ‘‘Knowledge in Flux” by Gärdenfors (1988). The AGM approach was revolutionary in applying rigorous logical and set-theoretic methods to BR, establishing it as a legitimate area of formal investigation.

The underlying formal logical framework used in the AGM approach has the following characteristics:

A propositional language $\mathcal{L}$ , closed under the standard logical connectives.

A consequence operator $Cn$ that is:

–

Monotonic: If $A\subseteq B$ then $Cn(A)\subseteq Cn(B)$ .

–

Idempotent: $Cn(Cn(A))=Cn(A)$ .

–

Compact: If $\alpha \in Cn(A)$ , then $\alpha \in Cn(A^{\prime })$ for some finite $A^{\prime }\subseteq A$ .

A set of formulas $K$ representing the belief set, where $K=Cn(K)$ .

The framework provides a systematic approach to belief change based on three fundamental operations:

Expansion: This operation involves adding a new belief to the belief set without concern for consistency. It simply incorporates the new information, regardless of potential contradictions, and may therefore result in inconsistent belief sets. This operation, denoted as $K+\alpha$ , represents the addition of a new belief $\alpha$ to the belief set $K$ , along with all the logical consequences. Formally:

$$\begin{array}{r}K+\alpha =Cn(K\cup \{\alpha \}).\end{array}$$

Contraction: This operation removes a belief from the belief set while maintaining logical consistency. It is used when the agent needs to ‘‘unlearn” certain beliefs, often to make room for future updates. Formally, it is denoted as $K-\alpha$ and entails removing a belief $\alpha$ such that it is no longer a logical consequence of the remaining beliefs. This may imply removing other beliefs from the belief set. The operation must satisfy the principle of minimal change while maintaining logical closure.

Revision: The most critical operation in the AGM model, revision consists of adding a new belief while preserving the consistency of the belief set. If the new belief contradicts existing beliefs, the model prescribes ways to modify the current belief set to accommodate the new information while preventing inconsistency. This operation, denoted as $K*\alpha$ , involves incorporating a new belief $\alpha$ while maintaining consistency. The Levi Identity, proposed by Levi (1978), provides a fundamental relationship between revision and contraction operations, describing revision as a two-step process: first, contract the belief set to remove any sentences that would conflict with the new belief; then expand the contracted set to include the new belief. This two-step approach ensures that the belief set remains consistent after revision, aligning with the AGM postulates. The relationship between revision and contraction is formalized as follows:

$$\begin{array}{r}K*\alpha =(K-\mathrm{\neg }\alpha )+\alpha .\end{array}$$

It assumes that beliefs are represented as logically closed sets (belief sets) and that the underlying logic satisfies standard properties, including supraclassical monotonicity (Strasser & Antonelli, 2024), deduction, and compactness.

A belief set $K$ is a set of sentences in the language $\mathcal{L}$ that is closed under logical consequence:

$$\begin{array}{r}K=Cn(K)=\{\alpha \in \mathcal{L}:K⊢\alpha \}.\end{array}$$

This closure property embodies the idea of logical omniscience: agents are assumed to be aware of all logical consequences of their beliefs (Gärdenfors, 1988).

4.1. Postulates of the AGM Model

The AGM model is based on a set of rationality postulates that govern how belief sets behave when revised or contracted. These postulates ensure that BR is carried out logically and coherently. The basic AGM postulates for revision (K*1–K*6) are as follows:

Closure: The revised belief set must be closed under logical consequence: if the revised set of beliefs logically implies a proposition, this proposition must also be included in the set.

$$\begin{array}{r}K*\alpha =Cn(K*\alpha ).\end{array}$$

Success: The new belief must be included in the BR set unless it leads to a contradiction.

$$\begin{array}{r}\alpha \in K*\alpha .\end{array}$$

Inclusion: The revised belief set should preserve as much of the original belief set as possible, with changes kept minimal and occurring only when necessary to preserve consistency.

$$\begin{array}{r}K*\alpha \subseteq K+\alpha .\end{array}$$

Consistency: The revised belief set must not contain contradictions.

$$\begin{array}{r}K*\alpha \text{is consistent if}\alpha \text{is consistent}.\end{array}$$

Vacuity: If the new belief is already part of the belief set, the revision must leave the set unchanged.

$$\begin{array}{r}\mathrm{\neg }\alpha \notin K\Rightarrow K+\alpha \subseteq K*\alpha .\end{array}$$

Extensionality: If two pieces of information are logically equivalent, revising the belief set with either must result in the same outcome.

$$\begin{array}{r}\alpha \equiv \beta \Rightarrow K*\alpha =K*\beta .\end{array}$$

The supplementary postulates (K*7–K*8) address composite revisions:

7.

Superexpansion: Revision by conjunction is a subset of revision followed by expansion:

$$\begin{array}{r}K*(\alpha \wedge \beta )\subseteq (K*\alpha )+\beta .\end{array}$$

8.

Subexpansion: If a conjunction is consistent with beliefs, revision followed by expansion is equivalent to revision by conjunction.

$$\begin{array}{r}\mathrm{\neg }\beta \notin K*\alpha \Rightarrow (K*\alpha )+\beta \subseteq K*(\alpha \wedge \beta ).\end{array}$$

For contraction, the model has its own set of postulates, designed to ensure that beliefs are removed logically while minimizing information loss. The AGM postulates for contraction (K-1–K-8) are as follows:

Closure: The contracted belief set must remain closed under logical consequence.

$$\begin{array}{r}K-\alpha =Cn(K-\alpha ).\end{array}$$

Inclusion: The contracted belief set must not contain any new beliefs; it must be a subset of the original set.

$$\begin{array}{r}K-\alpha \subseteq K.\end{array}$$

Vacuity: If the belief to be removed is not currently part of the belief set, the contraction leaves the set unchanged.

$$\begin{array}{r}\text{If }\alpha \notin K,\text{ then }K-\alpha =K.\end{array}$$

Success: If the belief is not a logical truth (tautology), it must be successfully removed from the belief set.

$$\begin{array}{r}\text{If }⊬\alpha ,\text{ then }\alpha \notin Cn(K-\alpha ).\end{array}$$

Recovery: The original belief set must be recoverable by expanding the contracted set with the removed belief (ensuring minimal information loss).

$$\begin{array}{r}K\subseteq (K-\alpha )+\alpha .\end{array}$$

Extensionality: If two pieces of information are logically equivalent, contracting the belief set by either must result in the same outcome.

$$\begin{array}{r}\alpha \equiv \beta \Rightarrow K-\alpha =K-\beta .\end{array}$$

Conjunctive overlap: Beliefs that remain after contracting by $\alpha$ and after contracting by $\beta$ individually must also remain when contracting by their conjunction.

$$\begin{array}{r}K-\alpha \cap K-\beta \subseteq K-(\alpha \wedge \beta ).\end{array}$$

Conjunctive inclusion: If contracting by a conjunction succeeds in removing a specific conjunct, the result should not retain more beliefs than contracting by that conjunct alone.

$$\begin{array}{r}\alpha \notin K-(\alpha \wedge \beta )\Rightarrow K-(\alpha \wedge \beta )\subseteq K-\alpha .\end{array}$$

The AGM framework operates with two distinct but related concepts for representing beliefs: belief sets and belief bases. These representational choices have deep implications for both the theoretical development and practical implementation of BR systems.

Knowledge sets (or belief sets) in the AGM context represent idealized and logically closed sets of beliefs that embody the theoretical foundations of rational BR (Alchourrón et al., 1985; Gärdenfors, 1988). These structures are characterized by deductive closure ( $Cn$ ), meaning that if a knowledge base contains certain beliefs, it must also contain all logical consequences of those beliefs. This property ensures theoretical completeness and provides strong guarantees about consistency when revision operators follow the AGM postulates. However, the requirement for logical closure implies that knowledge sets are infinite in size for any non-trivial set of initial beliefs, as they must contain all possible logical derivations.

The practical limitations of logically closed knowledge sets led to the development of knowledge bases (or belief bases) as a more computationally tractable alternative (Hansson, 1999c; Nebel, 1998). Belief bases are finite, non-closed sets of beliefs that provide explicit representation of only the basic or fundamental beliefs held by an agent. This approach offers several advantages for practical implementation: finite size enables computational tractability, the distinction between explicit and derived beliefs allows for more efficient reasoning procedures, and the overall structure provides more realistic modeling of how actual belief systems operate in resource-bounded agents (Dalal, 1988; Fermé, 1992; Fuhrmann, 1988, 1991b; Hansson, 1989, 1991b, 1992a, 1994b; Nebel, 1989; Rott, 1998; Wassermann, 1999).

The choice between knowledge sets and knowledge bases reflects a fundamental tension in BR research between theoretical elegance and computational feasibility. While knowledge sets provide the mathematical precision necessary for formal analysis and the development of rationality postulates, belief bases offer the practical advantages required for real-world implementation. Later approaches often attempt to bridge this gap by developing algorithms that operate on belief bases while approximating the rational behavior specified by AGM theory for knowledge sets (Liberatore & Schaerf, 1996; Wassermann, 1999).

4.2. Constructive Models

Constructive models in AGM theory serve as concrete mechanisms to implement belief change operations consistent with AGM postulates (Alchourrón et al., 1985). While the AGM postulates provide normative constraints on BR, they do not specify how belief changes are to be performed. Constructive models bridge this gap by offering explicit procedures for belief change operations (Gärdenfors, 1988).

The significance of constructive models can be highlighted in several respects:

They provide explicit procedures for implementing belief change operations (Gärdenfors, 1988).

They demonstrate that the AGM postulates are consistently satisfiable (Alchourrón et al., 1985).

They offer insights into the relationship between different types of belief change (Levi, 1991).

They serve as blueprints for practical implementations (Nebel, 1998).

The development of constructive models begins with the concept of remainder sets (Alchourrón & Makinson, 1981, 1982). For a belief set $K$ and a sentence $\alpha$ , the remainder set $K\mathrm{\perp }\alpha$ is defined as the collection of maximal subsets of $K$ that do not imply $\alpha$ . Formally:

$$\begin{array}{r}{K}^{\prime }\in K\mathrm{\perp }\alpha \text{iff:}\end{array}$$

• $K^{\prime }\subseteq K$ .

• $\alpha \notin Cn(K^{\prime })$ .

• For any $K^{″}$ such that $K^{\prime }\subset K^{″}\subseteq K$ , $\alpha \in Cn(K^{″})$ .

4.2.1. Maxichoice Contraction

The maximachoice contraction selects exactly one maximal subset of $K$ that does not imply  $\varphi$ :

$$\begin{array}{r}K{-}_{\text{max}}\varphi =\gamma (K\perp \varphi ),\end{array}$$

where $K\perp \varphi$ is the set of all maximal subsets of $K$ that do not imply $\varphi$ , and $\gamma$ is a selection function that chooses an element from this set.

4.2.2. Partial Meet Contraction

Partial meet contraction takes the intersection of some maximal subsets:

$$\begin{array}{r}K{-}_{\text{pm}}\varphi =\bigcap \gamma (K\perp \varphi ),\end{array}$$

where $\gamma$ selects a non-empty subset of $K\perp \varphi$ .

4.2.3. Full Meet Contraction

Full meet contraction takes the intersection of all maximal subsets:

$$\begin{array}{r}K{-}_{\text{fm}}\varphi =\bigcap (K\perp \varphi ).\end{array}$$

4.2.4. Selection Functions and Preferences

The choice of the selection function $\gamma$ encodes preferences for different ways of contracting the belief set. These preferences can be represented using various structures:

Epistemic entrenchment: A pre-order on sentences representing their relative importance or reliability (Gärdenfors, 1988).

Grove systems: Collections of propositions ordered by plausibility (Grove, 1988).

Ordinal conditional functions: Numerical measures of disbelief that can guide BR (Spohn, 1988).

4.3. Revision

The core of the AGM model lies in the way the revision function is constructed. Revision in AGM theory addresses the fundamental problem of incorporating new information into a belief set while preserving consistency (Gärdenfors, 1988). Unlike expansion, which might lead to inconsistencies, revision ensures that the resulting belief set remains consistent whenever possible. The operation must balance two competing principles:

Minimal change: Preserve as much of the original belief set as possible.

Consistency maintenance: Ensure that the resulting belief set is consistent if the epistemic input is consistent.

As introduced before, the Levi identity formalizes revision as a two-step process in the context of revision operations. This identity demonstrates that revision can be reduced to a sequence of:

contracting by the negation of the new belief; and

expanding with the new belief.

The Harper identity provides the converse relationship (Harper, 1976):

$$\begin{array}{r}K-\alpha =K\cap (K*\mathrm{\neg }\alpha ).\end{array}$$

This identity shows that contraction can be defined in terms of revision, establishing a deep connection between these operations.

Partial meet revision extends the partial meet contraction framework to revision operations (Alchourrón et al., 1985). The process involves:

Computing $K\mathrm{\perp }\mathrm{\neg }\alpha$ (the remainder set for $\mathrm{\neg }\alpha$ ).

Applying a selection function $\gamma$ .

Taking the intersection of selected remainders.

Adding $\alpha$ and its logical consequences.

Formally:

$$\begin{array}{r}K*\alpha =(\bigcap \gamma (K\mathrm{\perp }\mathrm{\neg }\alpha ))+\alpha .\end{array}$$

With his system of spheres, (Grove, 1988) provides an alternative semantic model for revision based on possible worlds. The framework consists of:

A set of possible worlds.

A system of nested spheres centered on $[K]$ (the worlds where $K$ is true).

A mechanism for selecting the closest $\alpha$ -worlds.

The revision operation selects the most plausible worlds where the new belief holds:

$$\begin{array}{r}[K*\alpha ]=\underset{⪯}{min}([\alpha ]).\end{array}$$

There are also specific types of revision that can be used with the AGM model. Selective revision (Fermé & Hansson, 1999) allows partial acceptance of new information:

Transformation: New information undergoes a transformation before incorporation.

Screening: Only certain aspects of new information are accepted.

Modification: New information is modified during the revision process.

Multiple revision (Zhang & Foo, 2001) handles the simultaneous incorporation of multiple pieces of information:

Package revision: Simultaneous revision with multiple beliefs.

Iterative revision: Sequential application of revision operations.

Prioritized revision: Revision with ordered sets of beliefs.

The classical AGM framework assumes that new information always takes priority over existing beliefs, as embodied in the Success postulate, which requires that newly received information must be incorporated into the revised belief set. However, this assumption has been challenged by developments in non-prioritized revision, which recognizes that not all new information deserves equal treatment or automatic acceptance (Hansson, 1997a).

Non-prioritized revision fundamentally challenges the Success postulate by introducing a more nuanced approach to information integration. Rather than mandating that new information must always be incorporated, this framework allows partial acceptance or complete rejection of new information based on its evaluated credibility and reliability. The system may determine that existing beliefs, particularly those with strong evidential support or high confidence levels, should be preferred over incoming information that appears dubious or contradicts well-established knowledge. This approach reflects a more realistic model of how rational agents actually process information in uncertain environments where the quality and trustworthiness of sources can vary significantly.

Parallel to these developments in information prioritization, researchers have also focused on adapting BR to work directly with belief bases rather than the idealized belief sets of classical AGM theory (Nebel, 1998). This shift involves fundamental changes in the way revision operations are conceptualized and implemented. When working with finite, non-closed sets of beliefs, revision procedures must explicitly distinguish between beliefs that are explicitly represented in the base and those that are merely derivable through logical inference. This distinction becomes crucial because different minimal change criteria may apply to explicit versus derived beliefs, leading to revision outcomes that can differ significantly from those predicted by classical AGM theory.

The combination of non-prioritized revision with belief bases approaches represents a significant evolution in BR theory, moving toward more realistic and implementable frameworks. These developments acknowledge the practical constraints faced by real agents: limited computational resources that make belief set closure infeasible, varying information quality that makes blanket acceptance policies inappropriate, and the need for revision procedures that can operate efficiently on finite representations while still maintaining principled approaches to belief change (Liberatore & Schaerf, 1996; Wassermann, 1999).

4.4. Importance and Criticisms

The AGM model was the first widely accepted formalization of how rational BR should be handled. It provided a clear, logical framework that could be applied in multiple domains, including AI, philosophy, and logic (Alchourrón et al., 1985).

One of the central ideas of the AGM model is the principle of minimal change. When revising beliefs, an agent should alter as little as possible to accommodate new information. This principle is crucial for maintaining the coherence of the agent’s beliefs over time and for preventing unnecessary disruptions in reasoning (Gärdenfors, 1988).

The AGM model applies to numerous fields within AI, such as knowledge representation, non-monotonic reasoning, ontologies, databases, and multi-agent systems. It is particularly useful for dynamic systems that must constantly update their knowledge as they interact with their environment (Allen, 1983).

By providing a set of logical postulates, the AGM model ensures that BR is rational and consistent, making it a critical tool for enabling AI systems to reason effectively in the face of new or conflicting information (Alchourrón et al., 1985).

The AGM model has inspired numerous extensions and refinements over the years, addressing limitations such as resource constraints in real-time systems or the need for more flexible revision methods. These works have further cemented their role in the ongoing development of BR theory (Hansson, 1999b).

It has also had an impact on practical implementations, such as:

Systematic evaluation: Providing the ability to formally assess BR systems (Hansson, 1996c).

Design guidance: Offering clear criteria for developing new algorithms (Gärdenfors, 1988).

Unified framework: Providing a common language for discussing and comparing different approaches (Makinson, 2002).

Despite its widespread acceptance as the predominant framework for belief change, the AGM framework has been subject to considerable critique. This section offers an overview of such critiques, which can be viewed as limitations of the model.

Theoretically, logical omniscience and deductive closure create a mismatch with bounded agents. AGM treats derived and non-derived beliefs as indistinguishable once in the belief set, offering no internal mechanism to mark provenance or status (Levi, 1978, 1991; Rott, 1998). Deductive closure renders belief sets infinite for any nontrivial base; representing or computing with such sets is infeasible for real agents. Hansson (1993) and Hansson (2013) argues for finiteness of bases and outcomes, but standard AGM operations on finite inputs still yield infinite closures (Hansson, 1997a), forcing approximations that weaken guarantees (Chopra et al., 2001). Maintaining consistency while maximizing information retention is also computationally demanding in general.

The Recovery postulate claims that contracting by $\phi$ and then re-adding $\phi$ restores the original belief set (Gärdenfors, 1982). Numerous counterexamples undermine this principle (Hansson, 1991b, 1996a, 1996b, 1999a; Niederée, 1991). Consequently, contraction schemes without Recovery, called withdrawals, were proposed (Fermé, 1998; Fermé & Rodríguez, 1998; Levi, 1997, 2004; Makinson, 1997; Meyer et al., 2002; Nebel, 1998; Rott & Pagnucco, 1999). No widely accepted weaker replacement for Recovery has yet emerged (Fermé & Hansson, 2018).

AGM revision and contraction assume full epistemic deference to new inputs (Cross & Thomason, 1992). Even in preference-ordered settings such as Katsuno and Mendelzon (1991b), fresh information overrides entrenched beliefs, but immediately loses any privileged status once incorporated. This rigidity motivated operators that relax or violate Success, grouped as non-prioritized revision (Booth et al., 2012; Fermé & Hansson, 1999; Fermé et al., 2003; Fuhrmann, 1996; Hansson, 1991b, 1992b, 1997a, 1997a, 1997b; Hansson et al., 2001; Hansson & Wassermann, 2002; Konieczny & Pino Pérez, 2008; Makinson, 1997; Olsson, 1997) and non-prioritized contraction (Fermé & Hansson, 2001; Fermé et al., 2003). Remainder sets likewise treat all survivors as epistemically equivalent to the agent’s aims; (Levi, 1991, 1997) argues instead for preserving beliefs with the highest instrumental or epistemic value relative to goals.

Iterated change, that is, consecutive revisions or contractions, is underspecified in the AGM model: the original postulates give no constraints on how revision or contraction should depend on history (memory), enabling pathological sequences and instability (Boutilier, 1996). Fermé and Hansson proposed an organization of iterated review according to their memory:

Without memory: In this scenario, each belief set undergoes revision according to a predefined method that remains uninfluenced by the manner in which the belief set was initially acquired. Full meet revision is a classic example of this category. An analysis of these operators was conducted by Areces and Becher (2001).

Full memory: opposed to the previous case, a full history of changes is maintained. Some operators of this class are (Brewka, 1991; Falappa et al., 2013; Konieczny & Pino Pérez, 2000; Lehmann, 1995).

Partial memory: These operators store information on how it arrived at the belief set, which is used for future operations, but the stored information is not enough to do a rollback. Most of the proposed operators are of this category. According to Rott (2009), it is possible to further organize this category:

Conservative revision: This operation conservatively minimizes changes to the pre-order to accept the input. When revising by $p$ , the maximal $p$ -worlds are repositioned to the bottom, leaving the rest of the pre-order unchanged. (Boutilier, 1993, 1996; Rott, 2003).

Moderate revision: Revising by p rearranges the pre-order by placing $p$ -worlds at the bottom and $\mathrm{\neg }p$ -worlds at the top, maintaining their relative orders (Makinson, 2009, 2011).

Radical revision: Similar to moderate revision, but it makes the new belief permanent. In radical revision, based on a pre-order, the $p$ -worlds maintain their order while the $\mathrm{\neg }p$ -worlds are excluded, becoming inaccessible (Fermé, 2000; Segerberg, 1998).

Epistemic entrenchment orderings face modeling issues: transitivity and totality can misrepresent context-dependent importance and may fail to capture realistic, non-linear hierarchies (Rott, 1992).

AGM is single-agent by design. Multi-agent settings require aggregation, conflict resolution, and source-sensitive trust handling that exceed the original scope (Dragoni, 1994). Some studies in this area include the work by Konieczny and Pino Pérez (2002, 2011) on merging, Castelfranchi (1997), Falappa et al. (2002, 2009), Paglieri (2006), Paglieri and Castelfranchi (2004, 2006), and Toulmin (2003), on argumentation, and Arló-Costa and Bicchieri (2007), Booth and Meyer (2006), Booth et al. (2010), and Zhang (2010) on game theory.

The binary acceptance stance is also too coarse for many applications; probabilistic beliefs, partial acceptance, and dynamic uncertainty demand graded representations and updates (Jeffrey, 1983; Spohn, 1988; Wassermann, 1999).

In knowledge-base maintenance, AGM-style global consistency checks are costly (Eiter & Gottlob, 1992). Local updates can produce hidden global conflicts, and preserving semantic dependencies during change is non-trivial (Hansson & Wassermann, 2002). Real-time systems add further constraints: strict latency bounds, resource limits, and continuous, possibly conflicting streams strain classical operators (Alechina et al., 2006; Wassermann, 1999).

With the AGM theoretical framework established, we can now examine the computational approaches that preceded and informed its development. These pre-AGM systems, while lacking systematic theoretical foundations, embodied algorithmic insights and implementation strategies that would later find formal expression in AGM theory and continue to influence contemporary BR implementations.

5. Pre-AGM BR

Before the AGM model, particularly in the late 1970s and early 1980s, ¹ several computational approaches to BR emerged from artificial intelligence research, especially in the context of reasoning systems and knowledge representation. These algorithms were developed as part of efforts to create automated reasoning systems capable of handling uncertain and dynamic information. As a result, they focused primarily on practical implementation rather than theoretical foundations (De Kleer, 1986; Doyle, 1979; McCarthy, 1980).

Central to understanding this pre-AGM landscape is the bibliography by Doyle and London (1980), which provided the first systematic organization of the emerging field. The authors’ survey took on a task that, at the time, had not yet been formalized by a consensus logic of belief change: to make sense of a rapidly growing practice of belief maintenance and model update across AI subfields by carving the space into an interpretable taxonomy (Doyle, 1980). Their method was deliberately empirical and cross-disciplinary. Rather than propose a monolithic theory, they curated an indexed bibliography and attached to each item a bundle of descriptors that reflected what the artifact does (e.g., maintains dependencies), how it is represented (e.g., operator schemas; context layers), what kind of inference it licenses (e.g., default rules), and where it is used (e.g., planning and explanation). The result is a pragmatic and multi-axis classification: eight top-level families with fine-grained subcategories that span implementation and theory.

Doyle and London’s indexing process proceeds in three steps:

Identify recurring tasks and pressures that force belief change (e.g., model update after action; reconciling conflicting hypotheses; and absorbing new evidence).

Identify representational devices that systems rely on to make updates feasible (e.g., operator add/delete lists, context layers, and dependency graphs).

Identify inference regimes and meta-theoretical commitments involved (e.g., default/non-monotonic rules vs. purely monotonic reasoning; probabilistic/fuzzy calculi; modal, temporal, and situation logics).

Then each bibliographic entry is multi-labeled along these axes. Crucially, the categories are not mutually exclusive: a single system might introduce a novel representation (context layers), rely on a specific procedure (dependency-directed backtracking) and presuppose an inference style (defaults), while being deployed in a particular application (explanation).

At the top level, the taxonomy comprises:

Global issues: The frame problem, choosing between competing BRs, change of belief or mind, and revising beliefs for new information.

Representations for revising beliefs: Manual updates, operator descriptions, context-layered databases, change-triggered procedures, logical data-dependencies, causal dependencies, and dependency-like representations.

Procedures for revising beliefs: Chronological and non-chronological backtracking, operator application, and dependency-based revision.

Non-monotonic inference techniques: Default reasoning, non-monotonic justifications, negation in databases, minimal model circumscription, and partial matching.

Inexact inferential techniques: Probabilistic inference, decision theory, conclusion theory, multi-valued logics, and fuzzy logics.

Theoretical issues: Logics of rational belief, temporal logics, situational calculus, evolution theory, proof theory, non-monotonic logics, meta theory, theory of incomplete databases, modal logics, and reasoning about uncertainty.

Applications: Explanation, modeling and execution, replanning from failures, transfer of expertise, learning, debugging computer programs, evolutionary computer systems, causal and perturbation analysis, and control of reasoning.

Related issues: Human belief and memory, epistemology, inductive reference, hypothetical reasoning and counterfactual conditionals, and scientific theory change.

The prehistory of BR, before an agreed-upon logic of change, already identifies core tasks: (i) update world models after actions (the frame problem); (ii) reconcile inconsistent hypotheses; and (iii) absorb new information with minimal disruption. Doyle’s categories exactly mirror these pressures. For example, “Global Issues” enumerates the update/choice/assimilation triad; “Representations” and “Procedures” identify the data structures and algorithms that made these tasks tractable at scale. In other words, the taxonomy is a codification of engineering practice that responds to the motivational cases introduced historically. This classification system not only captured the state of the field circa 1980 but also provided a framework that would prove durable across subsequent decades of research.

To understand the relative emphasis and development within each category of Doyle and London’s taxonomy, we conducted a quantitative analysis of the literature distribution across the eight classification areas. This analysis reveals not only which research directions received the most attention during the pre-AGM period but also provides insight into the computational priorities and theoretical interests that shaped early BR research. The distribution patterns illuminate the field’s evolution from predominantly procedural and representational concerns toward the more theoretical foundations that would eventually culminate in the AGM framework. Tables 1 to 8 present the numerical breakdown of the articles categorized by Doyle and London within each category, while Figure 1 provides a detailed visual representation of these research concentration patterns. For better visualization, a scaled version of this same figure is shown at the end of the article (Figure 2).

Table 1.

Global Issues.

Subcategory	#Refs
1. The frame problem	32
2. Alternate competing belief revisions	26
3. Change of belief or mind	4
4. Revise beliefs accounting for new information	32
Total	94

Table 2.

Representations for Revising Beliefs.

Subcategory	#Refs
1. Manual updates	1
2. Operator descriptions	32
3. Context-layered databases	26
4. Change-triggered procedures	30
5. Logical data-dependencies	67
6. Causal dependencies	9
7. Dependency-like representations	20
Total	185

Table 3.

Procedures for Revising Beliefs.

Subcategory	#Refs
1. Chronological backtracking	4
2. Operator application	17
3. Dependency-based revision	45
4. Non-chronological backtracking	46
Total	112

Table 4.

Non-Monotonic Inference Techniques.

Subcategory	#Refs
1. Default reasoning	39
2. Non-monotonic justifications	14
3. Negation in databases	3
4. Partial matching	8
5. Minimal model circumscription	2
Total	66

Table 5.

Inexact Inferential Techniques.

Subcategory	#Refs
1. Probabilistic Inference	27
2. Decision theory	8
3. Conclusion theory	2
4. Multi-valued logics	7
5. Fuzzy logics	7
Total	51

Table 6.

Theoretical Issues.

Subcategory	#Refs
1. Logics of rational belief	21
2. Temporal logics	11
3. Situational calculus	21
4. Theory evolution theory	11
5. Proof theory	13
6. Non-monotonic logics	10
7. Meta theory	8
8. Theory of incomplete databases	9
9. Modal logics	9
10. Reasoning about uncertainty	4
Total	117

Table 7.

Applications.

Subcategory	#Refs
1. Explanation	31
2. modeling and execution	15
3. Replanning from failures	18
4. Transfer of expertise	9
5. Learning	16
6. Debugging of computer programs and mechanisms	18
7. Evolutionary computer systems	9
8. Causal analysis	22
9. Perturbation analysis	6
10. Control of reasoning	24
Total	168

Table 8.

Related Issues.

Subcategory	#Refs
1. Human belief and memory	18
2. Epistemology	26
3. Inductive inference	15
4. Hypothetical reasoning and counterfactual conditionals	9
5. Scientific theory change	5
Total	73

Figure 1.

Detailed mapping of Doyle’s references.

Figure 2.

Detailed mapping of Doyle’s references (scaled).

For the purposes of this review, we focus particularly on extracting and analyzing the computationally representative systems that emerged from categories 2 and 3 of Doyle and London’s taxonomy, which deal with representations and procedures for BR. These systems embody the algorithmic innovations that would later inform both the development of AGM theory and contemporary implementations in intelligent agents. The computational approaches we examine include the TMSs by Doyle (1979), with their sophisticated dependency tracking mechanisms, the ATMSs by De Kleer (1986), that enabled reasoning with multiple contexts simultaneously, the probabilistic belief networks by Pearl (1986), that introduced uncertainty quantification into BR, and various dependency-based reasoning systems that pioneered incremental belief update strategies (McAllester, 1982). We will detail this approach in Section 6.

5.1. TMSs: The Doyle Legacy

The development of TMSs by Doyle (1979) represents one of the most significant pre-AGM contributions to computational BR. TMS addresses the fundamental problem of maintaining consistency in knowledge bases by tracking the justifications for beliefs and automatically retracting beliefs when their supporting assumptions are withdrawn.

5.1.1. Core TMS Architecture

The TMS architecture consists of several key components:

Belief nodes: Represent individual beliefs or propositions, each associated with a status (IN or OUT) indicating whether the belief is currently accepted.

Justification structures: Encode the inferential relationships between beliefs, specifying which combinations of beliefs support or contradict other beliefs.

Dependency networks: Maintain explicit records of how beliefs depend on each other, enabling efficient propagation of belief changes.

Contradiction detection: Mechanisms for identifying inconsistencies and triggering BR processes.

The TMS operates through a cycle of assumption making, inference, contradiction detection, and dependency-directed backtracking. When a contradiction is detected, the system identifies the minimal set of assumptions that must be retracted to restore consistency, using the recorded dependency structure to guide this process efficiently.

5.1.2. Algorithmic Innovations

Doyle’s TMS introduced several algorithmic innovations that remain influential:

Dependency-directed backtracking: Instead of chronological backtracking that undoes the most recent assumptions first, TMS uses dependency information to identify and retract only those assumptions that are causally responsible for contradictions.

Incremental consistency maintenance: Rather than rebuilding the entire belief set after each change, TMS propagates the changes incrementally through the dependency network.

Assumption-based reasoning: TMS explicitly represents and manages assumptions, enabling systematic exploration of alternative assumption sets.

Justification-based inference: All beliefs are associated with explicit justifications, providing transparency and enabling sophisticated BR strategies.

5.1.3. Implementation Details

Doyle (1978) provided detailed implementation descriptions and annotated code for TMS algorithms. Key implementation features include as follows:

Node data structures: Each belief node maintains pointers to its justifications, consequences, and current status, enabling efficient traversal of the dependency network.

Justification records: Encode support relationships using lists of antecedent nodes and subsequent nodes, with special handling for conditional and default rules.

Propagation algorithms: Breadth-first and depth-first search procedures for propagating belief changes through the network while maintaining consistency.

Conflict resolution: Algorithms for identifying minimal conflict sets and selecting which assumptions to retract when multiple resolution strategies are possible.

5.2. Assumption-Based TMSs

De Kleer’s (1986) ATMS extends TMS by maintaining multiple consistent belief bases simultaneously, each corresponding to different assumption combinations. This approach avoids the computational overhead of repeatedly computing BRs by precomputing the consequences of different assumption sets.

5.2.1. ATMS Architecture

The ATMS maintains as follows:

Assumption sets: Collections of assumptions that can be made simultaneously without contradiction.

Labels: Each belief node is associated with a label indicating which assumption sets support that belief.

Nogood sets: Collections of assumptions that lead to contradictions and must be avoided.

Justification networks: Similar to TMS but extended to handle multiple contexts simultaneously.

5.2.2. Computational Advantages

ATMS provides several computational advantages over single-context TMS:

Context switching: Rapid switching between different assumption sets without recomputation.

What-if analysis: Efficient exploration of hypothetical scenarios by examining different assumption combinations.

Parallel reasoning: Multiple reasoning contexts can be maintained and explored simultaneously.

Assumption minimality: Automatic identification of minimal assumption sets sufficient to support particular conclusions.

5.3. Probabilistic Belief Networks

Pearl’s (1986) work on probabilistic belief networks (later known as Bayesian networks) provided a fundamentally different approach to BR based on probability theory rather than logical inference. These networks represent probabilistic dependencies between variables and support BR through Bayesian conditioning.

5.3.1. Network Structure

Probabilistic belief networks consist of:

Nodes: Represent random variables corresponding to propositions or events.

Directed edges: Encode probabilistic dependencies between variables.

Conditional probability tables: Specify the probability distributions for each variable given its parents in the network.

Evidence nodes: Represent observed information that constrains the probability distributions.

5.3.2. BR Algorithms

Pearl developed several algorithms for BR in probabilistic networks:

Message passing: For singly connected networks, BR can be performed efficiently using local message-passing algorithms that propagate probability updates through the network.

Clustering methods: For multiply connected networks, clustering algorithms group variables to reduce computational complexity while maintaining exact inference.

Approximation methods: When exact inference is intractable, various approximation methods provide efficient approximate BR.

5.3.3. Computational Complexity

The computational complexity of BR in probabilistic networks depends on network structure (Pearl, 1986):

Singly connected networks: Linear time complexity in network size using message-passing algorithms.

Multiply connected networks: Exponential worst-case complexity, but often tractable for networks with appropriate structure.

Approximation trade-offs: Various approximation methods (Chopra et al., 2001) provide different trade-offs between accuracy and computational efficiency.

5.4. Default Reasoning Systems

Reiter’s (1980) default logic and related non-monotonic reasoning systems provided another pre-AGM approach to BR. These systems handle incomplete information by making default assumptions that can be retracted when contradictory information is discovered.

5.4.1. Default Logic Framework

Default logic extends classical logic with default rules of the form:

$$\begin{array}{r}\frac{\alpha :{\beta }_1,\dots ,{\beta }_n}{\gamma }.\end{array}$$

This rule states that if $\alpha$ is believed and it is consistent to believe ${\beta }_1,\dots ,{\beta }_n$ , then $\gamma$ can be concluded by default.

5.4.2. Computational Approaches

Several computational approaches to default reasoning were developed:

Fixed-point algorithms: Compute default extensions by iteratively applying default rules until a fixed point is reached.

Proof-theoretic methods: Develop proof procedures that can handle default rules directly without computing complete extensions.

Compilation approaches: Transform default theories into classical logic theories that can be processed using standard inference engines.

5.5. Dependency-Based Approaches

Several pre-AGM systems focused explicitly on dependency tracking and management.

5.5.1. Reason Maintenance Systems

In his reason maintenance system, McAllester (1982) provides a different approach to dependency tracking that emphasizes computational efficiency and incremental reasoning.

5.5.2. Causal Networks

Various researchers developed causal network approaches that represent causal relationships explicitly and use them to guide BR processes (Dean & Kanazawa, 1989; Halpern & Pearl, 2005; Pearl, 2009; Spirtes et al., 1993; Verma & Pearl, 1990).

While many of these algorithms lacked the formalism introduced by the AGM model, they represented important efforts to address BR within the AI domain. These algorithms often adopted pragmatic approaches to updating belief bases, which included:

Updating heuristics: Many pre-AGM algorithms were based on simple heuristics for adding or removing beliefs from the knowledge base, without considering the logical consequences of these actions. Although these techniques were computationally efficient in terms of resources, they frequently resulted in mechanisms lacking rigor, leading systems into inconsistent states (Doyle & London, 1980; Fikes & Nilsson, 1971; Hewitt, 1972).

Probability-based models: Some pre-AGM approaches used probabilistic methods for adjusting beliefs upon receiving new information. These approaches often attempted to incorporate probabilistic techniques such as Bayesian statistics. However, the lack of rigor also led to difficulties, particularly regarding scalability and applicability to systems based on pure logic (Dean & Kanazawa, 1989; Pearl, 1986; Verma & Pearl, 1990).

Rule-based systems: Another common approach in the 1970s involved rule-based systems, in which new beliefs were inserted into or removed from the knowledge base according to a set of predefined rules. While such systems were useful in certain scenarios, they were unable to handle contradictions or inconsistencies in the information received, as the rules were not adaptive (Fikes & Nilsson, 1971; Genesereth et al., 1981; Hewitt, 1972).

5.6. Additional Systems From Doyle’s Bibliography

Beyond the major systems detailed above, Doyle and London’s bibliography documents several other influential pre-AGM approaches that contributed to the computational foundations of BR:

STRIPS and operator-based planning: Fikes and Nilsson (1971) introduced operator descriptions with explicit add and delete lists, providing early mechanisms for representing state changes. While primarily an action planning system, STRIPS’s approach to minimal change (only specified facts change) anticipated AGM’s inclusion postulate and informed the later distinction between BR and belief update (Katsuno & Mendelzon, 1991b).

CONNIVER and context mechanisms: McDermott and Sussman (1972) introduced context layers and non-chronological backtracking, enabling efficient exploration of alternative belief states. These mechanisms anticipated ATMS’s multi-context reasoning and informed theoretical work on modularity and independence in BR (Parikh, 1999).

PLANNER and pattern-directed invocation: Hewitt (1972) provided early mechanisms for change-triggered procedures, where belief changes automatically invoke relevant inference rules. This approach influenced TMS’s justification propagation and anticipated active database triggers used in contemporary belief base implementations.

Limitations of pre-AGM implementations: Most pre-AGM systems were demonstrated primarily on toy examples and small-scale domains due to 1980s computational constraints. Notable exceptions that achieved real-world deployment include the use of a TMS-style reasoning architecture in the DART expert system (Genesereth et al., 1981) and ATMS in the GDE diagnostic system (De Kleer & Williams, 1987). Contemporary implementations benefit from orders-of-magnitude improvements in processing power and memory, potentially making pre-AGM algorithmic insights more practically viable at scale.

Despite the lack of formalism, the work undertaken during this period contributed significantly to the initial development of BR within AI, establishing an important foundation for subsequent, more formal approaches.

5.7. From Computational Practice to Theoretical Foundation

The pre-AGM period established computational BR as a legitimate and necessary component of intelligent systems, with each approach contributing distinct algorithmic innovations that would later inform theoretical developments. The TMS pioneered dependency tracking and non-chronological backtracking (Doyle, 1979), ATMS introduced multi-context reasoning capabilities (De Kleer, 1986), probabilistic networks brought uncertainty quantification to BR (Pearl, 1986), and default reasoning systems provided frameworks for handling incomplete information (Reiter, 1980). Our mapping (Figure 1 and Tables 1 to 8) shows that 47% of papers focused on procedural approaches (Category 3), while 77% concentrated on representational innovations (Category 2), 70% focused on applications (Category 7), and 48% on theoretical issues—most of them related to practical aspects of BR (Category 6), demonstrating the field’s primary emphasis on computational tractability and practical implementation during this formative period.

Doyle’s contribution extends beyond mere cataloging; his work with London established a taxonomical framework that anticipated the theoretical developments that would follow with AGM while capturing the diversity of computational approaches being explored at the time (Doyle & London, 1980). This taxonomy proved remarkably prescient, identifying key dimensions of BR research that remain relevant today and providing a structured lens through which to understand the relationship between early computational work and later theoretical developments (Doyle, 1979, 1988). The distribution patterns in our analysis show that out of the eight categories in the taxonomy, Categories 2, 3, 6, and 7 received the most attention, reflecting the pragmatic priorities of AI researchers who needed working systems before formal theories were available. It is also important to mention that while there were many papers that fit into multiple categories, the papers in Categories 2, 3, 6, and 7 represent 85% of the works analyzed by Doyle and London.

This move naturally follows the historical thread presented in the origins of BR research. The foundational concerns of maintaining a model of the world, reasoning under changing information, and coping with inconsistency emerged from early AI domains such as planning, vision, and language processing, as well as from adjacent philosophical work on theory change (McCarthy, 1980; McCarthy & Hayes, 1981). Doyle’s taxonomy codifies these concerns as named axes of practice, transforming ad hoc engineering solutions into systematic categories of investigation. It represents a pivot point between the pre-AGM era of algorithmic devices, dependence tracking, non-chronological backtracking, and defaulting machinery, and the later AGM paradigm of postulates and representation theorems that would provide normative foundations for BR (Alchourrón et al., 1985; Gärdenfors, 1988). In essence, the taxonomy captures what engineers were already doing to keep beliefs coherent while the formal postulate-based account was still on the horizon.

The computational approaches examined in this section represent more than historical curiosities; they embody algorithmic insights and implementation strategies that remain relevant for contemporary BR systems. However, understanding their true significance requires evaluating them through the lens of the theoretical framework that emerged in the mid-1980s with the AGM model. The question that naturally arises is: how do these pre-AGM computational innovations relate to the rationality postulates and construction methods that AGM theory would later establish? To address this question systematically, we must develop a methodological framework that allows us to re-examine Doyle and London’s taxonomy and the computational systems it encompasses from a post-AGM theoretical perspective, assessing both their contributions to and limitations within the broader evolution of BR research.

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

The emergence of the AGM framework in the mid-1980s fundamentally transformed the theoretical landscape of BR, providing rigorous axiomatic foundations that were absent during the pre-AGM era (Alchourrón et al., 1985; Gärdenfors, 1988). This transformation creates both an opportunity and a methodological challenge: how can we systematically re-evaluate the rich computational heritage of pre-AGM systems through the clarifying lens of AGM theory? Our approach addresses this challenge by mapping Doyle and London’s empirically derived taxonomy onto the theoretical framework established by AGM, thereby bridging the gap between historical computational practice and contemporary theoretical understanding.

6.1. Literature Selection and Scope

Our literature selection strategy is grounded in Doyle and London’s foundational 1980 bibliography while extending systematically to encompass key post-AGM developments. The selection process operates through three complementary approaches:

Core historical foundation: We begin with the approximately 250 papers cited by Doyle and London’s (1980) original bibliography, which provides comprehensive coverage of pre-AGM computational approaches to BR. This foundation ensures historical completeness and maintains continuity with the taxonomical framework that organizes our analysis.

Theoretical development tracking: We systematically include key papers that established and developed the AGM framework, beginning with the foundational work by Alchourrón et al. (1985) and extending through major theoretical developments including epistemic entrenchment (Gärdenfors, 1988), kernel methods (Hansson, 1994a), iterated revision (Darwiche & Pearl, 1997), and belief base approaches (Nebel, 1989). Although the AGM framework consolidated these ideas in a unified post-1985 formulation, key elements of belief change theory had already been developed earlier, including Gärdenfors’ initial proposal of rationality postulates (1982) and the first meet and partial meet constructions introduced by Alchourrón and Makinson (1982).

Contemporary implementation analysis: We include representative contemporary work that demonstrates how AGM principles have been implemented in practical systems, with particular attention to papers that explicitly connect theoretical foundations with computational approaches.

Our temporal scope extends from 1940 to 2024, with particular emphasis on the critical period from 1970 to 1990, which encompasses both the pre-AGM computational era and the emergence of AGM theory. We include work from AI, philosophy, logic, computer science, and related fields, maintaining interdisciplinary coverage that reflects the field’s diverse intellectual foundations.

Selection criteria prioritize works that (1) establish foundational concepts or methods; (2) provide computational implementations or algorithmic contributions; (3) bridge pre-AGM and post-AGM approaches; (4) demonstrate practical applications of BR principles; and (5) explicitly address the relationship between different theoretical or computational approaches. The detailed methodology is presented in Appendix ??.

6.2. Analytical Framework

Our analytical framework combines historical analysis with systematic theoretical evaluation through several complementary methodological components:

Taxonomical mapping: We systematically map computational approaches identified in Doyle and London’s bibliography to their taxonomical categories, analyzing how these categorizations reflect the empirical structure of pre-AGM research. This mapping reveals patterns of research emphasis and identifies computational innovations that were most influential in subsequent theoretical development.

Postulate correspondence analysis: For each pre-AGM computational approach, we analyze its relationship to specific AGM postulates, examining both direct correspondences and areas where computational practice anticipated theoretical development. This analysis reveals how empirical insights about rational belief change were later formalized through AGM theory.

Evolution tracing: We systematically trace how each category in Doyle’s taxonomy evolved in the post-AGM era, identifying key theoretical developments, seminal papers, and transformation patterns. This tracing reveals how computational insights were formalized, extended, and sometimes superseded by theoretical advances.

Synthesis identification: Throughout our analysis, we identify opportunities for synthesizing insights from different eras of research, examining how pre-AGM computational strategies can inform contemporary implementations of AGM-based systems.

6.3. Methodological Implementation

To systematically implement this correspondence analysis, we reconstruct the distribution of entries across Doyle’s original taxonomy and analyze how each subcategory has evolved in the post-AGM literature. This reconstruction process involves several methodological steps. First, we identify the computational systems and approaches that Doyle and London classified under each taxonomical category. Second, we analyze how these systems relate to specific AGM postulates, construction methods, or theoretical insights. Third, we trace the evolution of each subcategory through subsequent theoretical developments, identifying key papers and theoretical advances that formalized, extended, or refined the original computational insights.

While Doyle’s descriptor-based approach captures the complexity of early systems, its resulting lack of mutually exclusive categories (multi-labeling) and heterogeneous granularity pose challenges for a structured classification. However, these characteristics do not undermine its utility for our analysis. Rather, these limitations justify our AGM-aware refinements and highlight the theoretical progress made since 1980. Our methodology acknowledges these limitations while leveraging the taxonomy’s enduring insights about the fundamental dimensions of BR research.

It is important to note that while our analysis is comprehensive within its scope, certain aspects of contemporary BR research lie beyond the boundaries of both Doyle’s original taxonomy and our AGM-focused extension. Social dimensions of BR, including how social contexts and multi-agent interactions influence belief change, represent important areas of current research that were not anticipated in the pre-AGM era (Baltag & Smets, 2008). Similarly, emotional and psychological factors that affect human BR, while relevant for cognitive modeling applications, fall outside the computational and logical focus of both the original taxonomy and our theoretical analysis.

Our methodological framework provides the analytical tools necessary to examine how Doyle’s taxonomy evolved in the post-AGM era. We now apply this framework systematically to trace the theoretical transformation of each taxonomical category, demonstrating how empirical observations about computational practice were formalized into rigorous theoretical constructs while identifying both continuities and innovations in this evolution.

7. Taxonomical Evolution in the Post-AGM Era

Doyle’s descriptor-indexed taxonomy captured the practice of belief maintenance in the pre-AGM era through empirical observation and systematic categorization of existing computational approaches. The AGM paradigm fundamentally reframed this landscape by introducing a normative, postulate-based view of rational belief change supported by rigorous representation theorems (Alchourrón et al., 1985; Gärdenfors, 1988). In this section, we systematically revisit each of Doyle’s taxonomic categories and trace their evolution in the post-AGM literature, highlighting new theoretical derivations, conceptual unifications, and practical ramifications. Our aim extends beyond mere reference compilation to demonstrate how each theoretical thread matured into components of the modern BR toolkit and how AGM’s normative framework both validated and transformed pre-AGM computational insights.

The relationship between Doyle’s empirical taxonomy and AGM’s theoretical framework exhibits both continuity and transformation. AGM reframes BR as a normative problem about rational change subject to specific postulates, including closure, success, inclusion, consistency preservation, vacuity, extensionality, and additional constraints for iterated revision, while providing representation theorems that connect algebraic choice functions to belief change operators through constructions like partial-meet contraction and Levi and Harper identities (Gärdenfors, 1988). This theoretical foundation validates many pre-AGM computational intuitions while providing systematic justification for design choices that were previously ad hoc.

7.1. Global Issues: From Computational Problems to Theoretical Postulates

7.1.1. The Frame Problem and Action-Driven Change

Doyle’s original framing merged state change by action with belief change by information, reflecting the practical reality that early AI systems needed to handle both types of change within unified computational frameworks. Post-AGM theoretical work systematically separated these concerns, leading to the fundamental distinction between belief revision and belief update (Katsuno & Mendelzon, 1991b). This separation proved theoretically crucial: AGM-style revision integrates new information with minimal change to existing beliefs, while update handles world change due to actions or events by modeling how the world itself has changed rather than how our information about a static world has improved.

This theoretical distinction led to dual semantic frameworks that formalize the intuitive difference between learning new facts and accommodating world changes. BR employs semantic approaches, including faithful assignments (Katsuno & Mendelzon, 1991b), Grove’s (1988) system of spheres, and distance-based minimization (Dalal, 1988) that prioritize minimal change to belief content. Belief update, conversely, employs possible-model approaches and persistence principles (Winslett, 1991) to model how the world evolves over time. In contemporary planning and knowledge representation systems, the frame problem is typically addressed through action formalisms such as successor-state axioms or update operators that incorporate inertia principles, while AGM-style revision handles sensing, communication, and information-gathering activities.

7.1.2. Choosing Among Competing Revisions

Doyle’s theme of choice among alternatives becomes explicit and systematic in post-AGM representation theorems through the machinery of selection functions and preference orderings. Partial-meet contraction formalizes this choice process by selecting among maximal consistent subsets (remainders) through selection functions that encode preferences over different ways of restoring consistency (Alchourrón et al., 1985). Epistemic entrenchment provides an alternative formalization where choices are guided by resistance to contraction, with more entrenched beliefs being more difficult to give up (Gärdenfors, 1988).

The distance-based and sphere semantics developed by Grove (1988) and others Dalal (1988) reify choice as minimization problems or proximity relationships in logical space, providing computational methods for implementing preference-guided revision. This theoretical line matured into sophisticated frameworks for rational preferences over change, including Parikh’s (1999) work on relevance and splitting that enables modular BR, and various approaches to priority-based and relevance-sensitive change that maintain computational tractability while respecting normative constraints.

7.1.3. Change of Belief or Mind: Iterated Revision

The original AGM framework addressed single episodes of belief change, but Doyle’s subcategory of ‘‘change of mind” explicitly identified belief change over time as a distinct problem class, anticipating the need for principled approaches to sequences of BRs. Post-AGM work systematically addressed this limitation by studying iterated BR, asking how sequences of inputs should interact and what rationality constraints should govern belief evolution over time.

The Darwiche-Pearl (DP) (1997) postulates for iterated revision sparked extensive research into iteration policies, leading to a sophisticated taxonomy of approaches including natural and lexicographic revision (Boutilier, 1996), restrained and priority-based iterations that balance stability with responsiveness to new information (Booth & Meyer, 2006), and ordinal-ranking approaches based on the Spohn’s (1988) ranking functions that connect BR to conditional logic and default reasoning. These theoretical advances provide precise answers to Doyle’s question about ‘‘how to change one’s mind again” by specifying rational dynamics for belief evolution.

7.1.4. Absorbing New Information With Minimal Disruption

Doyle’s informal notion of ‘‘minimal disruption” receives precise theoretical treatment through AGM’s central theoretical results. The Levi identity ( $K*\varphi =(K-\mathrm{\neg }\varphi )+\varphi$ ) and Harper identity ( $K-\varphi =K\cap (K*\mathrm{\neg }\varphi )$ ) establish fundamental relationships between revision, contraction, and expansion operations (Gärdenfors, 1988). Partial-meet construction methods provide systematic procedures for implementing these operations through choice functions that select among maximal consistent subsets according to specified preference criteria.

The distance-based and sphere semantics provide equivalent minimization perspectives that make the notion of ‘‘minimal change” mathematically precise through metrics on possible worlds or logical theories (Dalal, 1988; Grove, 1988). Subsequent complexity and compilability results (Eiter & Gottlob, 1992; Liberatore & Schaerf, 1996) clarify the computational feasibility of these theoretical constructions, providing guidance for practical implementation while maintaining theoretical soundness.

7.2. Representations: From Data Structures to Theoretical Constructs

7.2.1. Manual Updates and Operator Descriptions

STRIPS-style add/delete lists, which Doyle classified as operator descriptions for manual updates, became the canonical vocabulary for action update in planning systems and were formally distinguished from informational revision (Fikes & Nilsson, 1971). Post-AGM theoretical work clarified that revision should be represented intensionally through belief sets, belief bases, and entrenchment orderings, while operator descriptions belong to the update side of the revision/update distinction (Winslett, 1991). This clarification resolved the pre-AGM conflation that Doyle noted between different types of belief change by providing distinct theoretical frameworks for different change scenarios.

7.2.2. Context Layers and Modularity

Doyle’s notion of layered contexts anticipated important theoretical developments in independence and modularity for BR. Post-AGM work made these intuitions precise through formal results like Parikh’s splitting theorem, which demonstrates that when a logical language decomposes into independent components, BR can be performed component-wise without undesirable interactions between modules (Parikh, 1999). Relevance and independence constraints became design criteria for practical BR operators and informed the development of belief base policies that respect modular structure (Hansson, 1999c).

7.2.3. Change-Triggered Procedures and Dependency Structures

Doyle’s emphasis on logical data dependencies evolved into the general theory of belief bases with kernel constructions and incision functions that provide systematic methods for base-level BR (Hansson, 1994a). To contract a belief base by a formula $\varphi$ , kernel methods identify all minimal subsets that imply $\varphi$ (the $\varphi$ -kernels) and remove at least one formula from each kernel through incision functions that encode preferences over which beliefs to sacrifice.

This base-level perspective supports the fine-grained control over belief change—including traceability, minimal deletion, and explicit justification management—that Doyle sought in dependency graph approaches, while maintaining compatibility with AGM’s postulate-based framework. The kernel approach bridges the gap between AGM’s abstract theoretical requirements and the concrete implementation needs of practical BR systems (Fermé & Hansson, 2018).

7.2.4. Causal and Justificatory Encodings

Pre-AGM approaches to non-monotonic dependencies and causal relationships matured along two complementary theoretical directions in the post-AGM era. AGM-compatible approaches encode support relationships through entrenchment orderings or kernel-based methods, where causal knowledge guides incision functions to produce domain-aware contraction that respects causal structure. Conditional and ordinal approaches employ Spohn’s (1988) ranking functions and Pearl’s (1990) system Z to map justificatory relationships into numerical or ordinal structures that drive both BR and default inference, providing unified frameworks for handling both definite information and defeasible patterns.

DEL (Baltag et al., 1998; Van Ditmarsch et al., 2008) later provided event-driven action models with explicit preconditions and postconditions for updating epistemic states, offering systematic approaches to the causal and procedural relationships that pre-AGM systems handled through ad hoc mechanisms. These developments formalize Doyle’s intuitions about change-triggered procedures while providing rigorous semantic foundations.

7.3. Procedures: From Algorithms to Semantic Characterizations

7.3.1. Operator Application and Backtracking Strategies

Doyle’s operational catalogue of procedural approaches—including chronological and non-chronological backtracking, operator application, and dependency-based revision—evolved into semantic characterizations that subsume many specific algorithmic approaches under unified theoretical frameworks. Partial-meet construction corresponds to remainder selection guided by preference criteria; sphere-based semantics implements locality through distance relationships; ranking-based approaches organize preferences as priority queues over possible worlds or belief states.

Non-chronological backtracking, pioneered in systems like TMS (Doyle, 1979), corresponds to dependency-directed change at the belief base level through kernel and incision methods (Hansson, 1994a). Iterated revision policies lift these base-level procedures to handle streams of inputs while maintaining rationality constraints across multiple revision episodes (Boutilier, 1996; Darwiche & Pearl, 1997).

7.3.2. Dependency-Based Revision

Dependency-based revision became the canonical belief base revision pipeline in post-AGM theory: compute kernels to identify minimal inconsistent subsets; choose incisions according to minimality criteria or priority orderings; reconstruct a revised base from the remaining beliefs; apply logical closure if needed for specific applications (Fermé & Hansson, 2018; Hansson, 1994a). This systematic approach formalizes the dependency-tracking intuitions of pre-AGM systems while providing theoretical guarantees about the rationality of the resulting belief changes.

Specialized procedures for restricted domains—including Horn clauses, description logics, and other logical fragments—require adapted methods with appropriate definability and complexity guarantees (Eiter & Gottlob, 1992; Flouris et al., 2008). These domain-specific approaches maintain the essential insights of dependency-based revision while exploiting structural properties of particular logical languages to achieve better computational performance.

7.4. Non-Monotonic Inference: Orthogonality and Integration

7.4.1. Defaults and Justifications Versus Revision

Post-AGM theoretical work systematically clarified the relationship between BR and non-monotonic reasoning that Doyle’s taxonomy implicitly recognized, while also motivating accounts in which the two are seen as complementary perspectives on the same underlying dynamics of belief change. This relationship has been characterized both as orthogonality (where the two address fundamentally different problems) and as duality (where they represent complementary perspectives on rational belief change, Gärdenfors, 1991; Rott, 1991).

Gärdenfors (1991) demonstrates that BR and non-monotonic reasoning can be viewed as ‘‘two sides of the same coin,” with non-monotonic consequence relations corresponding to families of revision operations and vice versa. Rott (1991) further develops this connection by identifying two fundamental dimensions of belief change: the informational dimension (captured by AGM revision) and the motivational dimension (captured by non-monotonic inference), showing how these dimensions interact in rational belief dynamics.

BR addresses changing commitments in light of new factual information, while default logics and circumscription govern tentative inference patterns in the absence of complete information (McCarthy, 1980; Reiter, 1980). The KLM framework for rational closure (Kraus et al., 1990) and Spohn’s ranking functions (Spohn, 1988) provide rigorous semantics for default entailment that complement rather than compete with AGM-style BR.

7.4.2. Interaction Principles

Despite their theoretical orthogonality, AGM revision and non-monotonic reasoning systems exhibit systematic relationships at the semantic level through ranking functions and faithful assignments. The DP (1997) postulates for iterated revision constrain how conditional beliefs evolve across revision episodes, while natural versus lexicographic revision policies correspond to different approaches for re-prioritizing conditional information after receiving new inputs (Boutilier, 1996). These connections bridge Doyle’s category of ‘‘justifications” with modern conditional semantics and iterated belief change.

7.5. Inexact Inferential Techniques: Qualitative and Quantitative Bridges

7.5.1. Probabilistic and Graded Belief Change

Doyle’s category of inexact inferential techniques anticipated important connections between AGM’s qualitative approach and probabilistic methods for belief under uncertainty. While Bayesian conditioning differs fundamentally from AGM revision, principled theoretical bridges exist through limiting cases and qualitative probability theory.

Axiomatic connections between qualitative and quantitative belief have been extensively explored through multiple frameworks (Boutilier, 1994; Darwiche & Pearl, 1997; Friedman & Halpern, 1999; Goldzsmidt et al., 1993): Spohn’s ranking functions correspond to limit cases of probability measures (Spohn, 1988), where ordinal conditional functions emerge as qualitative abstractions of probabilistic belief; Jeffrey-style probability updates relate to specific iterated revision policies (Jeffrey, 1983), with connections formalized through imaging operators; and representation theorems establish conditions under which qualitative preference orderings correspond to underlying probability measures (Krantz et al., 1971).

Possibility and necessity measures produce possibility-based revision and update operators with AGM-like properties under appropriate qualitative axioms (Dubois & Prade, 1993), providing alternative approaches to uncertain belief change that maintain AGM’s insights about minimal change while accommodating numerical uncertainty representations.

7.5.2. Decision-Theoretic Choice Functions

The AGM framework’s selection step in partial-meet contraction can be enhanced with utility-theoretic considerations by choosing remainders that minimize expected loss or maximize expected value under relevant integrity constraints (Hansson, 1999c). This approach links belief change with value-guided decision making in applications where the costs and benefits of different beliefs can be meaningfully quantified, extending AGM’s normative framework to accommodate practical decision-making contexts.

7.6. Theoretical Issues: Formalization and Unification

7.6.1. Representation Theorems and Semantic Equivalences

AGM’s partial-meet and entrenchment representations (Alchourrón et al., 1985; Gärdenfors, 1988) were systematically unified with Grove’s sphere semantics (Grove, 1988) and distance-based characterizations (Dalal, 1988; Katsuno & Mendelzon, 1991b) through a series of representation theorems that demonstrate the equivalence of different approaches to formalizing minimal change. These theoretical equivalences instantiate Doyle’s concern with ‘‘proof theory” and ‘‘meta theory” through precise mathematical derivations that connect syntactic and semantic approaches to BR.

7.6.2. Belief Bases Versus Belief Sets

The distinction between belief bases (finite, non-closed sets of explicit beliefs) and belief sets (infinite, logically closed sets of all believed consequences) emerged as a central theoretical issue in post-AGM work (Hansson, 1994a; Nebel, 1998). Belief bases enable non-closed repositories with explicit traceability and fine-grained control over belief change, while belief sets provide the mathematical precision necessary for theoretical analysis. Kernel contraction and related methods provide constructive, modular approaches to base-level change with postulate soundness guarantees (Fermé & Hansson, 2018).

For restricted logical fragments including Horn clauses and description logics, definability preservation and interpolation properties become central theoretical concerns (Eiter & Gottlob, 1992; Flouris, 2006; Flouris et al., 2008), leading to specialized approaches that maintain the essential insights of AGM theory while exploiting the structural properties of particular logical languages.

7.6.3. Ontology Repair and Description Logic Extensions

The extension of AGM BR principles to description logic ontologies represents an important theoretical development that addresses practical needs in semantic web and knowledge graph applications. Description logics provide the formal foundations for ontology languages like OWL, which are widely deployed in enterprise knowledge management, biomedical informatics, and linked data systems (Baader et al., 2003).

Recent work has established formal connections between classical AGM contraction operations and ontology repair mechanisms. Baader and Wassermann (2024) demonstrate that AGM-style contractions can be defined for description logic ontologies through optimal repair strategies that minimize the removal of axioms while restoring consistency. Their approach adapts partial meet contraction to the description logic setting by identifying minimal inconsistent subsets (analogous to kernels in belief base contraction) and applying incision functions that respect the structural properties of description logic axioms.

Souza’s comprehensive analysis bridges BR theory with ontology repair implementations, demonstrating how AGM postulates can be satisfied in description logic contexts while maintaining computational tractability through approximation strategies (Souza, 2024). This work reveals that many pre-AGM computational insights, including and particularly dependency tracking and modular repair strategies, remain relevant when adapted to the more expressive logical frameworks required for contemporary ontology applications.

Contemporary ontology repair implementations demonstrate the practical synthesis of AGM theory with computational efficiency concerns. Several systems exemplify this integration:

Pellet and HermiT reasoners: These description logic reasoners incorporate justification-based repair mechanisms, following the justification-based explanation framework introduced by Horridge (2011), and implement kernel-style contraction for OWL ontologies, providing interactive debugging tools that help ontology engineers identify and resolve inconsistencies (Shearer et al., 2008; Sirin et al., 2007).

OntoClean and OOPS!: Ontology validation and repair tools that combine automated consistency checking with user-guided repair strategies, addressing the preference elicitation challenge by incorporating domain expert knowledge through interactive interfaces (Guarino & Welty, 2002; Poveda-Villalón et al., 2014).

LogMap and AgreementMaker: Ontology alignment systems that handle BR during ontology matching and merging, implementing AGM-inspired operators for resolving conflicts between independently developed ontologies (Cruz et al., 2009; Jiménez-Ruiz & Grau, 2011).

These implementations validate the synthesis approach advocated throughout our survey: they combine AGM’s normative framework, through formal repair semantics, with pre-AGM computational strategies (dependency tracking, incremental processing, and modular repair) to achieve both theoretical soundness and practical scalability in real-world knowledge management applications.

The ontology repair domain illustrates how AGM principles generalize beyond propositional logic, while requiring careful adaptation to respect the semantic and computational properties of more expressive logical languages. This extension validates the enduring relevance of AGM’s normative framework while demonstrating the continued importance of computational pragmatism in practical implementations.

7.6.4. Iteration and Dynamics

The combination of iterated revision theory (through the DP postulates) and DEL provides operational models of information change through public announcements, private communications, and complex action models (Baltag et al., 1998; Van Ditmarsch et al., 2008). These frameworks remain consistent with AGM-style minimality principles when restricted to hard factual inputs, thus addressing Doyle’s concerns about ‘‘change of mind” and ‘‘temporal reasoning” through precise temporalized dynamics that maintain normative rationality constraints.

7.6.5. Complexity and Compilability

Post-AGM theoretical work systematically mapped the computational complexity landscape for BR and update operations, establishing tight bounds including NP-completeness and polynomial hierarchy results, along with parameterized complexity analyses (Eiter & Gottlob, 1992; Liberatore & Schaerf, 1996). These results replace Doyle’s informal feasibility observations with precise computational characterizations that guide practical implementation strategies while maintaining theoretical soundness.

7.7. Applications: From Use Cases to Systematic Frameworks

7.7.1. Explanation, Debugging, and Diagnosis

Model-based diagnosis and explanation systems align naturally with abductive reasoning combined with belief revision: generate hypothetical explanations through abduction, revise beliefs to restore consistency with observations, and prefer minimal changes according to distance or sphere-based semantics (Hansson, 1999c). Kernel methods operationalize the ‘‘blame assignment” problems in debugging applications by providing systematic approaches to targeted incision that preserve important beliefs while removing sources of inconsistency.

7.7.2. Planning, Execution, and Replanning

The AGM/update distinction proved decisive for planning applications: execution and replanning from failure employ update operations to model world changes, while sensing and communication trigger revision operations to incorporate new information about existing world states. Formal action update approaches, including possible models approach (PMA) and Winslett’s updates (1991), along with DEL-style event models (Van Ditmarsch et al., 2008), provide unified theoretical accounts that systematically address the planning concerns that motivated much pre-AGM research.

7.7.3. Knowledge Acquisition and Learning

Viewing learning through the lens of belief change naturally extends to belief merging frameworks, which offer systematic postulates and operators for handling multiple information sources (Konieczny & Pino Pérez, 2002). In the context of knowledge acquisition, however, the focus shifts to base-level operations. Unlike full belief set revision, base contraction preserves the structure of explicit information (Hansson, 1999c). When combined with provenance tracking (Buneman et al., 2001), this approach enables transparent editing and conflict resolution mechanisms—such as axiom pinpointing—that allow users to maintain understanding and control over the system’s evolution (Kalyanpur et al., 2005).

7.7.4. Control of Reasoning

Doyle’s notion of ‘‘control of reasoning” finds systematic realization through priority and entrenchment policies, relevance constraints (exemplified by Parikh’s splitting results (1999)), and modular approaches that govern which beliefs receive protection during change operations and where changes should be localized within complex knowledge structures (Hansson, 1999c).

7.8. Related Issues: Philosophical Foundations and Logical Extensions

7.8.1. Epistemology and Dynamics of Belief

Post-AGM work systematically developed connections between belief states, conditional logic, and belief dynamics through the integration of conditional logic (KLM framework) (Kraus et al., 1990), ranking functions (Spohn, 1988), and DEL (Van Ditmarsch et al., 2008). These theoretical frameworks jointly explain how accepted conditionals evolve under streams of information, providing rigorous foundations for the epistemological concerns that Doyle identified as related to but distinct from computational BR.

Comprehensive treatments by Rott (2001a), Hansson (1999c), and Fermé and Hansson (2018) provide book-length accounts that systematically connect philosophical intuitions about rational belief change to postulate-based theoretical frameworks and computational implementation strategies.

7.8.2. Theory Change Across Logical Systems

Beyond propositional logic, BR has been systematically adapted to description logics, Horn clause systems, and ontology frameworks with appropriate preservation properties and specialized algorithmic procedures including tableau-based and graph-based methods (Flouris et al., 2013, 2008). These extensions fulfill Doyle’s call for ‘‘theory evolution” across different logical systems, while maintaining the essential insights of the AGM theory through careful adaptation to the structural properties of particular logical languages.

8. Synthesis and Analysis

We traced the evolution of BR research from its computational origins in the 1970s through the theoretical revolution of the AGM framework and the follow-up work. Our analysis reveals several key influences and findings about the relationship between theory and practice in BR.

The AGM framework marked a watershed in BR. It legitimized the area as a subject of formal inquiry and set normative standards that still shape theory and practice. Its central contribution was theoretical unification. AGM connected heterogeneous pre-AGM proposals under common rationality postulates, which enabled systematic comparison and evaluation across methods (Alchourrón et al., 1985). It also raised methodological rigor. The framework demanded mathematical precision and proof-level analysis, which lifted baseline quality and supported advanced developments in representation and inference (Gärdenfors, 1988). Despite its abstractions, the AGM offered practical guidance. Postulates, construction methods, and representation theorems supplied design templates that link abstract criteria to implementable operators (Alchourrón et al., 1985). The AGM framework also generated research programs. Work on limitations, extensions, and computable realizations shows the fertility and durability of the approach (Fermé & Hansson, 2018; Hansson, 1999b).

We observed that pre-AGM and post-AGM practices display complementary virtues that motivate integration. Pre-AGM work foregrounds computational pragmatism: it targets implementable algorithms with explicit time and space complexity guarantees (Nebel, 1994), privileges incremental processing with efficient data structures for streaming or online updates (Doyle, 1979), and is attentive to practical constraints such as bounded memory and real-time responsiveness in deployed systems (Wassermann, 1999). This line also favors modular software architectures that separate parsing, representation, update, and evaluation to support substitutability and testing (Doyle, 1979).

AGM theory contributes to the formal discipline. It supplies explicit rationality postulates that norm revision behavior and make assumptions auditable (Alchourrón et al., 1985), mathematical precision that enables proof-level analysis and cross-method comparison (Gärdenfors, 1988), and a unifying conceptual scheme that relates disparate update procedures under common principles (Alchourrón et al., 1985). Crucially, representation theorems connect abstract postulates to concrete operators, enabling correctness arguments and systematic design choices (Gärdenfors, 1988).

Persistent challenges from the pre-AGM work remain salient. The frame problem endures: efficiently determining inert facts during revision is still costly in dynamic, partially observed settings, where naively recomputing closure is untenable (McCarthy & Hayes, 1981). Preference elicitation is underspecified: AGM presupposes entrenchment orderings or selection functions, yet offers little operational guidance for inferring these structures from users, logs, or latent models, especially under noise and strategic behavior (Hunter & Boyarinov, 2022; Rott, 2001b). Computational hardness results for AGM-style operators constrain scalability; practical deployments therefore rely on approximations, but the accuracy–efficiency frontier and its robustness under distributional shift are not well characterized (Eiter & Gottlob, 1992). Finally, iterated revision remains problematic: postulates adequate for single-shot updates can yield counterintuitive dynamics across sequences, exposing path dependence, non-commutativity, and instability that current axioms only partially address (Boutilier, 1996).

8.1. Theoretical Gaps and Extensions

Our correspondence analysis reveals important categories in Doyle’s taxonomy that do not map directly onto AGM postulates, highlighting areas where the theoretical framework may need extension or where alternative theoretical approaches are required.

The non-monotonic inference category represents a fundamental theoretical gap (Alchourrón & Makinson, 1982). Although systems like Reiter’s default logic (Reiter, 1980) and McCarthy’s circumscription (McCarthy, 1980) were central to pre-AGM computational practice, they address problems different from those of AGM-style BR. Non-monotonic inference concerns the derivation of tentative conclusions in the absence of complete information, while AGM revision addresses the incorporation of new definitive information into existing belief sets. This distinction has led to parallel theoretical developments, with non-monotonic reasoning finding formalization through approaches like preferential models (Kraus et al., 1990), expectation-based inference (Gärdenfors, 1991), and ranking functions (Spohn, 1988) that complement rather than compete with the AGM theory.

Similarly, the inexact inferential techniques category highlights the relationship between AGM’s categorical approach to belief and probabilistic or fuzzy approaches to uncertainty. While Pearl’s probabilistic networks (1986) provided sophisticated machinery for BR under uncertainty, AGM theory deliberately abstracts away from numerical uncertainty to focus on categorical belief change. Subsequent work has explored the connections between these approaches through limiting cases and qualitative probability theory (Boutilier, 1994), but the fundamental tension between categorical and graded approaches to belief remains an active area of theoretical investigation.

The applications category reveals practical concerns that extend beyond AGM’s theoretical scope. Real-world applications often require consideration of computational complexity, real-time constraints, user interaction, and domain-specific knowledge that AGM’s abstract framework does not directly address. This has led to the development of approximate and anytime algorithms (Chopra et al., 2001; Wassermann, 1999; Williams, 1997), user-guided revision procedures, and domain-specific adaptations that maintain AGM’s normative insights while accommodating practical constraints.

8.2. Synthesis: Theoretical Transformation of Doyle’s Taxonomy

The post-AGM evolution of each category in Doyle’s taxonomy reveals systematic patterns of theoretical development that transform empirical observations about computational practice into rigorous normative frameworks:

Global issues evolved from informal concerns about minimal disruption and competing alternatives into precise theoretical constructs, including the distinction between revision and update, systematic derivations through the Levi and Harper identities, and rigorous approaches to iterated change that transform ‘‘minimal disruption” into mathematically precise theorems about rational belief change (Section 7.1).

Representations progressed from ad hoc data structures and procedural mechanisms to systematic theoretical constructs including belief sets and bases with entrenchment orderings, sphere-based and distance-based semantics, kernel and incision methods, and independence and splitting results that formalize modularity intuitions (see Section 7.2).

Procedures evolved from operational algorithms and backtracking strategies to equivalent semantic constructors, including partial-meet contraction, faithful assignments, and implementable base-level algorithms through kernels and incisions that maintain both theoretical soundness and computational tractability (see Section 7.3).

Non-monotonic and inexact techniques developed clean theoretical interfaces to default reasoning systems and graded uncertainty measures, with DP postulates and KLM frameworks providing systematic unification of conditional dynamics and iterated belief change (see Sections 7.4 and 7.5).

Theoretical issues achieved comprehensive formalization through representation and complexity theorems, iteration and dynamic logic frameworks, and fragment-aware approaches to belief change that maintain AGM insights while accommodating the structural properties of restricted logical languages (see Section 7.6).

Applications evolved from informal use cases into principled change policies for planning, diagnosis, debugging, ontology evolution, and multi-source information merging that maintain both theoretical soundness and practical effectiveness (see Section 7.7).

This systematic theoretical transformation validates Doyle’s original taxonomical insights while demonstrating how empirical observation of computational practice can anticipate and guide subsequent theoretical development. The post-AGM evolution reveals that Doyle’s taxonomy captured enduring structural features of BR research that remain relevant across different levels of theoretical sophistication and computational implementation.

The analysis of taxonomical evolution reveals broader patterns about the relationship between computational practice and theoretical development in BR research. These patterns provide the foundation for synthesizing our findings about the field’s historical development and identifying opportunities for integrating insights from different eras of research.

8.3. Methodological Limitations

Although our analysis is comprehensive within its defined scope, several important limitations should be acknowledged:

Taxonomical constraints: Our analysis is organized around Doyle and London’s 1980 taxonomy, which may not capture all important aspects of contemporary BR research. Areas such as social epistemology, emotional factors in belief change, and certain aspects of multi-agent BR may be underrepresented due to the historical focus of the original taxonomy.

Implementation coverage: While we examine key computational approaches and their theoretical relationships, we do not provide comprehensive coverage of all BR implementations or systematic empirical evaluation of their performance characteristics. Our analysis is focused on the works presented in Section 5, and Subsections from 5.1 to 5.5, and their direct follow-up works.

Theoretical scope: Our focus on AGM theory and its extensions means that alternative theoretical frameworks for BR may receive less systematic treatment, though we acknowledge their importance and identify connections where relevant.

Contemporary developments: The rapid pace of development in AI and machine learning means that some contemporary approaches to BR may not be fully represented, particularly those emerging from deep learning and neural-symbolic integration.

These limitations are inherent to any survey of a large and active research field, but they do not undermine the validity of our core contributions regarding the historical development and theoretical evolution of BR research.

8.4. Contemporary AI Challenges and BR

The rapid advancement of AI in the 2020s has introduced new challenges and opportunities for BR that extend beyond the traditional scope captured by the Doyle’s taxonomy and the AGM theory. These contemporary developments both validate the historical foundations we have established and reveal new research directions that build upon them.

8.4.1. Neural-Symbolic Integration

The emergence of large language models (LLMs) and neural-symbolic AI systems creates novel requirements for BR mechanisms that can operate across both symbolic and subsymbolic representations (Garcez et al., 2019; Hamilton et al., 2017; Kautz, 2022). Traditional AGM operators assume symbolic belief sets, but contemporary AI systems must handle:

Distributed representations: Beliefs encoded in neural network weights require new approaches to belief identification, extraction, and modification that maintain both symbolic interpretability and neural network functionality (Koh et al., 2020; Locatello et al., 2020);

Probabilistic beliefs: Neural systems naturally represent uncertainty through probability distributions, requiring integration between AGM’s categorical approach and probabilistic BR frameworks (Belle et al., 2015; Manhaeve et al., 2018);

Learned preferences: Unlike AGM’s assumption of given entrenchment orderings, neural systems can learn preference structures from data, requiring dynamic adaptation of BR policies based on experience (Christiano et al., 2017; Ouyang et al., 2022).

The progression from Pearl’s probabilistic networks (1986) to modern neural architectures highlights a persistent tension between statistical inference and logical consistency. This suggests that today’s integration challenges are not entirely novel, but rather extensions of the structural concerns that motivated the AGM era, thereby validating the relevance of our historical analysis.

8.4.2. Distributed and Multi-Agent Systems

Contemporary AI applications increasingly operate in distributed environments where BR must handle (Robnik-Šikonja & Kononenko, 2003; Stone & Veloso, 2000):

Asynchronous updates: Unlike the sequential revision assumed by classical AGM theory, distributed systems must handle concurrent belief changes from multiple sources with potential conflicts and dependencies (Dragoni & Giorgini, 2003);

Trust and source reliability: Modern systems must incorporate dynamic trust models and source credibility assessments that extend beyond AGM’s assumption of equally reliable information sources (Marsh, 1994; Sabater & Sierra, 2005);

Scalability constraints: Cloud-based AI systems must perform BR across massive knowledge bases with strict latency requirements, requiring approximation strategies that maintain theoretical soundness (Dean & Ghemawat, 2008; Zaharia et al., 2016).

These challenges extend the multi-context reasoning pioneered by de Kleer’s ATMS (1986) to contemporary distributed architectures, demonstrating how pre-AGM computational insights remain relevant for modern implementation challenges and highlighting the need for BR operators that reconcile concurrency, trust, and scalability while preserving the normative guarantees articulated by the AGM theory.

8.4.3. Human-AI Collaboration

The integration of AI systems with human decision-making introduces BR challenges that bridge computational and cognitive considerations (Amershi et al., 2019; Wang et al., 2019):

Explainable revision: AI systems must provide transparent explanations of belief changes that humans can understand and validate, requiring revision procedures that maintain audit trails and justification structures reminiscent of Doyle’s TMS dependency tracking (Doyle, 1979; Gunning et al., 2019; Miller, 2019).

Interactive preference elicitation: Systems must learn human preferences for BR through interaction rather than a priori specification, requiring adaptive approaches to entrenchment and selection function learning (Boutilier, 2002).

Collaborative belief maintenance: Human-AI teams must maintain shared belief states while accommodating different reasoning styles and confidence levels, requiring extensions to traditional single-agent revision frameworks (Endsley, 2015; Klein et al., 2005).

8.4.4. Implications for Implementation Research

These contemporary challenges validate several key insights from our historical analysis:

Computational pragmatism remains essential: The efficiency and modularity concerns that motivated pre-AGM systems are amplified in contemporary applications that must operate at scale with real-time constraints (Bahdanau et al., 2014; Russell, 2019).

Theoretical foundations provide stability: AGM’s normative framework remains relevant for ensuring rational behavior even as implementation contexts evolve dramatically (Marcus, 2020; Pearl & Mackenzie, 2018).

Synthesis approaches are necessary: The combination of theoretical rigor with computational efficiency that we identified as a key research direction becomes even more critical for contemporary applications (Bengio et al., 2021; LeCun et al., 2015).

Future implementation research must therefore build upon the historical foundations we have established while addressing these contemporary extensions. The systematic approach developed in this survey provides the baseline necessary for principled investigation of these emerging challenges.

8.5. Concrete Implementation Examples: Pre-AGM Techniques Implementing AGM Operators

While the correspondence between pre-AGM systems and AGM theory has been established theoretically, concrete examples demonstrate how classical computational techniques can directly implement AGM operators. These examples illustrate the practical synthesis of algorithmic efficiency with theoretical rigor.

8.5.1. Example 1: TMS-Based Kernel Contraction

Doyle’s TMS can implement AGM kernel contraction through its dependency tracking mechanisms:

AGM kernel contraction specification: Given belief base $K$ and sentence $\alpha$ to remove, kernel contraction $K÷\alpha$ requires:

Identify all minimal subsets $K^{\prime }$ of $K$ such that $K^{\prime }⊢\alpha$ .

Apply an incision function $\sigma$ to select beliefs to remove from each kernel.

Return $K\setminus \bigcup \sigma (K⨿\alpha )$ .

TMS implementation strategy:

Kernel identification: Use TMS dependency graphs to identify minimal inconsistent subsets.

Traverse justification networks to find all derivation paths for $\alpha$ .

Note: TMS derivation paths are not necessarily minimal in the kernel sense. Additional processing is required: (1) identify all TMS derivation paths for $\alpha$ ; (2) extract the sets of assumptions used in each path; and (3) apply minimality filtering to obtain actual kernels.

This additional step adds computational overhead but leverages TMS’s existing dependency structure.

Incision function implementation: Adapt TMS mechanisms to implement incision functions.

Important distinction: TMS justifications represent inferential relationships, not belief preferences per se.

To implement AGM incision functions, we must (1) derive belief preferences from justification structures (e.g., beliefs supported by more/stronger justifications are more entrenched); (2) use explicit user-provided or learned preference orderings over beliefs; or (3) employ domain-specific heuristics.

The TMS literature (Doyle, 1979) did not systematically address preference elicitation. This remains an integration challenge when adapting TMS for AGM-compliant kernel contraction.

TMS provides mechanisms that can be adapted to implement incision functions, including assumption retraction strategies and dependency-directed conflict resolution, though the principles governing these were largely heuristic in original implementations.

Efficient update: Leverage TMS incremental update mechanisms

Remove selected beliefs using existing TMS node deletion procedures.

Propagate changes through the dependency network using standard TMS algorithms.

Maintain consistency through established truth maintenance protocols.

AGM compliance note: The construction described here targets kernel contraction. When embedded in a revision operator via the Levi identity, AGM success is guaranteed provided (i) the input sentence is consistent, and (ii) the incision function is non-empty; otherwise, the construction corresponds to semi-revision or external revision variants.

Algorithmic advantages:

Incremental processing: TMS naturally handles incremental belief changes.

Dependency tracking: Explicit representation enables efficient kernel identification.

Conflict resolution: Existing TMS mechanisms provide mechanistic support for implementing incision functions.

Computational efficiency: Avoids expensive theorem proving through cached dependencies.

8.5.2. Example 2: ATMS-Based Partial Meet Revision

The assumption-based TMS naturally implements partial meet revision through its context management capabilities:

AGM partial meet revision: For belief set $K$ and new information $\alpha$ :

Compute maximal subsets of $K\cup \{\alpha \}$ that remain consistent.

Apply selection function to choose preferred maximal subsets.

Return intersection of selected subsets.

ATMS implementation:

Context enumeration: Use ATMS assumption management for maximal subset computation:

Treat original beliefs and new information $\alpha$ as assumptions.

ATMS automatically computes all consistent assumption combinations.

Each consistent context corresponds to a maximal consistent subset.

Selection function: Implement preference-based context selection:

Rank contexts by assumption costs or preference weights.

Apply domain-specific selection criteria (e.g., minimize change and maximize informativeness).

Use ATMS focus-of-attention mechanisms to manage computational complexity.

Intersection computation: Derive beliefs common to selected contexts:

Identify nodes that are IN across all selected contexts.

Use ATMS label intersection operations for efficient computation.

Result forms the revised belief base satisfying AGM postulates.

Implementation benefits:

Multiple context management: ATMS naturally handles alternative belief states.

Efficient consistency checking: Built-in nogood management prevents inconsistent contexts.

Scalable context selection: Focus mechanisms manage exponential context spaces.

Parallel processing: Multiple contexts can be evaluated simultaneously.

8.5.3. Example 3: Probabilistic Network Belief Update as AGM Revision

Pearl’s belief networks can implement AGM revision when beliefs are represented as high-confidence probabilistic assertions:

Probabilistic-to-logical mapping:

Represent beliefs as propositions with probability $>\theta$ (e.g., $\theta =0.9$ ).

New evidence corresponds to setting specific node probabilities to 1.0.

BR corresponds to probabilistic updating followed by thresholding.

Implementation process:

Evidence incorporation: Set evidence nodes to reflect new information.

Probabilistic update: Use belief propagation algorithms to update network.

Belief extraction: Extract beliefs exceeding confidence threshold.

Consistency checking: Verify result satisfies AGM postulates.

AGM postulate satisfaction:

Success: New evidence always included (probability = 1.0).

Inclusion: Probabilistic update never adds unrelated beliefs.

Consistency: Network structure prevents inconsistent high-confidence beliefs.

Minimal change: Probabilistic updating minimizes information-theoretic distance.

8.5.4. Empirical Performance Considerations

Important caveat: Our examples demonstrate structural correspondence between pre-AGM techniques and AGM operators, not empirical superiority over contemporary approaches. Whether TMS/ATMS dependency tracking outperforms modern SAT-based approaches depends on multiple factors:

Problem structure: TMS/ATMS may excel in domains with sparse, hierarchical dependencies; SAT solvers may dominate in densely connected problems.

Update patterns: Incremental scenarios with frequent small updates may favor TMS/ATMS; batch scenarios requiring complete consistency checking may favor SAT compilation.

Implementation quality: Modern SAT solvers benefit from decades of optimization; comparable effort has not been invested in TMS/ATMS implementations.

Parallelization: We are not aware of well-documented parallel implementations of TMS/ATMS, though the multi-context architecture suggests natural parallelization opportunities.

Systematic empirical comparison—including benchmarking TMS/ATMS against contemporary SAT solvers, evaluating parallel implementations, and testing on real-world problem instances—represents important future work enabled by our foundational analysis but beyond the scope of this survey. Such empirical investigation is explicitly identified as a priority research direction in Section 9.

8.5.5. Synthesis Observations

These examples demonstrate several key principles for implementing AGM operators using pre-AGM techniques:

Structural correspondence: Pre-AGM data structures (dependency graphs, assumption sets, and probability networks) naturally map to AGM constructs (kernels, maximal subsets, and preference orderings).

Algorithmic efficiency: Pre-AGM algorithms provide computational shortcuts for operations that would be intractable if implemented naively from AGM definitions.

Incremental processing: All three examples leverage incremental update mechanisms that avoid recomputation from scratch.

Preference integration: Each approach provides natural mechanisms for incorporating domain-specific preferences required by AGM theory.

Practical scalability: The examples show how theoretical AGM operators can be implemented efficiently enough for real-world applications.

These concrete implementations bridge the gap between AGM’s theoretical elegance and the computational pragmatism of pre-AGM systems, demonstrating that the historical evolution of BR represents not just theoretical progress but also practical synthesis.

9. Discussion

The field of BR has evolved dramatically since Doyle and London’s foundational bibliography in 1980. What began as a collection of ad hoc computational techniques has developed into a sophisticated field with rigorous theoretical foundations and practical applications across numerous domains.

The journey from pre-AGM computational approaches through the theoretical revolution of AGM to contemporary implementations reveals both the power of formal analysis and the importance of computational pragmatism. Neither pure theory nor pure implementation is sufficient; the most successful approaches combine theoretical insights with computational innovation. Examples of such approaches include:

Ontology debugging and repair systems: Tools for debugging unsatisfiable classes in OWL ontologies compute minimal justifications (MUPS) and support semi-automatic repair, effectively instantiating kernel-style contraction at the ontology level while remaining usable on large real-world ontologies (Kalyanpur et al., 2006, 2005).

Belief merging systems: Implementations that combine AGM-inspired postulates with distance-based optimization and SAT compilation demonstrate practical scalability for multi-source information integration, showing how abstract rationality constraints can guide concrete algorithm design (Konieczny & Pino Pérez, 2002).

Ontology repair via kernel contraction: Recent prototypes compute ontology repairs using kernel (and partial meet) pseudo-contraction operators, explicitly realizing AGM-style belief base change in description logics and exposing it through Protégé plug-ins (Matos & Wassermann, 2022).

These systems demonstrate that the synthesis of pre-AGM computational efficiency with AGM theoretical rigor is not merely conceptual but has been achieved in deployed applications.

This review is deliberately bound. It traces the line from pre-AGM computational practice, through the AGM framework, to contemporary implementations of AGM-style operators. It does not survey the entire landscape of BR.

Within this scope, three findings hold. First, pre-AGM work delivered implementable, modular methods with explicit computational costs and effective dependency tracking. Second, AGM provided unifying rationality postulates, representation theorems, and a comparative language that raised methodological standards. Third, contemporary implementations operationalize selected AGM-style operators under practical constraints: they rely on incremental algorithms and approximations to address intractability; preference elicitation remains largely ad hoc; iterated revision and the frame problem continue to be open engineering concerns.

A feasible synthesis follows from these findings: use AGM as specification and pre-AGM as implementation, with learned preferences and resource-aware execution. This is a design hypothesis, not a claim of field-wide convergence.

9.1. Research Contributions

This targeted narrative review advances BR research through several interconnected contributions that establish a foundation for systematic implementation analysis:

Comprehensive historical analysis: We have provided the first systematic examination of BR evolution using Doyle and London’s taxonomy as an organizing framework, revealing how computational and theoretical approaches have influenced each other across four decades of research. This analysis establishes a comprehensive baseline that connects early algorithmic insights with contemporary theoretical understanding.

Systematic theory-practice integration: Our approach systematically identifies correspondence patterns between pre-AGM computational methods and AGM theoretical constructs, providing concrete foundations for implementations that combine efficiency with theoretical soundness. This integration goes beyond previous surveys by establishing specific mappings between algorithmic approaches and formal requirements.

Implementation research baseline: By comprehensively analyzing both historical precedents and theoretical developments, we have established the foundation necessary for systematic computational implementation research. This baseline enables systematic gap analysis, architectural design, and empirical validation of BR systems against both efficiency and correctness criteria.

Contemporary implementations that demonstrate a synthesis of BR principles with computational pragmatism are still relatively rare. Among notable examples are general-purpose belief change libraries such as Tweety, which implement AGM-style belief (base) revision and contraction operators, and ontology debugging/repair tools built on top of OWL reasoners (Kalyanpur et al., 2005; Matos & Wassermann, 2022; Thimm, 2014). In contrast, widely used OWL reasoners (Pellet and HermiT) and ontology alignment systems (LogMap and AgreementMaker) focus on efficient reasoning and matching, and are only indirectly connected to AGM-style belief change through their use in debugging, repair, and integration workflows (Cruz et al., 2009; Jiménez-Ruiz & Grau, 2011; Shearer et al., 2008; Sirin et al., 2007).

Strategic research framework: The comprehensive foundation provided here enables a systematic research program addressing computational BR implementation. This framework supports systematic investigation of engineering challenges while maintaining theoretical rigor and historical perspective.

Our emphasis on computational implementations and algorithmic details provides practical guidance for implementers while connecting implementation challenges to theoretical insights. This focus addresses a gap in the literature between abstract theory and concrete implementation by providing the comprehensive foundation necessary for systematic engineering research.

9.2. Toward Computational Implementation: Foundation and Research Directions

The historical analysis presented in this review establishes a comprehensive foundation for systematic computational implementation research. By tracing the evolution from Doyle and London’s taxonomy through AGM theory to contemporary approaches, we have identified key theoretical foundations, persistent implementation challenges, and synthesis opportunities that inform future engineering efforts.

9.2.1. Foundational Requirements for Implementation

Our analysis reveals several foundational requirements that any robust computational BR system must address:

Theoretical baseline: The AGM framework provides essential normative criteria that implementations should approximate or satisfy under specified conditions (Alchourrón et al., 1985). However, our historical analysis shows that pre-AGM computational insights regarding efficiency, incrementality, and modularity remain crucial for practical systems (Doyle, 1979).

Representational adequacy: The evolution from simple dependency networks (Doyle, 1979) to sophisticated graph-based structures (Williams, 1986) and contemporary probabilistic representations (Darwiche, 2009) demonstrates the need for representation schemes that support both efficient computation and theoretically sound revision operations.

Algorithmic foundations: The progression from chronological backtracking (Stallman & Sussman, 1977) through AGM construction methods (Gärdenfors, 1988) to modern SAT-based approaches (Eiter et al., 2009) establishes algorithmic patterns that balance computational tractability with theoretical guarantees.

Integration architecture: The historical development from isolated TMS components (Doyle, 1979) to integrated agent architectures (Forbus & De Kleer, 1993) reveals architectural principles essential for embedding BR within broader intelligent systems.

9.2.2. Research Directions Enabled by Historical Foundation

The comprehensive baseline established by this survey enables several systematic research directions:

Computational blueprint development: Future research can systematically address the engineering challenges of translating the theoretical foundations identified here into robust computational frameworks. This includes investigating knowledge representation choices, reasoning service requirements, and operator implementation strategies that preserve theoretical guarantees while achieving computational efficiency comparable to pre-AGM systems.

Implementation analysis framework: The historical taxonomy and theoretical baseline provided here support systematic evaluation methodologies for BR implementations. Research can develop assessment frameworks that measure implementations against both the efficiency benchmarks established by pre-AGM systems and the correctness criteria provided by the AGM theory.

Synthesis architecture investigation: The correspondence patterns identified between pre-AGM computational approaches and AGM theoretical constructs suggest concrete opportunities for hybrid implementations. Systematic investigation of these synthesis opportunities can yield architectures that combine AGM rigor with pre-AGM computational efficiency.

Gap analysis and validation: The comprehensive coverage provided by this survey enables systematic gap analysis between theoretical requirements and current implementation capabilities. This foundation supports the development of validation protocols and empirical studies that can guide implementation priorities.

9.2.3. Implementation Research Methodology

The historical perspective developed here suggests a systematic methodology for implementation research:

Historical precedent analysis: Each implementation challenge should be analyzed against the historical precedents identified in this survey, leveraging both successful pre-AGM computational strategies and post-AGM theoretical insights.

Theoretical constraint identification: Implementation research should systematically identify which AGM postulates and theoretical requirements are essential for specific applications and which can be relaxed for computational efficiency.

Synthesis pattern recognition: The correspondence analysis developed here provides templates for identifying how theoretical constructs can be realized through computational mechanisms derived from historical precedents.

Empirical validation design: Implementation research should leverage the comprehensive baseline provided here to design empirical studies that assess both correctness (against theoretical standards) and efficiency (against historical benchmarks).

This foundation enables a systematic research program that can address the engineering challenges of computational BR while maintaining theoretical rigor and historical perspective. The next phase of research can build on this comprehensive baseline to develop practical, theoretically sound, and computationally efficient BR systems for contemporary AI applications.

9.3. Future Research Directions

The comprehensive foundation established in this survey opens several strategic research directions that build systematically on the historical and theoretical baseline we have developed.

9.3.1. Engineering-Focused Implementation Research

Empirical validation design: Implementation research should leverage the comprehensive baseline provided here to design empirical studies that assess both correctness (against theoretical standards) and efficiency (against historical benchmarks).

A critical gap identified by this survey is the lack of systematic empirical comparison between AGM implementations, pre-AGM techniques, and hybrid approaches. Implementation research should leverage the comprehensive baseline provided here to design empirical studies that assess:

Correctness: Compliance with AGM postulates under various problem conditions.

Efficiency: Runtime and memory performance against historical benchmarks (TMS and ATMS) and contemporary baselines (SAT solvers and ASP systems).

Scalability: Performance degradation patterns as problem size increases.

Robustness: Behavior under noisy inputs, incomplete information, and adversarial scenarios.

Such empirical work would validate (or refute) our hypothesis that pre-AGM computational insights can improve contemporary AGM implementations, transforming our foundational analysis into actionable engineering guidance.

Computational blueprint development: Building on the theoretical foundations and historical precedents identified here, future work can systematically address the engineering challenges of developing robust computational BR frameworks. This includes investigating optimal knowledge representation choices, designing efficient reasoning services, and developing operator implementation strategies that maintain theoretical soundness while achieving practical performance.

Architecture and integration studies: The architectural insights derived from our historical analysis can inform systematic investigation of BR integration patterns within broader AI systems. Research can examine how different architectural approaches affect both computational efficiency and theoretical compliance across various application domains.

Performance analysis and optimization: The baseline established by our survey enables systematic performance analysis that evaluates implementations against both historical efficiency benchmarks and contemporary scalability requirements. This research direction can develop principled approaches to trading off theoretical guarantees for computational performance.

9.3.2. Theoretical Extensions and Validation

Synthesis framework development: The correspondence patterns identified between pre-AGM and AGM approaches suggest opportunities for developing unified theoretical frameworks that formalize the integration of computational efficiency with theoretical rigor. Future research can systematically explore these opportunities.

Empirical validation methodologies: The comprehensive coverage provided here enables the development of systematic empirical validation approaches for BR systems. Research can establish standardized evaluation frameworks that assess both correctness and practical performance across diverse application contexts.

Contemporary challenge analysis: Future work can leverage the historical perspective developed here to analyze how contemporary challenges—including machine learning integration, distributed systems, and human–AI collaboration—relate to historical precedents and theoretical requirements.

9.3.3. Methodological Innovations

Systematic implementation analysis: The foundation provided by this survey supports the development of systematic methodologies for analyzing and comparing BR implementations. Future research can establish frameworks for gap analysis, requirement specification, and design validation.

Historical-theoretical integration: The approach demonstrated here—systematically connecting historical computational insights with theoretical developments—can be extended to other areas of AI research where similar theory-practice integration challenges exist.

Interdisciplinary synthesis: Future work can build on the interdisciplinary foundation established here to develop more sophisticated connections between computational BR, cognitive science research, and philosophical epistemology.

9.3.4. Broader Research Program

To generalize beyond AGM-adjacent algorithms, the program should: (i) conduct a comprehensive systematic review that includes non-AGM paradigms (e.g., ranking-based and probabilistic models, dynamic-epistemic and database-update logics, belief merging/fusion, argumentation-based and logic-programming updates, multi-agent and social-choice approaches); (ii) define a cross-paradigm taxonomy of operators, inputs, and outputs with common test oracles; (iii) establish reproducible benchmarks, datasets, and evaluation protocols that test accuracy, stability under iterated revision, preference-elicitation fidelity, and cost-quality trade-offs; (iv) map complexity and approximation frontiers across paradigms; and (v) develop integration criteria that specify when heterogeneous operators can be composed while preserving stated invariants. This extension would permit the proposed synthesis to be validated and refined on the scale of the entire BR area.

The research directions identified here leverage the comprehensive baseline established by this survey while maintaining strategic focus on implementation challenges that require systematic investigation. These directions collectively support the development of BR systems that are both theoretically principled and practically deployable in contemporary AI applications.

This survey has established a comprehensive historical and theoretical foundation that enables systematic research into the implementation of computational BR. The baseline provided here—connecting pre-AGM computational insights with AGM theoretical requirements—supports the next phase of research: developing engineering-focused computational blueprints, implementation analysis frameworks, and empirical validation methodologies. Future work can build systematically on this foundation to create BR systems that are both theoretically principled and practically deployable in contemporary AI applications.