A Brief History of Updates of Answer-Set Programs

Abstract

Over the last couple of decades, there has been a considerable effort devoted to the problem of updating logic programs under the stable model semantics (a.k.a. answer-set programs) or, in other words, the problem of characterising the result of bringing up-to-date a logic program when the world it describes changes. Whereas the state-of-the-art approaches are guided by the same basic intuitions and aspirations as belief updates in the context of classical logic, they build upon fundamentally different principles and methods, which have prevented a unifying framework that could embrace both belief and rule updates. In this paper, we will overview some of the main approaches and results related to answer-set programming updates, while pointing out some of the main challenges that research in this topic has faced.

1 Introduction

In this paper, we will take a historical journey through some of the main approaches proposed to deal with the problem of updating logic programs under the stable model semantics.

Knowledge-based systems must keep a representation of the world – often encoded in some logic-based language equipped with a formal semantics and reasoning mechanisms – which is then used for reasoning, for example, to automate decision making. Whereas languages that are based on classical logic – hence monotonic – like description logics, are often used, it has been known for several decades that non-monotonic features are important for common-sense reasoning, for example, to properly deal with default information, preferences, the frame problem, etc. Of the many existing languages for knowledge representation that exhibit non-monotonic features, logic programming under the stable model semantics (a.k.a. answer-set programming, or ASP, for short), introduced by Gelfond and Lifschitz (1988, 1991), is perhaps the biggest success story so far. Established some 30 years ago, ASP is similar in syntax to traditional logic programming, and has a simple and well-understood non-monotonic declarative semantics with known relationships with other logic-based formalisms such as default logic, autoepistemic logic, propositional and predicate logic, etc. (cf. the work of Lifschitz 2008 and references therein). Its rich expressive power allows to compactly represent all NP and coNP problems if non-disjunctive logic programs are used, while disjunctive logic programs capture the complexity class $\Sigma_{2}^{p}$ and $\Pi_{2}^{p}$ (Eiter et al. 1997). Additionally, the existence of efficient implementations such as clasp (Gebser et al. 2011) and dlv (Leone et al. 2006) has made it possible to use ASP in significant applications in diverse areas such as configuration, diagnosis and repair, planning, classification, scheduling, robotics, information integration, legal reasoning, computational biology and bioinformatics, e-medicine, and decision support systems (cf. the surveys by Erdem et al. 2016; Erdem and Patoglu 2018; Falkner et al. 2018, and references therein).

One of the more recent challenges for knowledge engineering and information management is to efficiently and plausibly deal with the incorporation of new, possibly conflicting knowledge and beliefs. There are several domains where this may be required. For example, knowledge-based systems that check for legal and regulatory compliance – such as a public procurement monitoring system – need to keep track of changing laws and regulations, and reason with them. Simply adding the new laws and regulations to the knowledge base containing the older ones would not work, since the newer may be in conflict with the older. It may also not be as simple as deleting the old conflicting ones, since the conflict may be contingent on particular cases. For example, some initial regulation may state that institutions are allowed to enter a contract without a public offer if the contract’s value is below some fixed amount, and a later regulation may state that publicly funded foundations (a special kind of an institution) that have not filed their previous year’s tax return, are not allowed to enter a contract without a public offer. The knowledge-based system would have to automatically deal with these cases, in a way similar to the legal principle of lex posterior used by judges and other legal practitioners, according to which a newer law repeals an earlier conflicting one. Other domains where dealing with dynamic, possibly conflicting, knowledge and beliefs is important include multi-agent systems, where agents need to change their knowledge and beliefs to properly reflect their observations, including incoming messages from other agents, and even new norms, possibly resulting in a change in behaviour; stream reasoning systems that learn/extract knowledge from streams of data, which may be in conflict with previously learnt knowledge; or even transfer learning, where what is learnt by one system in one domain serves as initial knowledge when that system is placed in a different domain, which is then changed as new knowledge is learnt in the new domain. Indeed, any knowledge-based system that maintains a knowledge base about a dynamic world, that is, a world that changes, needs to efficiently and plausibly deal with the incorporation of new, possibly conflicting knowledge.

The problems associated with the evolution of knowledge have been extensively studied over the years, in the context of classical logic. Most of this work was inspired by the seminal contribution of AlchourrÓn, GÄrdenfors and Makinson (AGM) who proposed a set of desirable properties of belief change operators, now called AGM postulates (AlchourrÓn et al. 1985). Subsequently, update and revision have been distinguished as two very much related but ultimately different belief change operations (Keller and Winslett 1985; Winslett 1990; Katsuno and Mendelzon 1991). While revision deals with incorporating new better information about a static world, update takes place when changes occurring in a dynamic world are recorded. Katsuno and Mendelzon formulated a separate set of postulates for update, now known as KM postulates. For a comprehensive treatment of the subject and further references on belief change in classical logic, the reader is referred to the survey paper by FermÉ and Hansson (2011).

Despite the large body of research on belief change in general, and on updates in particular, in the context of classical logic, the use of ASP for knowledge representation in dynamic domains, mainely due to its rule-based syntax and non-monotonic semantics, has called for a specific line of research on how to update an answer-set program, which constitutes the central topic of this paper.

To illustrate the problem at hand, consider an agent with knowledge represented by the following program $\mathcal{P}$ (where $\mathop{\sim\!}$ denotes default negation):

(1) \begin{align} \mathsf{goHome} &\leftarrow \mathop{\sim\!} \mathsf{money}. \end{align}

(2) \begin{align} \mathsf{goRestaurant} &\leftarrow \mathsf{money}. \end{align}

(3) \begin{align} \mathsf{money} &. \end{align}

The only stable model of $\mathcal{P}$ is $I = {\mathsf{money}, \mathsf{goRestaurant}}$ , capturing that the agent has money by rule (3), so according to rule (2) it plans to go to a restaurant. Suppose that the beliefs of the agent are to be updated by the program $\mathcal{U}$ with the following two rules:

\begin{align*} \mathop{\sim\!} \mathsf{money} &\leftarrow \mathsf{robbed}. & \mathsf{robbed} &. \end{align*}

What should the agent’s beliefs be after the update of $\mathcal{P}$ by $\mathcal{U}$ ?

The central research question is then how to semantically characterise pairs or, more generally, sequences of ASP programs (a.k.a. dynamic logic programs) where each component represents an update of the preceding ones, and, if possible, produce an ASP program that encodes the result of the updates.

Going back to the previous example, when we update $\mathcal{P}$ by $\mathcal{U}$ , the intuitively correct result is that $\mathsf{robbed}$ is true and $\mathsf{money}$ is false, because of the rules in the update $\mathcal{U}$ , and that $\mathsf{goRestaurant}$ should now be false because its only justification, $\mathsf{money}$ , is no longer true. Furthermore, we would expect that $\mathsf{goHome}$ be now true, that is, the rule (1) should be triggered because $\mathsf{money}$ became false.

Over the years, many have tackled this issue, which has proved far more difficult and elusive than perhaps originally thought. Earlier approaches (Marek and Truszczynski 1994; Marek and Truszczynski 1998; Przymusinski and Turner 1995; Przymusinski and Turner 1997; Alferes and Pereira 1996) were based on literal inertia, following some of the basic principles inherited from the possible models approach by Winslett (1988) – an approach to updates in propositional logic based on minimising the set of atoms whose truth value changes when an interpretation is updated that satisfies the KM postulates. However, they were soon found to be inadequate, or at least not sufficiently expressive to capture the result of updating an answer-set program by means of another answer-set program (Leite and Pereira 1998).

Since then, many different approaches were put forward. Though the state-of-the-art approaches are guided by the same basic intuitions and aspirations as belief change in classical logic, they build upon fundamentally different principles and methods. While many are based on the so-called causal rejection principle (Leite and Pereira 1998; Alferes et al. 2000; Eiter et al. 2002; Alferes et al. 2005; Osorio and Cuevas 2007), others employ syntactic transformations and other methods, such as abduction (Sakama and Inoue 2003), forgetting (Zhang and Foo 2005), prioritisation (Zhang 2006), preferences (Delgrande et al. 2007), or dependencies on defeasible assumptions (ŠefrÁnek 2011; KrÜmpelmann 2012).

One interesting feature about these developments is that the resulting operators often bear characteristics of revision rather than update, as viewed from the perspective of belief change in classical logic, often blurring the frontier between these two types of operations. We will review not only those approaches that aim to deal with updates, but also some operators that are closer to revision, but whose authors position their contribution as having similar goals, namely by comparing them with the operators specifically defined for updates. However, while evaluating the reviewed approaches, we will guide ourselves by the basic idea of what an update is, that is, an operation that deals with incorporating new information about a dynamic world, as opposed to a revision which deals with incorporating better knowledge about a static world. In our opinion, underlying this definition of update is the assumption that the information acquired at each point in time is correct at that moment, as opposed to the assumption adopted in revision, whereby the information acquired at each time point is not necessarily correct, just better than what we had before. One relevant consequence is that an empty or tautological update (which we take to represent that nothing changed) should have no effect, because our beliefs about the world were correct and nothing changed, while it is acceptable that a revision by an empty or tautological update may lead to some change, for example restoring consistency, because we take it that in revision, our beliefs about the world were not necessarily correct.

More recently, both the AGM and KM postulates were revisited, taking into account a monotonic characterisation of ASP – $\textsf{HT}$ models (Pearce 1997; Lifschitz et al. 2001) – as the basis for new classes of revision and update operators (Delgrande et al. 2013; Slota and Leite 2014). Despite their own merits and shortcomings, these approaches based on $\textsf{HT}$ models have opened up new avenues to investigate other belief change operations in ASP, such as forgetting (Wang et al. 2012; Wang et al. 2013; Wang et al. 2014; Delgrande and Wang 2015) (see the paper by GonÇalves et al. 2016 for a survey on forgetting in ASP, or another survey in this volume), and new insights into unifying classical logic and ASP-based updates (Slota and Leite 2012a; Slota and Leite 2012b; Slota et al. 2015).

In this paper, we will briefly revisit the main landmarks in the history of updating answer-set programs. We will follow a chronological approach that divides it into three main eras, although not without intersection – model updates, syntax-based updates, and semantics-based updates – that correspond to the three main sections of this paper. These sections are preceded by a brief section (pre-history) on belief change in classical logic, and followed by an outlook where some current and future issues are discussed. Before we begin the journey, we provide a brief background section with the usual preliminaries on propositional logic, answer-set programming, and other basic concepts used throughout the paper.

Given the nature of this paper, we will often exercise some restraint on technical content in favour of better conveying the main intuitions and concepts underlying each approach and focusing on providing simple examples that bring forward their main differentiating features. Despite this compromise, this paper still conveys a novel and, we hope, significant scientific contribution, inasmuch as it is, to the best of our knowledge, the first encompassing and critical survey of the field, not only comparing different approaches but sometimes even providing intuitions and illustrative examples that were absent from the original papers.

2 Background

Propositional Logic. We consider a propositional language over a finite set of propositional variables $\mathcal{L}$ and the usual set of propositional connectives to form propositional formulae. A (two-valued) interpretation is any $I \subseteq\mathcal{L}$ . The set of all (two-valued) interpretations is denoted by $\mathscr{I}$ . Each atom $\mathsf{p}$ is assigned one of two truth values in I: $I(\mathsf{p}) = \mathsf{T}$ if $\mathsf{p} \in I$ and $I(\mathsf{p}) = \mathsf{F}$ otherwise. This assignment is generalised in the standard way to all propositional formulae. The set of all models of a formula $\phi$ is denoted by $[\kern-.3ex[{\phi}]\kern-.3ex]$ . We say $\phi$ is complete if $[\kern-.3ex[{\phi}]\kern-.3ex]$ is a singleton set. For two formulae $\phi, \psi$ we say that $\phi$ entails $\psi$ , denoted by $\phi\mathrel\mid= \psi$ , if $[\kern-.3ex[{\phi}]\kern-.3ex] \subseteq [\kern-.3ex[{\psi}]\kern-.3ex]$ , and that $\phi$ is equivalent to $\psi$ , denoted by $\phi \equiv \psi$ , if $[\kern-.3ex[{\phi}]\kern-.3ex] =[\kern-.3ex[{\psi}]\kern-.3ex]$ .

Answer-Set Programs. Answer-set programming (a.k.a. logic programming under the stable model semantics) has its roots in classical logic. However, answer-set programs diverge from classical semantics by adopting the closed world assumption and allowing for non-monotonic inferences. Here, we introduce the class of answer-set programs that allow for both disjunction and default negation in heads of rules.

The basic syntactic building blocks of rules are also propositional atoms from $\mathcal{L}$ . A negative literal is an atom preceded by $\mathop{\sim\!}{}$ denoting default negation. A literal is either an atom or a negative literal. Throughout this paper, we adopt a convention that double default negation is absorbed, so that $\mathop{\sim\!} \mathop{\sim\!}\mathsf{p}$ denotes the atom $\mathsf{p}$ . Given a set S of literals, we introduce the following notation: $S^+ = {\mathsf{p} \in \mathcal{L} | \mathsf{p} \in S}$ , $S^- = {\mathsf{p} \in \mathcal{L} | \mathop{\sim\!} \mathsf{p} \in S}$ , and $\mathop{\sim\!} S ={\mathop{\sim\!} L | L \in S}$ .

A rule is a pair of sets of literals $\pi = \langle H(\pi), B(\pi) \rangle$ . We say that $H(\pi)$ is the head of $\pi$ and $B(\pi)$ is the body of $\pi$ . Usually, for convenience, we write $\pi$ as

\begin{equation*} H(\pi)^+; \mathop{\sim\!} H(\pi)^- \leftarrow B(\pi)^+, \mathop{\sim\!} B(\pi)^-.\end{equation*}

A rule is called non-disjunctive if its head contains at most one literal; a fact if its head contains exactly one literal and its body is empty; an integrity constraint if its head is empty. A program is any set of rules. A program is non-disjunctive if all its rules are.

We define the class of acyclic programs using level mappings (Apt and Bezem 1991). A level mapping is a function $\ell$ that assigns a natural number to every atom, and is extended to default literals and sets of literals by putting $\ell(\mathop{\sim\!} L) = \ell(L)$ and $\ell(S) = \max {\ell(L) | L \in S}$ . We say that a program $\mathcal{P}$ is acyclic if there exists a level mapping $\ell$ such that for every rule $\pi \in \mathcal{P}$ it holds that $H(\pi)\neq\emptyset$ and $\ell(l_H) > \ell(l_B)$ for every $l_H \in H(\pi)$ and every $l_B \in B(\pi)$ .

In the following, we define the answer-sets (a.k.a. stable models) of a program (Gelfond and Lifschitz 1988; Gelfond and Lifschitz 1991) as well as two monotonic model-theoretic characterisations of rules and programs. One is that of classical models, where a rule is simply treated as a classical implication. The other, $\textsf{HT}$ models, is based on the logic of here-and-there (Heyting 1930; Pearce 1997) and is expressive enough to capture both classical models and answer sets.

Satisfaction of programs is obtained by treating rules as classical implications. Table 1 defines satisfaction of literals l and $\mathop{\sim\!} l$ , a set of literals S, a rule $\pi$ and a program $\mathcal{P}$ in an interpretation $J \subseteq \mathcal{L}$ . We say that J is a $\textsf{C}$ -model (classical model) of a rule $\pi$ if $J \mathrel\mid= \pi$ , and a $\textsf{C}$ -model of a program $\mathcal{P}$ if $J \mathrel\mid= \mathcal{P}$ . The set of all $\textsf{C}$ -models of a rule $\pi$ is denoted by $[\kern-.3ex[ {\pi} ]\kern-.3ex]_{\mathsf{C}}$ and for any program $\mathcal{P}$ , $[\kern-.3ex[ {\mathcal{P}} ]\kern-.3ex]_{\mathsf{C}} = \bigcap_{\pi \in \mathcal{P}} [\kern-.3ex[ {\pi} ]\kern-.3ex]_{\mathsf{C}}$ . A program $\mathcal{P}$ is consistent if $[\kern-.3ex[ {\mathcal{P}} ]\kern-.3ex]_{\mathsf{C}} \neq \emptyset$ , and inconsistent otherwise.

Table 1. Satisfaction of literals, rules and programs

The stable and $\textsf{HT}$ models are defined in terms of reducts. Given a program $\mathcal{P}$ and an interpretation J, the reduct of $\mathcal{P}$ w.r.t. J is defined as

\begin{equation*}\mathcal{P}^J = {\langle S^+[H(\pi)], S^+[B(\pi)] \rangle | \pi \in \mathcal{P} \land J \not\mathrel\mid= \langle \mathop{\sim\!} S^-[H(\pi)], \mathop{\sim\!} S^-[B(\pi)] \rangle}.\end{equation*}

An interpretation J is a stable model of a program $\mathcal{P}$ if J is a subset-minimal $\textsf{C}$ -model of $\mathcal{P}^J$ . The set of all stable models of $\mathcal{P}$ is denoted by $[\kern-.3ex[{{\mathcal{P}}}]\kern-.3ex]_{\mathsf{SM}}$ . A program $\mathcal{P}$ is coherent if $[\kern-.3ex[{{\mathcal{P}}}]\kern-.3ex]_{\mathsf{SM}} \neq \emptyset$ , and incoherent otherwise.

