Pavlos Peppas

AIJ Journal 2024 Journal Article

Revision operators with compact representations

• Pavlos Peppas
• Mary-Anne Williams
• Grigoris Antoniou

Despite the great theoretical advancements in the area of Belief Revision, there has been limited success in terms of implementations. One of the hurdles in implementing revision operators is that their specification (let alone their computation), requires substantial resources. On the other hand, implementing a specific revision operator, like Dalal's operator, would be of limited use. In this paper we generalise Dalal's construction, defining a whole family of concrete revision operators, called Parametrised Difference revision operators or PD operators for short. This family is wide enough to cover a wide range of different applications, and at the same time it is easy to represent. In addition to its semantic definition, we characterise the family of PD operators axiomatically (including a characterisation specifically for Dalal's operator), we prove its' compliance with Parikh's relevance-sensitive postulate (P), we study its computational complexity, and discuss its benefits for belief revision implementations.

AAAI Conference 2022 Conference Paper

Using Conditional Independence for Belief Revision

• Matthew James Lynn
• James P. Delgrande
• Pavlos Peppas

We present an approach to incorporating qualitative assertions of conditional irrelevance into belief revision, in order to address the limitations of existing work which considers only unconditional irrelevance. These assertions serve to enforce the requirement of minimal change to existing beliefs, while also suggesting a route to reducing the computational cost of belief revision by excluding irrelevant beliefs from consideration. In our approach, a knowledge engineer specifies a collection of multivalued dependencies that encode domain-dependent assertions of conditional irrelevance in the knowledge base. We consider these as capturing properties of the underlying domain which should be taken into account during belief revision. We introduce two related notions of what it means for a multivalued dependency to be taken into account by a belief revision operator: partial and full compliance. We provide characterisations of partially and fully compliant belief revision operators in terms of semantic conditions on their associated faithful rankings. Using these characterisations, we show that the constraints for partially and fully compliant belief revision operators are compatible with the AGM postulates. Finally, we compare our approach to existing work on unconditional irrelevance in belief revision.

JAIR Journal 2020 Journal Article

Incompatibilities Between Iterated and Relevance-Sensitive Belief Revision

• Theofanis Aravanis
• Pavlos Peppas
• Mary-Anne Williams

The AGM paradigm for belief change, as originally introduced by Alchourron, Gärdenfors and Makinson, lacks any guidelines for the process of iterated revision. One of the most influential work addressing this problem is Darwiche and Pearl's approach (DP approach, for short), which, despite its well-documented shortcomings, remains to this date the most dominant. In this article, we make further observations on the DP approach. In particular, we prove that the DP postulates are, in a strong sense, inconsistent with Parikh's relevance-sensitive axiom (P), extending previous initial conflicts. Immediate consequences of this result are that an entire class of intuitive revision operators, which includes Dalal's operator, violates the DP postulates, as well as that the Independence postulate and Spohn's conditionalization are inconsistent with axiom (P). The whole study, essentially, indicates that two fundamental aspects of the revision process, namely, iteration and relevance, are in deep conflict, and opens the discussion for a potential reconciliation towards a comprehensive formal framework for knowledge dynamics.

ECAI Conference 2020 Conference Paper

Modelling Belief-Revision Functions at Extended Languages

• Theofanis I. Aravanis
• Pavlos Peppas
• Mary-Anne Williams

The policy of rational belief revision is encoded in the so-called AGM revision functions. Such functions are characterized (both axiomatically and constructively) within the well-known AGM paradigm, proposed by Alchourrón, Gärdenfors and Makinson. In this article, we show that — although not in a straightforward way — a sufficient extension of the underlying language allows for the modelling of any AGM revision function (defined at the initial language), by means of a Hamming-based rule for belief revision introduced by Dalal (defined at the extended language). The established results enrich the applicability of Dalal’s proposal, leading to a conceptual and ontological reduction, as well as open new doors for the construction of any type of revision function in a practical context, given the intuitive appeal and simplicity of Dalal’s construction.

JAIR Journal 2019 Journal Article

Full Characterization of Parikh's Relevance-Sensitive Axiom for Belief Revision

• Theofanis Aravanis
• Pavlos Peppas
• Mary-Anne Williams

In this article, the epistemic-entrenchment and partial-meet characterizations of Parikh's relevance-sensitive axiom for belief revision, known as axiom (P), are provided. In short, axiom (P) states that, if a belief set $K$ can be divided into two disjoint compartments, and the new information $\varphi$ relates only to the first compartment, then the revision of $K$ by $\varphi$ should not affect the second compartment. Accordingly, we identify the subclass of epistemic-entrenchment and that of selection-function preorders, inducing AGM revision functions that satisfy axiom (P). Hence, together with the faithful-preorders characterization of (P) that has already been provided, Parikh's axiom is fully characterized in terms of all popular constructive models of Belief Revision. Since the notions of relevance and local change are inherent in almost all intellectual activity, the completion of the constructive view of (P) has a significant impact on many theoretical, as well as applied, domains of Artificial Intelligence.

IJCAI Conference 2019 Conference Paper

Observations on Darwiche and Pearl's Approach for Iterated Belief Revision

• Theofanis Aravanis
• Pavlos Peppas
• Mary-Anne Williams

Notwithstanding the extensive work on iterated belief revision, there is, still, no fully satisfactory solution within the classical AGM paradigm. The seminal work of Darwiche and Pearl (DP approach, for short) remains the most dominant, despite its well-documented shortcomings. In this article, we make further observations on the DP approach. Firstly, we prove that the DP postulates are, in a strong sense, inconsistent with Parikh's relevance-sensitive axiom (P), extending previous initial conflicts. Immediate consequences of this result are that an entire class of intuitive revision operators, which includes Dalal's operator, violates the DP postulates, as well as that the Independence postulate and Spohn's conditionalization are inconsistent with (P). Lastly, we show that the DP postulates allow for more revision polices than the ones that can be captured by identifying belief states with total preorders over possible worlds, a fact implying that a preference ordering (over possible worlds) is an insufficient representation for a belief state.

KR Conference 2018 Conference Paper

Incorporating Relevance in Epistemic States in Belief Revision

• James Delgrande
• Pavlos Peppas

We present an account of relevance in belief revision where, intuitively, one wants to only consider the relevant part of an agent’s epistemic state in a revision. We assume that relevance is a domain-specific notion, and that (ir)relevance assertions are given as part of the agent’s epistemic state. Such assertions apply in a given context, and are of the form “in the case that formula σ holds, the Y part of the agent’s epistemic state is independent of the rest of the epistemic state”, where Y is part of the signature of the language. Two approaches are given, one in which (in semantic terms) conditions are placed on a faithful ranking on possible worlds to enforce the (ir)relevance assertions, and a second in which the possible worlds characterising the agent’s beliefs may be modified in a revision. These approaches are shown to yield the same resulting belief set. Corresponding postulates and a representation result are given. The overall approach is compared to that of Parikh’s for language splitting as well as with multivalued dependencies in relational databases.

KR Conference 2018 Conference Paper

Parametrised Difference Revision

• Pavlos Peppas
• Mary-Anne Williams

Despite the great theoretical advancements in the area of Belief Revision, there has been limited success in terms of implementations. One of the hurdles in implementing revision operators is that their specification (let alone their computation), requires substantial resources. On the other hand, implementing a specific revision operator, like Dalal’s operator, would be of limited use. In a recent paper we generalised Dalal’s construction defining a whole family of concrete revision operators, called Parametrised Difference revision operators or PD operators for short. This family is wide enough to cover a whole range of different applications, and at the same time it is easy to represent. In this paper we characterise axiomatically the family of PD operators, study its computational complexity, and discuss its benefits for belief revision implementations.

IJCAI Conference 2017 Conference Paper

Construction of System of Spheres-based Transitively Relational Partial Meet Multiple Contractions: An Impossibility Result (Extended Abstract)

• Maurício D. L. Reis
• Eduardo Fermé
• Pavlos Peppas

In this paper we show that, contrary to what is the case in what concerns contractions by a single sentence, there is not a system of spheres-based construction of multiple contractions which generates each and every transitively relational partial meet multiple contraction. Furthermore, we propose two system of spheres-based constructions of multiple contractions which generate (only) transitively relational partial meet multiple contractions.

IJCAI Conference 2017 Conference Paper

Epistemic-entrenchment Characterization of Parikh’s Axiom

• Theofanis Aravanis
• Pavlos Peppas
• Mary-Anne Williams

In this article, we provide the epistemic-entrenchment characterization of the weak version of Parikh’s relevance-sensitive axiom for belief revision — known as axiom (P) — for the general case of incomplete theories. Loosely speaking, axiom (P) states that, if a belief set K can be divided into two disjoint compartments, and the new information φ relates only to the first compartment, then the second compartment should not be affected by the revision of K by φ. The above-mentioned characterization, essentially, constitutes additional constraints on epistemic-entrenchment preorders, that induce AGM revision functions, satisfying the weak version of Parikh’s axiom (P).

AIJ Journal 2016 Journal Article

Construction of system of spheres-based transitively relational partial meet multiple contractions: An impossibility result

• Maurício D.L. Reis
• Eduardo Fermé
• Pavlos Peppas

In this paper we show that, contrary to what is the case in what concerns contractions by a single sentence, there is not a system of spheres-based construction of multiple contractions which generates each and every transitively relational partial meet multiple contraction. Before proving the general result, we consider the class of system of spheres-based multiple contractions introduced in [17, 5] and show that this class neither subsumes nor is subsumed by the class of transitively relational partial meet multiple contractions. Furthermore, we propose two system of spheres-based constructions of multiple contractions which generate (only) transitively relational partial meet multiple contractions. Therefore we can conclude that, although it is impossible to obtain a system of spheres-based definition of all the transitively relational partial meet multiple contractions, there are classes of system of spheres-based multiple contractions which are subsumed by the class of transitively relational partial meet multiple contractions.

JELIA Conference 2016 Conference Paper

Kinetic Consistency and Relevance in Belief Revision

• Pavlos Peppas
• Mary-Anne Williams

Abstract A critical aspect of rational belief revision that has been neglected by the classical AGM framework is what we call the principle of kinetic consistency. Loosely speaking, this principle dictates that the revision policies employed by a rational agent at different belief sets, are not independent, but ought to be related in a certain way. We formalise kinetic consistency axiomatically and semantically, and we establish a representation result explicitly connecting the two. We then combine the postulates for kinetic consistency, with Parikh’s postulate for relevant change, and add them to the classical AGM postulates for revision; we call this augmented set the extended AGM postulates. We prove the consistency and demonstrate the scope of the extended AGM postulates by showing that a whole new class of concrete revision operators introduced hererin, called PD operators, satisfies all extended AGM postulates. PD operators are of interest in their own right as they are natural generalisations of Dalal’s revision operator. We conclude the paper with some examples illustrating the strength of the extended AGM postulates, even for iterated revision scenarios.

AIJ Journal 2015 Journal Article

Belief revision in Horn theories

• James P. Delgrande
• Pavlos Peppas

This paper investigates belief revision where the underlying logic is that governing Horn clauses. We show that classical (AGM) belief revision doesn't immediately generalise to the Horn case. In particular, a standard construction based on a total preorder over possible worlds may violate the accepted (AGM) postulates. Conversely, in the obvious extension to the AGM approach, Horn revision functions are not captured by total preorders over possible worlds. We address these difficulties by introducing two modifications to the AGM approach. First, the semantic construction is restricted to “well behaved” orderings, what we call Horn compliant orderings. Second, the revision postulates are augmented by an additional postulate. Both restrictions are redundant in the AGM approach, but not in the Horn case. In a representation result we show that the class of revision functions captured by Horn compliant total preorders over possible worlds is precisely that given by the (extended) set of Horn revision postulates. Further, we show that Horn revision is compatible with work in iterated revision and work concerning relevance in revision. We also consider specific revision operators. Arguably this work is interesting for several reasons. It extends AGM revision to inferentially-weaker Horn theories; hence it sheds light on the theoretical underpinnings of belief change, as well as generalising the AGM paradigm. Thus, this work is relevant to revision in areas that employ Horn clauses, such as deductive databases and logic programming, as well as areas in which inference is weaker than classical logic, such as in description logic.

AIJ Journal 2015 Journal Article

Relevance in belief revision

• Pavlos Peppas
• Mary-Anne Williams
• Samir Chopra
• Norman Foo

Possible-world semantics are provided for Parikh's relevance-sensitive axiom for belief revision, known as axiom (P). Loosely speaking, axiom (P) states that if a belief set K can be divided into two disjoint compartments, and the new information ϕ relates only to the first compartment, then the second compartment should not be effected by the revision of K by ϕ. Using the well-known connection between AGM revision functions and preorders on possible worlds as our starting point, we formulate additional constraints on such preorders that characterise precisely Parikh's axiom (P). Interestingly, the additional constraints essentially generalise a criterion of plausibility between possible worlds that predates axiom (P). A by-product of our study is the identification of two possible readings of Parikh's axiom (P), which we call the strong and the weak versions of the axiom. Regarding specific operators, we show that Dalal's belief revision operator satisfies both weak and strong (P), and it is therefore relevance-sensitive.

KR Conference 2014 Conference Paper

Belief Change and Semiorders

• Pavlos Peppas
• Mary-Anne Williams

comparative plausibility is transitive. To better illustrate our point, let us focus on plausibility rankings 4 on possible worlds, called faithful preorders in (Katsuno and Mendelzon 1991). Suppose that two distinct possible worlds w1, w2 are equally plausible (or implausible) relative to the agents’ current belief state K. We shall denote this by w1 „ w2; formally, w1 „ w2 iff w1 ⊀ w2 and w2 ⊀ w1, where ă denotes the strict part of 4. Suppose now that w2 is equally plausible to a third world w3; i. e. w2 „ w3. In the AGM framework we automatically conclude that w1 „ w3. Economists on the other hand are more cautious. It has long been acknowledged in the area of preference modelling that transitivity is not always a natural property for indifference of preference. The following quote from (Luce 1956) illustrates the problem: A central result in the AGM framework for belief revision is the construction of revision functions in terms of total preorders on possible worlds. These preorders encode comparative plausibility: r ă r1 states that the world r is at least as plausible as r1. Indifference in the plausibility of two worlds, r, r1, denoted r „ r1, is defined as r ⊀ r1 and r1 ⊀ r. Herein we take a closer look at plausibility indifference. We contend that the transitivity of indifference assumed in the AGM framework is not always a desirable property for comparative plausibility. Our argument originates from similar concerns in preference modelling, where a structure weaker than a total preorder, called a semiorder, is widely consider to be a more adequate model of preference. In this paper we essentially re-construct revision functions using semiorders instead of total preorders. We formulate postulates to characterise this new, wider, class of revision functions, and prove that the postulates are sound and complete with respect to the semiorder-based construction. The corresponding class of contraction functions (via the Levi and Harper Identities) is also characterised axiomatically. “Find a subject who prefers a cup of coffee with one cube of sugar to one with five cubes (this should not be difficult). Now prepare 401 cups of coffee with p1 ` i{100q ¨ x grams of sugar, i = 0, 1, ¨ ¨ ¨, 400, where x is the weight of one cube of sugar. It is evident that he will be indifferent between cup i and cup i ` 1, for any i, but by choice he is not indifferent between i “ 0 and i “ 400. ”

JELIA Conference 2014 Conference Paper

Constructive Models for Contraction with Intransitive Plausibility Indifference

• Pavlos Peppas
• Mary-Anne Williams

Abstract Plausibility rankings play a central role in modeling Belief Change, and they take different forms depending on the type of belief change under consideration: preorders on possible worlds, epistemic entrenchments, etc. A common feature of all these structures is that plausibility indifference is assumed to be transitive. In a previous article, [7], we argued that this is not always the case, and we introduced new sets of postulates for revision and contraction (weaker variants of the classical AGM postulates), that are liberated from the indifference transitivity assumption. Herein we complete the task by making the necessary adjustments to the epistemic entrenchment and the partial meet models. In particular we lift the indifference transitivity assumption from both these two models, and we establish representation results connecting the weaker models with the weaker postulates for contraction introduced in [7].

IJCAI Conference 2011 Conference Paper

Revising Horn Theories

• James P. Delgrande
• Pavlos Peppas

This paper investigates belief revision where the underlying logic is that governing Horn clauses. It proves to be the case that classical (AGM) belief revision doesn't immediately generalise to the Horn case. In particular, a standard construction based on a total preorder over possible worlds may violate the accepted (AGM) postulates. Conversely, Horn revision functions in the obvious extension to the AGM approach are not captured by total preorders over possible worlds. We address these difficulties by first restricting the semantic construction to "well behaved" orderings; and second, by augmenting the revision postulates by an additional postulate. This additional postulate is redundant in the AGM approach but not in the Horn case. In a representation result we show that these two approaches coincide. Arguably this work is interesting for several reasons. It extends AGM revision to inferentially-weaker Horn theories; hence it sheds light on the theoretical underpinnings of belief change, as well as generalising the AGM paradigm. Thus, this work is relevant to revision in areas that employ Horn clauses, such as deductive databases and logic programming, as well as areas in which inference is weaker than classical logic, such as in description logic.

ECAI Conference 2008 Conference Paper

Conflicts between Relevance-Sensitive and Iterated Belief Revision

• Pavlos Peppas
• Anastasios Michael Fotinopoulos
• Stella Seremetaki

The original AGM paradigm focuses only on one-step belief revision and leaves open the problem of revising a belief state with whole sequences of evidence. Darwiche and Pearl later addressed this problem by introducing extra (intuitive) postulates as a supplement to the AGM ones. A second shortcoming of the AGM paradigm, seemingly unrelated to iterated revision, is that it is too liberal in its treatment of the notion of relevance. Once again this problem was addressed with the introduction of an extra (also very intuitive) postulate by Parikh. The main result of this paper is that Parikh postulate for relevance-sensitive belief revision is inconsistent with each of the Darwiche and Pearl postulates for iterated belief revision.

KR Conference 2004 Conference Paper

Distance Semantics for Relevance-Sensitive Belief Revision

• Samir Chopra
• Norman Foo
• Pavlos Peppas

Possible-world semantics are provided for Parikh’s relevance-sensitive model for belief revision. Having Grove’s system-of-spheres construction as a base, we consider additional constraints on measuring distance between possible worlds, and we prove that, in the presence of the AGM postulates, these constraints characterize precisely Parikh’s axiom (P). These additional constraints essentially generalize a criterion of similarity that predates axiom (P) and was originally introduced in the context of Reasoning about Action. A by-product of our study is the identification of two possible readings of Parikh’s axiom (P), which we call the strong and the weak versions of the axiom. An interesting feature of the strong version is that, unlike classical AGM belief revision, it makes associations between the revision policies of different theories.

AIJ Journal 2003 Journal Article

Dynamic belief revision operators

• Abhaya C. Nayak
• Maurice Pagnucco
• Pavlos Peppas

The AGM approach to belief change is not geared to provide a decent account of iterated belief change. Darwiche and Pearl have sought to extend the AGM proposal in an interesting way to deal with this problem. We show that the original Darwiche–Pearl approach is, on the one hand excessively strong and, on the other rather limited in scope. The later Darwiche–Pearl approach, we argue, although it addresses the first problem, still remains rather permissive. We address both these issues by (1) assuming a dynamic revision operator that changes to a new revision operator after each instance of belief change, and (2) strengthening the Darwiche–Pearl proposal. Moreover, we provide constructions of this dynamic revision operator via entrenchment kinematics as well as a simple form of lexicographic revision, and prove representation results connecting these accounts.

IJCAI Conference 1999 Conference Paper

Preferential Semantics for Causal Systems

• Pavlos Peppas
• Maurice Pagnucco
• Mikhail Prokopenko
• Norman Y. Foo
• Abhaya Nayak

In the present work we examine the causal theory of actions put forward by McCain and Turner [Mc- Cain and Turner, 1995] for determining ramifications. Our principal aim is to provide a characterisation of this causal theory of actions in terms of a Shoham-like preferential semantics [Shoham, 19881. This would have a twofold advantage: it would place McCain and Turner's theory in perspective, allowing a comparison with other logics of action; and, it would allow us to glean further insights into the nature of causality underlying their work. We begin by showing that our aim is not attainable by a preferential mechanism alone. At this point we do not abandon preferential semantics altogether but augment it in order to arrive at the desired result. We draw f he following moral which is at the heart of our paper: two components — minimal change under a preferential structure and causality — are required to provide a concise solution to the frame and ramification problems.

ECAI Conference 1996 Conference Paper

Learning From Conditionals: Judy Benjamin's Other Problems

• Abhaya C. Nayak
• Maurice Pagnucco
• Norman Y. Foo
• Pavlos Peppas

ECAI Conference 1996 Conference Paper

PMA Epistemic Entrenchments: The General Case

• Pavlos Peppas

ECAI Conference 1996 Conference Paper

Revision vs. Update: Taking a Closer Look

• Pavlos Peppas
• Abhaya C. Nayak
• Maurice Pagnucco
• Norman Y. Foo
• Rex Bing Hung Kwok
• Mikhail Prokopenko

ECAI Conference 1996 Conference Paper

Well Behaved and Multiple Belief Revision

• Pavlos Peppas

ECAI Conference 1992 Conference Paper

On the Use of Epistemic Entrenchment in Reasoning about Action

• Pavlos Peppas
• Wayne Wobcke