Consistent Transformations of Knowledge Bases in Answer Set Programming

Abstract

-One of the major and traditional topics of Artificial Intelligence over many years has been knowledge representation and reasoning. It has proved to be a strong theoretical framework for Logic Programming to manage dynamic knowledge bases. In this work, one of two parts, we go through current and some of those past proposals to update knowledge coded into Answer Set Programming knowledge bases, by analysing their features and identifying challenges to represent correct evolving knowledge.

INTRODUCTION

T appeared as a technical report in [ 3 ]. Here we revisit it

HERE is a preliminary version of this paper has first and update it to current approaches, to classify them and compare them.

One of the significant and traditional topics in Artificial Intelligence over the last years has been knowledge representation and reasoning; this issue has proved to be a robust theoretical framework to manage knowledge bases. This particular topic has become more widely studied in the administration of knowledge bases of intelligent (rational) agents, especially in situations of incomplete knowledge from a changing environment. This area of research is known in the literature as belief change, and its relevance to program transformation is fundamental if we are interested in producing correct knowledge bases, especially if they represent critical systems requirements.

The history of semantics for updates1 of logic programs (in our context, formalisms for program transformations) is rather long. Indeed, it begins in the days of some of the first versions of PROLOG with its commands assert and retract. However, sooner they began to yield conflicting information and other (perhaps unexpected) side effects. It was also time of research on databases with publications like [ 21 ], and in particular for logical databases [ 19 ], [ 20 ], [ 36 ]. Nevertheless, some of the first formalisms to carry out proper changes to monotonic theories have been originally studied by [ 6 ], [ 23 ], [ 25 ], [ 27 ], [ 29 ], whereas in the non-monotonic side by [ 26 ], [ 28 ], [ 30 ].

In particular, [ 22 ] formulated the Stable Models Semantics (also refereed as Answer Sets Semantics, SM or simply ASP), and more concrete proposals arose within that framework, aimed at the problem of updating knowledge represented This project is mainly supported by The National Council for Science and Technology, CONACYT, 280712, Consolidacio´n de Laboratorios Nacionales 2017. We are also grateful to The Autonomous University of Juarez Manuscript received October 10, 2016 at ENC 2016; revised October 24, 2016.

1. For historical reasons, in this paper we call it update, although it’s actually belief revision. A study on the difference was first introduced by [ 24 ]. in ASP [ 2 ], [ 9 ], [ 14 ], [ 15 ], [ 16 ], [ 17 ], [ 32 ], [ 34 ], [ 35 ], [ 38 ], [ 39 ], [ 42 ].

In this work we introduce current and some of those past proposals to transform knowledge bases represented by logic programs. We point out features as well as some of their limitations to represent correct evolving knowledge and of course, correct program transformations. Nevertheless, this survey is just a small thread of a massive research over more than two decades, and is by no means exhaustive. It just takes into account those proposals that are the most relevant and of interest in our opinion.

The rest of our paper is divided into a very quick glimpse of basic background (Section 2) necessary to understand program transformations in ASP; the approaches to update logic programs are classified into several different categories (Sections 3–6) and a section for discussion and final remarks—Section 7. Each of the approaches show a few particular examples to illustrate their definitions, as well as common observations to show disadvantages and to compare with the others. 2

PRELIMINARIES

A main foundation of these proposals is the well-known Answer Sets Semantics, also known as Stable-Models Semantics. In this paper it is assumed, though, that the reader is familiar with basic notions of logic programming and (extended) disjunctive logic programs, DLP, EDLP, which are easily available in the literature. 2.1

Logic Programming and Answer Sets

As we represent knowledge by means of ASP programs for being one of the most studied and founded successful semantics to reason about incomplete (unknown) information, in the following we give a very-short description of Answer Sets Programming (ASP), which is identified with other names like Stable Logic Programming or Stable Model Semantics [ 22 ] and A-Prolog. Its formal language and some more notation are introduced from the literature as follows. Definition 1 (ASP Language, LASP). In the following LASP is a language of propositional logic with symbols: a0; a1; : : : ; connectives: “,” (conjunction) and metaconnective “;”; disjunction _, also denoted as j; (and its counterpart, !); : (default negation or weak negation, also denoted with the word not); “ ” (strong negation, equally denoted as “ ”). The propositional symbols are also called atoms or atomic propositions. A literal is an atom or a strong-negated atom. A rule is an ordered pair H( ) B( ), where H( ) is a possiblyempty finite set of literals in disjunction and B( ) a possibly-empty finite set of literals (or default-negated literals) in conjunction.

The meaning we give the propositional constants is the same meaning than having an empty set in either component of a rule. Finally, a logic program (or just program) is a possibly empty finite set of rules, also known as knowledge base.

With the notation just introduced in Definition 1, one may construct program clauses of several forms that are well known in the literature, such as Extended Logic Program (ELP), Extended Disjunctive Logic Program (EDLP), etc.

Informally, the semantics of such programs consists of reducing the general rules to rules without default negation “:”, because the latter are universally well understood. For page limitation, we just skip the formal definition of such reduct, which can be easily found in the literature.

Formally, we say that a program is inconsistent if and only if it has no answer sets, and consistent otherwise. Definition 2 (EDLP). An extended disjunctive logic program is a set of rules of form `1 _ `2 _ : : : _ `l `l+1; : : : ; `m; :`m+1; : : : ; :`n (1) where `i is a literal and 0 l m