$\textsf{HT}$ models are semantic structures that can be seen as three-valued interpretations. In particular, we call a pair of interpretations $X =\langle I, J \rangle$ such that $I \subseteq J$ a three-valued interpretation. Each atom $\mathsf{p}$ is assigned one of three truth values in X: $X(\mathsf{p}) = \mathsf{T}$ if $\mathsf{p} \in I$ ; $X(\mathsf{p}) = \mathsf{U}$ if $\mathsf{p}\in J \backslash I$ ; $X(\mathsf{p}) = \mathsf{F}$ if $\mathsf{p} \in \mathcal{L} \backslash J$ . The set of all three-valued interpretations is denoted by $\mathscr{X}$ . A three-valued interpretation $\langle {I, J} \rangle$ is an $\textsf{HT}$ model of a rule $\pi$ if $J\mathrel\mid=\pi$ and $I\mathrel\mid=\pi^J$ . The set of all $\textsf{HT}$ models of a rule $\pi$ is denoted by $[\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{HT}}$ and for any program $\mathcal{P}$ , $[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}} = \bigcap_{\pi \in\mathcal{P}} [\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{HT}}$ . Note that J is a stable model of $\mathcal{P}$ if and only if $\langle J, J \rangle \in [\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ and for all $I \subsetneq J$ , $\langle I, J \rangle \notin [\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ . Also, $J \in [\kern-.3ex[ {\mathcal{P}} ]\kern-.3ex]_{\mathsf{C}}$ if and only if $\langle J, J \rangle \in [\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ . We write $({I, J}) \mathrel\mid= \mathcal{P}$ if $({I, J}) \in [\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ . We say that $\mathcal{P}$ is strongly equivalent to $\mathcal{Q}$ , denoted by $\mathcal{P} \equiv_{\mathsf{HT}} \mathcal{Q}$ , if $[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}} = [\kern-.3ex[{\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}}$ , and that $\mathcal{P}$ strongly entails $\mathcal{Q}$ , denoted by $\mathcal{P} \mathrel\mid=_{\mathsf{HT}} \mathcal{Q}$ , if $[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}} \subseteq [\kern-.3ex[{\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}}$ . A rule $\pi$ is tautological if $[\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{HT}}= \mathscr{X}$ . It follows from the results of Inoue and Sakama (2004) and Cabalar et al. (2007) that a rule $\pi$ is tautological if $B(\pi)\cap H(\pi)\neq\emptyset$ or $B(\pi)^+\cap B(\pi)^-\neq\emptyset$ .

The class of programs defined above can be extended to allow for a second form of negation, dubbed strong negation. In a nutshell, $\mathcal{L}$ is extended to also include, for each of its original atoms $\mathsf{p}$ , its (strong) negation $\lnot\mathsf{p}$ . Elements of this extended $\mathcal{L}$ are dubbed objective literals and we use the following notation to refer to complementary objective literals: $\overline{\mathsf{p}}= \lnot \mathsf{p}$ and $\overline{\lnot \mathsf{p}} = \mathsf{p}$ for any atom $\mathsf{p}$ . Each atom $\mathsf{p}$ is interpreted separately of (though still consistently with) its strong negation $\lnot \mathsf{p}$ . Each interpretation naturally corresponds to a consistent subset of the extended set $\mathcal{L}$ . More formally, an (extended) interpretation is a subset of $\mathcal{L}$ that does not contain both l and $\overline{l}$ for any objective literal l. Note that this is in contrast with the definition of answer-set by Gelfond and Lifschitz (1991), which allows for certain programs to have their semantics be characterised by the so-called contradictory answer-set $\mathcal{L}$ .

To simplify notation, first-order atoms with variables are often used in program rules. Such rules should be seen as a shortcut corresponding to the set of rules obtained by replacing the variables with constants to form atoms in $\mathcal{L}$ , in all possible ways.

Order Theory. Given a set $\mathcal{S}$ , a preorder over $\mathcal{S}$ is a reflexive and transitive binary relation over $\mathcal{S}$ ; a strict preorder over $\mathcal{S}$ is an irreflexive and transitive binary relation over $\mathcal{S}$ ; a partial order over $\mathcal{S}$ is a preorder over $\mathcal{S}$ that is antisymmetric. Given a preorder $\leq$ over $\mathcal{S}$ , we denote by $<$ the strict preorder induced by $\leq$ , that is $s < t$ if and only if $s \leq t$ and not $t \leq s$ . For any subset $\mathcal{T}$ of $\mathcal{S}$ , the set of minimal elements of $\mathcal{T}$ w.r.t. $\leq$ is $ \min(\mathcal{T}, \leq) = { s \in \mathcal{T} | \lnot \exists t \in \mathcal{T} : t < s }$ . A preorder assignment over $\mathcal{S}$ is any function $\omega$ that assigns a preorder $\leq^{s}_{\omega}$ over $\mathcal{S}$ to each $s \in \mathcal{S}$ . A partial order assignment over $\mathcal{S}$ is any preorder assignment $\omega$ over $\mathcal{S}$ such that $\leq^{s}_{\omega}$ is a partial order over $\mathcal{S}$ for every $s \in \mathcal{S}$ . A total order assignment over $\mathcal{S}$ is any preorder assignment $\omega$ over $\mathcal{S}$ such that $\leq^{s}_{\omega}$ is a total order over $\mathcal{S}$ for every $s \in \mathcal{S}$ .

3 Pre-history – belief change in classical logic

An update is typically described as an operation that brings a knowledge base up to date when the world described by it changes, whereas a revision is typically described as an operation that deals with incorporating new better knowledge about a world that did not change (Keller and Winslett 1985; Winslett 1990; Katsuno and Mendelzon 1991). From a generic perspective, both forms of belief change operators – update and revision – were studied within the context of propositional logic.

Propositional belief change operators, either for update ( $\mathbin{\diamond}$ ) or for revision ( $\mathbin{\circ}$ ), take two propositional formulas, representing the original knowledge base and its update, as arguments, and return a formula representing the updated knowledge base. Any such operator $\mathbin{\ast}\in\{\mathbin{\diamond},\mathbin{\circ}\}$ is inductively generalised to finite sequences $\langle \phi_i \rangle_{i < n}$ of propositional formulas as follows: $*\langle {\phi _0}\rangle = {\phi _0}$ and $*{\langle {\phi _i}\rangle _{i < n + 1}} = (*{\langle {\phi _i}\rangle _{i < n}})*{\phi _n},n > 0$ . To further specify the desired properties of belief change operators, Katsuno and Mendelzon (1989, 1991) proposed two sets of postulates – one for revision and one for update. Following the original order of presentation, we will first briefly review the postulates for revision, and then those for update. Even though these postulate have been mostly absent from the literature in updates of answer-set programs, more so during the era of syntax-based updates, they took a more prominent role during the era of semantic-based updates, and will be revisited in Section 6.

We start with the following six postulates for a belief revision operator $\mathbin{\circ}$ and formulas $\phi$ , $\psi$ , $\mu$ , $\nu$ , proposed by Katsuno and Mendelzon (1989), which correspond to the AGM postulates for the case of propositional logic.

1. ( $\mathsf{BR1}$ ) $\phi \mathbin{\circ} \mu \mathrel\mid= \mu$ .

2. ( $\mathsf{BR2}$ ) If $[\kern-.3ex[{{\phi\land\mu}}]\kern-.3ex] \neq \emptyset$ , then $\phi \mathbin{\circ} \mu \equiv \phi \land \mu$ .

3. ( $\mathsf{BR3}$ ) If $[\kern-.3ex[{\mu}]\kern-.3ex] \neq \emptyset$ , then $[\kern-.3ex[{{\phi \mathbin{\circ} \mu}}]\kern-.3ex] \neq \emptyset$ .

4. ( $\mathsf{BR4}$ ) If $\phi \equiv \psi$ and $\mu \equiv \nu$ , then $\phi \mathbin{\circ} \mu \equiv \psi \mathbin{\circ} \nu$ .

5. ( $\mathsf{BR5}$ ) $(\phi \mathbin{\circ} \mu) \land \nu \mathrel\mid= \phi \mathbin{\circ} (\mu \land \nu)$ .

6. ( $\mathsf{BR6}$ ) If $[\kern-.3ex[{{(\phi \mathbin{\circ} \mu) \land \nu}}]\kern-.3ex] \neq \emptyset$ , then $\phi \mathbin{\circ} (\mu \land \nu) \mathrel\mid= (\phi \mathbin{\circ} \mu) \land \nu$ .

Most of these postulates can be given a simple intuitive reading. For instance, $\mathsf{BR1}$ requires that information from the revision be retained in the revised belief base. This is also frequently referred to as the principle of primacy of new information (Dalal 1988). Postulate $\mathsf{BR2}$ requires that whenever the original formula and the revision are jointly consistent, the result corresponds to their conjunction. Postulate $\mathsf{BR3}$ requires that whenever the formula used for revision is satisfiable, then so should be the result of the revision. Postulate $\mathsf{BR4}$ encodes independence of syntax. Postulates $\mathsf{BR5}$ and $\mathsf{BR6}$ require that revision should be accomplished with minimal change.

The main idea behind these postulates is formally captured by the notion of a belief revision operator characterised by an order assignment.

Definition 1 (Belief Revision Operator Characterised by an Order Assignment) Let $\mathbin{\circ}$ be a belief revision operator and $\omega$ a preorder assignment over the set of all formulas. We say that $\mathbin{\circ}$ is characterised by $\omega$ if for all formulae $\phi$ , $\mu$ ,

\begin{equation*} [\kern-.3ex[{{\phi \mathbin{\circ} \mu}}]\kern-.3ex] = \min \left({ [\kern-.3ex[{\mu}]\kern-.3ex], \leq^{\phi}_{\omega} }\right) . \end{equation*}

A set of natural conditions on the assigned orders is captured by the following notion of a faithful order assignment.

Definition 2 (Faithful Preorder Assignment Over Formulas) A preorder assignment $\omega$ over the set of all formulas is faithful if the following three conditions hold:

• $\text{If }I,J\in[\kern-.3ex[{\phi}]\kern-.3ex]\text{, then }I\not<^{\phi}_{\omega}J$ .

• $\text{If }I\in[\kern-.3ex[{\phi}]\kern-.3ex]\text{ and }J\not\in[\kern-.3ex[{\phi}]\kern-.3ex]\text{, then }I<^{\phi}_{\omega}J$ .

• $\text{If }[\kern-.3ex[{\phi}]\kern-.3ex]=[\kern-.3ex[{\psi}]\kern-.3ex]\text{, then }<^{\phi}_{\omega}=<^{\psi}_{\omega}$ .

The representation theorem of Katsuno and Mendelzon (1989) states that operators characterised by faithful total preorder assignments over the set of all formulas are exactly those that satisfy the KM revision postulates.

Theorem 3 (Katsuno and Mendelzon 1989) Let $\mathbin{\circ}$ be a belief revision operator. Then the following conditions are equivalent:

• The operator $\mathbin{\circ}$ satisfies conditions $\mathsf{BR1}$ – $\mathsf{BR6}$ .

• The operator $\mathbin{\circ}$ is characterised by a faithful total preorder assignment over the set of all formulas.

Whereas according to Katsuno and Mendelzon (1991), revision is used when we are obtaining new information about a static world, updates consists of bringing a knowledge base up to date when the world described by it changes. To characterise updates, Katsuno and Mendelzon (1991) proposed the following eight postulates for a belief update operator $\mathbin{\diamond}$ and formulas $\phi$ , $\psi$ , $\mu$ , $\nu$ :

1. ( $\mathsf{BU1}$ ) $\phi \mathbin{\diamond} \mu \mathrel\mid= \mu$ .

2. ( $\mathsf{BU2}$ ) If $\phi \mathrel\mid= \mu$ , then $\phi \mathbin{\diamond} \mu \equiv \phi$ .

3. ( $\mathsf{BU3}$ ) If $[\kern-.3ex[{\phi}]\kern-.3ex] \neq \emptyset$ and $[\kern-.3ex[{\mu}]\kern-.3ex] \neq \emptyset$ , then $[\kern-.3ex[{{\phi \mathbin{\diamond} \mu}}]\kern-.3ex] \neq \emptyset$ .

4. ( $\mathsf{BU4}$ ) If $\phi \equiv \psi$ and $\mu \equiv \nu$ , then $\phi \mathbin{\diamond} \mu \equiv \psi \mathbin{\diamond} \nu$ .

5. ( $\mathsf{BU5}$ ) $(\phi \mathbin{\diamond} \mu) \land \nu \mathrel\mid= \phi \mathbin{\diamond} (\mu \land \nu)$ .

6. ( $\mathsf{BU6}$ ) If $\phi \mathbin{\diamond} \mu \mathrel\mid= \nu$ and $\phi \mathbin{\diamond} \nu \mathrel\mid= \mu$ , then $\phi \mathbin{\diamond} \mu \equiv \phi \mathbin{\diamond} \nu$ .

7. ( $\mathsf{BU7}$ ) If $\phi$ is complete, then $(\phi \mathbin{\diamond} \mu) \land (\phi \mathbin{\diamond} \nu) \mathrel\mid= \phi \mathbin{\diamond} (\mu \lor \nu)$ .

8. ( $\mathsf{BU8}$ ) $(\phi \lor \psi) \mathbin{\diamond} \mu \equiv (\phi \mathbin{\diamond} \mu) \lor (\psi \mathbin{\diamond} \mu)$ .

Postulates $\mathsf{BU1}$ – $\mathsf{BU5}$ correspond to postulates $\mathsf{BR1}$ – $\mathsf{BR5}$ . However, when $\phi$ is consistent, then $\mathsf{BU2}$ is weaker than $\mathsf{BR2}$ . The property expressed by $\mathsf{BU8}$ is at the heart of belief updates: Alternative models of the original belief base $\phi$ or $\psi$ are treated as possible real states of the modelled world. Each of these models is updated independently of the others to make it consistent with the update $\mu$ , obtaining a new set of interpretations – the models of the updated belief base. Based on this view of updates, Katsuno and Mendelzon (1991) proved an important representation theorem that makes it possible to constructively characterize and evaluate every operator $\mathbin{\diamond}$ that satisfies postulates $\mathsf{BU1}$ – $\mathsf{BU8}$ . The main idea, based on postulate $\mathsf{BU8}$ , is formally captured by the notion of a belief update operator characterized by an order assignment.

Definition 4 (Belief Update Operator Characterised by an Order Assignment) Let $\mathbin{\diamond}$ be a belief update operator and $\omega$ a preorder assignment over $\mathscr{I}$ . We say that $\mathbin{\diamond}$ is characterised by $\omega$ if for all formulae $\phi$ , $\mu$ ,

\begin{equation*} [\kern-.3ex[{{\phi \mathbin{\diamond} \mu}}]\kern-.3ex] = \bigcup_{I \in [\kern-.25ex[{{\phi}}]\kern-.25ex]} \min \left({ [\kern-.3ex[{\mu}]\kern-.3ex], \leq^{I}_{\omega} }\right) . \end{equation*}

A natural condition on the assigned orders is that every interpretation be the closest to itself, captured by the following notion of a faithful order assignment.

Definition 5 (Faithful Order Assignment over Interpretations) A preorder assignment $\omega$ over $\mathscr{I}$ is faithful if for every interpretation I the following condition is satisfied:

\begin{equation*} \text{For every } J \in \mathscr{I} \text{ with } J \neq I \text{ it holds that } I <^{I}_{\omega} J . \end{equation*}

The representation theorem of Katsuno and Mendelzon (1989) states that operators characterised by faithful order assignments over $\mathscr{I}$ are exactly those that satisfy the KM update postulates.

Theorem 6 (Katsuno and Mendelzon 1991) Let $\mathbin{\diamond}$ be a belief update operator. Then the following conditions are equivalent:

• The operator $\mathbin{\diamond}$ satisfies conditions $\mathsf{BU1}$ – $\mathsf{BU8}$ .

• The operator $\mathbin{\diamond}$ is characterised by a faithful preorder assignment over $\mathscr{I}$ .

• The operator $\mathbin{\diamond}$ is characterised by a faithful partial order assignment over $\mathscr{I}$ .

Katsuno and Mendelzon’s result provides a framework for belief update operators, each specified on the semantic level by strict preorders assigned to each propositional interpretation. The most influential instance of this framework is the possible models approach by Winslett (1988), based on minimising the set of atoms whose truth value changes when an interpretation is updated. Formally, for all interpretations I, J and K, the strict preorder $<^{I}_{\mathsf{W}}$ is defined as follows: $J <^{I}_{\mathsf{W}} K$ if and only if $(J \div I) \subsetneq (K\div I)$ , where $\div$ denotes set-theoretic symmetric difference. The operator $\mathbin{\mathbin{\diamond}_{\mathsf{W}}}$ by Winslett, unique up to equivalence of its inputs and output, thus satisfies the following equation:

\begin{equation*} [\kern-.3ex[{{\phi \mathbin{\mathbin{\diamond}_{\mathsf{W}}} \mu}}]\kern-.3ex] =\bigcup_{I \in [\kern-.25ex[{{\phi}}]\kern-.25ex]} { J \in [\kern-.3ex[{\mu}]\kern-.3ex] | \lnot \exists K \in [\kern-.3ex[{\mu}]\kern-.3ex] : (K \div I) \subsetneq (J \div I) }.\end{equation*}

Note that it follows from Theorem 6 that $\mathbin{\mathbin{\diamond}_{\mathsf{W}}}$ satisfies postulates $\mathsf{BU1}$ – $\mathsf{BU8}$ .

4 The first era – model updates

The first authors to address the issue of updates and logic programs using the stable model semantics were Marek and Truszczynski (1994, 1998), although not as a means to update logic program. Instead, they used a rule-based language, and a semantics similar to the stable models semantics, to specify the updates of a database.

The underlying idea was that the rules would specify constraints that had to be satisfied by a database. Then, given an initial database and a set of rules, Marek and Truszczynski (1994, 1998) defined a semantics that assigns a set of databases that are the justified result of the update.

In a nutshell, a database $DB^{\prime}$ is considered to be a justified update of a database DB by a program U if $DB^{\prime}$ , viewed as an interpretation, is a model of U, and no other database $DB^{\prime\prime}$ , that is also a model of U, is closer to DB than $DB^{\prime}$ .

Procedurally, this notion of justified update corresponds to following the common-sense law of inertia, whereby only those elements that need to be changed due to the update specification are actually changed, the remaining staying the same, in line with the ideas proposed by Winslett (1988).

Representing databases as interpretations, update programs as logic programs, and with $\div$ denoting set-theoretic symmetric difference, as before, the set of interpretations resulting from updating I by $\mathcal{U}$ is given by

\begin{equation*} { J \in [\kern-.3ex[ {\mathcal{U}} ]\kern-.3ex]_{\mathsf{C}} | \lnot\exists K \in [\kern-.3ex[ {\mathcal{U}} ]\kern-.3ex]_{\mathsf{C}} : (K \div I) \subsetneq (J \div I) }. \end{equation*}

Example 7 Consider an initial interpretation $I={\mathsf{cold},\mathsf{sun}}$ and suppose we want to update it according to the following program $\mathcal{U}$ :

\begin{align*} \mathsf{rain}.& &\mathsf{clouds} \leftarrow \mathsf{rain}.& &\mathop{\sim\!}\mathsf{sun} \leftarrow \mathsf{clouds}.\end{align*}

The only justified update is the interpretation $J={\mathsf{cold}, \mathsf{clouds}, \mathsf{rain}}$ . Declaratively, $\mathcal{P}$ has two models ${\mathsf{cold}, \mathsf{clouds}, \mathsf{rain}}$ and ${\mathsf{clouds}, \mathsf{rain}}$ , where the former is obviously closer to I than the latter. Procedurally, $\mathsf{rain}$ is true in J because of the fact in $\mathcal{U}$ , $\mathsf{clouds}$ is true in J because of the second rule in $\mathcal{U}$ , together with the fact that $\mathsf{rain}$ is now true, $\mathsf{sun}$ is false because of the third rule in the program, while $\mathsf{cold}$ is true in J, by inertia, because it was true in I and there is nothing in $\mathcal{U}$ forcing it to become false.

Subsequently, Przymusinski and Turner (1995, 1997) showed how the framework proposed by Marek and Truszczynski (1994, 1998) could be captured by logic programming under the stable models semantics, by encoding the initial database as a set of facts, the rules proposed by Marek and Truszczynski (1994, 1998) as rules of logic programming, and by adding additional rules encoding the common-sense law of inertia, so that the stable models of the resulting logic program would correspond to the justified updates of the initial database.

It was Alferes and Pereira (1996) who first proposed to use a logic program to update another logic program, under the stable model semantics. Following the possible models approach proposed by Winslett (1988), a knowledge base $DB^{\prime}$ is considered to be the update of a knowledge base DB by U if each model of $DB^{\prime}$ is an update of a model of DB by U.

According to this approach, dubbed the model update approach, the problem of finding an update of a logic program $\mathcal{P}$ is reduced to the problem of individually finding updates of each of its stable models I. Each stable model would be updated following the ideas proposed by Marek and Truszczynski (1994, 1998), that is, following the common-sense law of inertia, or minimal change.

Just like Przymusinski and Turner (1995, 1997), Alferes and Pereira (1996) proposed an encoding of the problem of updating a program $\mathcal{P}$ by a program $\mathcal{U}$ into logic programming, producing another logic program, written in an extended language, whose stable models correspond to the updates of each of the stable models of $\mathcal{P}$ by $\mathcal{U}$ .

According to Alferes and Pereira (1996), the update of a program $\mathcal{P}$ by a program $\mathcal{U}$ is characterized by the following set of interpretations:

\begin{equation*} \bigcup_{I \in [\kern-.3ex[{{\mathcal{P}}}]\kern-.3ex]_{\mathsf{SM}}} { J \in [\kern-.3ex[ {\mathcal{U}} ]\kern-.3ex]_{\mathsf{C}} | \lnot\exists K \in [\kern-.3ex[ {\mathcal{U}} ]\kern-.3ex]_{\mathsf{C}} : (K \div I) \subsetneq (J \div I) }. \end{equation*}

As it turns out, when we take a closer look at this semantics, we soon realise that things do not behave exactly as one might expect.

Example 8 Consider the same example from the introduction, where an agent had its beliefs represented by the program $\mathcal{P}$ :

\begin{align*} \mathsf{goHome} \leftarrow \mathop{\sim\!} \mathsf{money}.& &\mathsf{goRestaurant} \leftarrow \mathsf{money}.& &\mathsf{money}. \end{align*}

which was then the subject of an update by $\mathcal{U}$ with the following two rules:

\begin{align*} \mathop{\sim\!} \mathsf{money} &\leftarrow \mathsf{robbed}. & \mathsf{robbed} &. \end{align*}

The only stable model of $\mathcal{P}$ is $I = {\mathsf{money}, \mathsf{goRestaurant}}$ . Program $\mathcal{U}$ has the following four models: $K_1={\mathsf{robbed}}$ , $K_2={\mathsf{robbed}, \mathsf{goRestaurant}}$ , $K_3={\mathsf{robbed}, \mathsf{goHome}}$ , and $K_4={\mathsf{robbed}, \mathsf{goRestaurant},\mathsf{goHome}}$ . Of these four models, $K_2$ is the only one that is closest to I, hence it is the only one that characterizes the update of $\mathcal{P}$ by $\mathcal{U}$ according to Alferes and Pereira (1996).

Procedurally, if we update $\mathcal{P}$ by $\mathcal{U}$ following the fundamental ideas behind the possible models approach and the common sense law of inertia, the result must be characterized by the stable models of $\mathcal{P}$ after they are minimally changed to become consistent with $\mathcal{U}$ . And in order to make I consistent with the rules in $\mathcal{U}$ , one needs to modify the truth value of two atoms, $\mathsf{robbed}$ and $\mathsf{money}$ , arriving at the interpretation $K_2 = {\mathsf{robbed}, \mathsf{goRestaurant}}$ . So, after the update, the agent has no money but still plans to go to a restaurant, different from the intuitively correct result where, after being robbed, the agent would not go to the restaurant, and instead go home, because he has no money.

The undesirable behaviour illustrated by the previous example was first observed by Leite and Pereira (1998), leading to the beginning of the second era.

5 The second era – syntax-based updates

The reason for the problem illustrated by the example at the end of the previous section is that modifications on the level of individual stable models, akin to model-based belief update operators, are unable to capture the essential relationships between literals encoded in rules. This was first argued by Leite and Pereira (1998), who took a closer look at Newton’s first law, also known as the law of inertia, which states that “every body remains at rest or moves with constant velocity in a straight line, unless it is compelled to change that state by an unbalanced force acting upon it” (Newtono 1726). ¹ In their discussion, Leite and Pereira pointed out that the common-sense interpretation of this law as “things keep as they are unless some kind of force is applied to them” is true, but does not exhaust its meaning. It is the result of all applied forces that governs the outcome. Take a body to which several forces are applied, and which is in a state of equilibrium due to those forces cancelling out. Later, one of those forces is removed and the body starts to move. The same kind of behaviour presents itself when updating programs. Before obtaining the truth value, by inertia, of those elements not directly affected by the update program, one should verify whether the truth of such elements is not indirectly affected by the updating of other elements or, in other words, whether there is still some rule that supports such truth.

To rectify this problem, a number of approaches were proposed. Despite being based on fundamentally different principles and methods when compared to their model update counterparts, they all take into account the syntactic rule-based form of the programs involved.

This section provides an overview of existing rule update semantics, pointing at some of the technical as well as semantic differences between them, often relying on examples to show how these semantics are interrelated.

Rule update semantics typically deal only with ground non-disjunctive rules and some do not allow for default negation in their heads. While some of them follow the belief update tradition and construct an updated program given the original program and its update, others only assign a set of stable models to a pair or sequence of programs where each represents an update of the preceding ones. In order to compare these semantics, we adopt the latter, less restrictive point of view. The “input” of a rule update semantics is thus defined as follows:

Definition 9 (Dynamic Logic Program) A dynamic logic program (DLP) is a finite sequence of ground non-disjunctive logic programs. Given a DLP $\boldsymbol{P}$ , we denote by $\mathsf{all}(\boldsymbol{P})$ the set of all rules belonging to the programs in $\boldsymbol{P}$ . We say that $\boldsymbol{P}$ is acyclic if $\mathsf{all}(\boldsymbol{P})$ is acyclic.

In order to avoid issues with rules that are repeated in multiple components of a DLP, we assume throughout this section that every rule is uniquely identified in all set-theoretic operations. This could be formalised by assigning a unique name to each rule and performing operations on names instead of on the rules themselves.

The set of stable models assigned to dynamic logic programs under a particular update semantics will be denoted as follows:

Definition 10 (Rule Update Semantics) A rule update semantics $\mathsf{S}$ is characterised by a (partial) function $[\kern-.3ex[{\cdot}]\kern-.3ex]_{\mathsf{S}}$ that assigns a set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{S}}$ of interpretations to a dynamic logic program $\boldsymbol{P}$ . We call each member of $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{S}}$ an $\mathsf{S}$ -model of $\boldsymbol{P}$ .

Whenever an approach is defined through a rule update operator, such an operator is understood as a function that assigns a program to each pair of programs. A rule update operator $\mathbin{\oplus}$ is extended to DLPs as follows: $\mathop{\bigoplus} \langle \mathcal{P}_0 \rangle = \mathcal{P}_0$ ; $\mathop{\bigoplus} \langle \mathcal{P}_i \rangle_{i <n+1} = (\mathop{\bigoplus} \langle \mathcal{P}_i \rangle_{i < n}) \mathbin{\oplus} \mathcal{P}_n$ , $n>0$ . Note that such an operator naturally induces a rule update semantics $\textsf{S}_{\mathbin{\oplus}}$ : given a DLP $\boldsymbol{P}$ , the $\textsf{S}_{\mathbin{\oplus}}$ -models of $\boldsymbol{P}$ are the stable models of $\mathop{\bigoplus} \boldsymbol{P}$ . In the rest of this paper, we exercise a slight abuse of notation by referring to the operators and their associated update semantics interchangeably.

We first discuss a major group of semantics based on the causal rejection principle (Leite and Pereira 1998; Buccafurri et al. 1999; Alferes et al. 2000; Eiter et al. 2002; Alferes et al. 2005; Osorio and Cuevas 2007), followed by semantics based on preferences (Zhang 2006; Delgrande et al. 2007). We then proceed to discuss semantics that bear some characteristics of revision rather than update (Sakama and Inoue 2003; Osorio and Zepeda 2007; Delgrande 2010) and touch upon approaches that manipulate dependencies on default assumptions induced by rules (ŠefrÁnek 2011; KrÜmpelmann and Kern-Isberner 2010; KrÜmpelmann 2012). Towards the end of this section, we formulate some fundamental properties of rule update semantics.

The use and effect of integrity constraints within the semantics presented in this section has not received significant attention in the literature. Whereas most semantics are only defined for programs without integrity constraints, often pointing to the fact that one can replace the integrity constraint $\leftarrow B(\pi).$ with the rule $a_\pi\leftarrow\mathop{\sim\!} a_\pi,B(\pi).$ , where $a_\pi$ is a new atom, with the same effect, other semantics are defined for programs with integrity constraints, but without any specific provisions regarding their role. Since all these semantics that were defined for programs with integrity constraints are preserved under the above transformation that eliminates them, in this section we will restrict the definition of semantics to only consider DLPs without integrity constraints.

5.1 Causal rejection-based semantics

The causal rejection principle (Leite and Pereira 1998) forms the basis of a number of rule update semantics. Informally, it can be stated as follows:

A rule should be rejected when it is directly contradicted by a more recent rule.

The common understanding of this principle has been to consider a direct contradiction between rules to mean a conflict between the heads of rules, that is, that the head of the rejecting rule is the negation of the head of the rejected one.

In the first proposals based on the causal rejection principle, only conflicts between objective literals in rule heads were considered, and default negation in rule heads was not allowed (Leite and Pereira 1998; Eiter et al. 2002). Later, it was found that this approach has certain limitations, namely that some belief states, represented by stable models, become unreachable (Alferes et al. 2000; Leite 2003). For example, no update of the program $\mathcal{P} = {\mathsf{p}.}$ leads to a stable model where neither $\mathsf{p}$ nor $\lnot \mathsf{p}$ is true. Default negation in rule heads was thus used to regain reachability of such states. For instance, the update $\mathcal{U} = {\mathop{\sim\!} \mathsf{p}., \mathop{\sim\!} \lnot \mathsf{p}.}$ forces $\mathsf{p}$ to be unknown, regardless of its previous state. Hence, strong negation is used to express that an atom becomes explicitly false, while default negation allows for more fine-grained control: the atom only ceases to be true, but its truth value may not be unknown. The latter also makes it possible to move between any pair of epistemic states by means of updates, as illustrated by the following example from the book by Leite (2003):

Example 11 (Railway crossing) Suppose that we use the following logic program to choose an action at a railway crossing:

\begin{align*} \mathsf{cross} &\leftarrow \lnot \mathsf{train}. & \mathsf{wait} &\leftarrow \mathsf{train}. & \mathsf{listen} &\leftarrow \mathop{\sim\!} \mathsf{train}, \mathop{\sim\!} \lnot \mathsf{train}. \end{align*}

The intuitive meaning of these rules is as follows: one should $\mathsf{cross}$ if there is evidence that no train is approaching; $\mathsf{wait}$ if there is evidence that a train is approaching; $\mathsf{listen}$ if there is no such evidence.

Consider a situation where a train is approaching, represented by the fact $(\mathsf{train}.)$ . After this train has passed by, we want to update our knowledge to an epistemic state where we lack evidence with regard to the approach of a train. If this was accomplished by updating with the fact $(\lnot \mathsf{train}.)$ , we would cross the tracks at the subsequent state, risking being killed by another train that was approaching. Therefore, we need to express an update stating that all past evidence for an atom is to be removed. The proposal was to accomplish this by allowing default negation in heads of rules. In this scenario, the intended update could be expressed by the fact $(\mathop{\sim\!} \mathsf{train}.)$ .

In the following, we thus present the semantics from Leite and Pereira (1998) and Eiter et al. (2002) in generalised forms that allow default negation in rule heads, but coincide with their original definitions on programs without such feature (Leite 2003).

The notion of conflicting rules plays an important role in all the semantics based on the causal rejection principle. When generalised logic programs are used, a conflict between rules occurs when the head literal l of one rule is the default or strong negation of the head literal of the other rule, $\mathop{\sim\!}l$ or $\overline{l}$ , respectively. Following the proposal of Leite (2003), we consider the conflicts between a rule with an objective literal l in its head and a rule with the default negation of the same literal $\mathop{\sim\!}l$ in its head as primary conflicts, while conflicts between rules with complementary objective literals in their heads, l and $\overline{l}$ , are handled by expanding DLPs. Expansion of a DLP corresponds to the following operation: whenever a DLP contains a rule with an objective literal l in its head, its expansion also contains a rule with the same body and the literal $\mathop{\sim\!}\overline{l}$ in its head. Formally:

Definition 12 (Expanded Version of a DLP) Let $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ be a DLP. The expanded version of $\boldsymbol{P}$ is the DLP $\boldsymbol{P}^{\mathsf{e}} = \langle \mathcal{P}_i^{\mathsf{e}} \rangle_{i < n}$ where for every $i < n$ ,

\begin{equation*} \mathcal{P}_i^{\mathsf{e}} = \mathcal{P}_i \cup \{ \mathop{\sim\!} \overline{l} \leftarrow B(\pi). | \pi \in \mathcal{P}_i \land H(\pi) = {l} \land l \in \mathscr{L} \}.\end{equation*}

The additional rules in the expanded version capture the coherence principle: when an objective literal l is derived, its complement $\overline{l}$ cannot be concurrently true and thus $\mathop{\sim\!} \overline{l}$ must be true. In this way, every conflict between complementary objective literals directly translates into a conflict between an objective literal and its default negation. By ensuring that we always use expanded versions of DLPs, we can adopt the following definition of a conflict between a pair of rules.

Definition 13 (Conflicting rules) We say that rules $\pi$ , $\sigma$ are in conflict, denoted by $\pi \Join \sigma$ , if and only if

\begin{equation*} H(\pi)[\pi] \neq \emptyset \enspace\text{ and }\enspace H(\pi)[\pi] = \mathop{\sim\!} H(\pi)[\sigma] .\end{equation*}

5.1.1 The $\textsf{JU}$ semantics and the $\textsf{AS}$ semantics

The historically first rule update semantics in answer-set programming is the justified update semantics, or $\textsf{JU}$ semantics for short (Leite and Pereira 1998), with the idea to define a set of rejected rules, which depends on a stable model candidate, and then verify that the candidate is indeed a stable model of the remaining rules.

Definition 14 ( $\textsf{JU}$ Semantics Leite and Pereira 1998) Let $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ be a DLP and J an interpretation. We define the set $\mathsf{rej}_{[\mathsf{JU}]}({\boldsymbol{P}, J})$ of rejected rules as

\begin{equation*} \mathsf{rej}_{[\mathsf{JU}]}({\boldsymbol{P}, J}) = \{ \pi \in \mathcal{P}_i | \exists j \, \exists \sigma : i < j < n \land \sigma \in \mathcal{P}_j \land \pi \Join \sigma \land J \mathrel\mid= B(\pi)[\sigma] \} .\end{equation*}

The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}}$ of $\textsf{JU}$ models of a DLP $\boldsymbol{P}$ consists of all stable models J of the program

\begin{equation*} \mathsf{all}(\boldsymbol{P}^{\mathsf{e}}) \backslash \mathsf{rej}_{[\mathsf{JU}]}({\boldsymbol{P}^{\mathsf{e}}, J}) . \end{equation*}

Under the $\textsf{JU}$ semantics, a rule $\pi$ is rejected if and only if a more recent rule $\sigma$ is in conflict with $\pi$ and the body of $\sigma$ is satisfied in the stable model candidate J. Note that the latter condition is essential – without it, rules might get rejected simply because a more recent rule $\sigma$ has a conflicting head, without a guarantee that $\sigma$ will actually be activated.

Before we illustrate the $\textsf{JU}$ semantics with an example, we first present a related semantics, which prevents rejected rules from rejecting other rules. It is dubbed the update answer-set semantics, or $\textsf{AS}$ semantics for short (Eiter et al. 2002):

Definition 15 ( $\textsf{AS}$ Semantics Eiter et al. 2002) Let $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ be a DLP and J an interpretation. We define the set of rejected rules $\mathsf{rej}_{[\mathsf{AS}]}({\boldsymbol{P}, J})$ as ²

\begin{equation*} \mathsf{rej}_{[\mathsf{AS}]}({\boldsymbol{P}, J}) = \{ \pi \in \mathcal{P}_i | \exists j \, \exists \sigma : i < j < n \land \sigma \in \mathcal{P}_j \backslash \mathsf{rej}_{[\mathsf{AS}]}({\boldsymbol{P}, J}) \land \pi \Join \sigma \land J \mathrel\mid= B(\pi)[\sigma] \}.\end{equation*}

The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{AS}}$ of $\textsf{AS}$ models of a DLP $\boldsymbol{P}$ consists of all stable models J of the program

\begin{equation*} \mathsf{all}(\boldsymbol{P}^{\mathsf{e}}) \backslash \mathsf{rej}_{[\mathsf{AS}]}({\boldsymbol{P}^{\mathsf{e}}, J}) . \end{equation*}

The definitions of the $\textsf{JU}$ and $\textsf{AS}$ semantics are fairly straightforward and reflect intuitions about rule updates better than an approach based on a belief update construction, such as the one by Alferes and Pereira (1996). As an illustration, let us look at the result of these semantics when applied to the example in the introduction:

Example 16 Consider again the program $\mathcal{P}$ from the example in the introduction which contains the rules

\begin{align*} \mathsf{goHome} \leftarrow \mathop{\sim\!} \mathsf{money}.& &\mathsf{goRestaurant} \leftarrow \mathsf{money}.& &\mathsf{money}. \end{align*}

and its update $\mathcal{U}$ with the rules

\begin{align*} \mathop{\sim\!} \mathsf{money} &\leftarrow \mathsf{robbed}. & \mathsf{robbed} &. \end{align*}

Following the discussion in the introduction, the expected stable model of the DLP $\langle \mathcal{P}, \mathcal{U} \rangle$ is $J = {\mathsf{robbed}, \mathsf{goHome}}$ . Also, $\mathsf{rej}_{[\mathsf{JU}]}({\langle \mathcal{P}, \mathcal{U} \rangle^{\mathsf{e}}, J}) = \mathsf{rej}_{[\mathsf{AS}]}({\langle \mathcal{P}, \mathcal{U} \rangle^{\mathsf{e}}, J}) = {\mathsf{money}.}$ , and J is indeed a stable model of the remaining rules in $\mathsf{all}(\langle \mathcal{P}, \mathcal{U} \rangle^{\mathsf{e}})$ . Furthermore, J is the only interpretation with these properties, so

\begin{equation*} [\kern-.3ex[{\langle \mathcal{P}, \mathcal{U} \rangle}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\langle \mathcal{P}, \mathcal{U} \rangle}]\kern-.3ex]_{\mathsf{AS}} = {J} . \end{equation*}

Example 17 To illustrate the expansion mechanism and its interplay with the rejection mechanism, consider again the program $\mathcal{P}$ from the example in the introduction which contains the rules

\begin{align*} \mathsf{goHome} \leftarrow \mathop{\sim\!} \mathsf{money}.& &\mathsf{goRestaurant} \leftarrow \mathsf{money}.& &\mathsf{money}. \end{align*}

but now its update $\mathcal{U}$ is modified by replacing $\mathop{\sim\!} \mathsf{money}$ with $\lnot\mathsf{money}$ :

\begin{align*} \lnot \mathsf{money} &\leftarrow \mathsf{robbed}. & \mathsf{robbed} &. \end{align*}

The expanded version of both programs are:

\begin{align*}\mathcal{P}^{\mathsf{e}}& &\mathsf{goHome} &\leftarrow \mathop{\sim\!} \mathsf{money}. &\mathsf{goRestaurant} &\leftarrow \mathsf{money}.& &\mathsf{money}.\\ & &\mathop{\sim\!}\lnot\mathsf{goHome} &\leftarrow \mathop{\sim\!} \mathsf{money}. &\mathop{\sim\!}\lnot\mathsf{goRestaurant} &\leftarrow \mathsf{money}.& &\mathop{\sim\!}\lnot\mathsf{money}.\\\mathcal{U}^{\mathsf{e}}& &\lnot \mathsf{money} &\leftarrow \mathsf{robbed}. &\mathsf{robbed}.& &\\ & &\mathop{\sim\!} \mathsf{money} &\leftarrow \mathsf{robbed}. &\mathop{\sim\!}\lnot\mathsf{robbed}.& & \end{align*}

The expected stable model of the DLP $\langle \mathcal{P}, \mathcal{U} \rangle$ is $J = {\mathsf{robbed},\lnot\mathsf{money}, \mathsf{goHome}}$ . Also, $\mathsf{rej}_{[\mathsf{JU}]}({\langle \mathcal{P}, \mathcal{U} \rangle^{\mathsf{e}}, J}) = \mathsf{rej}_{[\mathsf{AS}]}({\langle \mathcal{P}, \mathcal{U} \rangle^{\mathsf{e}}, J}) = {\mathsf{money}.,\mathop{\sim\!}\lnot\mathsf{money}.}$ , and J is indeed a stable model of the remaining rules in $\mathsf{all}(\langle \mathcal{P}, \mathcal{U} \rangle^{\mathsf{e}})$ . Furthermore, J is the only interpretation with these properties, so

\begin{equation*} [\kern-.3ex[{\langle \mathcal{P}, \mathcal{U} \rangle}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\langle \mathcal{P}, \mathcal{U} \rangle}]\kern-.3ex]_{\mathsf{AS}} = {J} . \end{equation*}

Nevertheless, problematic examples which are not handled correctly by these semantics have also been identified (Leite 2003). Many of them involve tautological updates, the intuition being that a tautological rule (i.e., a rule whose head literal also belongs to its body) cannot indicate a change in the modelled world because it is always true. It thus follows that a tautological update should not affect the stable models of the original program. Interestingly, immunity to tautological updates is a desirable property of belief updates in classical logic, being a direct consequence of postulate $\mathsf{BU2}$ . The following example illustrates a misbehaviour of the $\textsf{AS}$ semantics

Example 18 Consider the DLP $\boldsymbol{P}_1 = \langle {\mathsf{p}.}, {\lnot \mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{p}.} \rangle$ . Under the $\textsf{AS}$ semantics, we obtain $ [\kern-.3ex[{\boldsymbol{P}_1}]\kern-.3ex]_{\mathsf{AS}} = {{\lnot \mathsf{p}}, {\mathsf{p}}}$ , where the expected result is ${{\lnot \mathsf{p}}}$ .

In the previous example, the $\textsf{JU}$ semantics provides an adequate solution: since it allows rejected rules to reject, the initial rule is always rejected and $[\kern-.3ex[{\boldsymbol{P}_1}]\kern-.3ex]_{\mathsf{JU}} ={{\lnot \mathsf{p}}}$ as expected. Unfortunately, there are also numerous DLPs to which the $\textsf{JU}$ semantics assigns unwanted models, as illustrated b the following example.

Example 19 Consider the DLP $\boldsymbol{P}_2 = \langle {\mathsf{p}.}, {\mathop{\sim\!} \mathsf{p} \leftarrow \mathop{\sim\!} \mathsf{p}.} \rangle$ . Under the $\textsf{JU}$ and $\textsf{AS}$ semantics, we obtain $[\kern-.3ex[{\boldsymbol{P}_2}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}_2}]\kern-.3ex]_{\mathsf{AS}} = {\emptyset, {\mathsf{p}}}$ , where the expected result is ${{\mathsf{p}}}$ . The unwanted stable model $\emptyset$ arises because rejecting $\mathsf{p}.$ causes the default assumption $\mathop{\sim\!} \mathsf{p}$ to be “reinstated”, that is, $\mathsf{p}$ to be assumed false by default – despite $\mathsf{p}$ being initially asserted as a fact.

5.1.2 The $\textsf{DS}$ semantics

The problem illustrated with Example 19 is addressed in the dynamic stable model semantics, or $\textsf{DS}$ semantics for short (Alferes et al. 2000), by constraining the set of atoms that can be assumed false by default.

Definition 20 ( $\textsf{DS}$ Semantics Alferes et al. 2000) Let $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ be a DLP and J an interpretation. The set of rejected rules $\mathsf{rej}_{[\mathsf{DS}]}({\boldsymbol{P}, J})$ is identical to the set $\mathsf{rej}_{[\mathsf{JU}]}({\boldsymbol{P}, J})$ and we define the set of default assumptions $\mathsf{def}(\boldsymbol{P}, J)$ as

\begin{equation*} \mathsf{def}(\boldsymbol{P}, J) = \{ \mathop{\sim\!} l | l \in \mathscr{L} \land \lnot \exists \pi \in \mathsf{all}(\boldsymbol{P}) : H(\pi) = {l} \land J \mathrel\mid= B(\pi) \}.\end{equation*}

The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{DS}}$ of $\textsf{DS}$ models of a DLP $\boldsymbol{P}$ consists of all interpretations J such that

\begin{equation*} J' = \mathsf{least}( [ \mathsf{all}(\boldsymbol{P}^{\mathsf{e}}) \backslash \mathsf{rej}_{[\mathsf{DS}]}({\boldsymbol{P}^{\mathsf{e}}, J}) ] \cup \mathsf{def}(\boldsymbol{P}^{\mathsf{e}}, J) ) , \end{equation*}

where $J' = J \cup \mathop{\sim\!}\,(\mathscr{L} \backslash J)$ and $\mathsf{least}(\cdot)$ denotes the least model of the argument program with all literals treated as atoms.

Note that it follows from the definition of a (regular) stable model that J is a $\textsf{JU}$ stable model of a DLP $\boldsymbol{P}$ if and only if

\begin{equation*} J' = \mathsf{least}( [ \mathsf{all}(\boldsymbol{P}^{\mathsf{e}}) \backslash \mathsf{rej}_{[\mathsf{DS}]}({\boldsymbol{P}^{\mathsf{e}}, J}) ] \cup \mathop{\sim\!}\,(\mathscr{L} \backslash J) ) .\end{equation*}

Hence, the difference between the $\textsf{JU}$ and $\textsf{DS}$ semantics is only in the set of default assumptions that can be adopted to construct the model. In particular, if a rule that derives an objective literal l is present in $\mathsf{all}(\boldsymbol{P})$ , then $\mathop{\sim\!} l$ is not among the default assumptions in the $\textsf{DS}$ semantics although it could be used as a default assumption in the $\textsf{JU}$ semantics. In other words, according to the $\textsf{DS}$ semantics, once some objective literal l can be derived by some (older) rule, we can no longer assume $\mathop{\sim\!} l$ by default. The $\textsf{DS}$ semantics thus resolves problems with examples such as the previous one encoded by $\boldsymbol{P}_2$ , that is, it holds that $[\kern-.3ex[{\boldsymbol{P}_2}]\kern-.3ex]_{\mathsf{DS}} ={{\mathsf{p}}}$ . But even the $\textsf{DS}$ semantics exhibits problematic behaviour when tautological updates are involved, as illustrated by the following example.

Example 21 Consider the DLP $\boldsymbol{P}_3 = \langle {\mathsf{p}., \lnot \mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{p}.} \rangle$ . Under the $\textsf{DS}$ semantics, just as the case with the $\textsf{JU}$ and the $\textsf{AS}$ semantics, we obtain $ [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{AS}} = [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{DS}} = {{\mathsf{p}}}$ , where the expected result is ${}$ . The expected result here is that no stable model should be assigned to $\boldsymbol{P}_3$ because initially it has none and the tautological update should not change anything about that situation. Whereas one might wonder why not simply achieve immunity to tautologies by preprocessing programs and removing them, it is important to note that the problem runs deeper. Immunity to tautologies is a simple, easy to understand manifestation of a deeper problem concerning updates that should be considered tautological, even though there are no tautological rules. These tautological updates are characterized by the existence of cycles involving more than one rule, which could not be dealt with by simply removing tautologies, not even sets of cyclic rules within a single program.

5.1.3 The $\textsf{RD}$ semantics

The trouble with tautological and some other types of irrelevant updates has been discussed and finally resolved by Alferes et al. (2005) who defined the so-called refined extension principle – a principle encoding the desirable immunity to tautological, cyclic and other irrelevant updates – as well as a rule update semantics satisfying the principle. The definition of this semantics is very similar to the $\textsf{DS}$ semantics, the only difference being that in the set of rejected rules, $i \leq j$ is required instead of $i < j$ , which seems to be a technical trick with little correspondence to any intuition. The semantics is called the refined dynamic stable model semantics, or $\textsf{RD}$ semantics for short:

Definition 22 ( $\textsf{RD}$ Semantics Alferes et al. 2005) Let $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ be a DLP and J an interpretation. We define the set of rejected rules $\mathsf{rej}_{[\mathsf{RD}]}({\boldsymbol{P}, J})$ as

\begin{equation*} \mathsf{rej}_{[\mathsf{RD}]}({\boldsymbol{P}, J}) = \{ \pi \in \mathcal{P}_i | \exists j \, \exists \sigma : i \leq j < n \land \sigma \in \mathcal{P}_j \land \pi \Join \sigma \land J \mathrel\mid= B(\pi)[\sigma] \}.\end{equation*}

The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RD}}$ of $\textsf{RD}$ models of a DLP $\boldsymbol{P}$ consists of all interpretations J such that

\begin{equation*} J' = \mathsf{least}( [ \mathsf{all}(\boldsymbol{P}^{\mathsf{e}}) \backslash \mathsf{rej}_{[\mathsf{RD}]}({\boldsymbol{P}^{\mathsf{e}}, J}) ] \cup \mathsf{def}(\boldsymbol{P}^{\mathsf{e}}, J) ) , \end{equation*}

where J’ and $\mathsf{least}(\cdot)$ are as before.

Due to satisfying the refined extension principle, the $\textsf{RD}$ semantics is completely immune to tautological updates. For instance, in case of the previous example encoded by $\boldsymbol{P}_3$ we obtain $[\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{RD}} = \emptyset$ . As we shall see, a vast majority of rule update semantics, even those that have been developed much later and are not based on causal rejection, are not immune to tautological updates.

Banti et al. (2005) present an alternative, equivalent, characterisation for the $\textsf{RD}$ semantics, based on level mappings, which is perhaps better in helping understand the difference w.r.t. previous semantics than the trick used in the previous definition of the set of rejected rules where $i \leq j$ is required instead of $i < j$ .

Theorem 23 ( $\textsf{RD}$ Semantics, Alternative Characterisation Banti et al. 2005) Let $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ be a DLP and J an interpretation. Given a level mapping $\ell$ , let the set $\mathsf{rej}_{[\ell]}({\boldsymbol{P}, J})$ of rejected rules be defined as follows:

\begin{equation*} \mathsf{rej}_{[\ell]}({\boldsymbol{P}, J}) = \{ \pi \in \mathcal{P}_i | \exists j \, \exists \sigma : i < j < n \land \sigma \in \mathcal{P}_j \land \pi \Join \sigma \land J \mathrel\mid= B(\pi)[\sigma] \land \ell(H(\pi)[\sigma]) > \ell(B(\pi)[\sigma]) \}.\end{equation*}

Then, $J\in[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RD}}$ iff there exists a level mapping $\ell$ such that:

1. 1. J is a $\textsf{C}$ -model of $\mathsf{all}(\boldsymbol{P}^{\mathsf{e}}) \backslash \mathsf{rej}_{[\ell]}({\boldsymbol{P}^{\mathsf{e}}, J})$ , and

2. 2. $\forall\mathsf{p}\in J,\exists\sigma\in\mathsf{all}(\boldsymbol{P}^{\mathsf{e}}) \backslash \mathsf{rej}_{[\ell]}({\boldsymbol{P}^{\mathsf{e}}, J})$ such that $H(\pi)[\sigma]=\mathsf{p}\land, \ell(H(\pi)[\sigma]) > \ell(B(\pi)[\sigma])\land J\models B(\pi)[\sigma]$ .

This characterisation borrows from the work of Hitzler and Wendt (2005) on uniform characterisations of different semantics for logic programs in terms of level mappings. In particular, this characterisation is based on the notion of well-supported models (Fages 1994), an alternative view of stable models that characterises them as $\textsf{C}$ -models with the additional requirement that there exists some level mapping such all atoms in the model are supported by some rule whose head is that atom and the level of the that atom is greater than the level of the rule’s body. When extended to the case of DLPs, besides being used to decide whether some objective literal should be true, rules are also used to reject other rules. Hence, the concept of well-supportedness is also adopted to the rejection mechanism, and rules can only reject other rules with the additional constraint that the level of their heads be greater than the level of their bodies.

5.1.4 Relationship between semantics based on causal rejection

The rule update semantics introduced above are strongly related to one another. The above considerations show that undesired stable models of the $\textsf{AS}$ , $\textsf{JU}$ and $\textsf{DS}$ semantics were eliminated by enlarging the set of rejected rules or by shrinking the set of default assumptions. The following theorem shows that no additional stable models were added in the process:

Theorem 24 (Leite 2003; Alferes et al. 2005) Let $\boldsymbol{P}$ be a DLP. Then,

\begin{equation*} [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{AS}} \supseteq [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}} \supseteq [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{DS}} \supseteq [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RD}} . \end{equation*}

Moreover, for each inclusion above there exists a DLP for which the inclusion is strict.

Furthermore, all of these semantics coincide when only acyclic DLPs are considered, showing that the differences in the definitions of rejected rules and default assumptions are only relevant in the presence of cyclic dependencies between literals.

Theorem 25 (Homola 2004) Let $\boldsymbol{P}$ be an acyclic DLP. Then,