Naturally, an extended logic program (or ELP hereafter) is a finite set of rules of form (1) with l = 1; while an integrity constraint (also known in the literature as strong constraint) is a rule of form (1) with l = 0; while a fact is a rule of the same form with l = m = n. In particular, given a set of literals A, for a literal ` 2 A, the complementary literal is ` and vice versa; for a set M of literals, M = f ` j ` 2 Mg, and LitM denotes the set M [ M; finally, a signature LK is a finite set of literals occurring in a knowledge base, K. Additionally, given a set of literals M A, the complement set M = A n M.

The well-known semantics of an EDLP consists of reducing general rules to rules without default negation “:” because the latter can be interpreted in classical logic by means of the well-known Herbrand models. In particular, the reduced rules with no default negation Mon of a rule of the form (1) is `1 _ `2 _ : : : _ `l `l+1; : : : ; `m (2) where `i are literals and 0 l m. This kind of rules is known in the literature as monotonic counterpart or positive program. Additionally, the monotonic counterpart of a set of rules is the set of the monotonic counterparts of its rules.

Now let us introduce the meaning of programs with both monotonic and nonmonotonic counterparts. (3) (4)

Suppose a finite ground program K, consisting of clauses of form (1). For any set S LK, the answer-sets reduct KS corresponds to

KS = f`1 _ `2 _ : : : _ `l

`l+1; : : : ; `m : f`m+1; : : : ; `ng \ S = ;g Stating S as a set of literals rather than atoms, makes one of the differences with Stable-models semantics.

Next, the meaning of a monotonic counterpart corresponds to its minimal classical model as follows.

Definition 3 (Minimal Closure, Cn(K)). Let K be a positive extended disjunctive program and LK the signature (set of all ground literals) from K. The set Cn(K) denotes the minimal subset of LK where, 1) for each ground clause p0 _ p1 _ _ pl q1; : : : ; qm in K, q1; : : : ; qn 2 S implies pi 2 S for some 0 i l; and for each ground clause of the form ?

q1; : : : ; qm fq1; : : : ; qmg * S. 2) If S contains a pair of complementary literals, then

S = LK.

Note that item (2) in Definition 3 extends Stable Models by giving a meaning to strong negation.

Finally, an answer set of a given program K is a minimal closure of its reduct as following stated.

Definition 4 (Answer Set). Suppose K is a EDLP and S a set of literals. Then, S is an answer set of K if and only if S = Cn(KS ).

Notice that all stable models can be viewed as minimal Herbrand models of a set of first-order sentences, but not the converse. Additionally, S is a consistent answer set of a given program K if it does not contain a complementary pair of literals.

Although we have introduced ASP as propositional (ground) programs, fixed non-ground ASP-programs of arbitrary arity are also considered in the same way than [ 13 ] do. Accordingly, non-ground ASP-programs with variables or constants as arguments can be seen as a simplified expressions of larger ground (propositional) ones without variables, where each ground program K is a set of its ground rules 2 K. In addition, a ground rule is the set obtained by all possible substitutions of variables in by constants occurring in K [ 13 ].

In general, ASP is the necessary background and main foundation that is common to all the approaches here presented. Yet another framework employed by a few of the approaches to update knowledge in ASP is called Generalized Answer Sets.

This is the basic background to understand the following approaches to update knowledge represented in ASP programs. So, let us begin with the different proposals. 3

EITER’S TEAM

To the best of our knowledge, [ 17 ] achieved the most complete survey of most known semantics for updates of logic programs, by gathering relevant postulates and principles from the literature. Their approach first appeared in [ 14 ] with a vast study of well-known and well-accepted postulates and properties, and later refined [ 17 ] and extended to be a main component in more general problems like agents [ 18 ] or preferences. They also implemented a solver2 that is the main engine of an experimental graphical front end we have implemented3.

In [ 17 ] they formulate a natural definition for updating logic program sequences on a restricted Answer Sets language by rejecting rules under a causal rejection principle. The principle is due to [ 9 ] that later, however, turned out to be counterintuitive. See [ 8 ], [ 18 ], [ 32 ]. The problem comes up from a strong dependency upon the syntax of programs, first noted by [ 18 ], [ 33 ], [ 37 ], and is further discussed in Section 4. In particular, the formula under which they, [ 17 ], [ 18 ], analyze and describe update properties is as follows.

Given an update sequence (K1; K2; : : : ; Kn), with 2 n, over a set of atoms A, assume A as an extension of A by new pair-wise unique atoms rej( ) and i, for each rule occurring in K; each atom 2 A, and 1 i n. An injective naming function Name( ; ) is also assumed, which assigns to each rule in a program Ki a unique name, Name( ; Ki), provided that Name( ; Ki) 6= Name( 0; Kj ) whenever i 6= j. Finally, for a literal `, they use `i to denote the result of replacing an atomic formula of ` by i.

The intuitive idea of rej( ) is that of an atom that blocks (rejects or inhibits) a related rule when the former is true, provided that there is another more recent rule 0 with conflicting information.

Then [ 17 ] define the intended answer sets of an update sequence (K1; K2; : : : ; Kn) in terms of the answer sets of K/ = (K1 / / Kn). In other words, the models are back expressed in the original alphabet by the intersection of them and the original atoms: Definition 5 ( [ 17 ]). Given an update sequence,

(K1; K2; : : : ; Kn) over a set of atoms A, then S LitA is an update answer set of (K1; K2; : : : ; Kn) if and only if S = S0 \ A for some answer set S0 of K/ = (K1 / / Kn). The collection of all the update answer sets of (K1; K2; : : : ; Kn) is denoted by U (K1; K2; : : : ; Kn).

In addition to the declarative version, this semantics is also supported by a solver available both for downloading and running online4, which is yet another valuable asset worth considering when comparing the approach with others.

Let us present the following example, inspired in [ 17 ], to illustrate their approach. Later we will reuse it with other approaches: Example 1. Suppose we have the following simple-butillustrative two sets of system requirements (translated 2. Available at http://www.kr.tuwien.ac.at/staff/giuliana/project. html#Download.

3. The graphical online front end to [ 18 ] command-line solver can be found at: http://logic-lab.sourceforge.net/upd.html.

4. We have installed an online version, which also provides a graphicoriented interface on the server itself—http://logic-lab.sourceforge. net/upd.html. Obviously, no download or installation is necessary to run the latter version. into ASP), h K1; K2 i, representing the initial and current knowledge of an intelligent greenhouse, which acts autonomously under specific circumstances, where K1 = fnotify

K2 = f wSystem wPlants night ; not wSystem

night wSystem wSystemg blackout blackout g Program K1 might represent the following configuration:

Notify when it’s night and there isn’t evidence of the water system working.

It’s night now.

Water the plants when the water system is working.

The system is working now.

The unique model of such requirements is

fnight ; wPlants; wSystemg: Now suppose that the systems engineer needs to incorporate a new rule that states to not water plants when the ground is flood: wPlants gFlood . By their definition, the transformed update program K/ = (K1 / / Kn) consists of the following rules—amongst the rest of the rules that we skip for page constraints: wSystem1 wSystem2 blackout ; not rej( 5)

rej( 4) not wSystem2 notify 1 notify 2: notify notify 1 wSystem1 wSystem2: wSystem wSystem2 wSystem3: wSystem blackout 2 blackout 3: blackout wSystem1 wSystem2 blackout 2 not rej( 4): whose unique answer set is fnotify 1; night ; night 1; rej( 4); wSystem2; blackout ; blackout 2; notify ; wSystemg and its update answer set is just: fnight ; blackout ; notify ; wSystemg.

Let us complete Example 1, which is one of the major disadvantages the framework exhibits [ 35 ]: Observation 1 (Continued Example 1). Now let us consider Example 1 again and perform a second update to the sequence with program K3 = f blackout g. Accordingly, the new answer set of the resulting update program is fwSystem1; wSystem; night 1; night ; wPlants1; wPlants; rej( 6); blackout 3; blackout g: As a result, by Definition 5 the corresponding update answer sets are U (K1; K2) = fnight ; blackout ; notify ; wSystemg and U (K1; K2; K3) = fwSystem; night ; wPlants; blackout g: However, this result does not coincide with common intuition, just because one of the possible models contradicts the latest fact ( blackout ) stating that it is no longer happening! On the other hand, the second model says that system is working, back again for no obvious reason, which is counterintuitive too.

Despite the satisfactory deep nice analysis they realize of known postulates and principles from the literature and their available solver, yet another major disadvantage of [ 17 ]’s approach has to do with syntactic and semantic contents, as illustrated by the following example inspired from [ 8 ] and modified by [ 37 ] that may produce counterintuitive models: Observation 2.

Suppose an agent who believes that when it is day it is not night and vice versa, and that there are stars when it is night and when there are no clouds. Finally, that at the current moment it is a fact that there are no stars. This simple story may be coded5 into a logic program K1 as follows:

K1 = f(day not night ); (stars night ; not cloudy ); (night starsg not day ) whose unique answer set is fday ; starsg. Later, the agent acquires new information stating that stars and constls6 are the same thing, as coded in K2. As soon as the agent updates K1 with program

K2 = f(stars constls); (constls stars)g the augmented alphabet of the two programs contains only one new extra atom with respect to K1: constls. As the model of K2 is obviously the empty answer set, constls is considered synonym of stars by means of K2, and thus the update should not change the original beliefs. However, the update yields an extra answer set in some of the existing update semantics based on the causal rejection principle see [ 8 ], [ 9 ], [ 17 ]: fstars; constls; night g; which does not coincide with common intuition.

The reason is that, although stars can not be true, introducing constls gives another possibility for stars to be true. Thus, the additional answer set is derived [ 37 ]. In general, these supplementary rules in the update are a conservative extension [ 31 ] to K1: the original language is extended and all answer sets ought to be extensions of the old answer sets. In this specific situation, constls should be true if and only if stars is true.

So, Observation 2 means that the proposed semantics is inappropriate to model the corresponding kind of problems.

Finally, updating knowledge through a sequence of logic programs does not seem to be natural in our opinion. For instance, consider Observation 1 again and try to perform a new update. Although the authors might have had other goals and intentions, their current approach does not allow to do that (i.e. you would have to “initialize” the sequence and append the new update to it.

To recap, [ 17 ] were very good at gathering relevant postulates and principles from the literature and at analysing them in terms of their proposal. Their approach, however, suffers from a few disadvantages for our interests owing to its reliance on the causal rejection principle (see [ 9 ]) and to its sequence-based approach.

5. Notice that there are other ways to represent the story. The problem is, however, what to do in this particular situation, when the agent’s original knowledge base runs across a redundant piece of information. 6. i.e. constellations.

DYLP AND OTHER EARLY PROPOSALS

One of the earliest approaches to update logic programs through transformations appeared in the late 90’s from [ 9 ], [ 10 ] that was extended to an interesting language called LUPS, by [ 11 ], to specify explicit updates in programs on a semantics that they called Dynamic Logic Programming or DyLP [ 9 ]. Some years later, though, [ 8 ] refined the latter, whom over the previous periods formulated a principle of rejection, also known as causal rejection principle [ 8 ], [ 9 ], [ 17 ] and [ 7 ].

Informally, the called refined principle of rejection consists in rejecting rules of previous and upcoming programs in an update sequence, whenever there are other conflicting rules at the current state.

To begin with, [ 8 ] motivation comes from a simple example to what they themselves called a tautology (a rule from which they expect no models):7 not p not p

(5) One may verify that the rule alone produces no models in their semantics8—i.e. just the empty model, ;, which actually contains all non-positive (default-negated) atoms— and updating knowledge with this rule should have no effect, and that is why they introduced the refined principle of rejection.

Additionally, [ 8 ] explain in a footnote what tautology means: A rule of the form ` B with ` 2 B, where ` is an atom (or a default-negated atom) and the body of a rule, respectively. Although the authors might have had other goals for their approach, this high dependency on syntax will prove to be one of their major disadvantages as a semantics for updates in our opinion, as explained along this paper.

Before introducing their proper definitions for their semantics, a special notation is necessary, which can be obtained from the literature and from [ 8 ].

Intuitively, a refined interpretation of a DyLP program is a dynamic stable model if the following happens. The least model of the positive program, which results from the difference of the rejected rules and the union of the default assumptions, is the same than the union of the interpretation and the default-negated literals that do not appear in the latter.

Definition 6 introduces the model of the transformed program from the original dynamic logic program. The intuition behind Rej( ; ) is the set of rules that conflict (./) with both current and previous ones in the sequence. Moreover, Def( ; ) consists of the positive “default-negated” atoms that do not appear in the intended model.

Formally, two rules, 1, 2, are in conflict, denoted as 1 ./ 2, if and only if H( 1) = not B( 2).

7. Note that the kind of rule in (5) is invalid in LASP, and it also illustrates why strong negation “ ” should not be a simple replacement to “not” in the head. Take for example, the program f p not pg whose unique answer set differs from the empty set: f pg.

8. The details are easily available in the literature, like [ 9 ]. Definition 6 (Dynamic Stable Model, [ 8 ]). Let P be a dynamic logic program and M an interpretation. M is a dynamic stable model of P if and only if9

Although [ 9 ] were some of the first researchers to for

Rej(P; M) = mulate and implement a semantics for updates through f j 2 Ki; 9 0 2 Kj ; i j; ./ 0; M j= B( 0)g; apdrovgarnatmagetsralniksefotrhmeaotnioenssp,othinetyedstoilul thinavtehiqsusietcetiaonf:eFwirsdtilsy-,

Def(P; M) = for the particular syntax and semantics of their transformed fnot a j @ 2 (P); H( ) = a; M j= B( )g; generalized logic programs, which is a different variant of M = least( (P) n Rej(P; M) [ Def(P; M))g: Stable-Models Semantics, or in other words, a non-standard concept of ASP [ 17 ]; secondly, for their causal rejection prin

This approach has had several implementations, includ- ciple that produces the mentioned counterintuitive results. Fiing one for the original version before the so-called refined nally, their sequence-of-knowledge-bases approach is in our principle, and another for the principle itself. Additionally, opinion counterintuitive, as we have already commented at LUPS is also implemented, which we consider a major asset, the end of Section 3. and the following list shows their respective locations: fnot cg; and least[(K0[K1)nRej(P; M)[Def(P; M)] = fnot c; not rg = M. http://centria.di.fct.unl.pt/ jja/updates http://centria.di.fct.unl.pt/ banti/

FedericoBantiHomepage/refdlp.htm

Now let us analyze an example inspired by [ 35 ], originally proposed by [ 9 ].

Observation 3. The above framework has missing information. Let us code the story introduced in Example 1 and Observation 1 as follows: P = K1 R K2 R K3, where: K1 = f(notify not wSystem); (wPlants

wSystem); (wSystem)g;

blackout )g;

K3 = fnot blackout g:

K2 = f(blackout ); (not wSystem M = fwSystem; wPlantsg is a refined dynamic stable model of the update sequence, since the unique rejected rule is blackout and the unique default is not notify , where the least model is

fwPlants; wSystem; not blackout ; not notify g = M: In a similar example [ 35 ] argue, however, that the resulting model is counterintuitive, because after the first update, the refined dynamic stable model was fblackout ; notify g and thus there is no reason to believe that once the power is restored, the system should be working back again! A similar counterintuitive result is given in Observation 1.

In addition to that, there is still a simple example, first suggested by [ 17 ], that still causes counterintuitive results in this DyLP-semantics.

Observation 4. Suppose an initial knowledge base K0 = f(c r); (r)g updated with K1 = fnot r not cg.

Firstly, the initial generalized stable model of K0 is fc; rg, and one would expect no further changes after the update because, according to [ 17 ], such an update should be irrelevant to the known fact r and the derived c. However, the update P = K0 R K1 has the extra model M = fnot c; not rg because

M = fnot c; not rg; Rej(P; M) = frg; Def(P; M) = 9. Notice that it seems they have missed the “ ” and have typed “not a” rather than “not a” in (6) from the original paper in [ 8 ].

Moreover, (6) should be a set of rules, rather than a set of literals, to be sound with the equality in (6)! In the rest of the section, it is assumed the former, as the authors do. 5

MINIMAL CHANGES

In [ 34 ], [ 35 ] they propose three types of updates through program transformation, to which they call inconsistency removal, view updates and theory updates. Each of them correspond to a special case of updates and revision in the literature.

For page and comparison reasons, this paper is focused on theory updates, rather than other special cases such as making an inconsistent program consistent or differentiating between variant and invariant knowledge. As a result, this section does not include other types of belief changes, which are easily available in the literature.

Once the extended abductive program is normalized, its interpretations shall correspond to transformed update programs that consist of the rules of the original theory that don’t belong to the normalized abductive set, merged with a new set of update rules, as specified in [ 35 ].

Next, this transformation of update rules takes part of a new transformation called update program of the normalized extended abductive program that is an intermediate EDLP. This intermediate program specification is as follows, where P is an EDLP over A, and A a set of abducibles, such that A \ A = ;: Definition 7 (Update Program, [ 35 ]). Given an abductive program h P; A i, its update program, U P, is defined as an EDLP such that U P = (P n A ) [ U R:

Then the models of an update program denote the deletion of facts or rules from the original program in the pair. Definition 8 (U-minimal Answer Sets, [ 35 ]). An answer set S of U P is called U-minimal (U-MAS) if there is no answer set S0 of U P such that S0 \ U A S \ U A.

As a result, there is one or more new corresponding updated programs to the U-MAS. 5.1

Discussion

This abduction framework proves to have nice properties of a syntactical minimal change of rules in the original nonmonotonic theory—Theory Updates Definition in [ 35 ]—by means of consistent interpretations of hypothetical changes. With this framework, [ 35 ] can perform particular kinds of updates and maintenance of knowledge-bases consistency, and can also present a vast analysis of disadvantages in other comparable approaches.

In general, [ 35 ]’s first goal is to provide an update semantics to compute their extended abduction. Secondly, they also characterize updates through the extended abduction, as they themselves state it. Consequently, the approach lacks of a proper analysis of more principles and postulates from the literature of program transformation or belief change. Additionally, they characterize different kinds of updates with their extended abduction, claiming that they can provide an algebra of rules deletion, besides the addition of them, to explain observations.

Let us recapitulate [ 35 ]’s approach in a few words. They construct their update program out of the normal abductive form of an extended abductive program h P [ Q; P n Q i whose models are U-MAS’s interpreted from an update program. Last, the interpretations correspond to one (or more) new programs representing knowledge bases, derived from the addition and/or deletion of facts that the U-MAS’s describe in turn.

In [ 35 ] they propose an example as an argument against other approaches—like [ 9 ], [ 17 ]—that brings back previous knowledge of the original theory. That is to say, their interpretation is that a TV in their example10 turns itself on again and it is possible to watch it as well with no reason to do so: ftvon; watchtv ; blackout g, which does not coincide with their intuition. This is similar to our conclusions in Observation 1, where the system is working back again upon no justification. However, this argument seems to be too strong to generalize that all update semantics should behave accordingly, because [ 35 ] are differentiating fluents and actions in a language that does not have such an explicit difference.

Finally, there is a simple example that might represent another disadvantage of this approach.

Observation 5. Suppose the initial knowledge base K = ; updated by a simple fact K1 = fxg. Following [ 35 ]’s framework, the answer sets of its update program is empty: U P = (; n fxg) [ U R, where U R is clearly empty because the extended abductive program from the update pair has no abducibles: A = ; n fxg.

Moreover, although the authors present a deep analysis of their proposal and although it seems to be robust-enough for agent’s changing environment, there is a lack of further and more general properties and a lack of a solver, which make it hard to compare with other alternate approaches. [ 42 ] pointed out that this approach is classified into a syntaxbased semantics. As a result, it has no general semantic foundation that justifies its updates [ 42 ], and by interpreting the resulting knowledge bases with a given semantics might interfere with the ASP semantics that performs the update operation. It is clear that they justify their updates with an extended abductive framework, which is still a specific problem and then leaves the mentioned absence of update characterisation.

Finally, a minor disadvantage is that the approach is undefined to update a knowledge base with an inconsistency. [ 35 ] state that such a kind of update “makes no sense”, which clearly does not mean that an agent or whoever is updating the knowledge base will never come across 10. See [ 35 ] for further details. an originally inconsistent observation. Nevertheless, they do consider cases where an initial knowledge base is originally inconsistent, and they identify such case as inconsistency removal. This method consists in updating an inconsistency knowledge base with an empty update. 6

ZHANG’S

An interesting proposal for updates through program transformation comes from [ 42 ], where the author identifies three types of problems to solve in an update process: elimination of contradictory information, conflict resolution and syntactic representation.

Additionally, one of the applications from [ 12 ] is an interesting language that is specialized in updates of agent’s policies and defined at the top of ASP. In [ 12 ], they specify such policies in terms of clauses with a predefined semiimperative syntactical structure, as well as an initial planning approach.

However, owing to a specialisation the work has on policies, the programmer is restricted and obliged to use reserved words like “always”, “implied by”, “with absence”, etc. which, besides constraining the domain to specific applications, it reduces the language and has potentially different meanings in the meta-language. Nevertheless, they already have a fully fledged system, as they themselves mention it [ 12 ]. 6.1

General View

In [ 42 ] he characterizes program-transformation updates in terms of three main objectives: contradiction elimination, conflict resolution and syntactic representation. The first topic is one of the most obvious in semantics for updates, which should be real by preserving a minimal-change principle and a proper justification. On the other hand, conflict resolution has to do with potential future contradictions an update might yield. That is because of the introduction of two kinds of negations in logic programs—strong and default negation. Finally, once the process meets the two main goals, the author argues that a proper semantics should also preserve as many as possible of the original rules from the updating knowledge base.

In order to realize these three goals, [ 41 ] performs program update transformation by means of a called prioritized logic program. In an intuitive way, this kind of program consists in preferring the latest update to the original knowledge base including non-contradictory but conflicting rules. His approach definitions and plenty of examples are easily accessible in the literature, from which we also recommend [ 3 ].

A mandatory test is the example in Observation 2, which produces counterintuitive results in many of the existing semantics for updates. This is not the case for Zhang’s semantics, whose expected answer set is just what intuition would tell us: fday ; starsg.

Despite this approach is well behaved, though, one of the counter-intuitive examples to [ 42 ]’s approach has to do with solving conflicts between rules, where most of the current semantics differ, as first pointed out by [ 17 ]: Observation 6. Suppose an initial knowledge base K0 = fp not qg being updated by K1 = fq not pg. Its simple-fact update specification corresponds to

UPLP(SK0 ; K1) = (K ; N ; <); where

Initial Knowledge:

Inertial Rules: As a result, its unique answer set SPLP(UPLP(SK0 ; K1)) = fpg and none of its <-relations are used. Next, the minimal subset of K0 that is coherent with its answer set is just K(K0;K1) = K0. Then, the update specification of K0 and K1 is UPLP(K0; K1) = (K1 [ K(K0;K1); N ; <), where (t : p :q); (u : q :p); (u < t):

Finally, its unique reduct q not p comes from

(K1 [ K(K0;K1)) n ftg defeating rule t. Therefore, the conclusion of such an update is just fqg, what we would not expect.

Last, besides not satisfying some of the principles already pointed out, one of the major drawbacks of this approach is being limited to only one update to a knowledge base. Namely, it is undefined for update sequences and for successive updates, which does not seem to lead to immediate practical use. Although [ 42 ] also suggests an extension to one of his earliest approaches in [ 40 ] to deal with multiple updates, his proposal still makes the same strong assumptions when deciding between multiple models, as in Observation 6. 7

CONCLUSIONS

This work is a critique of current and past proposals for update semantics, as an attempt to classify them and to bring out new challenges. This Part I starts with a set of early proposals. All of them update and revise knowledge by means of program transformations in ASP or similar semantics. They run from a wide range from simple-fact one-step updates of logic programs, up to unlimited updates either in a sequence or by an iterative process. Some of these works present a vast collection of postulates and principles for correct knowledge-base changes, and/or implementation. However, nearly all the proposals here introduced still present drawbacks either for being limited to only one update, or for relying on syntactical principles to change the original logic program that leads to counterintuitive results. Nearly all of the issues here pointed out have been surpassed by current approaches, like [ 5 ], where they have found nice properties and applications— [ 1 ], [ 4 ]. On the other hand, for practical and commercial reasons, the proposals here presented are often called semantics for updates, although there are implicit operations in some of them that may suggest a different classification, say semantics for belief revisions. 8

ACKNOWLEDGMENTS

The author is very grateful to J. Dix and W. Jamroga for their many useful comments and proofreading some preliminary versions of this work. Special thanks are due to E. Mart´ınez too, for proofreading this paper.

References

[1] J. C. Acosta-Guadarrama , Rogelio Da´vila Pe´rez, Mauricio Osorio, and Victor Saldivar. Modeling Natural Language Metaphors with an Answer Set Programming Framework , volume LNAI 8856 of ISSN 0302-9743 ISBN 978-3-319-13646-2 , chapter IV , pages 28 - 36 . Springer-Verlag, 2014 .

[2] Juan C. Acosta-Guadarrama . Maintaining knowledge bases at the object level . In Alexander Gelbukh and Angel F. Kuri Morales , editors, Special Session of the 6th International MICAI Conference , pages 3 - 13 , Aguascalientes, Mexico, November 2007 . IEEE Computer Society . ISBN: 978 -0- 7695 -3124-3.

[3] Juan C. Acosta-Guadarrama . A road map of updating in ASP . ISSN: 1860 -8477 IfI-07-16, TU-Clausthal, Clausthal, Germany, December 2007 . 35pp .

[4] Juan C. Acosta-Guadarrama . Towards a logic-programming system to debug ASP knowledge bases . In Mauricio Osorio , Claudia Zepeda, Iva´n Olmos , Jose´ L. Carballido , Jose´ Arrazola, and Carolina Medina, editors, 7th Latin American Workshop on NonMonotonic Reasoning 2011 , volume Vol- 804 , pages 3 - 12 , Germany, November 2011 . CEUR Workshop Proceedings.

[5] Juan C. Acosta-Guadarrama . Towards a unified framework for declarative knowledge-change-principles and consistency . In Mauricio Osorio, Claudia Zepeda, Ivan Olmos, Jose´ Luis Carballido, and Carolina Medina, editors, 8th Latin American Workshop on Non-Monotonic Reasoning 2012 , pages 51 - 62 . Direccio´ n de Fomento Editorial, Beneme´rita Universidad Aut o´noma de Puebla, 2012 .

[6] Carlos E. Alchourr o´n, Peter Ga¨rdenfors, and David Makinson. On the logic of theory change: Partial meet contraction and revision functions . The Journal of Symbolic Logic , 50 ( 2 ): 510 - 530 , June 1985 .

[7] Jose´ J u´lio Alferes, Federico Banti, Antonio Brogi, and Pascal Hitzler . The well supported semantics for multidimensional dynamic logic programs . In Chitta Baral, Gianluigi Greco, Nicola Leone, and Giorgio Terracina, editors, Logic Programming and Nonmonotonic Reasoning , volume 3662 /2005 of LNCS, pages 356 - 368 , Diamante, Italy, September 2005 . Springer Berlin/Heidelberg.

[8] Jose´ J u´lio Alferes, Federico Banti, Antonio Brogi, and Joa˜o Alexandre Leite. The refined extension principle for semantics of dynamic logic programming . Studia Logica , 79 ( 1 ): 7 - 32 , 2005 .

[9] Jose´ J u´lio Alferes, Joa˜o Alexandre Leite , Lu´ıs Moniz Pereira, Halina Przymusinska, and Teodor C. Przymusinski . Dynamic updates of non-monotonic knowledge bases . Journal of Logic Programming , 45 ( 1-3 ): 43 - 70 , 1999 .

[10] Jose´ J u´lio Alferes, Joa˜o Alexandre Leite , Lu´ıs Moniz Pereira, Teodor C. Przymusinski, and Halina Przymusinska . Dynamic logic programming . In A. Cohn , L. Schubert , and S. Shapiro, editors, Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR-98) , pages 98 - 111 , San Francisco, June 2-5 1998 . Morgan Kaufmann Publishers.

[11] Jose´ Ju´ lio Alferes, Lu´ıs Moniz Pereira, Halina Przymusinska, and Teodor C. Przymusinski. LUPS - A language for updating logic programs . Artificial Intelligence , 138 ( 1-2 ): 87 - 116 , June 2002 .

[12] Vino Fernando Crescini and Yan Zhang . Policy updater: A system for dynamic access control . International Journal of Information Security , 5 ( 3 ): 145 - 165 , 2005 .

[13] Evgeny Dantsin , Thomas Eiter, Georg Gottlob, and Andrei Voronkov . Complexity and expressive power of logic programming . ACM Computing Surveys , 33 ( 3 ): 374 - 425 , September 2001 .

[14] T. Eiter , M. Fink , G. Sabbatini, and H. Tompits . On updates of logic programs: Semantics and properties . Technical Report INFSYS RR1843-00-08 , TU Wien , Institute fu¨ r Informationssysteme, 2000 .

[15] Thomas Eiter , Michael Fink, Giuliana Sabbatini, and Hans Tompits . Considerations on updates of logic programs . In Manuel Ojeda-Aciego , Inman P. de Guzma´n, Gerhard Brewka, and L. Moniz Pereira, editors, Logics in Artificial Intelligence , European Workshop, JELIA 2000, pages 2 - 20 , Malaga, Spain, 2000 . Springer Verlag.

[16] Thomas Eiter , Michael Fink, Giuliana Sabbatini, and Hans Tompits . A framework for declarative update specifications in logic programs . In Bernhard Nebel, editor, Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI , volume I , pages 649 - 654 , Seattle, Washington, 2001 . Morgan Kaufmann.

[17] Thomas Eiter , Michael Fink, Giuliana Sabbatini, and Hans Tompits . On properties of update sequences based on causal rejection . Theory and Practice of Logic Programming , 2 ( 6 ): 711 - 767 , 2002 .

[18] Thomas Eiter , Michael Fink, Giuliana Sabbatini, and Hans Tompits . Reasoning about evolving nonmonotonic knowledge bases . ACM Transactions on Computational Logic , 6 ( 2 ): 389 - 440 , 2005 .

[19] Ronald Fagin . Reasoning about Knowledge . The MIT Press, Cambridge, Massachusetts, USA, 1995 .

[20] Ronald Fagin , Gabriel M. Kuper, Jeffrey D. Ullman , and Moshe Y. Vardi . Updating logical databases . Advances in Computing Research , 3 : 1 - 18 , 1986 .

[21] Ronald Fagin , Jeffrey D. Ullman , and Moshe Y. Vardi . On the semantics of updates in databases . In PODS '83: Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems , pages 352 - 365 , New York, NY, USA, 1983 . ACM Press.

[22] Michael Gelfond and Vladimir Lifschitz . The Stable Model Semantics for Logic Programming . In Robert A. Kowalski and Kenneth A . Bowen, editors, Logic Programming , Proceedings of the Fifth International Conference and Symposium ICLP/SLP , pages 1070 - 1080 , Seattle, Washington, 1988 . MIT Press.

[23] Hirofumi Katsuno and Alberto O. Mendelzon . A unified view of propositional knowledge base updates . In N. S. Sridharan, editor, the 11th International Joint Conference on Artificial Intelligence, IJCAI-89 , pages 1413 - 1419 , Detroit, Michigan, USA, 1989 . Morgan Kaufmann.

[24] Hirofumi Katsuno and Alberto O. Mendelzon . On the difference between updating a knowledge base and revising it . In KR'91 , pages 387 - 394 , Cambridge, Massachusetts, USA, 1991 . Morgan Kaufmann Publishers.

[25] Hirofumi Katsuno and Alberto O. Mendelzon . Propositional knowledge base revision and minimal change . Artificial Intelligence , 52 ( 3 ): 263 - 294 , 1991 .

[26] Sarit Kraus , Daniel Lehmann, and Menachem Magidor . Nonmonotonic Reasoning , Preferential Models and Cumulative Logics. Artificial Intelligence , 44 ( 1 ): 167 - 207 , 1990 .

[27] Daniel Lehmann . Plausibility Logic. In E. Bo¨ rger, G. Ja¨ger, H. Kleine-Bu¨ ning, and M. M. Richter, editors, Computer Science Logic, 5th Workshop , CSL 91, Berne , Switzerland, LNCS 626 , pages 227 - 241 , Berlin, 1992 . Springer.

[28] Daniel Lehmann and Menachem Magidor . What does a conditional knowledge base entail? Artificial Intelligence , 55 : 1 - 60 , 1992 .

[29] David Makinson . General theory of cumulative inference . In Non-Monotonic Reasoning, 2nd International Workshop , pages 1 - 18 , Grassau, Federal Republic of Germany, 1988 . Springer.

[30] David Makinson . General Patterns in Nonmonotonic Reasoning . In D. Gabbay, C. J. Hogger , and J. A . Robinson, editors, Handbook of Logic in Artificial Intelligence and Logic Programming , Nonmonotonic and Uncertain Reasoning , volume 3 , chapter 3, pages 35 - 110 . Oxford University Press, Oxford, UK, 1994 .

[31] Mauricio Osorio , Juan Antonio Navarro, and Jose´ Arrazola. Equivalence in answer set programming . In Alberto Pettorossi, editor, Logic Based Program Synthesis and Transformation: 11th International Workshop; selected papers / LOPSTR 2001 , Paphos, Cyprus, LNCS 2372 , pages 57 - 75 , Paphos, Cyprus, November 2001 . SpringerVerlag Berlin.

[32] Mauricio Osorio and Fernando Zacar´ıas. Irrelevance of syntax in updating answer set programs . In Proceedings of the Fourth Mexican International Conference on Computer Science (ENC' 03) In Workshop on Logic and Agents , Apizaco, Mexico, 2003 . IEEE Computer Society.

[33] Mauricio Osorio and Fernando Zacar´ıas. On updates of logic programs: A properties-based approach . In FoIKS, pages 231 - 241 , Wilhelminenburg Castle , Austria, 2004 . Springer.

[34] Chiaki Sakama and Katsumi Inoue . Updating extended logic programs through abduction . In Michael Gelfond , Nicole Leone, and Gerald Pfeifer, editors, LPNMR '99: Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning , volume 1730 of LNCS , pages 147 - 161 , El Paso , Texas, USA, 1999 . Springer-Verlag.

[35] Chiaki Sakama and Katsumi Inoue . An abductive framework for computing knowledge base updates . Theory and Practice of Logic Programming , 3 ( 6 ): 671 - 715 , 2003 .

[36] Marianne Winslett . Updating logical databases . Cambridge University Press, New York, NY, USA, 1990 .

[37] Fernando Zacar´ıas, Mauricio Osorio, Juan C. Acosta-Guadarrama, and J u¨rgen Dix. Updates in Answer Set Programming Based on Structural Properties . In Sheila McIlraith, Pavlos Peppas , and Michael Thielscher, editors, 7th International Symposium on Logical Formalizations of Commonsense Reasoning , pages 213 - 219 , Corfu, Greece, May 2005 . Fakulta¨t Informatik, TU-Dresden, ISSN 1430- 211X.

[38] Yan Zhang . On propositional knowledge base updates . Australian Journal of Intelligent Information Processing Systems , 2 : 20 - 29 , 1995 .

[39] Yan Zhang. The complexity of logic program updates . In AI '01: Proceedings of the 14th Australian Joint Conference on Artificial Intelligence , pages 631 - 642 , London, UK, 2001 . Springer-Verlag.

[40] Yan Zhang . Minimal change and maximal coherence for epistemic logic program updates . In IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence , pages 112 - 120 , Acapulco, Mexico, 2003 . Morgan Kaufmann.

[41] Yan Zhang . Two results for prioritized logic programming . Theory and Practice of Logic Programming , 3 ( 2 ): 223 - 242 , March 2003 .

[42] Yan Zhang . Logic program-based updates . ACM Transactions on Computational Logic , 7 ( 3 ): 421 - 472 , July 2006 .