\begin{equation*} [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{AS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{DS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RD}} . \end{equation*}

The relation between these semantics and other formalisms has also been studied. It has been shown by Eiter et al. (2002) that the $\textsf{AS}$ semantics coincides with the non-disjunctive case of the semantics for inheritance programs by Buccafurri et al. (1999).

One of the open issues with these semantics is that one cannot easily condense a DLP to a single logic program that could be used instead of the DLP to perform further updates. The first obstacle is that the stable models of a DLP may be non-minimal, as illustrated by the following example.

Example 26 Consider the DLP $\boldsymbol{P}_4 = \langle {\mathsf{p}., \mathsf{q} \leftarrow \mathsf{p}.}, {\mathop{\sim\!} \mathsf{p} \leftarrow \mathop{\sim\!} \mathsf{q}.} \rangle$ . According to all semantics introduced so far, we obtain $[\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{AS}} = [\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{DS}} = [\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{RD}} = {\emptyset, {\mathsf{p}, \mathsf{q}}}$ .

Since stable models of non-disjunctive programs are subset-minimal, no such program can have the set of stable models $[\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{RD}}$ . Condensing to a disjunctive program is also problematic because rule update semantics are constrained to non-disjunctive programs only, so after a condensation one would not be able to perform any further updates.

Nevertheless, the original definition of the four discussed $\mathsf{S}$ -semantics ( $\textsf{JU}$ , $\textsf{AS}$ , $\textsf{DS}$ and $\textsf{RD}$ semantics) was accompanied by a translation of a DLP to a single non-disjunctive program over an extended language whose stable models correspond one-to-one to the $\mathsf{S}$ -models assigned to the DLP under the respective rule update semantics. Due to the language extension, the new program cannot simply be updated directly as a substitute for the original DLP, but may serve as a way to study the computational properties of the rule update semantics and as a way to implement it using existing answer-set solvers.

In the literature, we can also find the semantics proposed by Osorio and Cuevas (2007) which can be seen as simpler substitutes for the $\textsf{AS}$ semantics. Unlike the semantics discussed above, they are not defined declaratively, instead they are specified directly by translating the initial program and its update to a single program over the same language. The first translation essentially weakens the rules from the original program by making them defeasible, that is, a rule $l\leftarrow B(\pi)$ is transformed into the rule $l \leftarrow B(\pi), \mathop{\sim\!}\overline{l}$ . The authors have shown that the resulting semantics is equivalent to the $\textsf{AS}$ semantics if a single update is performed and the updating program contains a tautology $l \leftarrow l$ for every objective literal l. Due to its simplicity, because it only deals with a single update in a way that cannot immediately be extended to additional updates, this semantics is not sensitive to the addition and removal of tautologies, but it adopts the problematic behaviour of the $\textsf{AS}$ semantics even when the tautologies are removed from the updating program. For example, when considering the DLPs

\begin{align*} \boldsymbol{P}_5 &= \langle {\mathsf{p}., \lnot \mathsf{p}.}, \emptyset \rangle\enspace\text{and}\\ \boldsymbol{P}_5' &= \langle {\mathsf{p}., \lnot \mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{p}., \lnot \mathsf{p} \leftarrow \lnot \mathsf{p}.} \rangle\end{align*}

the $\textsf{AS}$ semantics correctly assigns no $\textsf{AS}$ model to $\boldsymbol{P}_5$ although its sensitivity to tautological updates causes $\boldsymbol{P}_5'$ to have two $\textsf{AS}$ models: ${\mathsf{p}}$ and ${\lnot \mathsf{p}}$ . The first semantics suggested by Osorio and Cuevas (2007) assigns these two interpretations, ${\mathsf{p}}$ and ${\lnot \mathsf{p}}$ , to both $\boldsymbol{P}_5$ and $\boldsymbol{P}_5'$ , so it exhibits problematic behaviour even on DLPs that were correctly handled by the $\textsf{AS}$ semantics.

The second translation is more involved as it produces a program that may not be expressible by a non-disjunctive program. The resulting update semantics is shown to coincide with the $\textsf{AS}$ semantics in case only a single update is performed. Note that since the $\textsf{AS}$ semantics coincides with the $\textsf{JU}$ semantics on DLPs of length two, ³ the above mentioned relationships between semantics by Osorio and Cuevas (2007) and the $\textsf{AS}$ semantics also hold for the $\textsf{JU}$ semantics. Their behaviour on DLPs of length three or more has not been studied.

5.2 Preference-based semantics

A smaller group of rule update semantics relies on syntactic transformations and semantics for prioritised logic programs. These semantics do not consider default negation in heads of rules.

Formally, a prioritised logic program is a pair $({\mathcal{P}, \prec})$ where $\mathcal{P}$ is a program and $\prec$ is a strict partial order over $\mathcal{P}$ . The intuitive meaning of $\prec$ is that if $\pi \prec \sigma$ , then $\sigma$ is more preferred than $\pi$ . There exist a number of different semantics for prioritised logic programs (Brewka and Eiter 1999; Delgrande et al. 2003; Schaub and Wang 2003; Zhang 2003). Their goal is to plausibly use the preference relation $\prec$ to choose the preferred stable models among the stable models of $\mathcal{P}$ , or to constrain the rules of $\mathcal{P}$ used to determine the stable models.

5.2.1 The $\textsf{PRZ}$ semantics

One rule update semantics of this type was defined by Zhang (2006) and relies on the semantics for prioritised logic programs proposed by Zhang (2003). ⁴ Generally speaking, according to Zhang (2006), the semantics is assigned to a prioritised logic program $({\mathcal{P}, \prec})$ by pruning away less preferred rules, obtaining an ordinary logic program $\mathcal{P}^\prec \subseteq \mathcal{P}$ called a reduct. Formally, $\mathcal{P}^<$ is a reduct of $({\mathcal{P}, \prec})$ if there exists a sequence of sets $\mathcal{P}_{i}$ ( $i=0,1,\ldots$ ) such that

\begin{align*}\mathcal{P}_{0} = \mathcal{P},\quad\quad\quad\quad\quad\mathcal{P}_{i+1} = \mathcal{P}_{i}-\mathcal{R}_{i},\quad\quad\quad\quad\quad\mathcal{P}^< = \bigcap_{i=0}^{\infty}\mathcal{P}_{i},\end{align*}

where

\begin{align*}\mathcal{R}_{i}=\{\pi\in\mathcal{P}_{i} \mid &\exists\pi'\in\mathcal{P}_{i}, \text{ such that }\forall\pi''\in\mathcal{R}_{i}, \pi''<\pi' \land \pi'' \triangleleft (\mathcal{P}_{i}-\mathcal{R}_{i}) \text{ and}\\[3pt]&\not\exists \mathcal{R}'_{i}\subseteq\mathcal{P}_{i} \text{ such that }\exists\pi''\in\mathcal{R}_{i},\forall\pi'\in\mathcal{R}'_{i}, \pi'<\pi'' \land \pi' \triangleleft (\mathcal{P}_{i}-\mathcal{R}'_{i}) \},\end{align*}

and $\pi\triangleleft\mathcal{Q}$ denotes that rule $\pi$ is defeated by program $\mathcal{Q}$ , which is true if there exists some objective literal $l\in I\in[\kern-.3ex[{{\mathcal{Q}}}]\kern-.3ex]_{\mathsf{SM}}$ such that $l\in B(\pi)^-$ .

A prioritised logic program may have zero or more reducts and the preferred stable models are all the stable models of all the reducts. For a detailed discussion of reducts and their properties the reader can refer to the paper by Zhang (2003).

Subsequently, the update semantics defined by Zhang (2006) performs an update of a program $\mathcal{P}$ by a program $\mathcal{U}$ by executing the following steps:

1. 1. Take some stable model $J_\mathcal{P}$ of $\mathcal{P}$ .

2. 2. Determine the set $\mathit{Update}(J_\mathcal{P},\mathcal{U})$ of interpretations resulting from updating $J_\mathcal{P}$ by $\mathcal{U}$ , in a way similar to to the approach of Marek and Truszczynski (1994, 1998), given by:

   \begin{equation*} \mathit{Update}(J_\mathcal{P},\mathcal{U}) = { I \in [\kern-.3ex[ {\mathcal{U}} ]\kern-.3ex]_{\mathsf{C}} | \lnot \exists J \in [\kern-.3ex[ {\mathcal{U}} ]\kern-.3ex]_{\mathsf{C}} : (J \div J_\mathcal{P}) \subsetneq (I \div J_\mathcal{P}) },\end{equation*}
   where $\div$ denotes set-theoretic symmetric difference. Choose any interpretation from $\mathit{Update}(J_\mathcal{P},\mathcal{U})$ and denote it by $J_{\langle \mathcal{P}, \mathcal{U} \rangle}$ .

3. 3. Extract a maximal subset $\mathcal{P}'$ of $\mathcal{P}$ that is coherent with $J_{\langle \mathcal{P}, \mathcal{U} \rangle}$ , that is, such that there exists a stable model of $\mathcal{P}' \cup {l. | l \in J_{\langle \mathcal{P}, \mathcal{U} \rangle}}$ .

4. 4. The set $({\mathcal{P}' \cup \mathcal{U}, \mathcal{P}' \times \mathcal{U}})^<$ of reducts of the prioritised logic program $({\mathcal{P}' \cup \mathcal{U}, \mathcal{P}' \times \mathcal{U}})$ is the result of updating $\mathcal{P}$ by $\mathcal{U}$ .

As explained byZhang (2006), the intuition behind the first two steps is that simply taking a maximal subset of $\mathcal{P}$ coherent with $\mathcal{U}$ is too crude an operation because it does not take into account the source of a conflict.

Example 27 (Intuition For Steps 1. and 2. Zhang 2006) Consider the programs

\begin{align*} \begin{aligned} \mathcal{P}: && \mathsf{p} &. \\ && \mathsf{q} &\leftarrow \mathsf{r}. \end{aligned} && \text{and} && \begin{aligned} \mathcal{U}: && \mathsf{r} &\leftarrow \mathsf{p}. \\ && \lnot \mathsf{q} &\leftarrow \mathsf{r}. \end{aligned} \end{align*}

Since $\mathcal{P} \cup \mathcal{U}$ is incoherent, some part of $\mathcal{P}$ needs to be eliminated to regain coherence. There are two maximal subsets of $\mathcal{P}$ that are coherent with $\mathcal{U}$ : ${\mathsf{p}.}$ and ${\mathsf{q} \leftarrow \mathsf{r}.}$ . However, intuition suggests that the former set is preferable since the direct conflict between rules $(\mathsf{q} \leftarrow \mathsf{r}.)$ and $(\lnot \mathsf{q} \leftarrow \mathsf{r}.)$ provides a justification for eliminating the rule $(\mathsf{q} \leftarrow \mathsf{r}.)$ and thus keeping the fact $(\mathsf{p}.)$ .

The approach taken, then, is to first consider a stable model of $\mathcal{P}$ and update it by $\mathcal{U}$ , obtaining a new interpretation $J_{\langle \mathcal{P}, \mathcal{U} \rangle}$ that reflects the new information in $\mathcal{U}$ . Afterwards, a maximal set of rules from $\mathcal{P}$ coherent with $J_{\langle \mathcal{P}, \mathcal{U} \rangle}$ is used to form a prioritised logic program that prefers rules from $\mathcal{U}$ over rules from $\mathcal{P}$ . The reducts of this program form the result of the update.

Due to the possibility of having multiple reducts as possible results of the update, it is not completely clear how updates can be iterated. Do we choose one reduct and commit to it? Which one do we choose, then? Or do we simply consider all of the reducts and all possible evolutions? Due to these unresolved issues, we formally define this semantics only for DLPs of length two. We call it preference-based Zhang’s semantics, or $\textsf{PRZ}$ semantics for short.

Definition 28 ( $\textsf{PRZ}$ Semantics Zhang 2006) Let $\boldsymbol{P} = \langle \mathcal{P}, \mathcal{U} \rangle$ be a DLP without default negation in heads of rules. The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{PRZ}}$ of $\textsf{PRZ}$ models of $\boldsymbol{P}$ is the union of sets of stable models of all reducts obtained by performing the steps 1–4 above.

One distinguishing feature of the $\textsf{PRZ}$ semantics is that by relying on a stable model of $\mathcal{P}$ for conflict resolution, it is unable to detect “latent” conflicts between rules that have not been “triggered” in the initial stable model or its update. This is illustrated in the following example: ⁵

Example 29 (Undetected Latent Conflicts in the $\textsf{PRZ}$ semantics) Consider the programs

\begin{align*} \begin{aligned} \mathcal{P}: && \mathsf{p} &\leftarrow \mathsf{r}. \\ && \mathsf{q} &\leftarrow \mathsf{r}. \end{aligned} && \text{and} && \begin{aligned} \mathcal{U}: && \mathsf{r}&. \\ && \lnot \mathsf{p} &\leftarrow \mathsf{q}. \end{aligned} \end{align*}

and let $\boldsymbol{P} = \langle \mathcal{P}, \mathcal{U} \rangle$ . The single stable model of $\mathcal{P}$ is $J_\mathcal{P} = \emptyset$ and its update by $\mathcal{U}$ results in the interpretation $J_{\langle \mathcal{P}, \mathcal{U} \rangle} = {\mathsf{r}}$ which is coherent with $\mathcal{P}$ . The resulting prioritised logic program $({\mathcal{P} \cup \mathcal{U}, \mathcal{P} \times \mathcal{U}})$ has only one reduct, $\mathcal{P} \cup \mathcal{U}$ , that has no stable model. In other words, $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{PRZ}} = \emptyset$ and the conflict between $\mathcal{P}$ and $\mathcal{U}$ remained unresolved. Note also that $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{AS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{DS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RD}} = {{\lnot \mathsf{p}, \mathsf{q}, \mathsf{r}}}$ .

The $\textsf{PRZ}$ semantics is also sensitive to tautological updates:

Example 30 (Tautological Updates in the $\textsf{PRZ}$ semantics) Consider the programs

\begin{align*} \begin{aligned} \mathcal{P}: && \mathsf{p} &\leftarrow \mathop{\sim\!} \lnot \mathsf{p}. \\ && \lnot \mathsf{p} &\leftarrow \mathop{\sim\!} \mathsf{p}. \end{aligned} && \text{and} && \begin{aligned} \mathcal{U}: && \mathsf{p} &\leftarrow \mathsf{p}. \end{aligned} \end{align*}

Both stable models ${\mathsf{p}}$ and ${\lnot \mathsf{p}}$ of $\mathcal{P}$ remain unchanged after an update by $\mathcal{U}$ and thus both rules of $\mathcal{P}$ are retained in the resulting prioritised logic program $({\mathcal{P} \cup \mathcal{U}, \mathcal{P} \times \mathcal{U}})$ . Its only reduct, however, is the program ${\mathsf{p} \leftarrow \mathop{\sim\!} \lnot \mathsf{p}., \mathsf{p} \leftarrow \mathsf{p}.}$ , which has a single stable model ${\mathsf{p}}$ . The tautological update has thus discarded one of the stable models of $\mathcal{P}$ .

5.2.2 The $\mathsf{PRD}_i^-$ , $\mathsf{PRW}_i$ and $\mathsf{PRB}_i$ semantics

Preference-based rule update semantics were also considered by Delgrande et al. (2007), utilising the semantics for prioritised logic programs examined by Schaub and Wang (2003). ⁶ Instead of defining how a prioritised logic program $({\mathcal{P}, \prec})$ can be characterized in terms of reducts, as done by Zhang (2003), Schaub and Wang (2003) specify conditions that a stable model of $\mathcal{P}$ must satisfy in order to be a preferred stable model of $({\mathcal{P}, \prec})$ . They use three such conditions, defined in the literature on programs with preferences, dubbed $\mathsf{D}$ -preference, $\mathsf{X}$ -preference and $\mathsf{B}$ -preference, which yield an increasing number of preferred stable models. For further details about these preference strategies the reader can refer to the paper by Schaub and Wang (2003) and the references therein.

Unlike in the approach by Zhang (2006), the methodology chosen by Delgrande et al. (2007) for performing rule updates is based on relatively simple transformations into a prioritised logic program. In order to define these transformations, we first need to introduce the following notation for arbitrary programs $\mathcal{P}$ and $\mathcal{U}$ :

\begin{align*} \mathcal{P}^d &= { l \leftarrow B(\pi), \mathop{\sim\!} \overline{l}. | (l \leftarrow B(\pi).) \in \mathcal{P} }, \\ C(\mathcal{P}, \mathcal{U}) &= \{ ({\pi, \sigma}) | \exists l \in \mathscr{L} : \pi \in \mathcal{P} \land \sigma \in \mathcal{U} \land H(\pi)[\pi] = {l} \land H(\pi)[\sigma] = {\overline{l}} \}, \\ c(\mathcal{P}, \mathcal{U}) &= { \pi, \sigma | ({\pi, \sigma}) \in C(\mathcal{P}, \mathcal{U}) }. \end{align*}

Intuitively, $\mathcal{P}^d$ denotes a program obtained from $\mathcal{P}$ by making all its rules defeasible, analogically to the semantics based on weakenings by Osorio and Cuevas (2007). The set $C(\mathcal{P}, \mathcal{U})$ contains pairs of rules from $\mathcal{P}$ and $\mathcal{U}$ with conflicting heads and $c(\mathcal{P}, \mathcal{U})$ contains rules from $\mathcal{P}$ and $\mathcal{U}$ involved in such conflicts.

Delgrande et al. (2007) proposed three different operators for updating a program $\mathcal{P}$ by a program $\mathcal{U}$ , each of which outputs a different prioritised logic program:

\begin{align*} \mathcal{P} *_0 \mathcal{U} &= \left({{\mathcal{P}^d \cup \mathcal{U}^d, \mathcal{P}^d \times \mathcal{U}^d}}\right), \\ \mathcal{P} *_1 \mathcal{U} &= \left({{\mathcal{P}^d \cup \mathcal{U}^d, C(\mathcal{P}^d, \mathcal{U}^d)}}\right), \\ \mathcal{P} *_2 \mathcal{U} &= \left({{ c(\mathcal{P}, \mathcal{U})^d \cup ((\mathcal{P} \cup \mathcal{U}) \backslash c(\mathcal{P}, \mathcal{U})), C(\mathcal{P}^d, \mathcal{U}^d) }}\right). \end{align*}

Informally, $*_0$ makes all rules from $\mathcal{P}$ and $\mathcal{U}$ defeasible and gives preference to every rule from $\mathcal{U}$ over any rule from $\mathcal{P}$ . The operator $*_1$ produces a more cautious preference relation, only preferring rules from $\mathcal{U}$ over rules from $\mathcal{P}$ with conflicting heads. In addition, the operator $*_2$ refrains from making defeasible rules that are not involved in any conflict.

It is argued by Delgrande et al. (2007) that these operators can be naturally generalised to account for arbitrary (finite) sequences of programs as follows:

\begin{align*} * (\langle \mathcal{P}_i \rangle_{i < n}) = \begin{cases} \mathcal{P}_0 * \mathcal{P}_1 & \text{if $n = 2$} ,\\ * (\langle \mathcal{P}_i \rangle_{i < n - 1}) * \mathcal{P}_{n - 1} & \text{if $n > 2$}. \end{cases}\\[-26pt]\end{align*}

This definition is slightly incomplete since the result of operators $*_0$ , $*_1$ , and $*_2$ is not an ordinary logic program but a prioritised one. The question then arises as to what happens with the priority relation of an intermediate result, say $\mathcal{P}_0 * \mathcal{P}_1$ , when it is further updated by $\mathcal{P}_2$ . In the following, we assume that the preference relations are merged and measures are taken to ensure that the merged relation remains a strict partial order, that is, transitivity is enforced after the merge. We can now define the update semantics by Delgrande et al. (2007) for arbitrary DLPs. We call them the $\mathsf{PRX}_i$ semantics with $\mathsf{X}$ representing the preference strategy (i.e., $\mathsf{X}$ is one of $\mathsf{D}$ , $\mathsf{X}$ , or $\mathsf{B}$ ), and i denoting the particular operator used for forming the prioritised logic program (i.e., $i \in {0, 1, 2}$ ).

Definition 31 ( $\mathsf{PRX}_i$ Semantics Delgrande et al. 2007) Let $\boldsymbol{P}$ be a DLP without default negation in heads of rules, $\mathsf{X}$ be one of $\mathsf{D}$ , $\mathsf{X}$ , or $\mathsf{B}$ , and $i \in {0, 1, 2}$ . The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{PRX_i}}$ of $\mathsf{PRX}_i$ models of $\boldsymbol{P}$ is the set of preferred stable models of the prioritised logic program $*_i (\boldsymbol{P})$ under the preference strategy $\mathsf{X}$ .

The overall properties of these rule update semantics depend on the chosen operator ( $*_0$ , $*_1$ , or $*_2$ ) and on the chosen preference strategy ( $\mathsf{D}$ -, $\mathsf{X}$ -, or $\mathsf{B}$ -preference). Nevertheless, as Delgrande et al. (2007) illustrated by examples, all $\textsf{PRX}_i$ semantics are sensitive to tautological updates. In addition, the following example shows an interesting behaviour that distinguishes these semantics from the previously discussed ones:

Example 32 (Default Assumptions vs. Facts Delgrande et al. 2007) Consider the programs

\begin{align*} \begin{aligned} \mathcal{P}: && \lnot \mathsf{p} &. \end{aligned} && \text{and} && \begin{aligned} \mathcal{U}: && \mathsf{p} &\leftarrow \mathop{\sim\!} \lnot \mathsf{p}. \end{aligned} \end{align*}

and let $\boldsymbol{P} = \langle \mathcal{P}, \mathcal{U} \rangle$ . For any operator $*_i$ and preference strategy $\mathsf{X}$ , $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{PRX_i}} = {{\mathsf{p}}}$ . This indicates that the default assumption in the updating program is given preference over the fact in the initial program. If we interpret $\mathsf{p}$ as $\mathsf{man}(\mathit{mary})$ , then this example shows that if initially $\mathsf{man}(\mathit{mary})$ is known to be false and later we learn that

\begin{equation*} \mathsf{man}(\mathbf{x}) \leftarrow \mathop{\sim\!} \lnot \mathsf{man}(\mathbf{x}). , \end{equation*}

meaning that by default all individuals are men, then this immediately changes our knowledge about $\mathsf{man}(\mathit{mary})$ : we now know that $\mathsf{man}(\mathit{mary})$ is true!

It seems more natural to give preference to initial facts over default assumptions in more recent rules. Note that $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{AS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}} = {{\mathsf{p}}, {\lnot \mathsf{p}}}$ and $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{DS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RD}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{PRZ}} = {{\lnot \mathsf{p}}}$ , that is, the causal rejection semantics with unrestricted set of default assumptions allow both ${\mathsf{p}}$ and ${\lnot \mathsf{p}}$ to be stable models of $\boldsymbol{P}$ while the “fixed” versions of these semantics together with Zhang’s preference-based semantics actually prefer the initial fact over the default assumption.

5.3 Other approaches

5.3.1 The $\textsf{RVS}$ semantics

Sakama and Inoue (2003) have proposed a rule update semantics that is clearly based on ideas from belief revision, similarly as formula-based belief update operators. In particular, they define that a program $\mathcal{P}' \cup \mathcal{U}$ achieves the update of $\mathcal{P}$ by $\mathcal{U}$ if $\mathcal{P}'$ is a maximal subset of $\mathcal{P}$ such that $\mathcal{P}' \cup \mathcal{U}$ is coherent, that is, it has a stable model.

As with the $\textsf{PRZ}$ semantics, we define the semantics of Sakama and Inoue (2003) only for DLPs of length two because it is not clear how one should deal with multiple results of an update. We call the resulting semantics the $\textsf{RVS}$ semantics:

Definition 33 ( $\textsf{RVS}$ Semantics Sakama and Inoue 2003) Let $\boldsymbol{P} = \langle \mathcal{P}, \mathcal{U} \rangle$ be a DLP. The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RVS}}$ of $\textsf{RVS}$ models of $\boldsymbol{P}$ is the union of sets of stable models of all programs $\mathcal{P}' \cup \mathcal{U}$ where $\mathcal{P}'$ is a maximal subset of $\mathcal{P}$ such that $\mathcal{P}' \cup \mathcal{U}$ is coherent.

Similarly to the $\textsf{PRZ}$ semantics, as discussed in Example 27, the approach adopted by the $\textsf{RVS}$ semantics pays no attention to the source of conflicts – any solution of a conflict is as good as any other as long as only a minimal set of rules is eliminated. Another consequence is that conflicts are removed at any cost, even if there is no plausible way to explain why the update should restore coherence. This has been criticised by Leite (2003), who argued that every conflict has several causes and each type of conflict should be dealt with accordingly. One consequence of this is that an empty or tautological update may restore coherence (and consistency) of an initial program. If we compare this to belief change principles and operators, such a behaviour is typical of revision but is not desirable for updates. Garcia et al. (2019) introduced a family of revision operators for logic programs similar in spirit to the $\textsf{RVS}$ semantics, except that they allow both for the addition and/or removal of rules from a logic program to achieve coherence. As with the $\textsf{RVS}$ semantics, these operators are sensitive to empty or tautological updates.

5.3.2 The $\textsf{RVD}$ semantics

Similar ideas form the basis of the rule revision semantics proposed by Delgrande (2010). Note that since the distinction between program update and revision, as these terms are used in the literature, is somewhat blurry, in the following we also refer to this semantics as an update semantics. Informally, the stable model of a sequence of programs is constructed by first keeping all rules from the last program and committing to a minimal set of default literals used to derive one of its stable models. Subsequently, a maximal coherent subset of the previous program is added and further commitments are made. This process is iterated until the first program of the sequence is processed, as illustrated by the following example.

Example 34 Consider the DLP

\begin{equation*} \boldsymbol{P} = \langle {\mathsf{p}.}, {\mathsf{q}.}, {\mathsf{r} \leftarrow \mathop{\sim\!} \mathsf{p}., \mathsf{r} \leftarrow \mathop{\sim\!} \mathsf{q}.} \rangle . \end{equation*}

We start with the last program of the sequence which has the stable model ${\mathsf{r}}$ . This stable model can be derived either using the literal $\mathop{\sim\!} \mathsf{p}$ or $\mathop{\sim\!} \mathsf{q}$ and we need to choose one of these and commit to it. If we pick the former, the overall set of literals we commit to at this stage is ${\mathop{\sim\!} \mathsf{p}, \mathsf{r}}$ . We then proceed to the second program and realise that it is coherent with our commitments as well as the rules from the last program. We thus add $\mathsf{q}$ to our set of commitments and the fact $(\mathsf{q}.)$ to the set of rules that we are going to keep. Proceeding to the first program of the sequence, the rule within it is inconsistent with our commitment to $\mathop{\sim\!} \mathsf{p}$ , so the rule needs to be discarded. The set of objective literals we committed to until now, namely ${\mathsf{q}, \mathsf{r}}$ , forms one stable model of $\boldsymbol{P}$ . Note that if we initially commit to $\mathop{\sim\!} \mathsf{q}$ , we obtain the stable model ${\mathsf{p}, \mathsf{r}}$ .

To formalise this construction, Delgrande (2010). uses three-valued interpretations, defined as pairs of disjoint interpretations $J = (J^+,J^-)$ , which we dub three-valued d-interpretations to distinguish from the three-valued interpretations used elsewhere in this paper, based on which a modified notion of reduct of a program $\mathcal{P}$ without default negation in the head is defined as

\begin{equation*}\mathcal{P}^J = \{\langle S^+[H(\pi)] \leftarrow S^+[B(\pi)]\cup\mathop{\sim\!}S^-[B(\pi)]\backslash J^- \rangle | \pi \in \mathcal{P} \land J^+ \cap S^-[B(\pi)] = \emptyset\}.\end{equation*}

This reduct is used to define a special notion of three-valued answer-sets of a program $\mathcal{P}$ which are those three-valued d-interpretations $J = (J^+,J^-)$ such that $\mathsf{least}(\mathcal{P}^{J^+})=\mathsf{least}(\mathcal{P}^{J})=J^+$ and for any $I = (J^+,I^-)$ such that $I^- \subset J^-$ we have that $\mathsf{least}(P^{I}) \neq J^+$ , where $\mathsf{least}(\cdot)$ is as before. Additionally, Delgrande (2010). defines a concept of canonical program corresponding to a three-valued d-interpretation $J = (J^+,J^-)$ as

\begin{equation*}Pgm(J)=\{ \mathsf{p}. \mid \mathsf{p} \in J^+ \}\;\cup\;\{ \leftarrow \mathsf{p}. \mid \mathsf{p} \in J^- \}.\end{equation*}

Then, given a DLP without default negation in heads of rules $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n+1}$ , an interpretation J is an r-answer-set of $\boldsymbol{P}$ iff there is a sequence $\langle (\mathcal{P}^r_i,J_i) \rangle_{i < n+1}$ such that

1. 1. $\mathcal{P}^r_n = \mathcal{P}_n$ and $J_n$ is a three-valued answer-set of $\mathcal{P}_n$ ;

2. 2. for $i < n$ , $\mathcal{P}^r_i$ is a maximal set of rules of $\mathcal{P}_i$ consistent with $\mathcal{P}^r_{i+1} \cup Pgm(J_{i+1})$ (or $\mathscr{L}$ if $\mathcal{P}^r_{i+1} \cup Pgm(J_{i+1})$ is inconsistent) and $J_i$ is a three-valued answer-set of $\mathcal{P}^r_i$ ;

3. 3. $J=J^+_1$ .

We refer to this semantics as the $\textsf{RVD}$ semantics:

Definition 35 ( $\textsf{RVD}$ Semantics Delgrande 2010) Let $\boldsymbol{P}$ be a DLP without default negation in heads of rules. The set $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RVD}}$ of $\textsf{RVD}$ models of $\boldsymbol{P}$ is the set of r-answer-sets of $\boldsymbol{P}$ .

Similarly as the $\textsf{RVS}$ semantics, the $\textsf{RVD}$ semantics resolves conflicts at any cost, a consequence of which is that empty and tautological updates restore coherence and consistency. Furthermore, it exhibits the same behaviour as the $\textsf{PRX}_i$ semantics in Example 32, that is, it prefers to satisfy default assumptions in further programs to satisfying earlier facts. It actually goes even further than the $\textsf{PRX}_i$ semantics, as illustrated in the following example:

Example 36 (Default Assumptions vs. Facts in the $\textsf{RVD}$ semantics) Consider the programs

\begin{align*} \begin{aligned} \mathcal{P}: && \mathsf{p} &. \end{aligned} && \text{and} && \begin{aligned} \mathcal{U}: && \mathsf{q} &\leftarrow \mathop{\sim\!} \mathsf{p}. \end{aligned} \end{align*}

and let $\boldsymbol{P} = \langle \mathcal{P}, \mathcal{U} \rangle$ . We obtain $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RVD}} = {{\mathsf{q}}}$ , as opposed to $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{AS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{DS}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RD}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{PRZ}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{PRX_i}} = [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{RVS}} = {{\mathsf{p}}}$ . This indicates that the default assumptions in the updating program are given preference over facts from the initial program even more aggressively than in case of the $\textsf{PRX}_i$ semantics. If we interpret $\mathsf{p}$ as $\mathsf{dog}(\mathit{bo})$ and $\mathsf{q}$ as $\lnot \mathsf{canBark}(\mathit{bo})$ , then this example shows that if initially $\mathsf{dog}(\mathit{bo})$ is known to be true and later we learn that

\begin{equation*} \lnot \mathsf{canBark}(\mathbf{x}) \leftarrow \mathop{\sim\!} \mathsf{dog}(\mathbf{x}). , \end{equation*}

meaning that, by default, individuals that are not dogs cannot bark, then this immediately modifies our knowledge about $\mathit{bo}$ : we no longer know whether $\mathsf{dog}(\mathit{bo})$ is true or not and, in addition, we conclude that $\mathsf{canBark}(\mathit{bo})$ is (explicitly) false. Poor $\mathit{bo}$ …

A methodology based on maximal subsets of the initial program coherent with its update was also used by Osorio and Zepeda (2007) for updating programs under the pstable model semantics. The idea is used indirectly by augmenting the bodies of original rules with additional literals and using an abductive framework to minimise the set of rules “disabled” by falsifying the added literal. We do not further consider this semantics because it diverges from the standard notion of a stable model and uses pstable models instead.

Finally, there also exist approaches based on a semantic framework that directly encodes literal dependencies induced by rules, and performs changes on the dependencies instead of on the rules themselves. The advantage over dealing with rules is that the dependency relation is monotonic, so AGM postulates and operators can be applied to it directly (KrÜmpelmann and Kern-Isberner 2010; KrÜmpelmann 2012). In the work of SefrÁnek (2006, 2011), the dependency framework is used for specifying irrelevant updates, an instance of which are tautological updates, and designing update semantics immune to such irrelevant updates.

5.4 Fundamental properties

As demonstrated above, rule update semantics are based on a number of different approaches and constructions and provide different results even on very simple examples.

In this section, we indicate and examine some fundamental properties of rule update semantics. We call them syntactic because they have been discussed in the context of syntax-based semantics for rule updates and, with only two exceptions, their formulation requires that we refer to the syntax of the respective DLP. The first three properties, as well as the last one, will be satisfied by all rule update semantics that we formally introduced above. The remaining four will only be satisfied by a subset of the semantics, serving as entry points for comparing them.

Recall that the distinct semantics have been defined for different classes of DLPs, with the assumption that none contained integrity constraints. The properties defined below do not have that assumption. When we say that a semantics $\mathsf{S}$ satisfies a particular property, we constrain ourselves only to DLPs in the scope of the definition of $\mathsf{S}$ . The classes of DLPs to which the introduced semantics are applicable is summarized in Table 2.

Table 2. Applicability of rule update semantics

The reader can find a systematic account of the proofs of the theorems in this subsection in the PhD thesis by Slota (2012), either by presenting the proof or pointing to the relevant paper where the result was first proved.

The first fundamental property captures the fact that rule update semantics produce only supported models. In a static setting, support (Apt et al. 1988; Dix 1995) is one of the basic conditions that logic programming semantics are intuitively designed to satisfy. Its generalisation to the dynamic case is straightforward.

Definition 37 (Support) Let $\mathsf{S}$ be a rule update semantics, $\mathcal{P}$ a program, l an objective literal and J an interpretation. We say that

• $\mathcal{P}$ supports l in J if for some rule $\pi \in \mathcal{P}$ , $l \in H(\pi)$ , and $J \mathrel\mid= B(\pi)$ ;

• $\mathcal{P}$ supports J if every objective literal $l \in J$ is supported by $\mathcal{P}$ in J;

• $\mathsf{S}$ respects support if for every DLP $\boldsymbol{P}$ to which $\mathsf{S}$ is applicable and every $\mathsf{S}$ -model J of $\boldsymbol{P}$ , $\mathsf{all}(\boldsymbol{P})$ supports J.

In other words, a rule update semantics $\mathsf{S}$ respects support if every objective literal l that is true in an $\mathsf{S}$ -model of a DLP is the head of some rule of that DLP whose body is true in the same model. Such a rule then provides a justification for l.

A consequence of support is that the rule update semantics satisfies language conservation, defined as follows:

Definition 38 (Language Conservation for Rule Updates) Let $\mathsf{S}$ be a rule update semantics. We say that $\mathsf{S}$ conserves the language if for every set $\mathcal{L}$ of propositional variables, every DLP $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ to which $\mathsf{S}$ is applicable, and every $\mathsf{S}$ -model J of $\boldsymbol{P}$ , if $\mathsf{pr}(\mathcal{P}_i) \subseteq \mathcal{L}$ for all $i < n$ , then $\mathsf{pr}(J) \subseteq \mathcal{L}$ . Where $\mathsf{pr}(\mathcal{P}_i)$ (resp. $\mathsf{pr}(J)$ ) denotes the set of all propositional variables appearing in $\mathcal{P}_i$ (resp. J).

Informally, if both the initial and updating theories represent knowledge about propositional variables from the set $\mathcal{L}$ , then the updated theory should not introduce knowledge about propositional variables that do not belong to $\mathcal{L}$ .

Though support and language conservation are basic requirements, and certainly too weak to be sufficient for a “good” rule update semantics, they seem to be intuitive from the logic programming perspective. And, indeed, they are satisfied by all rule update semantics that we introduced previously.

Theorem 39 (Respect for Support and Language Conservation) Let $\mathsf{X}$ be one of $\mathsf{D}$ , $\mathsf{X}$ , $\mathsf{B}$ and $i \in {0, 1, 2}$ . The rule update semantics $\textsf{AS}$ , $\textsf{JU}$ , $\textsf{DS}$ , $\textsf{RD}$ , $\textsf{PRZ}$ , $\textsf{PRX}_i$ , $\textsf{RVS}$ , and $\textsf{RVD}$ respect support and conserve the language.

The third fundamental property for rule update semantics expresses the usual expectation regarding how facts should be updated by newer facts.

Definition 40 (Fact Update) Let $\mathsf{S}$ be a rule update semantics. We say that $\mathsf{S}$ respects fact update if for every finite sequence $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ of consistent sets of facts to which $\mathsf{S}$ is applicable, the unique $\mathsf{S}$ -model of $\boldsymbol{P}$ is the interpretation

\begin{equation*} \{ l \in \mathscr{L} | \exists j < n : (l.) \in \mathcal{P}_j \land(\forall i : j < i < n \Longrightarrow {\overline{l}., \mathop{\sim\!} l.} \cap \mathcal{P}_i = \emptyset ) \}.\end{equation*}

Fact update enforces literal inertia, which forms the basis for belief update operators such as the one by Winslett, but only for the case when both the initial program and its updates are consistent sets of facts. Similarly as before, all rule update semantics adhere to this property.

Theorem 41 (Respect for Fact Update) Let $\mathsf{X}$ be one of $\mathsf{D}$ , $\mathsf{X}$ , $\mathsf{B}$ and $i \in {0, 1, 2}$ . The rule update semantics $\textsf{AS}$ , $\textsf{JU}$ , $\textsf{DS}$ , $\textsf{RD}$ , $\textsf{PRZ}$ , $\textsf{PRX}_i$ , $\textsf{RVS}$ , and $\textsf{RVD}$ respect fact update.

The fourth and fifth syntactic properties are fundamental for all semantics based on causal rejection. The first of them is the causal rejection principle itself.

Definition 42 (Causal Rejection) Let $\mathsf{S}$ be a rule update semantics. We say that $\mathsf{S}$ respects causal rejection if for every DLP $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ to which $\mathsf{S}$ is applicable, every $\mathsf{S}$ -model J of $\boldsymbol{P}$ , all $i < n$ , and all rules $\pi \in \mathcal{P}_i$ ,

\begin{equation*} J \not\mathrel\mid= \pi \enspace\enspace\enspace\text{implies}\enspace\enspace\enspace \exists j \, \exists \sigma : i < j < n \land \sigma \in \mathcal{P}_j^{\mathsf{e}} \land \pi \Join \sigma \land J \mathrel\mid= B(\pi)[\sigma].\end{equation*}

This principle requires a cause for every violated rule in the form of a more recent rule with a conflicting head and a satisfied body. It is hard-wired in the definitions of sets of rejected rules of the four rule update semantics that are based on it.

Theorem 43 (Respect for Causal Rejection) The rule update semantics $\textsf{AS}$ , $\textsf{JU}$ , $\textsf{DS}$ , and $\textsf{RD}$ respect causal rejection.

Example 44 The following examples illustrate why each of the rule update semantics $\textsf{PRZ}$ , $\textsf{PRX}_i$ , $\textsf{RVS}$ , and $\textsf{RVD}$ does not respect causal rejection.

\begin{align*} &\boldsymbol{P}_1 = \langle {\mathsf{p} \leftarrow \mathsf{q}.,\lnot\mathsf{p} \leftarrow \mathsf{q}.}, {\mathsf{q}.} \rangle\text{, where } [\kern-.3ex[{\boldsymbol{P}_1}]\kern-.3ex]_{\mathsf{PRZ}} = {{\lnot \mathsf{p}, \mathsf{q}}, {\mathsf{p},\mathsf{q}}};\\ &\boldsymbol{P}_2 = \langle {\mathsf{p}.,\lnot\mathsf{p}.}, {\mathsf{q} \leftarrow \mathsf{p}.} \rangle\text{, where } [\kern-.3ex[{\boldsymbol{P}_2}]\kern-.3ex]_{\mathsf{PR{B}_{0}}} = [\kern-.3ex[{\boldsymbol{P}_2}]\kern-.3ex]_{\mathsf{PR{B}_{1}}} = {{\lnot\mathsf{p}},{\mathsf{p},\mathsf{q}}};\\ &\boldsymbol{P}_3 = \langle {\mathsf{p}.,\lnot\mathsf{p}.}, {\mathsf{q} \leftarrow \mathsf{p}.} \rangle\text{, where } [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{PR{D}_{0}}} = [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{PR{D}_{1}}} = [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{PR{W}_{0}}} = [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{PR{W}_{1}}} = {{\lnot\mathsf{p}}};\\ &\boldsymbol{P}_4 = \langle {\mathsf{p}.,\lnot\mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{q}.,\lnot\mathsf{p} \leftarrow \mathsf{q}.} \rangle\text{, where } [\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{PR{B}_{2}}} = [\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{PR{D}_{2}}} = [\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{PR{W}_{2}}}\\ &\quad = {{\lnot\mathsf{p}},{\mathsf{p}}};\\ &\boldsymbol{P}_5 = \langle {\mathsf{p} \leftarrow \mathop{\sim\!}\mathsf{p}.}, {} \rangle\text{, where } [\kern-.3ex[{\boldsymbol{P}_5}]\kern-.3ex]_{\mathsf{RVS}} = {{}}; \text{ and }\\ &\boldsymbol{P}_6 = \langle {\mathsf{p}.}, {\mathsf{q} \leftarrow \mathop{\sim\!}\mathsf{p}.} \rangle\text{, where } [\kern-.3ex[{\boldsymbol{P}_6}]\kern-.3ex]_{\mathsf{RVD}} = {{\mathsf{q}}}.\end{align*}

The sixth syntactic property stems from the fact that all rule update semantics based on causal rejection coincide on acyclic DLPs (Homola 2004; Alferes et al. 2005). Thus, the behaviour of any rule update semantics on acyclic DLPs can be used as a way to compare it to all these semantics simultaneously.

Definition 45 (Acyclic Justified Update) Let $\mathsf{S}$ be a rule update semantics. We say that $\mathsf{S}$ respects acyclic justified update if for every acyclic DLP $\boldsymbol{P}$ to which $\mathsf{S}$ is applicable, the set of $\mathsf{S}$ -models of $\boldsymbol{P}$ coincides with $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}}$ .

Theorem 46 (Respect for Acyclic Justified Update) The rule update semantics $\textsf{AS}$ , $\textsf{JU}$ , $\textsf{DS}$ , and $\textsf{RD}$ respect acyclic justified update.

The next property has been extensively discussed in the literature, and has been at the heart of the motivation for developing some of the variants of semantics based on causal rejection. It requires that the semantics be immune to tautological updates (i.e., an update composed only of rules whose head literal also belongs to its body), the intuition being that such update cannot indicate any change in the modelled world because it is always true. Immunity to tautological updates is a desirable property of belief updates in classical logic, being a direct consequence of postulate $\mathsf{BU2}$ .

Definition 47 (Immunity to Tautological Updates) Let $\mathsf{S}$ be a rule update semantics, $\pi$ a tautological rule, and $\boldsymbol{P}^{\pi}$ the DLP obtained from DLP $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ by appending $\mathcal{P}_n=\{\pi\}$ . We say that $\mathsf{S}$ respects immunity to tautological updates if for every DLP $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ and every tautological rule $\pi$ such that $\mathsf{S}$ is applicable to $\boldsymbol{P}^{\pi}$ , $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{S}}=[\kern-.3ex[{\boldsymbol{P}^{\pi}}]\kern-.3ex]_{\mathsf{S}}$ .

As it turns out, only the $\textsf{RD}$ semantics is immune to tautological updates.

Theorem 48 (Immunity to Tautologies) The rule update semantics $\textsf{RD}$ respects immunity to tautological updates.

The remaining semantics are not immune to tautologies for one of the following three reasons:

1. 1. the tautology can be used to reject other rules, as is the case with most semantics based on causal rejection, namely $\textsf{AS}$ , $\textsf{JU}$ , and $\textsf{DS}$ , such as for example

   \begin{align*}&\boldsymbol{P}_1 = \langle {\mathsf{p}., \lnot \mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{p}.} \rangle \text{, where } [\kern-.3ex[{\boldsymbol{P}_1}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}_1}]\kern-.3ex]_{\mathsf{AS}} = [\kern-.3ex[{\boldsymbol{P}_1}]\kern-.3ex]_{\mathsf{DS}}= {{\mathsf{p}}};\\[3pt]&\boldsymbol{P}_2 = \langle {\mathsf{p}.}, {\lnot \mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{p}.} \rangle \text{, where } [\kern-.3ex[{\boldsymbol{P}_2}]\kern-.3ex]_{\mathsf{AS}} = {{\lnot \mathsf{p}} {\mathsf{p}}};\\[3pt]&\boldsymbol{P}_3 = \langle {\mathsf{p}.}, {\mathop{\sim\!} \mathsf{p} \leftarrow \mathop{\sim\!} \mathsf{p}.} \rangle \text{, where } [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{JU}} = [\kern-.3ex[{\boldsymbol{P}_3}]\kern-.3ex]_{\mathsf{AS}} = {\emptyset, {\mathsf{p}}};\end{align*}

2. 2. the tautology can be used as a reason not to prefer other rules, as is the case with semantics based on preferences, namely $\textsf{PRZ}$ and $\textsf{PRX}_i$ (for $\mathsf{X}$ be one of $\mathsf{D}$ , $\mathsf{X}$ , $\mathsf{B}$ and $i \in {0, 1, 2}$ ), such as for example

   \begin{align*}&\boldsymbol{P}_4 = \langle {\mathsf{p} \leftarrow \mathop{\sim\!} \lnot \mathsf{p}., \lnot\mathsf{p}\leftarrow\mathop{\sim\!}\mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{p}.} \rangle \text{, where } [\kern-.3ex[{\boldsymbol{P}_4}]\kern-.3ex]_{\mathsf{PRZ}} = {{\mathsf{p}}};\\[3pt]&\boldsymbol{P}_5 = \langle {\mathsf{p} \leftarrow \mathop{\sim\!} \lnot \mathsf{p}., \lnot\mathsf{p}.}, {\mathsf{p} \leftarrow \mathsf{p}.} \rangle \text{, where } [\kern-.3ex[{\boldsymbol{P}_5}]\kern-.3ex]_{\mathsf{PRX_i}} = {{\mathsf{p}}};\end{align*}

3. 3. conflicts are resolved at any cost, as is the case with the $\textsf{RVS}$ and $\textsf{RVD}$ semantics, such as for example

   \begin{align*}&\boldsymbol{P}_6 = \langle {\mathsf{p} \leftarrow \mathop{\sim\!} \mathsf{p}.}, {\mathsf{q} \leftarrow \mathsf{q}.} \rangle \text{, where } [\kern-.3ex[{\boldsymbol{P}_6}]\kern-.3ex]_{\mathsf{RVS}} =[\kern-.3ex[{\boldsymbol{P}_6}]\kern-.3ex]_{\mathsf{RVD}} = {\emptyset};\\[3pt]&\boldsymbol{P}_7 = \langle {\mathsf{p}., \lnot\mathsf{p}.}, {\mathsf{q} \leftarrow \mathsf{q}.} \rangle \text{, where } [\kern-.3ex[{\boldsymbol{P}_7}]\kern-.3ex]_{\mathsf{RVS}} = [\kern-.3ex[{\boldsymbol{P}_7}]\kern-.3ex]_{\mathsf{RVD}} = {{\mathsf{p}},{\lnot\mathsf{p}}}.\end{align*}

The next two properties are no longer syntactical as the ones considered so far, but we mention them here since they have been often discussed together with the semantics considered in this section.

The first one can be seen as a weaker version of immunity to tautological updates. It imposes that semantics be immune to empty updates, and is obeyed by a larger set of semantics.

Definition 49 (Immunity to Empty Updates) Let $\mathsf{S}$ be a rule update semantics and $\boldsymbol{P}^\emptyset$ the DLP obtained from DLP $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ by appending $\mathcal{P}_n=\emptyset$ . We say that $\mathsf{S}$ respects immunity to empty updates if for every DLP $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i < n}$ such that $\mathsf{S}$ is applicable to $\boldsymbol{P}^\emptyset$ , $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{S}}=[\kern-.3ex[{\boldsymbol{P}^\emptyset}]\kern-.3ex]_{\mathsf{S}}$ .

Theorem 50 (Immunity to Empty Updates) Let $\mathsf{X}$ be one of $\mathsf{D}$ , $\mathsf{X}$ , or $\mathsf{B}$ . The rule update semantics $\textsf{AS}$ , $\textsf{JU}$ , $\textsf{DS}$ , $\textsf{RD}$ , $\textsf{PRZ}$ , and $\textsf{PRX}_2$ respect immunity to empty updates.

There has been a considerable amount of discussion regarding whether immunity to empty updates should be considered a desirable property. At the heart of such discussion is the fact that most counter-examples used to show why some semantics does not obey this property involve incoherent/contradictory programs whose coherence/consistency is restored through an empty update. Two arguments are usually used to support the adequacy of this property, and why coherence/consistency should not be regained no matter what.

The first argument is conceptual, and related to the difference between revision and update. Since revision is about incorporating better knowledge about some world that did not change, there is an implicit assumption that the initial knowledge was not perfect (complete, correct,…), which can somehow be used to justify the removal of inconsistencies/incoherences, even if better explicit knowledge to incorporate is not available, as indicated by an empty program. On the contrary, an update is about incorporating new knowledge about a world that changed. The knowledge about the old world might be a bad representation of the new world, but there is no underlying assumption that it was an imperfect representation of the old world, that is, it could simply be that the old world being represented is simply incoherent/inconsistent. And, if nothing changed in that incoherent/inconsistent world, as indicated by the empty program, we should still take it to remain incoherent/inconsistent.

The second argument is more pragmatic, and tied to the answer-set programming methodology for problem solving (Marek and TruszczyŃski 1999; NiemelÄ 1999; Lifschitz 1999), where stable models correspond to solutions to the problem, and the lack of existing stable models simply means that the problem has no solutions. As a concrete example, suppose that a logic program encodes the well-known n-queens problem, and includes some facts encoding the queens that have already been placed on the chessboard. Stable models will correspond to possible solutions to the n-queens problem, indicating where queens should be further placed, given the ones already on the board. To enforce this, the program would have several rules, acting as integrity constraints, encoding that no two queens should be placed in the same column, line or diagonal. Suppose that the initial program encodes a situation where two queens have already been placed in the same column, hence without stable models. It seems clear that an update by an empty program, encoding that no further queens have been added or removed, should not change the fact that those two queens are still attacking each other, and no solution can exist with them on the board, that is, the program should still have no stable models after the update.

The last property mentioned here – primacy of new information (Dalal 1988) – is at the heart of every update operator, independently of the base formalism for which it is defined. It corresponds to postulate $\mathsf{BR1}$ in belief updates, and conveys the fact that the models produced by a rule update semantics should conform to the new information, captured by the following definition:

Definition 51 (Primacy of New Information) Let $\mathsf{S}$ be a rule update semantics. We say that $\mathsf{S}$ respects primacy of new information if for every DLP $\boldsymbol{P} = \langle \mathcal{P}_i \rangle_{i \leq n}$ to which $\mathsf{S}$ is applicable and every $\mathsf{S}$ -model J of $\boldsymbol{P}$ , $J\models\mathcal{P}_n$ .

Primacy of new information is satisfied by all rule update semantics that we considered so far.

Theorem 52 (Respect for Primacy of New Information) Let $\mathsf{X}$ be one of $\mathsf{D}$ , $\mathsf{X}$ , or $\mathsf{B}$ and $i \in {0, 1, 2}$ . The rule update semantics $\textsf{AS}$ , $\textsf{JU}$ , $\textsf{DS}$ , $\textsf{RD}$ , $\textsf{PRZ}$ , $\textsf{PRX}_i$ , $\textsf{RVS}$ , and $\textsf{RVD}$ respect primacy of new information.

6 The third era – semantics-based updates

Though useful in practical scenarios (Alferes et al. 2003; Saias and Quaresma 2004; Siska 2006; Ilic et al. 2008; Slota et al. 2011), it turned out that most of the syntax-based semantics exhibit some undesirable behaviour. For example, except for the semantics proposed by Alferes et al. (2005), a tautological update may influence the result under all of these semantics, a behaviour that is highly undesirable when considering knowledge updates. But, more importantly, the common feature of all of these semantics is that they make heavy use of the syntactic structure of programs and rules, while lacking some semantic characterisation that would allow, for example, some adequate notion of equivalence under updates. This is a well known problem associated with these semantics (Eiter et al. 2002; Leite 2003; Slota 2012), which has prevented a more thorough analysis and understanding of their semantic properties.

6.1 Operators based on $\textsf{HT}$ models

Recently, AGM revision was reformulated in the context of logic programming in a manner analogous to belief revision in classical propositional logic, and specific revision operators for logic programs were investigated by Delgrande et al. (2008, 2013) and by Osorio and Cuevas (2007). Central to this novel approach are $\textsf{HT}$ models, based on the logic of here-and-there (Heyting 1930; Pearce 1997), which provide a monotonic semantic characterisation of logic programs that is strictly more expressive than the answer-set semantics in the sense that it is possible to determine the answer-sets of a program from its set of $\textsf{HT}$ models, but not vice-versa that is, there are programs with the same set of answer-sets but different sets of $\textsf{HT}$ models. Furthermore, two programs have the same set of $\textsf{HT}$ models if and only if they are strongly equivalent (Lifschitz et al. 2001), which means that programs $\mathcal{P}, \mathcal{Q}$ with the same set of $\textsf{HT}$ models can be modularly replaced by one another, even in the presence of additional rules, without affecting the resulting answer-sets.

Indeed, these investigations constitute an important breakthrough in the research of answer-set program evolution. They change the focus from the syntactic representation of a program, where not all rules and literal occurrences are necessarily relevant to its meaning as a whole, to its semantic content, that is, to the information that the program is intended to represent.

Subsequently, Slota and Leite (2010, 2014) followed a similar path, but to tackle the problem of answer-set program updates, instead of revision as tackled by Delgrande et al. (2008, 2013). The studied operators are semantic in their very nature and in line with KM postulates for updates, in contrast with the traditional syntax-based approaches to rule updates described in the previous section. Others have followed this path of defining change operators for logic programs characterised by their $\textsf{HT}$ models. For example, Zhuang et al. (2016) introduced a revision operator that adds and/or removes rules from a logic program while minimising the symmetric difference between $\textsf{HT}$ models. Binnewies et al. (2018) introduced partial meet and ensconcement constructions for logic program belief change, which allowed them to define revision and contraction operators.

In this subsection, we first briefly review the revision approach of Delgrande et al. (2008, 2013) and the update approach of Slota and Leite (2010, 2014). Then, we discuss a serious drawback which extends to all rule update operators that characterise logic programs through their $\textsf{HT}$ models. It turns out that both these revision and the update operators are incompatible with the properties of support and fact update, which are at the core of rule updates (cf. Theorems 39 and 41). This is a very important finding as it guides the research on rule revision and updates away from the semantic approach materialised in AGM and KM postulates or, alternatively, to the development of semantic characterisations of programs, richer than $\textsf{HT}$ models, that are appropriate for describing their dynamic behaviour.

Before we proceed, and in order to reformulate some of the postulates for programs under the $\textsf{HT}$ models semantics, we assume some given program conjunction and disjunction operators $\mathbin{\dot{\wedge}}$ , $\mathbin{\dot{\lor}}$ , where each assigns, to each pair of programs, a program whose set of $\textsf{HT}$ models is the intersection and union, respectively, of the sets of $\textsf{HT}$ models of argument programs. The program conjunction operator may simply return the union of argument programs – it is the same as the expansion operator defined by Delgrande et al. (2008, 2013) – while the program disjunction operator can be defined by translating the argument programs into the logic of here-and-there (Heyting 1930; Lukasiewicz 1941; Pearce 1997), taking their disjunction, and transforming the resulting formula back into a logic program (using results by Cabalar and Ferraris 2007).

In this section, we no longer restrict programs and DLPs to those without integrity constraints.

6.1.1 Revision based on $\textsf{HT}$ models

For a rule revision operator $\mathbin{\otimes}$ and programs $\mathcal{P}$ , $\mathcal{Q}$ , $\mathcal{U}$ , $\mathcal{V}$ , acording to Delgrande et al. (2008, 2013), the KM postulates for belief revision are adapted to answer-set program revision using $\textsf{HT}$ models as follows:

1. ( $\textsf{PR1}_{\textsf{HT}}$ ) $\mathcal{P} \mathbin{\otimes} \mathcal{U} \mathrel\mid=_{\mathsf{HT}} \mathcal{U}$ .

2. ( $\textsf{PR2}_{\textsf{HT}}$ ) If $[\kern-.3ex[{\mathcal{P}\mathbin{\dot{\wedge}}\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}}\neq \emptyset$ , then $\mathcal{P} \mathbin{\otimes} \mathcal{U} \equiv_{\mathsf{HT}} \mathcal{P}\mathbin{\dot{\wedge}}\mathcal{Q}$ .

3. ( $\textsf{PR3}_{\textsf{HT}}$ ) If $[\kern-.3ex[{\mathcal{U}}]\kern-.3ex]_{\mathsf{HT}} \neq \emptyset$ , then $[\kern-.3ex[{\mathcal{P} \mathbin{\otimes} \mathcal{U}}]\kern-.3ex]_{\mathsf{HT}} \neq \emptyset$ . [ $\textsf{PR4}_{\textsf{HT}}$ ] If $\mathcal{P} \equiv_{\mathsf{HT}} \mathcal{Q}$ and $\mathcal{U} \equiv_{\mathsf{HT}} \mathcal{V}$ , then $\mathcal{P} \mathbin{\otimes} \mathcal{U} \equiv_{\mathsf{HT}} \mathcal{Q} \mathbin{\otimes} \mathcal{V}$ .

4. ( $\textsf{PR5}_{\textsf{HT}}$ ) $(\mathcal{P} \mathbin{\otimes} \mathcal{U}) \mathbin{\dot{\wedge}} \mathcal{V} \mathrel\mid=_{\mathsf{HT}} \mathcal{P} \mathbin{\otimes} (\mathcal{U} \mathbin{\dot{\wedge}} \mathcal{V})$ .

5. ( $\textsf{PR6}_{\textsf{HT}}$ ) If $[\kern-.3ex[{(\mathcal{P} \mathbin{\otimes} \mathcal{U})\mathbin{\dot{\wedge}}\mathcal{V}}]\kern-.3ex]_{\mathsf{HT}}\neq \emptyset$ then $\mathcal{P} \mathbin{\otimes} (\mathcal{U}\mathbin{\dot{\wedge}}\mathcal{V}) \mathrel\mid=_{\mathsf{HT}} (\mathcal{P} \mathbin{\otimes} \mathcal{U})\mathbin{\dot{\wedge}}\mathcal{V}$ .

As discussed by Delgrande et al. (2008, 2013) no $\mathbin{\otimes}$ can be immune to tautologies or empty updates – whenever $\mathcal{P}$ is unsatisfiable and $\mathcal{U}$ is tautological or empty, immunity to tautologies and immunity to empty updates conflicts with $\textsf{PR3}_{\textsf{HT}}$ . As also discussed by Delgrande et al. (2008, 2013) immunity to tautologies and empty updates could have been adopted instead of $\textsf{PR3}_{\textsf{HT}}$ .

Analogically to belief revision, a constructive characterisation of rule revision operators satisfying conditions $\textsf{PR1}_{\textsf{HT}}$ – $\textsf{PR6}_{\textsf{HT}}$ is based on an order assignment. Since the set of $\textsf{HT}$ models of any program $\mathcal{P}$ must be well-defined, that is, $({I, J})\in[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ implies that $({J, J})\in[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ , not every order assignment characterises a rule revision operator. Slota and Leite (2010, 2014) additionally define well-defined order assignments as those that do.

Definition 53 (Rule Revision Operator Characterised by an Order Assignment) Let $\mathbin{\otimes}$ be a rule revision operator and $\omega$ a preorder assignment over the set of all logic programs. We say that $\mathbin{\otimes}$ is characterised by $\omega$ if for all programs $\mathcal{P}$ , $\mathcal{U}$ ,

\begin{equation*} [\kern-.3ex[{\mathcal{P} \mathbin{\otimes} \mathcal{U}}]\kern-.3ex]_{\mathsf{HT}} = \min \left( [\kern-.3ex[{\mathcal{U}}]\kern-.3ex]_{\mathsf{HT}}, \leq^{\mathcal{P}}_{\omega} \right) . \end{equation*}

A preorder assignment over over the set of all programs is well-defined if some rule update operator is characterised by it.

Similarly as with belief revision, the following definition captures a set of conditions on the assigned orders.

Definition 54 (Faithful Order Assignment Over Programs) A preorder assignment $\omega$ over the set of all programs is faithful if the following three conditions hold, for all programs $\mathcal{P}$ , $\mathcal{Q}$ :

• $\text{If }I,J\in[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}\text{, then }I\not<^{\mathcal{P}}_{\omega}J$ ;

• $\text{If }I\in[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}\text{ and }J\not\in[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}\text{, then }I<^{\mathcal{P}}_{\omega}J$ ;

• $\text{If }[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}=[\kern-.3ex[{\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}}\text{, then }<^{\mathcal{P}}_{\omega}=<^{\mathcal{Q}}_{\omega}$ .

The representation theorem of Delgrande et al. (2013) states that operators characterised by faithful order assignments over the set of all programs are exactly those that satisfy $\textsf{PR1}_{\textsf{HT}}$ – $\textsf{PR6}_{\textsf{HT}}$ .

Theorem 55 (Delgrande et al. 2013) Let $\mathbin{\otimes}$ be a rule revision operator. Then the following conditions are equivalent:

• The operator $\mathbin{\otimes}$ satisfies conditions $\textsf{PR1}_{\textsf{HT}}$ – $\textsf{PR6}_{\textsf{HT}}$ .

• The operator $\mathbin{\otimes}$ is characterised by a faithful total preorder assignment over the set of all programs.

Schwind and Inoue (2016) provided an alternative constructive characterisation of logic programs revision operators in terms of preorders over interpretations. Delgrande et al. (2008, 2013) present two different revision operators, one analogous to the so-called set-containment based revision proposed by Satoh (1988), and the other analogous to the so-called cardinality-based revision proposed by Dalal (1988). Here, we recap the latter one, because, unlike the former, it obeys all six postulates $\textsf{PR1}_{\textsf{HT}}$ – $\textsf{PR6}_{\textsf{HT}}$ .

The operator is based on a notion of closeness that is given in terms of cardinality:

Definition 56 Let $\mathcal{M}$ and $\mathcal{N}$ be sets of either interpretations or three-valued interpretations. Then,

\begin{equation*}\sigma_{\vert\vert}(\mathcal{M},\mathcal{N})=\{X\in\mathcal{M}\vert\exists Y\in\mathcal{N}\text{ such that }\forall X'\in\mathcal{M},\forall Y'\in\mathcal{N},\vert X'\div Y'\vert\not<\vert X\div Y\vert\},\end{equation*}

where $\div$ denotes the symmetric difference, extended for three-valued interpretations $\langle I, J \rangle$ and $\langle K, L \rangle$ as follows:

\begin{equation*}\langle I, J \rangle\div \langle K, L \rangle = \langle I\div K, J\div L \rangle,\end{equation*}

and

\begin{align*}\vert\langle I, J \rangle\vert\leq\vert\langle K, L \rangle\vert\text{ iff }\vert J\vert\leq\vert L\vert\text{ and if }\vert J\vert = \vert L\vert\text{ then }\vert I\vert\leq\vert K\vert;\\[4pt]\vert\langle I, J \rangle\vert < \vert\langle K, L \rangle\vert\text{ iff } \vert\langle I, J \rangle\vert\leq\vert\langle K, L \rangle\vert\text{ and } \vert\langle K,L \rangle\vert\not\leq\vert\langle {I, J} \rangle\vert.\end{align*}

The operator is then defined as follows:

Definition 57 (Cardinality-based Program Revision Delgrande et al. 2008;2013) Let $\mathcal{P}$ and $\mathcal{U}$ be two logic programs. The cardinality-based revision operator $\mathbin{\otimes}_c$ is defined, up to equivalence of its input and output, as a logic program such that:

\begin{align*}[\kern-.3ex[{\mathcal{P}\mathbin{\otimes}_c\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}}=&[\kern-.3ex[{\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}},&\text{if }[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}=\emptyset;\\[4pt][\kern-.3ex[{\mathcal{P}\mathbin{\otimes}_c\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}}=&\{\langle I, J\rangle\vert J\in\sigma_{\vert\vert}([\kern-.3ex[ {\mathcal{P}} ]\kern-.3ex]_{\mathsf{C}},[\kern-.3ex[ {\mathcal{Q}} ]\kern-.3ex]_{\mathsf{C}}),I\subseteq J,\\[4pt]&\enspace\text{ and if }I\subset J\text{ then } \langle {I, J} \rangle\in\sigma_{\vert\vert}([\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}},[\kern-.3ex[{\mathcal{Q}}]\kern-.3ex]_{\mathsf{HT}})\},&\text{otherwise}.\end{align*}

Theorem 58 The cardinality based operator $\mathbin{\otimes}_c$ satisfies $\textsf{PR1}_{\textsf{HT}}$ – $\textsf{PR6}_{\textsf{HT}}$ .

6.1.2 Updates based on $\textsf{HT}$ models

To adapt the KM postulates for updates to answer-set program updates, Slota and Leite (2010, 2014) substitute the notion of a complete formula used in $\mathsf{BU7}$ with the notion of a basic program, that is, a program that either it has a unique $\textsf{HT}$ model (J, J), or a pair of $\textsf{HT}$ models (I, J) and (J, J). In the former case, the program exactly determines the truth values of all atoms – the atoms in J are true and the remaining atoms are false. In the latter case, the program makes atoms in I true, the atoms in $J \backslash I$ may either be undefined or true, as long as they all have the same truth value, and the remaining atoms are false. The latter case needs to be allowed in order to make the new postulate applicable to three-valued interpretations (I, J) with $I \subsetneq J$ because no program has the single $\textsf{HT}$ model (I, J).

Using $\textsf{HT}$ models, the adaptation of the KM postulates for updates to answer-set program updates, which, for a rule update operator $\mathbin{\oplus}$ and programs $\mathcal{P}$ , $\mathcal{Q}$ , $\mathcal{U}$ , $\mathcal{V}$ become:

1. ( $\textsf{PU1}_{\textsf{HT}}$ ) $\mathcal{P} \mathbin{\oplus} \mathcal{U} \mathrel\mid=_{\mathsf{HT}} \mathcal{U}$ .

2. ( $\textsf{PU2}_{\textsf{HT}}$ ) If $\mathcal{P} \mathrel\mid=_{\mathsf{HT}} \mathcal{U}$ , then $\mathcal{P} \mathbin{\oplus} \mathcal{U} \equiv_{\mathsf{HT}} \mathcal{P}$ .

3. ( $\textsf{PU3}_{\textsf{HT}}$ ) If $[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}} \neq \emptyset$ and $[\kern-.3ex[{\mathcal{U}}]\kern-.3ex]_{\mathsf{HT}} \neq \emptyset$ , then $[\kern-.3ex[{\mathcal{P} \mathbin{\oplus} \mathcal{U}}]\kern-.3ex]_{\mathsf{HT}} \neq \emptyset$ . ( $\textsf{PU4}_{\textsf{HT}}$ ) If $\mathcal{P} \equiv_{\mathsf{HT}} \mathcal{Q}$ and $\mathcal{U} \equiv_{\mathsf{HT}} \mathcal{V}$ , then $\mathcal{P} \mathbin{\oplus} \mathcal{U} \equiv_{\mathsf{HT}} \mathcal{Q} \mathbin{\oplus} \mathcal{V}$ .

4. ( $\textsf{PU5}_{\textsf{HT}}$ ) $(\mathcal{P} \mathbin{\oplus} \mathcal{U}) \mathbin{\dot{\wedge}} \mathcal{V} \mathrel\mid=_{\mathsf{HT}} \mathcal{P} \mathbin{\oplus} (\mathcal{U} \mathbin{\dot{\wedge}} \mathcal{V})$ .

5. ( $\textsf{PU6}_{\textsf{HT}}$ ) If $\mathcal{P} \mathbin{\oplus} \mathcal{U} \mathrel\mid=_{\mathsf{HT}} \mathcal{V}$ and $\mathcal{P} \mathbin{\oplus} \mathcal{V} \mathrel\mid=_{\mathsf{HT}} \mathcal{U}$ , then $\mathcal{P} \mathbin{\oplus} \mathcal{U} \equiv_{\mathsf{HT}} \mathcal{P} \mathbin{\oplus} \mathcal{V}$ .

6. ( $\textsf{PU7}_{\textsf{HT}}$ ) If $\mathcal{P}$ is basic, then $(\mathcal{P} \mathbin{\oplus} \mathcal{U}) \mathbin{\dot{\wedge}} (\mathcal{P} \mathbin{\oplus} \mathcal{V}) \mathrel\mid=_{\mathsf{HT}} \mathcal{P} \mathbin{\oplus} (\mathcal{U} \mathbin{\dot{\lor}} \mathcal{V})$ .

7. ( $\textsf{PU8}_{\textsf{HT}}$ ) $(\mathcal{P} \mathbin{\dot{\lor}} \mathcal{Q}) \mathbin{\oplus} \mathcal{U} \equiv_{\mathsf{HT}} (\mathcal{P} \mathbin{\oplus} \mathcal{U}) \mathbin{\dot{\lor}} (\mathcal{Q} \mathbin{\oplus} \mathcal{U})$ .

Analogically to belief updates, a constructive characterisation of rule update operators satisfying conditions $\textsf{PU1}_{\textsf{HT}}$ – $\textsf{PU8}_{\textsf{HT}}$ is based on an order assignment, but this time over the set of all three-valued interpretations $\mathscr{X}$ . Since the set of $\textsf{HT}$ models of any program $\mathcal{P}$ must be well-defined that is, $({I, J})\in[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ implies that $({J, J})\in[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{HT}}$ , not every order assignment characterises a rule update operator. Slota and Leite (2010, 2014) additionally define well-defined order assignments as those that do.

Definition 59 (Rule Update Operator Characterised by an Order Assignment) Let $\mathbin{\oplus}$ be a rule update operator and $\omega$ a preorder assignment over $\mathscr{X}$ . We say that $\mathbin{\oplus}$ is characterised by $\omega$ if for all programs $\mathcal{P}$ , $\mathcal{U}$ ,

\begin{equation*} [\kern-.3ex[{\mathcal{P} \mathbin{\oplus} \mathcal{U}}]\kern-.3ex]_{\mathsf{HT}} = \bigcup_{X \in [\kern-.25ex[{\mathcal{P}}]\kern-.25ex]_{\mathsf{HT}}} \min \left( [\kern-.3ex[{\mathcal{U}}]\kern-.3ex]_{\mathsf{HT}}, \leq^{X}_{\omega} \right) . \end{equation*}

A preorder assignment over $\mathscr{X}$ is well-defined if some rule update operator is characterised by it.

Similarly as with belief updates, order assignments are required to be faithful, that is to consider each three-valued interpretation the closest to itself.

Definition 60 (Faithful Order Assignment Over Three-valued Interpretations) A preorder assignment $\omega$ over $\mathscr{X}$ is faithful if for every three-valued interpretation X the following condition is satisfied:

\begin{equation*} \text{For every } Y \in \mathscr{X} \text{ with } Y \neq X \text{ it holds that } X <^{X}_{\omega} Y . \end{equation*}

Interestingly, faithful assignments characterise the same class of operators as the larger class of semi-faithful assignments, defined as follows:

Definition 61 (Semi-Faithful Order Assignment) A preorder assignment $\omega$ over $\mathscr{X}$ is semi-faithful if for every three-valued interpretation $X = ({I, J})$ the following conditions are satisfied (where $X^* = ({J, J})$ ):

\begin{align*} &\text{For every }Y \in \mathscr{X} \text{ with }Y \neq X\text{ and }Y \neq X^*\text{ , either }X <^{X}_{\omega} Y\text{ or }X^* <^{X}_{\omega} Y.\\[4pt] &\text{If }X^* \leq^{X}_{\omega} X \text{, then }X \leq^{X}_{\omega} X^*. \end{align*}

Preorder assignments need to satisfy one further condition, related to the well-definedness of sets of SE models of every program. It can naturally be seen as the semantic counterpart of $\textsf{PU7}_{\textsf{HT}}$ .

Definition 62 (Organised Preorder Assignment) A preorder assignment $\omega$ is organised if for all three-valued interpretations X, Y and all well-defined sets of three-valued interpretations $\mathcal{M}$ , $\mathcal{N}$ the following condition is satisfied:

\begin{align*} & \text{If } Y \in \min ( \mathcal{M}, \leq^{X}_{\omega} ) \cup \min ( \mathcal{M}, \leq^{X^*}_{\omega} ) \text{ and } Y \in \min ( \mathcal{N}, \leq^{X}_{\omega} ) \cup \min ( \mathcal{N}, \leq^{X^*}_{\omega} ), \\[3pt] & \text{then } Y \in \min ( \mathcal{M} \cup \mathcal{N}, \leq^{X}_{\omega} ) \cup \min (\mathcal{M} \cup \mathcal{N}, \leq^{X^*}_{\omega} ). \end{align*}

Just as with updates in classical logic, the following representation theorem provides a constructive characterisation of rule update operators satisfying the postulates, making it possible to define and evaluate any operator satisfying the postulates using an intuitive construction.

Theorem 63 (Representation theorem for rule updates Slota and Leite 2014) Let $\mathbin{\oplus}$ be a rule update operator. The following conditions are equivalent:

1. 1. The operator $\mathbin{\oplus}$ satisfies conditions $\textsf{PU1}_{\textsf{HT}}$ – $\textsf{PU8}_{\textsf{HT}}$ .

2. 2. The operator $\mathbin{\oplus}$ is characterised by a semi-faithful and organised preorder assignment.

3. 3. The operator $\mathbin{\oplus}$ is characterised by a faithful and organised partial order assignment.

One of the benefits of dealing with rule updates on the semantic level is that semantic properties that are rather difficult to show for syntax-based update operators are much easier to analyse and prove. As we have seen, one of the most widespread and counterintuitive side-effects of syntax-based rule update semantics is that they are sensitive to tautological updates. In case of the semantic update operators characterised in the previous theorem, such a behaviour is impossible given that the operators satisfy $\textsf{PU2}_{\textsf{HT}}$ and $\textsf{PU4}_{\textsf{HT}}$ .

Slota and Leite (2014) additionally defined a concrete update operator that can be seen as a counterpart to the belief update operator by Winslett (1988), which we do not present here.

6.1.3 Problems with revision and update operators based on $\textsf{HT}$ models

The most important contribution by Slota and Leite (2010, 2014) is not the adaptation of the postulates to answer-set program updates, the representation theorem, nor even the concrete update operator they defined, but rather the uncovering of a serious drawback that extends to all rule update and revision operators based on KM postulates and on $\textsf{HT}$ models. In particular, it turns out that these operators are incompatible with the properties of support and fact update which are at the core of logic programming and their updates.

The following theorem shows that every rule update operator satisfying $\textsf{PU4}_{\textsf{HT}}$ violates either support or fact update, while its proof illustrates why.

Theorem 64 (Slota and Leite 2014) A rule update operator that satisfies $\textsf{PU4}_{\textsf{HT}}$ either does not respect support or it does not respect fact update.

Proof. Let $\mathbin{\oplus}$ be a rule update operator that satisfies $\textsf{PU4}_{\textsf{HT}}$ and $\mathcal{P}$ , $\mathcal{Q}$ and $\mathcal{U}$ the following programs:

\begin{align*} \mathcal{P}:\quad \mathsf{p}&. & \mathcal{Q}:\quad \mathsf{p} &\leftarrow \mathsf{q}. & \mathcal{U}:\quad \mathop{\sim\!} \mathsf{q}. \\ \mathsf{q}&. & \mathsf{q}&. \end{align*}

Since $\mathcal{P}$ is strongly equivalent to $\mathcal{Q}$ , by $\textsf{PU4}_{\textsf{HT}}$ we obtain that $\mathcal{P} \mathbin{\oplus} \mathcal{U}$ is strongly equivalent to $\mathcal{Q} \mathbin{\oplus} \mathcal{U}$ . Consequently, $\mathcal{P} \mathbin{\oplus} \mathcal{U}$ has the same answer-sets as $\mathcal{Q} \mathbin{\oplus} \mathcal{U}$ . It only remains to observe that if $\mathbin{\oplus}$ respects fact update, then $\mathcal{P} \mathbin{\oplus} \mathcal{U}$ has the unique answer-set ${\mathsf{p}}$ . But then ${\mathsf{p}}$ is an answer-set of $\mathcal{Q} \mathbin{\oplus} \mathcal{U}$ in which $\mathsf{p}$ is unsupported by $\mathcal{Q} \cup \mathcal{U}$ . Hence $\mathbin{\oplus}$ does not respect support.

So, any answer-set program update operator based on $\textsf{HT}$ models and the KM approach to belief update, as materialised in the fundamental principle $\textsf{PU4}_{\textsf{HT}}$ , cannot respect two basic and desirable properties: support and fact update. This is a major drawback of such operators, severely diminishing their applicability.

Moreover, the principle $\textsf{PU4}_{\textsf{HT}}$ is also adopted as $\textsf{PR4}_{\textsf{HT}}$ for revision of answer-set programs based on $\textsf{HT}$ models by Delgrande et al. (2013). This means that Theorem 64 extends to semantic program revision operators, such as those defined by Delgrande et al. (2013): whenever support and fact update are expected to be satisfied by a rule revision operator, it cannot be defined by purely manipulating the sets of $\textsf{HT}$ models of the underlying programs.

One question that suggests itself is whether a weaker version of the principle $\textsf{PU4}_{\textsf{HT}}$ can be combined with properties such as support and fact update. Its two immediate weakenings, analogous to the weakenings of $\mathsf{BU4}$ by Herzig and Rifi (1999), are as follows:

1. ( $\textsf{PU4.1}_{\textsf{HT}}$ ) If $\mathcal{P} \equiv_{\mathsf{HT}} \mathcal{Q}$ , then $\mathcal{P} \mathbin{\oplus} \mathcal{U} \equiv_{\mathsf{HT}} \mathcal{Q} \mathbin{\oplus} \mathcal{U}$ .

2. ( $\textsf{PU4.2}_{\textsf{HT}}$ ) If $\mathcal{U} \equiv_{\mathsf{HT}} \mathcal{V}$ , then $\mathcal{P} \mathbin{\oplus} \mathcal{U} \equiv_{\mathsf{HT}} \mathcal{P} \mathbin{\oplus} \mathcal{V}$ .

In case of $\textsf{PU4.1}_{\textsf{HT}}$ , it is easy to see that the proof of Theorem 64 applies in the same way as with $\textsf{PU4}_{\textsf{HT}}$ , so $\textsf{PU4.1}_{\textsf{HT}}$ is likewise incompatible with support and fact update.

On the other hand, principle $\textsf{PU4.2}_{\textsf{HT}}$ , also referred to as weak independence of syntax (WIS) (Osorio and Cuevas 2007), does not suffer from such severe limitations. It is, nevertheless, violated by syntax-based rule update semantics that assign a special meaning to occurrences of default literals in heads of rules, as illustrated in the following example:

Example 65 Let the programs $\mathcal{P}$ , $\mathcal{U}$ and $\mathcal{V}$ be as follows:

\begin{align*} \mathcal{P}:\quad \mathsf{p}&. & \mathcal{U}:\quad \mathop{\sim\!} \mathsf{p} &\leftarrow \mathsf{q}. & \mathcal{V}:\quad \mathop{\sim\!} \mathsf{q} &\leftarrow \mathsf{p}. \\ \mathsf{q}&. \end{align*}

Since $\mathcal{U}$ is strongly equivalent to $\mathcal{V}$ , $\textsf{PU4.2}_{\textsf{HT}}$ requires that $\mathcal{P} \mathbin{\oplus} \mathcal{U}$ be strongly equivalent to $\mathcal{P} \mathbin{\oplus} \mathcal{V}$ . This is in contrast with the $\textsf{JU}$ , $\textsf{DS}$ , and $\textsf{RD}$ semantics where a default literal $\mathop{\sim\!} \mathsf{p}$ in the head of a rule indicates that whenever the body of the rule is satisfied, there is a reason for $\mathsf{p}$ to cease being true. A consequence of this is that an update of $\mathcal{P}$ by $\mathcal{U}$ results in the single answer-set ${\mathsf{q}}$ while an update by $\mathcal{V}$ leads to the single answer-set ${\mathsf{p}}$ . Thus, when considering the principle $\textsf{PU4.2}_{\textsf{HT}}$ , benefits of the declarativeness that it brings with it need to be weighed against the loss of control over the results of updates by rules with default literals in their heads.

6.2 Operators based on RE-models

The problems identified by Slota and Leite (2010, 2014) could be mitigated if, instead of $\textsf{HT}$ models, a richer semantic characterisation of logic programs was used. Such a characterisation would have to be able to distinguish between programs such as $\mathcal{P} = {\mathsf{p}., \mathsf{q}.}$ and $\mathcal{Q} = {\mathsf{p} \leftarrow \mathsf{q}., \mathsf{q}.}$ because they are expected to behave differently when subject to evolution. And it would have to distinguish between the rule $\mathop{\sim\!} \mathsf{p} \leftarrow \mathsf{q}.$ and the rule $\mathop{\sim\!} \mathsf{q} \leftarrow \mathsf{p}.$ , inasmuch as they are expected to have different behaviour, for example, when used to update the program $\mathcal{P} = {\mathsf{p}., \mathsf{q}.}$ .

This is precisely the approach taken by Slota and Leite (2012a), who defined a new monotonic characterisation of rules, dubbed robust equivalence models, or $\mathsf{RE}$ -models for short, which is expressive enough to distinguish between the so-called abolishing rules $\mathop{\sim\!} \mathsf{p} \leftarrow \mathsf{q}.$ , $\mathop{\sim\!} \mathsf{q} \leftarrow \mathsf{p}.$ , and $\leftarrow \mathsf{p},\mathsf{q}$ . Then, they introduced a generic method for specifying semantic rule update operators in which

1. 1. a logic program is viewed as the set of sets of $\mathsf{RE}$ -models of its rules, ⁷ hence acknowledging rules as the atomic pieces of knowledge while, at the same time, abstracting away from unimportant differences between their syntactic forms, focusing on their semantic content;

2. 2. updates are performed by introducing additional interpretations (exceptions) to the sets of $\mathsf{RE}$ -models of rules in the original program.

Instances of such generic framework were shown to obey properties such as support, fact update, and causal rejection, thus far only obeyed by syntactic approaches. Furthermore, they have a semantic characterisation that ensures several semantic properties such as replacement of equivalents captured by $\mathsf{BU4}$ , adapted to employ this novel semantic characterisation using $\mathsf{RE}$ -models instead of $\textsf{HT}$ models. One such instance is also shown to provide a semantic characterisation of the $\textsf{JU}$ Semantics for DLPs without local cycles.

The $\mathsf{RE}$ -models and associated notions of equivalence are defined as follows.

Definition 66 ( $\mathsf{RE}$ -models, $\mathsf{RE}$ -equivalence, and $\mathsf{RR}$ -equivalence) A three-valued interpretation $\langle I, J\rangle$ is an $\mathsf{RE}$ -model of a rule $\pi$ if $I\mathrel\mid=\pi^J$ . The set of all $\mathsf{RE}$ -models of a rule $\pi$ is denoted by $[\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}}$ . Rules $\pi$ , $\sigma$ are $\mathsf{RE}$ -equivalent whenever $[\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}} = [\kern-.3ex[{\sigma}]\kern-.3ex]_{\mathsf{RE}}$ . Programs $\mathcal{P}$ and $\mathcal{Q}$ are $\mathsf{RE}$ -equivalent, denoted by $\mathcal{P}\equiv_{\mathsf{RE}}\mathcal{Q}$ , whenever $[\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{RE}} = [\kern-.3ex[{\mathcal{Q}}]\kern-.3ex]_{\mathsf{RE}}$ . The set of sets of $\mathsf{RE}$ -models of rules inside a program $\mathcal{P}$ is denoted by $\langle\kern-.5ex\langle {\mathcal{P}} \rangle\kern-.5ex\rangle_{\mathsf{RE}} = {[\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}} | \pi \in \mathcal{P} }$ , and is used as the basis for the notion of robust rule equivalence, or $\mathsf{RR}$ -equivalence for short. Programs $\mathcal{P}$ and $\mathcal{Q}$ and $\mathsf{RE}$ -equivalent, denoted by $\mathcal{P} \equiv_{\mathsf{RR}} \mathcal{Q}$ , whenever $\langle\kern-.5ex\langle {\mathcal{P}^\tau} \rangle\kern-.5ex\rangle_{\mathsf{RE}} = \langle\kern-.5ex\langle {\mathcal{Q}^\tau} \rangle\kern-.5ex\rangle_{\mathsf{RE}}$ , where, given a program $\mathcal{P}$ , $\mathcal{P}^\tau = \mathcal{P} \cup {\tau}$ , where $\tau$ is the canonical tautology, that is, the rule $\mathsf{p}_\tau \leftarrow \mathsf{p}_\tau$ given a fixed atom $\mathsf{p}_\tau$ from $\mathcal{L}$ . Interestingly, the affinity between $\textsf{HT}$ models and stable models is fully retained by $\mathsf{RE}$ -models: an interpretation J is a stable model of a program $\mathcal{P}$ if and only if $\langle J, J \rangle \in [\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{RE}}$ and for all $I \subsetneq J$ , $\langle I, J \rangle \notin [\kern-.3ex[{\mathcal{P}}]\kern-.3ex]_{\mathsf{RE}}$ . Furthermore, unlike with $\textsf{HT}$ models, any set of three-valued interpretations can be represented by a program using $\mathsf{RE}$ -models (Slota and Leite 2012a; Slota 2012).

The formalisation of the idea of viewing updates as introducing additional interpretations – exceptions – to the sets of $\mathsf{RE}$ -models of rules in the original program is straightforward: an exception-driven update operator is characterised by an exception function $\varepsilon$ that takes three inputs: the set of $\mathsf{RE}$ -models $[\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}}$ of a rule $\pi \in \mathcal{P}$ and the semantic characterisations, $\langle\kern-.5ex\langle {\mathcal{P}} \rangle\kern-.5ex\rangle_{\mathsf{RE}}$ and $\langle\kern-.5ex\langle {\mathcal{U}} \rangle\kern-.5ex\rangle_{\mathsf{RE}}$ , of the original and updating programs. It then returns the three-valued interpretations that are to be introduced as exceptions to $\pi$ , so the characterisation of the updated program contains the augmented set of $\mathsf{RE}$ -models,

(4) \begin{equation} [\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}} \cup \varepsilon \left( [\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}}, \langle\kern-.5ex\langle {\mathcal{P}} \rangle\kern-.5ex\rangle_{\mathsf{RE}}, \langle\kern-.5ex\langle {\mathcal{U}} \rangle\kern-.5ex\rangle_{\mathsf{RE}} \right).\end{equation}

A rule update operator $\mathbin{\oplus}$ is exception-driven if for some exception function $\varepsilon$ , $\langle\kern-.5ex\langle {\mathcal{P} \oplus \mathcal{U}} \rangle\kern-.5ex\rangle_{\mathsf{RE}}$ is equal to

(5) \begin{equation} { [\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}} \cup \varepsilon \left( [\kern-.3ex[{\pi}]\kern-.3ex]_{\mathsf{RE}}, \langle\kern-.5ex\langle {\mathcal{P}} \rangle\kern-.5ex\rangle_{\mathsf{RE}}, \langle\kern-.5ex\langle {\mathcal{U}} \rangle\kern-.5ex\rangle_{\mathsf{RE}} \right) | \pi \in \mathcal{P} } \cup \langle\kern-.5ex\langle {\mathcal{U}} \rangle\kern-.5ex\rangle_{\mathsf{RE}},\end{equation}

for all programs $\mathcal{P}$ and $\mathcal{U}$ . In that case we also say that $\mathbin{\oplus}$ is $\varepsilon$ -driven. In words, the set of $\mathsf{RE}$ -models of each rule $\pi$ from $\mathcal{P}$ is augmented with the respective exceptions while the sets of $\mathsf{RE}$ -models of rules from $\mathcal{U}$ are kept untouched. Note that since a set of three-valued interpretations may have different syntactic representations as a program using $\mathsf{RE}$ -models, for each exception function $\varepsilon$ there is a whole class of $\varepsilon$ -driven rule update operators that differ in the syntactic representations of the sets of $\mathsf{RE}$ -models in (5). ⁸

Slota and Leite (2012a) further investigated a constrained class of exception functions, which they dubbed simple exception functions, characterised by the fact that they produce (local) exceptions based on conflicts between pairs of rules, one from the original and one from the updating program, while ignoring the context in which these rules are situated, that is, the other rules in the programs. Formally, an exception function $\varepsilon$ is simple if for all $\mathcal{M} \subseteq \mathscr{X}$ and $\mathcal{S}, \mathcal{T} \subseteq 2^{\mathscr{X}}$ ,

\begin{equation*} \varepsilon(\mathcal{M}, \mathcal{S}, \mathcal{T}) = \textstyle \bigcup_{\mathcal{N} \in \mathcal{T}} \delta(\mathcal{M}, \mathcal{N}), \end{equation*}

where $\delta : 2^{\mathscr{X}} \times 2^{\mathscr{X}} \rightarrow 2^{\mathscr{X}}$ is a local exception function.

Despite their local nature, particular simple exception functions generate rule update operators that satisfy the syntactic properties of rule update semantics discussed before. We will recap two simple exception functions proposed by Slota and Leite (2012a), dubbed $\delta_\textsf{a}$ and $\delta_\textsf{b}$ , inspired by rule update semantics based on causal rejection, one of them closely related to the $\textsf{JU}$ semantics.

Since rule update semantics based on causal rejection make use of the concepts of conflicting rules (c.f. Def. 13) and rejected rules (c.f. Def. 14 for the case of the $\textsf{JU}$ semantics), which rely on rule syntax to which an exception function has no direct access, the semantic counterparts to these concepts were first defined.

Towards the definition of conflicting sets of $\mathsf{RE}$ -models, two preparatory concepts are required.

First, a truth value substitution is defined as follows: Given an interpretation J, an atom $\mathsf{p}$ and a truth value $\mathsf{V} \in {\mathsf{T},\mathsf{U}, \mathsf{F}}$ , by $J[\mathsf{V}/\mathsf{p}]$ we denote the three-valued interpretation X such that $X(\mathsf{p}) = \mathsf{V}$ and $X(\mathsf{q}) = J(\mathsf{q})$ for all atoms $\mathsf{q} \neq \mathsf{p}$ .

This enables the introduction of the main concept needed for defining a conflict between two sets of three-valued interpretations. Given a set of three-valued interpretations $\mathcal{M}$ , an atom $\mathsf{p}$ , a truth value $\mathsf{V}_0$ and a two-valued interpretation J, we say that $\mathcal{M}$ forces $\mathsf{p}$ to have the truth value $\mathsf{V}_0$ w.r.t. J, denoted by $\mathcal{M}^J(\mathsf{p})= \mathsf{V}_0$ , if

\begin{equation*} J[\mathsf{V}/\mathsf{p}] \in \mathcal{M} \text{ if and only if } \mathsf{V} = \mathsf{V}_0 .\end{equation*}

In other words, the three-valued interpretation $J[\mathsf{V}_0/\mathsf{p}]$ must be the unique member of $\mathcal{M}$ that either coincides with J or differs from it only in the truth value of $\mathsf{p}$ . Note that $\mathcal{M}^J(\mathsf{p})$ stays undefined in case no $\mathsf{V}_0$ with the above property exists.

Two sets of three-valued interpretations $\mathcal{M}$ , $\mathcal{N}$ are in conflict on atom $\mathsf{p}$ w.r.t. J, denoted by $\mathcal{M}\Join^{J}_{\mathsf{p}} \mathcal{N}$ , if both $\mathcal{M}^J(\mathsf{p})$ and $\mathcal{N}^J(\mathsf{p})$ are defined and $\mathcal{M}^J(\mathsf{p}) \neq\mathcal{N}^J(\mathsf{p})$ . The following example illustrates all these concepts.

Example 67 Consider rules $\pi_0 = (\mathsf{p}.)$ , $\pi_1 = (\mathop{\sim\!} \mathsf{p} \leftarrow \mathop{\sim\!} \mathsf{q}.)$ with the respective sets of $\mathsf{RE}$ -models ⁹

\begin{align*} \mathcal{M}_0 &= { ({\mathsf{p}, \mathsf{p}}), ({\mathsf{p}, \mathsf{p}\mathsf{q}}), ({\mathsf{p}\mathsf{q}, \mathsf{p}\mathsf{q}}) } , \\[3pt] \mathcal{M}_1 &= { ({\emptyset, \emptyset}), ({\emptyset, \mathsf{q}}), ({\mathsf{q}, \mathsf{q}}), ({\emptyset, \mathsf{p}\mathsf{q}}), ({\mathsf{p}, \mathsf{p}\mathsf{q}}), ({\mathsf{q}, \mathsf{p}\mathsf{q}}), ({\mathsf{p}\mathsf{q}, \mathsf{p}\mathsf{q}}) }. \end{align*}

Intuitively, $\mathcal{M}_0$ forces $\mathsf{p}$ to $\mathsf{T}$ w.r.t. all interpretations and $\pi_1$ forces $\mathsf{p}$ to $\mathsf{F}$ w.r.t. interpretations in which $\mathsf{q}$ is false. Formally it follows that $\mathcal{M}_0^\emptyset(\mathsf{p}) = \mathsf{T}$ because $({\mathsf{p}, \mathsf{p}})$ belongs to $\mathcal{M}_0$ and neither $({\emptyset, \mathsf{p}})$ nor $({\emptyset, \emptyset})$ belongs to $\mathcal{M}_0$ . Similarly, it follows that $\mathcal{M}_1^\emptyset(\mathsf{p}) = \mathsf{F}$ . Hence $\mathcal{M}_0 \Join^{\emptyset}_{\mathsf{p}} \mathcal{M}_1$ . Using similar arguments we can conclude that $\mathcal{M}_0 \Join^{\mathsf{p}}_{\mathsf{p}} \mathcal{M}_1$ . However, it does not hold that $\mathcal{M}_0 \Join^{\mathsf{p}\mathsf{q}}_{\mathsf{p}} \mathcal{M}_1$ because $\mathcal{M}_1^{\mathsf{p}\mathsf{q}}(\mathsf{p})$ is undefined.

We are now ready to introduce the local exception function $\delta_\textsf{a}$ .

Definition 68 (Local Exception Function $\delta_\textsf{a}$ ) The local exception function $\delta_\textsf{a}$ is for all $\mathcal{M}, \mathcal{N} \subseteq \mathscr{X}$ defined as

\begin{equation*} \delta_\mathsf{a}(\mathcal{M}, \mathcal{N}) = { ({I, J}) \in \mathscr{X} | \exists \mathsf{p} : \mathcal{M} \Join^{J}_{\mathsf{p}} \mathcal{N} } . \end{equation*}

Thus if there is a conflict on some atom w.r.t. J, the exceptions introduced by $\delta_\textsf{a}$ are of the form (I, J) where I can be an arbitrary subset of J. This means that $\delta_\textsf{a}$ introduces as exceptions all three-valued interpretations that preserve false atoms from J while the atoms that are true in J may be either true or undefined. This is somewhat related to the definition of a stable model where the default assumptions (false atoms) are fixed while the necessary truth of the remaining atoms is checked against the rules of the program. The syntactic properties of $\delta_\textsf{a}$ -driven operators are as follows.

Theorem 69 (Syntactic Properties of $\delta_\textsf{a}$ Slota and Leite 2012a) Every $\delta_\textsf{a}$ -driven rule update operator respects support and fact update. Furthermore, it also respects causal rejection and acyclic justified update w.r.t. DLPs of length at most two.

This means that $\delta_\textsf{a}$ -driven rule update operators enjoy a combination of desirable syntactic properties that operators based on SE models cannot (cf. Theorem 64). However, these operators diverge from causal rejection, even on acyclic DLPs, when more than one update is performed.

Example 70 Consider again the rules $\pi_0$ , $\pi_1$ and their sets of $\mathsf{RE}$ -models $\mathcal{M}_0$ , $\mathcal{M}_1$ from Example 67 and some $\delta_\textsf{a}$ -driven rule update operator $\mathbin{\oplus}$ . Then, $\langle\kern-.5ex\langle {{\pi_0} \mathbin{\oplus} {\pi_1}} \rangle\kern-.5ex\rangle_{\mathsf{RE}}$ will contain two elements: $\mathcal{M}_0'$ and $\mathcal{M}_1$ , where

\begin{equation*} \mathcal{M}_0' = \mathcal{M}_0 \cup \delta_\mathsf{a}(\mathcal{M}_0, \mathcal{M}_1) = \mathcal{M}_0 \cup {({\emptyset, \emptyset}), ({\emptyset, \mathsf{p}})} . \end{equation*}

An additional update by the fact ${\mathsf{q}.}$ then leads to the characterisation

\begin{equation*} \left\langle\kern-.8ex\left\langle {\mathop{\bigoplus} \langle {\pi_0}, {\pi_1}, {\mathsf{q}.} \rangle} \right\rangle\kern-.8ex\right\rangle_{\mathsf{RE}}, \end{equation*}

which contains three elements: $\mathcal{M}_0''$ , $\mathcal{M}_1$ and $\mathcal{M}_2$ , where

\begin{equation*} \mathcal{M}_0'' = \mathcal{M}_0' \cup {({\emptyset, \mathsf{q}}), ({\mathsf{q}, \mathsf{q}})}, \end{equation*}

and $\mathcal{M}_2$ is the set of $\mathsf{RE}$ -models of $(\mathsf{q}.)$ .

Furthermore, due to the relationship between $\mathsf{RE}$ -models and stable models, the interpretation $J = {\mathsf{q}}$ is a stable model of $\mathop{\bigoplus} \langle {\pi_0}, {\pi_1}, {\mathsf{q}.} \rangle$ because $({\mathsf{q}, \mathsf{q}})$ belongs to all sets of models in the set of sets of models $\langle\kern-.5ex\langle {\mathop{\bigoplus} \langle {\pi_0}, {\pi_1}, {\mathsf{q}.} \rangle} \rangle\kern-.5ex\rangle_{\mathsf{RE}}$ and $({\emptyset, \mathsf{q}})$ does not belong to $\mathcal{M}_2$ . However, J does not respect causal rejection and it is not a $\textsf{JU}$ model of $({{\pi_0}, {\pi_1}, {\mathsf{q}.}})$ .

This shortcoming of $\delta_\textsf{a}$ was overcome by Slota and Leite (2012a) as follows:

Definition 71 (Local Exception Functions $\delta_\textsf{b}$ ) The local exception functions $\delta_\textsf{b}$ is for all $\mathcal{M}, \mathcal{N} \subseteq \mathscr{X}$ defined as

\begin{align*} \delta_\mathsf{b}(\mathcal{M}, \mathcal{N}) &= { ({I, K}) \in \mathscr{X} \mid \exists J \, \exists \mathsf{p} : \mathcal{M} \Join^{J}_{\mathsf{p}} \mathcal{N} \land I \subseteq J \subseteq K \land (\mathsf{p} \in K \backslash I \Longrightarrow K = J) } . \end{align*}

The function $\delta_\textsf{b}$ introduces more exceptions than $\delta_\textsf{a}$ . A conflict on $\mathsf{p}$ w.r.t. J leads to the introduction of interpretations in which atoms either maintain the truth value they had in J, or they become undefined. They must also satisfy an extra condition: when $\mathsf{p}$ becomes undefined, no other atom may pass from false to undefined. This leads to operators that satisfy all syntactic properties.

Theorem 72 (Syntactic Properties of $\delta_\textsf{b}$ Slota and Leite 2012a) Let $\mathbin{\oplus}$ be a $\delta_\textsf{b}$ -driven rule update operator. Then $\mathbin{\oplus}$ respects support, language conservation, fact update, causal rejection, acyclic justified update, immunity to tautological and empty updates, and primacy of new information.

Under $\mathsf{RR}$ equivalence, the postulate that requires update operators to be syntax indepent can be defined as follows, for a rule update operator $\mathbin{\oplus}$ and programs $\mathcal{P}$ , $\mathcal{Q}$ , $\mathcal{U}$ , and $\mathcal{V}$ :

$\mathsf{PU4}_\mathrm{RR}$ If $\mathcal{P} \equiv_{\mathsf{RR}} \mathcal{Q}$ and $\mathcal{U} \equiv_{\mathsf{RR}} \mathcal{V}$ , then $\mathcal{P} \mathbin{\oplus} \mathcal{U} \equiv_{\mathsf{RR}} \mathcal{Q} \mathbin{\oplus} \mathcal{V}$ .

Theorem 73 (Syntax Independence of $\delta_\textsf{b}$ Slota and Leite 2012a) Let $\mathbin{\oplus}$ be a $\delta_\textsf{b}$ -driven rule update operator. Then, $\mathbin{\oplus}$ respects $\mathsf{PU4}_\mathrm{RR}$ .

It is worth noting that $\delta_\textsf{b}$ -driven operators are very closely related to the $\textsf{JU}$ semantics, even on programs with cycles. They diverge from it only on programs with tautologies.

Theorem 74 (Slota and Leite 2012a) Let $\boldsymbol{P}$ be a DLP, J an interpretation and $\mathbin{\oplus}$ a $\delta_\textsf{b}$ -driven rule update operator. Then,

• $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\textsf{S}_{\mathbin{\oplus}}} \subseteq [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}}$ and

• if $\mathsf{all}(\boldsymbol{P})$ contains no tautologies, then $[\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\mathsf{JU}} \subseteq [\kern-.3ex[{\boldsymbol{P}}]\kern-.3ex]_{\textsf{S}_{\mathbin{\oplus}}}$ .

This means that up to the case of tautologies, $\delta_\textsf{b}$ can be seen as semantic characterisation of the justified update semantics: it leads to stable models that, typically, coincide with justified update models.

Example 75 Consider again the program $\mathcal{P}$ from the example in the introduction, which contains the rules

\begin{align*} \mathsf{goHome} \leftarrow \mathop{\sim\!} \mathsf{money}.& &\mathsf{goRestaurant} \leftarrow \mathsf{money}.& &\mathsf{money}. \end{align*}

and its update $\mathcal{U}$ with the rules

\begin{align*} \mathop{\sim\!} \mathsf{money} &\leftarrow \mathsf{robbed}. & \mathsf{robbed} &. \end{align*}

Unsurprisingly, $\delta_\textsf{b}$ would only introduce exceptions to the third rule of $\mathcal{P}$ . A $\delta_\textsf{b}$ -driven rule update operator $\mathbin{\oplus}$ would produce, as the result of $\mathcal{P}\mathbin{\oplus}\mathcal{U}$ , a program $\mathsf{RR}$ -equivalent to:

\begin{align*} \mathsf{goHome} &\leftarrow \mathop{\sim\!} \mathsf{money}. \\ \mathsf{goRestaurant} &\leftarrow \mathsf{money}.\\ \mathsf{money} &\leftarrow \mathop{\sim\!} \mathsf{robbed}. \\ \mathop{\sim\!} \mathsf{money} &\leftarrow \mathsf{robbed}.\\ \mathsf{robbed} &. \end{align*}

Example 76 Going back to Example 65 where the programs $\mathcal{P}$ , $\mathcal{U}$ , and $\mathcal{V}$ were as follows:

\begin{align*} \mathcal{P}:\quad \mathsf{p}&. & \mathcal{U}:\quad \mathop{\sim\!} \mathsf{p} &\leftarrow \mathsf{q}. & \mathcal{V}:\quad \mathop{\sim\!} \mathsf{q} &\leftarrow \mathsf{p}. \\ \mathsf{q}&. \end{align*}

A $\delta_\textsf{b}$ -driven rule update operator $\mathbin{\oplus}$ would produce, up to $\mathsf{RR}$ -equivalence, the following results, which respect both support and fact update:

\begin{align*} \mathcal{P} \mathbin{\oplus} \mathcal{U}:\quad \mathsf{p} &\leftarrow \mathop{\sim\!} \mathsf{q}.\\ \quad \mathsf{q}&.\\ \quad \mathop{\sim\!}\mathsf{p} &\leftarrow \mathsf{q}. \end{align*}

\begin{align*} \mathcal{P} \mathbin{\oplus} \mathcal{V}:\quad \mathsf{p}&.\\ \quad \mathsf{q}&\leftarrow \mathop{\sim\!} \mathsf{p}\\ \quad \mathop{\sim\!}\mathsf{q} &\leftarrow \mathsf{p}. \end{align*}

The new monotonic characterisation of rules – $\mathsf{RE}$ -models – and the generic method for specifying semantic rule update operators in which a logic program is viewed as the set of sets of $\mathsf{RE}$ -models of its rules and updates are performed by introducing additional interpretations to the sets of $\mathsf{RE}$ -models of rules in the original program, allowed the definition of concrete update operators that enjoy a combination of syntactic as well as semantic properties that had never been reconciled before.

Acknowledging rules as first-class objects by viewing a program as the set of sets of their models essentially amounts to adopting the view used by base revision operators (GÄrdenfors 1992; Hansson 1993) where a theory is composed of a set of formulas, each considered an atomic piece of knowledge that could be falsified by an update. This view has also been more recently adopted within the context of description logic updates (Liu et al. 2006; De Giacomo et al. 2009; Calvanese et al. 2010; Lenzerini and Savo 2011).

Nevertheless, departing from $\textsf{HT}$ models and using $\mathsf{RE}$ -models instead may raise a few eyebrows. After all, characterising strong equivalence between programs through $\textsf{HT}$ models is one of the great landmarks in the history of answer-set programming. However, strong equivalence characterised by $\textsf{HT}$ models only considers the union of rules, while other kinds of operations must also be considered when dealing with belief change such as updates and revisions, for example, falsifying an atom that was previously true. Just as the rule $\mathsf{p} \leftarrow \mathsf{q}.$ specifies $\mathsf{q}$ as a justification for $\mathsf{p}$ , the rule $\mathop{\sim\!} \mathsf{p} \leftarrow \mathsf{q}.$ should be seen as specifying $\mathsf{q}$ as a justification for $\mathop{\sim\!} \mathsf{p}$ and the rule $\mathop{\sim\!} \mathsf{q} \leftarrow \mathsf{p}.$ as specifying $\mathsf{p}$ as a justification for $\mathop{\sim\!} \mathsf{q}$ . Whereas the latter two rules are $\textsf{HT}$ equivalent – each can be modularly replaced by the other, the remaining rules staying the same – they provide different justifications in a dynamic setting, for example, when used to update the program $\mathcal{P} = {\mathsf{p}., \mathsf{q}}$ : the former provides a justification to make $\mathsf{p}$ false while the latter a justification to make $\mathsf{q}$ false. Distinguishing between these two rules, and between them and the integrity constraint $\leftarrow \mathsf{p},\mathsf{q}.$ , is precisely the difference between $\textsf{HT}$ models and $\mathsf{RE}$ -models.

Other properties that are obeyed by a $\delta_\textsf{b}$ -driven rule update operator $\mathbin{\oplus}$ include, for example, initialisation ( $\emptyset \mathbin{\oplus} \mathcal{U} \equiv \mathcal{U}$ ), non-interference (If $\mathcal{U}$ , $\mathcal{V}$ are over disjoint alphabets, then $(\mathcal{P} \mathbin{\oplus} \mathcal{U}) \mathbin{\oplus} \mathcal{V} \equiv (\mathcal{P} \mathbin{\oplus} \mathcal{V}) \mathbin{\oplus} \mathcal{U}$ ), absorption ( $(\mathcal{P} \mathbin{\oplus} \mathcal{U}) \mathbin{\oplus} \mathcal{U} \equiv \mathcal{P} \mathbin{\oplus} \mathcal{U}$ ), augmentation (If $\mathcal{U} \subseteq \mathcal{V}$ , then $(\mathcal{P} \mathbin{\oplus} \mathcal{U}) \mathbin{\oplus} \mathcal{V} \equiv \mathcal{P} \mathbin{\oplus} \mathcal{V}$ ), among others. A more thorough discussion on $\delta_\textsf{b}$ -driven rule update operators’ properties as well as on the reasons why they fail other semantic properties drawn from the KM postulates are given by Slota and Leite (2012a).

Despite this success, a closer inspection shows that $\mathsf{RR}$ -equivalence might still be slightly too strong for characterising updates, because programs such as ${\mathsf{p}.}$ and ${\mathsf{p}., \mathsf{p} \leftarrow \mathsf{q}.}$ are not considered $\mathsf{RR}$ -equivalent even though we expect the same behaviour from them when they are updated. A notion of program equivalence that is weaker than $\mathsf{RR}$ -equivalence but stronger than $\mathsf{RE}$ -equivalence so that both $\mathsf{BU4}$ and properties such as $\mathcal{P} \cup \mathcal{U} \mathrel\mid= \mathcal{P} \mathbin{\oplus} \mathcal{U}$ can be achieved under a single notion of program equivalence still needs to be found. Slota and Leite (2011) speculate that this could be solved by adopting a weaker equivalence – $\mathsf{SMR}$ -equivalence – which discards rules whose set of models are supersets of the set of models of other rules. However, such equivalence is too weak since, when instantiated with $\mathsf{RE}$ -models, programs such as ${\mathop{\sim\!}\mathsf{q}.}$ and ${\mathop{\sim\!} \mathsf{q}., \mathsf{p} \leftarrow \mathsf{q}.}$ are $\mathsf{SMR}$ -equivalent although, when updated by ${\mathsf{q}.}$ , different results are expected for each of them.

7 State of affairs – comments and outlook

McCarthy (1998) described elaboration tolerance as “the ability to accept changes to a person’s or computer program’s representation of facts about a subject without having to start all over”, arguing that human-level AI will require representation formalisms that are elaboration tolerant. Representing knowledge as a DLP – a sequence of logic programs – equipped with automated mechanisms to deal with overlapping, possibly conflicting information, as those provided by the rule update semantics surveyed in this paper, constitutes one significant step towards equipping logic programming with elaboration tolerance. It allows for the kind of incremental specification proposed by McCarthy where one can focus on specifying what is new or what has changed, adding it to the end of the sequence, without having to rework a new encompassing representation.

One of the most important lessons learnt so far is that the syntactic nature of answer-set programming cannot be ignored when programs are subjected to a belief change operation such as an update, or even a revision. Whereas this was at the heart of the rejection of model-based updates, which led to the myriad of approaches developed during the second era – syntax-based updates – it was partially forgotten at the beginning of the third era – semantics-based updates – with the promise that characterising a program through its $\textsf{HT}$ models would move us away from having to rely on the program’s syntax. Theorem 64 killed this hope by showing that such a characterisation of programs based on $\textsf{HT}$ models simply cannot be used if fundamental properties such as support and fact update are required. And these are indeed two fundamental properties. Fact update is a very straightforward, simple and rather undisputed property, which corresponds to the simple unconditional change operations – insertion and deletion – performed on extensional (relational) databases, for example, corresponding to the SQL commands INSERT/DELETE $\mathsf{fact}$ FROM P. The second property, support, is related to the fact that implication in rules plays a significantly different role than material implication in classical logic, for example, not allowing for the contrapositive, instead being tied to the intuitionistic logic of here-and-there (Heyting 1930; Pearce 1997) where the notion of truth is tied to the notion of proof/justification, somehow provided by rules from their bodies to their heads. Accordingly, unsupported atoms are usually not accepted in logic programming.

The negative result encoded by Theorem 64 should certainly make us look back to the so-called syntactical approaches through a different set of lenses, less critical of the fact that its syntactic features play a central role, and see whether they indeed provide a viable alternative, such as the $\textsf{RD}$ semantics, which is the only one immune to tautological updates while maintaining all other syntactical properties discussed here. But at the same time, Theorem 6.1.3 should not drive us away from the pursuit of a semantical characterisation of updates that somehow reconciles the syntactical properties such as support, fact update, and causal rejection with the semantic properties encoded in both the AGM and KM postulates.

Acknowledging the importance of these syntactical properties, Binnewies et al. (2018) also adopted $\textsf{HT}$ models as the underlying semantic characterisation of logic programs to introduce partial meet and ensconcement constructions for logic program belief change, which allowed them to define syntax-preserving operators that obey support.

The introduction of the abstract exception-driven update abstract framework (Slota and Leite 2012b) seems to be another important step in the direction of reconciling the syntactical nature of logic programming with the semantic properties encoded in the AGM family of postulates. On the one hand, it served as a framework to capture updates of logic programs, namely the $\textsf{JU}$ semantics, reconciling semantical as well as syntactical properties. It did so by using $\mathsf{RE}$ -models to characterise rules, and viewing a program as the set of sets of the $\mathsf{RE}$ -models of its rules. This way, it acknowledged rules as the atomic pieces of knowledge while, at the same time, abstracting away from unimportant differences between their syntactic forms, focusing on their semantic content. On the other hand, this abstract framework was shown to also capture several update operators used for ontology updates, such as the model-based Winslett’s operator, or the formula-based WIDTIO and bold operators (Liu et al. 2006; De Giacomo et al. 2009; Calvanese et al. 2010; Lenzerini and Savo 2011).

The exception-driven update framework also seems to provide a promising vehicle to reconcile updates in classical logic with updates of logic programs, opening up a promising avenue to investigate updates of hybrid knowledge bases composed of rules and ontologies (Slota 2012; Slota et al. 2015). Additionally, the logic programming instantiation of the exception-driven update framework shed new light into the long lasting problem of state condensing, ¹⁰ which was solved by Slota and Leite (2013) for the $\textsf{JU}$ and $\textsf{AS}$ semantics, by resorting to more expressive classes of answer-set programs, namely nested and disjunctive.

The historical account of the research on updating logic programs found in this paper is almost entirely focused on the declarative side of the problem, leaving out most procedural and computational aspects. Our choice to follow this path was somehow grounded on the fact that over the years the procedural and computational aspects have played a secondary role in this line of research. As far as we know, there are currently no efficient native implementations available to compute the $\mathsf{S}$ -models for any of the semantics $\mathsf{S}$ presented in this paper. The absence of efficient native implementations is more important given the known negative results regarding state condensing, which in general prevent the direct usage of existing efficient solvers, since it is in general not possible to construct a single logic program that corresponds to the result of the updates encoded in a DLP, written in the same language $\mathcal{L}$ as the DLP. Several authors have addressed the procedural and computational aspects of updating logic programs through the definition of general transformations that convert any DLP into a single logic program – written in a language that extends to the original language $\mathcal{L}$ with new propositional symbols to allow the representation of the temporal aspect of the DLP, and other notions such as the rejection of rules – whose stable models, restricted to the original language $\mathcal{L}$ , correspond to the $\mathsf{S}$ -models according to the rule update semantics $\mathsf{S}$ in question. Each of the semantics based on causal rejection has one such corresponding transformation. With these transformations, the $\mathsf{S}$ -models of the DLP can be computed through the resulting logic program using existing efficient solvers such as clasp (Gebser et al. 2011) and dlv (Leone et al. 2006), even though the syntactical overhead introduced by the transformations could result in a significant computational cost. Delgrande et al. (2007), on the other hand, define their semantics through a transformation into a prioritised logic program, which doesn’t need the extension of the language $\mathcal{L}$ , but for which there are no efficient native implementations, as far as we know. Hence, the resulting prioritised logic program would have to be further converted into a logic program to enable the use of existing efficient solvers, with a similar syntactical overhead as the transformations mentioned above. Other semantics either do not mention procedural and computational aspects, or provide transformations that only deal with DLPs of length two, whose result cannot be further updated, as discussed earlier in this paper. All in all, whereas the known results regarding the procedural and computational aspects of many of the semantics presented in this paper are enough to allow the development of prototypical implementations – some of which have actually been created by the authors of the original semantics, even if no longer easily available – more research is needed to develop native efficient implementations that could support large applications.

Despite the progress towards a full understanding of updates of logic programs, many open questions remain, whose difficulty in answering seems to always be tied to the tension created by the syntactical nature of logic programs, and the wish for a semantical characterisation of belief change operations. We discuss some of the most important ones below.

Can other syntactical rule update semantics be captured by the exception-driven update framework? The need to detect non-tautological irrelevant updates (Alferes et al. 2005; ŠefrÁnek 2006; ŠefrÁnek 2011) to capture, for example, the $\textsf{RD}$ semantics poses a number of challenges. For instance, simple exception functions based on local exceptions such as $\delta_\textsf{c}$ cannot distinguish an update of ${\mathsf{p}.}$ by $\mathcal{U} = {\mathop{\sim\!} \mathsf{p} \leftarrow \mathop{\sim\!} \mathsf{q}., \mathop{\sim\!} \mathsf{q} \leftarrow \mathop{\sim\!}\mathsf{p}.}$ , where it is plausible to introduce the exception $\langle \emptyset, \emptyset \rangle$ , from an update of ${\mathsf{p}., \mathsf{q}.}$ by $\mathcal{U}$ , where such an exception should not be introduced due to the cyclic dependency of justifications to reject $\mathsf{p}.$ and $\mathsf{q}.$ In such situations, context-aware functions need to be used. Such functions would also have the potential of satisfying properties such as $\mathsf{BU3}$ and associativity ( $\mathcal{P} \mathbin{\oplus} (\mathcal{U} \mathbin{\oplus} \mathcal{V}) \equiv (\mathcal{P} \mathbin{\oplus} \mathcal{U}) \mathbin{\oplus} \mathcal{V}$ ).

Can we characterise rule update semantics through binary operators on some class of programs over the same alphabet so that they can be iterated, hence addressing the state condensing problem? Whereas answering the previous question on this list might certainly provide hints on how to characterise rule update semantics through binary operators, it may well be a problem without solution for some of the existing semantics, even resorting to more expressive classes of logic programs. This is probably the case with the $\textsf{PRZ}$ and the $\textsf{RVS}$ semantics because of how they are defined, which involves the construction of possibly more than one program, using maximality criteria. Given its properties and relationship with the $\textsf{JU}$ and $\textsf{AS}$ semantics, for which a solution already exists, perhaps the bigger reward lies in addressing this question for the $\textsf{RD}$ semantics.

What is the appropriate logic corresponding to the $\mathsf{RE}$ -models? Just as the logic of here-and-there (Heyting 1930; Pearce 1997), a nonclassical logic extending intuitionistic logic, served as a basis for a logical characterisation of answer-set programming, finding the nonclassical logic that subsumes $\mathsf{RE}$ -models and provides an adequate basis to characterise the dynamics of logic programs would be most useful. The difficulties in extending even $\mathsf{RE}$ -models to more general classes of logic programs hints on the difficulty of this task.

Can a characterisation based on $\mathsf{RE}$ -models bring added value when used to describe logic programs that undergo other belief change operations such as revision, contraction, erasure, forgetting and ensconcement? Ultimately, the answer to this question boils down to whether the rule $\mathop{\sim\!} \mathsf{p} \leftarrow \mathsf{q}.$ , the rule $\mathop{\sim\!} \mathsf{q} \leftarrow \mathsf{p}.$ , and the integrity constraint $\leftarrow \mathsf{p},\mathsf{q}.$ should be considered equivalent, or not, within the belief change operation in question. In the context of updates of logic programs, as we have seen throughout this paper, some semantics distinguish them, as for example those based on causal rejection, where updating the program ${\mathsf{p}.,\mathsf{q}.}$ with $\mathop{\sim\!} \mathsf{p} \leftarrow \mathsf{q}.$ results in the model ${\mathsf{q}}$ while updating it with $\mathop{\sim\!} \mathsf{q} \leftarrow \mathsf{p}.$ would result in the model ${\mathsf{p}}$ . If this distinction makes sense in other belief change operations – for example, one might conceive a revision operator with a similar behaviour – then a characterisation based on $\mathsf{RE}$ -models might be more suitable than using, for example, $\textsf{HT}$ models.

How can the syntax-based updates be extended to deal with disjunctive logic programs? Interestingly, updating disjunctive logic programs under the answer-set semantics has received very little attention so far. Whereas extending some of the syntax-based approaches seems straightforward – in fact, the $\textsf{RVS}$ semantics was defined by Sakama and Inoue (2003) for disjunctive logic programs – dealing with semantics such as those based on the causal rejection principle might prove more difficult. For example, conflicts that provide a cause for rejecting rules would no longer be restricted to pairs of rules.

How to precisely characterise the related though distinct belief change operations of revision and update within the context of answer-set programming? At an abstract level, the difference between these two forms of belief change rests on whether we are acquiring better information about a static world (revision) or whether we are acquiring newer information about a changing world (update). The influence of such difference when dealing with belief change in answer-set programming has been limited and, to some extent, restricted to the extent to which one seeks to deal with inconsistencies/contradictions: whereas in revision they are removed at any cost, even as the result of an empty/tautological belief change operation, in updates such an empty/tautological operation should have no effect. More is needed in order to better understand and characterise what revision and update have in common, and in difference, when taken within the context of answer-set programming.

Does it make sense to consider other causes for rejection within causal-rejection based semantics? The answer to this question is, to some extent, related to the previous question, inasmuch as it relates to finding other conflicts that, if not resolved, could result in a contradiction/incoherence which should be avoided in the context of an update. But other avenues for extending the causes for rejection exist such as, for example, explicitly declaring certain pairs of otherwise unrelated atoms as being in conflict.

All in all, the quest for the perfect approach to updating answer-set programs has been quite fruitful. We are not there yet – and we may never be – but we are certainly much closer.