Coherence Approach to Logic Program Revision.
AbstractIn this paper, we present a new approach to the problem of revising extended programs; we base this approach on the coherence theory initially advocated by Gardenfors for belief revision. Our approach resolves contradiction by removing only conflicting information, not the believed source of it, and therefore, keeps information loss minimal. Furthermore, since there is no need to search for problematic assumptions, as is done in the traditional assumption-removal approach, our approach provides a skeptical revision semantics that is tractable. We define the skeptical and credulous coherence semantics and show that both semantics can be characterized in terms of the fixpoint semantics of a revised program using a simple program-revision technique. These semantics provide a suitable framework for knowledge and belief revision in the context of logic programs. Semantical properties and advantages of the proposed revision semantics are also analyzed.
Introduction
T HE extension of logic programs with classical negation
significantly increases the expressive power of logic
programs, but also presents new challenges [9]. Among
other things, the contradiction problem brought up by classical
negation has to be addressed.
Unlike normal programs, an extended program with
classical negation may not be consistent. For example,
considered contradictory since
both a and :a can be derived from it.
Many attempts have been made to resolve the contradiction
problem. However, almost all proposals are based
on one approach: Resolve the contradiction problem by
removing some problematic assumptions, though different
mechanisms may be used for the removal. (The assumptions
here refer to the values of the default negations. The
term is used simply because such values are usually determined
by first assuming a value and then justifying the
value.) Three notable examples are:
1. the contradiction removal semantics [14],
2. the argumentation semantics [6], and
3. the assumption denial semantics [23].
The assumption removal approach, though avoiding contradictory
conclusions caused by negation as failure, is not
suitable for many applications, such as knowledge and belief
revision.
An analysis of semantical properties shows that the
assumption-removal approach violates two important semantical
principles in logic programming and knowledge
revision: the principles of conservatism and relevance.
The authors are with the Department of Computing Science, University
of Alberta, Edmonton, Canada T6G 2H1; email: fyuan,
youg@cs.ualberta.ca.
Manuscript received 24 Apr. 1995; revised 29 Feb. 1996.
IEEE Log Number 104442
One of the basic postulates in knowledge revision is that
of conservatism which requires that any conclusions derived
from a revised system be derivable from the system prior to
the revision [7]. The assumption-removalapproach, though
avoiding contradiction, does not address the consequences
of assumption removal. As such, conservatism may not
hold.
Example 1.1: Consider \Pi below
:a / notb; a /; c / not:a;
and the credulous argumentation semantics [6].
With each negative literal :ff viewed as a named proposition
ff, the credulous argumentation semantics of \Pi does
not imply c, which demonstrates that c is not true with
respect to the credulous argumentation semantics without
involving any revision mechanism. Since \Pi has a unique
preferred extension fnot:ag, the credulous argumentation
semantics of \Pi does imply a and c which violates
conservatism (see Section 5 for details). 2
The principle of relevance requires that the values of the
literals in a set be determined by only those clauses that define
them [3], [11]. Relevance has been considered essential
in any goal-directed query evaluation [2] while the goal-directed
theoretical characterization forms suitable bases
for logic programming [12]. The following example demonstrates
that the assumption removal approach may violate
relevance.
Example 1.2: Assume \Pi is defined by
a / notb; :a / notb; d / notb:
To resolve the conflict between a and :a, the assumption-
removal semantics has to remove notb. Consequently, d
cannot be derived. Note that the relevant program of d ,
i.e., the set of all clauses that define d, is fd / notbg
which deduces d. 2
Furthermore, the assumption-removal approach suffers
computationally from finding a minimal set of problematic
assumptions. This is the cause of intractability in the
contradiction removal semantics, as shown in [19], and in
the grounded version of the ideal skeptical semantics [1],
as shown in [22]. Although Dung's grounded argumentation
semantics [6] does not attempt to compute a minimal
removal set, it is also NP-hard since it is NP-complete to
determine if an atom is derivable from a sound argument
[22], an essential property in attack and counterattack relationships

In this paper, we present an alternative approach, based
on the coherence theory [7], to removing contradiction from
extended programs. This approach provides a suitable semantics
for knowledge and belief revision in the framework
of logic programs. The idea is simple but very effective:
Given an extended logic program \Pi and a set N
of assumptions, the coherence revision semantics
is determined by the disjunction of maximal consistent
sets of literals derivable from \Pi N 1 .
Note that the assumption-removal approach is based on
the assumption that inconsistency is caused by problematic
assumptions while the coherence approach removes contradiction
regardless the source of it.
We investigate the coherence approach mainly because
1. the coherence approach resolves contradiction by removing
only conflicting information, not the believed
source of it, and therefore, keeps information loss min-
imal; and
2. in this approach there is no need of searching for minimal
sets of problematic assumptions, and thus it provides
a skeptical revision semantics that is tractable.
In the paper, we first define the notion of consistent-and-
justified (CJ) partial models, based on a negation-as-failure
rule and the coherence theory, and then present the skeptical
and credulous coherence semantics in terms of CJ partial
models.
A remarkable fact about CJ partial models of a program
\Pi is that they are fixpoints of a suitably defined operator
for program \Pi R , which is obtained from \Pi by a simple
program revision technique: semi-normalizing the doubling
program [17]. This program revision technique is simple
but not trivial, and it gives a natural revision semantics
based on the coherence theory.
We also analyze the semantical properties of the proposed
revision semantics and show that these semantics
satisfy conservatism and relevance, among a number of
properties along the line similar to that of Dix [4].
II. Preliminaries
We briefly review the basic concepts and important results
that are useful for the following discussions. An ex-
1 \Pi N is the program obtained by GL-transformation defined in Section
2.
tended clause is a formula of the form
where L i are literals and notL j are assumed negations (or
assumptions). Note that :A denotes a fact that A is false
while notA denotes an assumption that A cannot be true.
Sometimes, we also use rhs to denote the body of a clause.
An extended logic program, or a program for short, is a set
of extended clauses. Assume L is a literal, by :L we mean
the literal that is complementary to L. For simplicity we
consider propositional logic only and the only literals of
interest are the set of all literals, denoted as L \Pi , whose
atoms appear in a given program \Pi.
Given \Pi, an assumption set N is defined as a set of assumed
negations whose literals are in L \Pi . The intended
meaning of \Pi under N is determined by \Pi N , the GL-
transformation, obtained from \Pi by first deleting all notL
if notL 2 N , and then deleting all clauses that contain assumptions
in their bodies [10]. We say L is derivable from
\Pi, denoted as \Pi ' L, if either
1. L / is an extended clause in \Pi, or inductively,
2. there exist a clause L /
Apparently, \Pi ' L if and only if L is derivable from all
positive clauses, i.e., clauses without default negations, in
\Pi.
2.1 Three-valued logic and semantical character-
ization
A three-valued interpretation is a pair I
contains all the literals true in I, F all the literals false in
I such that T " and the rest literals are considered
undefined. We use t, f , and u respectively to denote the
three truth values, and the order of the truth values, based
on the so called truth ordering, is defined as: f ! u t.
The connective not is defined as: not t, and
not u. The truth value of a conjunction is defined as
the minimum value among all the truth values of the literals
and assumptions in the conjunction. A program clause
is satisfied by an interpretation I if the truth value of the
head of the clause is greater than or equal to that of the
body. A model of a program is an interpretation in which
all the program clauses are satisfied. A three-valued interpretation
reduces to a two-valued interpretation if T [ F
contains all concerned literals. A binary relation among all
interpretations, based on the so called knowledge ordering,
is defined as:
In this case, I is said to be a sub-interpretation of I 0 . An
interpretation M is said to be a partial model of \Pi if there
exists a model M 0 of \Pi such that M - M 0 . For convenience
we abuse the notation in the following way: a set
I of literals and assumed negations and an interpretation
are used interchangeably. Since all proposed
semantics for programs can be characterized by a set of
three-valued interpretation, we have:
Definition 2.1: [4] Given program \Pi, we use SEM (\Pi) to
represent the set of all extended literals contained in every
characteristic interpretation under the semantics SEM .
That is,
where SEM \Pi assigns to every program \Pi a set of three
valued interpretations whose literals appear in \Pi. 2
Note that by SEM (\Pi) we mean a set of literals and assumed
negations as well as a three-valued interpretation,
whichever is convenient.
2.2 Justified models
We redefine the justified model [25] that can be used to
represent many existing semantics.
Definition 2.2: Let \Pi be a program and I an
interpretation.
1. A literal L in T is said to be positively justified wrt
I if there, recursively, exists a clause
in \Pi such that L i are positively
justified literals in T and L j 2 F for
2. A literal L 2 F is said to be negatively justified wrt
I if L is not positively justified wrt -
The following lemma presents an alternative definition for
the justified literals. Its proof is straightforward.
Lemma 2.3: Let I
not -
Tg. Then
1. positively justified if and only if \Pi notF ' L
(through literals in T ),
2. L is negatively justified if and only if \Pi not -
F 6' L.
Note by \Pi ' L through literals in T , we mean there, recur-
sively, exists a clause L /
such that for justified model of \Pi if
1. L is in T if and only if L is positively justified wrt M ;
and
2. L is in F if and only if L is negatively justified wrt
The justified model was proposed by Yuan and You and
it coincides with the partial stable model of Przymusinski
[15], [25]. The idea behind the justification model is very
simple and clear:
1. L is true if and only if it can be derived from the
program and all the assumed negations, and
2. L is assumed false if and only if it cannot be derived
from the program even when all non-true literals are
assumed false.
We define a least justified model as the justified model that
is a sub-interpretation of any justified model and a maximal
justified model as a justified model that is not a sub-
interpretation of any other justified model.
Proposition 2.5: Any program \Pi has a least justified
model.
The expressive power of the justified model is demonstrated
below by the fact that most semantics proposed so far can
be characterized in terms of the justified models.
Theorem 2.6: Let \Pi be a normal program. Then
1. the well-founded model of \Pi coincides with the least
justified model of \Pi;
2. M is a stable model of \Pi iff it is a two-valued justified
model of \Pi;
3. M is a regular model of \Pi iff it is a maximal justified
model of \Pi.Note that the regular model semantics of You and Yuan
[20] has been recently shown to coincide with the partial
stable model semantics of Sacca and Zaniolo [16] and with
Dung's preferred extension semantics [5], as well as with
Przymusinski's maximal three-valued stable models [21].
For convenience, we will use the least justified model and
well-founded model interchangeably.
2.3 The alternating fixpoint theory revisited
The alternating fixpoint theory, first proposed by Van
Gelder [8] and then further developed by You and Yuan
[21], [24], is a powerful tool to characterize the various semantics
of programs. The theory is based on an important
transformation defined below.
Definition 2.7: Let \Pi be a program and N a set of assumed
negations. Then T \Pi is defined as a mapping on the
set of all assumption sets as follows:
T \Pi is anti-monotonic, i.e., T \Pi
but not monotonic.
Definition 2.8: Let \Pi be a program and N an assumption
set. Then N is
1. a fixpoint of \Pi if
2. an alternating fixpoint of \Pi if
3. a normal alternating fixpoint of \Pi if
The following theorem establishes a one-to-one correspondence
between the justified model and the normal alternating
fixpoint.
Theorem 2.9:
1. If N is a normal alternating fixpoint of \Pi then hT ; F i
is a justified model of \Pi,
2. If hT ; F i is a justified model of \Pi then fnotL j L 2 Fg
is a normal alternating fixpoint of \Pi.
The proof of the theorem is quite straightforward. Assume
N is a normal alternating fixpoint of \Pi. Then we have
which implies that I = hT; F i is a three-valued
interpretation. Lemma 2.3 implies that L 2 T if and only
if L is positively justified wrt hT ; F i, and L 2 F if and
only if L is negatively justified wrt I = hT ; F i, which, by
Definition 2.4, implies that hT ; F i is a justified model.
(2) follows similarly. 2
2.4 The contradiction problem
Obviously, a program \Pi is inconsistent if there exists a
pair of complementary literals, a and :a such that \Pi ' a
and \Pi ' :a. Unfortunately, this simple criterion does not
identify many problematic programs.
Example 2.1: Let \Pi be
Though no pair of complementary literals can be derived
from \Pi, the program is not
contradiction-free. In fact, the unique answer set of \Pi is
inconsistent in that it contains a pair of complementary
literals b and :b. 2
A program is considered problematic if it leads to contradictory
conclusions under a given semantics. Since most
proposed semantics of extended programs can be characterized
by justified models, we are to classify problematic
programs by their justified models.
A justified model does
not contain a pair of complementary literals. Further, an
extended program is said to be contradiction-free if all of its
justified models are consistent. Otherwise, it is considered
contradictory.
III. Coherence Semantics
If a justified model inconsistent then naturally
we may have to revise it, using either the assumption-
removal approach or the coherence approach. The former
is to consider only those subsets of F that do not cause
inconsistency, and the latter is to find a proper consistent
subset of T , as illustrated below.
Example 3.1: Consider \Pi below:
a / notb; :a / notc; d / notb; notc:
Assume justified model of \Pi. Since
b does not appear in the head of any clause in \Pi, b is
not positively justified wrt any interpretation, which implies
b is negatively justified wrt M , and therefore, b 2
F . Similarly, we have fc; :b; :c; :dg ' F . By Definition
2.2, this implies that a; :a; d are all positively justified
wrt M , that is, fa; :a; dg ' T . It follows that
hfa; :a; dg; fb; c; :b; :c; :dgi is the only justified model of
\Pi and, obviously, it is inconsistent.
Consider four consistent sub-interpretations of M :
For any literal is assumed false if and
only if it is negatively justified wrt M i and a literal is true
only if it is positively justified wrt M i . However, :a and a
are undefined in M 1 and M 2 respectively, despite the fact
that :a and a are positively justified wrt M 1 and M 2 respectively

For 4, on the other hand, a literal is
true in M j if and only if it is positively justified wrt M j and
a literal is assumed false only if it is negatively justified wrt
Similarly, notc and notb are not assumed in M 3 and
respectively even though c and b are negatively justified
wrt M 3 and M 4 respectively.
The assumption removal approach favors M 3 and M 4
while the coherence approach chooses M 1 and M 2 . 2
As argued at the outset, we choose the coherence approach
to revise any inconsistent justified models. One of the challenges
in the coherence revision is how to find an appropriate
consistent subset of T . Two different philosophical
beliefs lead to two different approaches: the credulous and
the skeptical. The credulous approach favors the maximum
consistent subsets of all positively justified literals,
and naturally, is not computationally tractable. The skeptical
approach, on the other hand, derives a conclusion only
if it is well-founded. However, the question arises as to
what degree a conclusion is considered well-founded. Before
answering this question, let us see another illustrating
example.
Example 3.2: Assume \Pi is defined as
a /; :a /; d / nota; :d /;
and
Then M 1 is a justified but inconsistent model of \Pi, and
is a consistent partial model of \Pi,
though M 2 is a sub-model of M 3 and M 3 is a sub-model of
both M 4 and M 5 .
For the credulous approach, both M 4 and M 5 are an obvious
choice since they contain a maximal consistent subset
of all positively justified literals. For the skeptical approach,
to be extremely cautious, we could always take an empty set,
like though it is obviously not reasonable.
The difference between M 3 and M 4 is that M 4 derives
:a without a well-founded justification (note that a may
also be selected, as in M 5 derives :d because d
is negatively justified wrt the well-founded semantics of \Pi
in that notd is true under the well-founded semantics of
\Pi, and therefore, d will never conflict with :d. 2
The above example leads to the following definition of
"shadow-justification" to characterize the special status of
d and the like.
Definition 3.1: Let \Pi be a program and
partial model of \Pi. Further, let \Pi M be the program obtained
from \Pi by deleting notL if L 2 F . A literal L is
said to be negatively shadow-justified wrt M if notL is assumed
under the well-founded semantics of \Pi M . 2
The following lemma demonstrates that the negative
shadow-justification is a weaker notion than negative-
justification.
Lemma 3.2: Assume is a partial model of
\Pi such that each literal in T is positively justified wrt M .
Then L is negatively shadow-justified wrt
is negatively justified wrt M . 2
A negatively shadow-justified literal, on the other hand,
is not necessarily a negatively justified literal. For exam-
ple, consider M 3 in Example 3.2. d is negatively shadow-
justified wrt M 3 , but not negatively justified wrt M 3 .
We are to define a suitable partial model such that L
is derived under the skeptical approach if it is positively
justified and :L is negatively shadow-justified. This leads
to the following key definition.
Definition 3.3: An interpretation is said to
be a consistent-and-justified partial model (or, CJ partial
model) of \Pi if
1. L 2 F if and only if L is negatively justified wrt M ,
2. L is in T only if L is positively justified wrt M ,
3. L is in T if (1) L is positively justified wrt M and (2)
:L is negatively shadow-justified wrt M , and
4. T contains no pair of complementary literals. 2
The first condition retains the negative justification rule
for assumed negations. The second indicates that all true
literals must be positively justified. The third condition
specifies the lower bound of the well-foundedness, that is, L
must be in T if it is positively justified and :L is negatively
shadow-justified.
Example 3.3: Consider \Pi in Example 3.2 again.
are the set of all CJ partial models of \Pi while
is not a CJ partial model of \Pi. 2
It is straightforward to see that for any normal program
justified model of \Pi if and only if it is a CJ
partial model of \Pi. The following shows that any extended
program has a least CJ partial model and its proof follows
from Theorem 4.2.
Theorem 3.4: Every extended program has a least CJ
partial model that is a sub-interpretation of every CJ partial
model of \Pi. 2
Definition 3.5: Let \Pi be an extended program. Then M
is said to be
1. a skeptical partial model of \Pi if it is the least CJ
partial model of \Pi, and
2. a maximal consistent-and-justified partial model of
\Pi if it is a CJ partial model of \Pi and not a sub-
interpretation of any other CJ partial model of \Pi.Obviously, any extended program has the unique skeptical
partial model. Now we are in the position to define the
coherence semantics for extended programs.
Definition 3.6: Let \Pi be an extended program. Then
1. the skeptical coherence semantics (SCS) of \Pi is characterized
by the skeptical partial model; and
2. the credulous coherence semantics (CCS) of \Pi is characterized
by the set of all maximal consistent-and-
justified partial models of \Pi. 2
Note that we say a semantics is characterized by a set S of
partial models if an extended literal is true in the semantics
if and only if it is contained in every partial model in
S. Theorem 3.4 shows that both the skeptical and credulous
coherence semantics are well-defined over all extended
programs.
IV. Revised Programs
In this section we first present the revised program, based
on two simple program revision techniques, namely, the
doubling transformation, first proposed by Wallace [17],
and the semi-normalization. Then we will show that the
revised program can be used to characterize the coherence
semantics.
A clause with L as the head is semi-normal if its body
contains not:L. In the following, we define the revised
program \Pi R as the semi-normalized program of the doubling
transformation of \Pi.
Definition 4.1: Let \Pi be an extended program. Then
the revised program of \Pi, denoted as \Pi R , is the program
obtained from \Pi such that for each clause
in \Pi, \Pi R contains precisely two clauses:
1:
notLm+n ; not -
2: -
are newly introduced atoms. 2
Note that the doubling transformation \Pi D of \Pi is defined
the same as \Pi R above but without semi-normalization.
Further, semi-normalization is applied only to (4:1), not
(4:2). This is simply because the head of (4:2) is a newly
introduced atom -
negative literal does not appear
in the revised program.
Example 4.1: Let notbg. Then
\Pi R is defined by:
:a / nota; a / not:a; b / notb; not - b; not:b
:a /; -a /; - b / notbThe revised program \Pi R of \Pi consists of two programs \Pi 1
and \Pi 2 such that the heads of all the clauses in \Pi 1 and
are original and newly-introduced literals respectively.
Furthermore, since every clause in \Pi 1 is semi-normalized
and there are no negative occurrences of newly-introduced
literals -
L, \Pi R is always consistent.
The role of newly-introduced literals -
L is quite subtle
and interesting. Given any set N of assumptions, \Pi N and
are identical, subject to a homogeneous mapping between
L and -
L. Therefore, -
L characterizes the behavior
of L with respect to the original program \Pi under any assumption
set. Such characterizations effectively guarantee
the conservatism.
Consider not:ag
in Example 1.1. Then \Pi
not:a; not -
:a; not:cg and \Pi
not:ag.
Assume not:ag. Then both -a and -
:a are
derivable from \Pi R
simply because both a and :a are
derivable from \Pi N . The derivation of -
:a then effectively
prevents c from being derived under \Pi R N since not -
:a cannot
be assumed. Without the derivation of -
:a, the revision
may derive c which violates the conservatism.
Interestingly, both the skeptical and credulous coherence
semantics can be characterized through the revised pro-
gram, as shown below.
Theorem 4.2: Let \Pi R be the revised program of \Pi,
the well-founded model of \Pi R , and
where
Then M is the unique skeptical partial model of \Pi. 2
This theorem not just shows the existence of the skeptical
partial model but also gives a polynomial algorithm
for computing the skeptical partial model of any given extended
program.
Definition 4.3: N is an L-maximal fixpoint of the revised
program \Pi R of \Pi if
1. N is a fixpoint of \Pi R , and
2. there exists no fixpoint N 0 of \Pi R such that
fnot -
Ljnot -
Ljnot -
establishes one to one correspondence
between the L-maximal fixpoint of \Pi R and the maximal
CJ partial model of \Pi.
Theorem 4.4:
1. If N is an L-maximal fixpoint of \Pi R then
is a maximal CJ partial model of \Pi, where
2. If hT ; F i is a maximal CJ partial model of \Pi then
is an L-maximal fixpoint
of \Pi R .Note that L used in the above two theorems refers to a
literal appearing in \Pi, not a newly introduced atom -
some literal L 0 .
V. Semantical Properties
In this section, we first define several interesting semantical
properties, and then demonstrate that the coherence
semantics satisfies some of these properties.
Given program \Pi and set S of literals, the value of S
should be determined by only those clauses whose heads
define literals in S. This leads to the relevant program,
denoted as REL(\Pi; S), of S under \Pi.
1. L / body is in REL(\Pi; S) if either L or :L is in S.
2. L / body is in REL(\Pi; S) if L is contained in
LREL(\Pi;S) .
3. Nothing else is in REL(\Pi; S).
Note that we always consider L and :L to be relevant.
With the introduction of classical negation we have to consider
the coherence between L and :L. In order to reflect
the degree of coherence of various semantics, we define an
isomorphy transformation I by replacing each negative literal
:a with a newly introduced propositional symbol. I \Gamma1
is then defined as the reverse transformation of I. Note that
for any newly introduced proposition pnew , I returns
the nil value since no literals in L \Pi are mapped to
:pnew . It is easy to see that for most of the existing non-
revision semantics, we have I \Gamma1 (SEM
However, this does not hold for the revision semantics if \Pi
is not contradiction-free.
Now we are in the position to define some very interesting
properties for extended logic program semantics.
Definition 5.1: A semantics SEM is said to satisfy
1. N-cumulativity if SEM
set of negations F ' SEM (\Pi);
2. negative-justification if notL 2 SEM (\Pi) for
every L that is negatively justified with respect to
3. simplicity if L 2 SEM (\Pi) for every L / in \Pi;
4. relevance if SEM (\Pi) "
for any set S ' L \Pi ;
5. conservatism if (SEM (\Pi)) ' I \Gamma1 (SEM (I(\Pi)));
6. preservation if (SEM
any contradiction-free program \Pi; and
7. coherence if L 2 SEM (\Pi) implies not:L 2
N-cumulativity expresses the desire that the semantical inference
can be carried out incrementally, based on assumed
negations. Negative-justification is used to characterize the
negation as failure rule, and simplicity is plain and straight-
forward. The value of any set of literals should be determined
by only those clauses that define them, and this
is relevance [3], [11]. Conservatism requires that no new
conclusions be derived through the revision. Preservation
indicates that the revision semantics should not change
the intended meaning of the program if the program is
contradiction-free. Coherence, first realized by Pereira and
Alferes [13], is to measure the degree of coherence of the
concerned semantics.
Remark In the context of normal programs, it is easy to
check that
1. almost all well-behaved semantics, as defined in [4],
satisfy N-cumulativity, negative-justification, simplicity
and relevance, and any proposed semantics that
satisfies N-cumulativity, negative-justification, simplicity
and relevance is well-behaved; 2 and
2. any semantics for normal program satisfies the rest of
above properties trivially.
2 The subtle difference between the well-behaved semantical properties
and these four properties will be discussed elsewhere.
In the context of extended programs, however, it is not difficult
to see that any consistent semantics CANNOT satisfy
both negative-justification and simplicity. The reason
is simple: to remove inconsistency, we have to give up either
negative-justification or simplicity. The assumption
removal approach gives up negative-justification and retains
simplicity while the coherence approach gives up the
simplicity and retains negative-justification.
Theorem 5.2:
1. Both SCS and CCS satisfy N-cumulativity, negative-
justification, relevance, and conservatism, but not simplicity

2. The CCS satisfies preservation but the SCS does not.
3. Neither SCS nor CCS satisfies coherence 3 . 2
The following example shows that SCS does not satisfy
preservation and CCS does not satisfy coherence.
Example 5.1: Let
is the only justified model and is consistent.
Further, the skeptical partial model of \Pi is h;; ;i. 2
It is very important for a semantics to satisfy preserva-
tion, meaning that the intended meaning of a program
should not change during the revision if the program is
problem-free. The skeptical coherence semantics does not
satisfy preservation, mainly due to the weak definition of
contradiction-free. As a matter of fact, SCS does satisfy
both preservation and coherence for any program whose
well-founded model satisfies coherence.
We conclude this section with the following demonstrating
example.
Example 5.2: Let us consider the following knowledge
base:
Most presidential candidates are honest;
Most presidential candidates are professional;
politicians;
Politicians are not honest;
Republic politicians are conservative;
Non-conservative presidential candidates are;
liberals;
Dole is a Republican presidential candidate.
This can be represented by the following program:
republican(Dole) /
pres candidate(Dole) /
pres candidate(X), not abnormal(X)
politician(X) / pres candidate(X), not abnormal(X)
liberal(X) / pres candidate(X), not conservative(X)
3 Our approach was named after the coherence theory advocated
by Gardenfors for belief revision while the coherence property was
formulated by Pereira and Alferes [13]. The term coherence has two
entirely different meanings which explain why our coherenceapproach
does not satisfy the coherence property.
The program is inconsistent because both honest(Dole) and
: honest(Dole) can be derived. The program, however, has
a unique CJ-partial mode M and, therefore, both revision
semantics coincide and imply the following:
republican(Dole),
pres-candidate(Dole),
politician(Dole),
not liberal(Dole).
Please note that the revision semantics concludes neither
honest(Dole) nor :honest(Dole).
For comparison, the assumption removal approach has
to remove not abnormal(Dole), and therefore, may not be
able to derive politician(Dole). For example, the credulous
argumentation semantics of this program assumes not con-
servative(Dole) and consequently, concludes that Dole is
a liberal. The derivation of liberal(Dole) in the credulous
argumentation semantics is due to its violation of conser-
VI. Prioritized Revision
The proposed coherence approach does not impose any
priority relations among conflicting parties, though in
many applications, certain priority relations are desired.
Example 6.1: Consider the following program \Pi:
light on / switch on; notbroken;
switch on /; :light on /;
which describes the following situation:
normally lights are on if the switch is not broken
and as a matter of fact, we found out that lights
are not on.
For such applications, we do expect that lights are not
on. In fact both the skeptical revision of Witteveen and
Brewka and the argumentation semantics of Dung conclude
switch on and :light on by contrapositive reasoning and
the like [18], [6]. However, the skeptical coherence semantics
of \Pi implies that switch is on but not :light on due
to the conflict between the pair of complementary literals.This example demonstrates that the proposed coherence
semantics does not favor literals that are directly derivable
from a given program over those that are derivable through
assumed negations. For such applications, a priority relation
is necessary.
Assume \Pi is an extended program and L \Pi the set of
all literals involved in \Pi. Then a priority relation - is
defined as a binary relation on L \Pi such that L i - L j if the
priority of L i to be derived is at least as high as that of
. Since this paper concentrates on the conflict resolving,
only priorities between L and :L are considered.
Definition 6.1: Let \Pi be an extended program and -
the priority relation among literals in \Pi. Then the prioritized
program of \Pi, denoted as \Pi - is the program obtained
from \Pi by changing every clause L i / body into
Example 6.2: Consider \Pi in Example 6.1 and a priority
relation
-= f:light on - light ong:
Then \Pi - is
light on / switch on; notbroken; not:light on;
switch on /;
:light on /.
\Pi - is contradiction-free and its well-founded semantics implies
that the switch is on and :light on. 2
As expected, the priority relation should be determined according
to applications and it is difficult to form a general
guideline. However, many revision semantics implicitly favor
the following priority:
for every set N of assumptions such
that \Pi N ' :L there exists a subset N 0 of N such
that \Pi N 0
Unfortunately, computing a semantics under such a priority
relation is very difficult. In many applications, literals
that are derivable directly from a given program are considered
to have higher priority to be held than their negations
that are derivable from assumed negations. Light on is a
notable example for such priority relations. The following
algorithm revises a given program \Pi according to such a
priority, based on the well-founded approach.
Algorithm 6.1:
Input \Pi: an extended program
Output revised program with a priority based on
the well-founded approach
Methods
(3) for each L 2 T but :L 62 F do
changing :L / body in \Pi - into
(5) exit if no changes, otherwise goto (2).This algorithm assigns a higher priority to those literals
that are derived without assuming newly derived negations
than those that are derived only after assumed nega-
tions. The algorithm can also be used to compute the well-founded
semantics of \Pi - and it is polynomial to the size
of the input program. For \Pi in Example 6.1, the skeptical
coherence semantics of \Pi - implies switch is on and
:light on.
The coherence approach is proposed as a general approach
to logic program revision based on a simple idea:
Resolve contradiction by removing conflicting parties, regardless
their sources. This approach works better than the
assumption removal approach for many applications, as our
examples demonstrated, simply because it is too difficult, if
not impossible, to correctly identify the source of conflict.
However, if the source of conflict is known to the agent,
then, of course, it is better to remove the troublemaker -
the source of conflicts - directly. This is the motivation
of prioritized revision. The priority relation, if applicable,
clearly indicates the agent's intension and therefore, must
be honored in the revision.
VII. Comparisons and Further Discussion

The following are some examples that illustrate the similarity
and the difference between several proposals.
Example 7.1: Consider the following program:
Under the skeptical belief revision [18], none of c, d, and
:d can be derived, nor nota can be assumed. Similarly, c
cannot be derived under the argumentation semantics [6].
Obviously, under any circumstances, a cannot be derived,
and therefore, nota should be assumed. The contradiction
between d and :d may suggest that the last two rules should
be revised. However, the inconsistency between the last two
clauses should not affect that c can be derived under the
condition that a cannot be proved. Note that both coherence
semantics of the program assume nota and consequently
conclude c.This example demonstrates that the skeptical belief revision
semantics and the argument semantics do not satisfy
the negative-justification and relevance.
One of the important aspects in knowledge revision is
the minimality, that is, the change of information during
revision should be minimized. Although unnecessary loss
of information is usually associated with the violation of
relevance, as demonstrated in the example below, a precise
characterization of the minimality is not an easy task and
is currently under investigation.
Example 7.2: Consider
notb; c / notdg. The relevant program of fcg is fc /
notdg and therefore, by relevance, c should be deduced.
However, to resolve the conflict between a and :a with the
assumption removal approach, either notb or notd has to
be removed which fails to derive c. 2
VIII. Conclusions
The coherence approach to logic program revision is
based on the idea that contradiction may be resolved by removing
only conflicting information, without searching for
believed source of conflict. We have demonstrated that this
approach satisfies many desirable properties, including the
conservatism and relevance. Furthermore, simply because
the revision can be achieved regardless of the source of con-
flict, the coherence approach provides a tractable skeptical
revision semantics.
Various coherence semantics provides an alternative approach
to logic program revision, and its applications are
currently under investigation.
IX.

Appendix


This section contains utility lemmas and proofs of the
main theorems. First, some convenient notations. Let
be an interpretation. Then -
Tg and F denotes fnotL j L 2 Fg. Note that we abuse
F as a set of literals as well as a set of assumed negations,
whenever convenient.
Proposition 2.5 Any program \Pi has a least justified
model.
Proof: Since T \Pi is anti-monotonic, any program has at least
one normal alternating fixpoint [24]. By Theorem 2.9, this
implies that any program has at least one justified model.Theorem 2.6 Let \Pi be a normal program. Then
1. the well-founded model of \Pi coincides with its least
justified model;
2. M is a stable model of \Pi iff it is a two-valued justified
model of \Pi;
3. M is a regular model of \Pi iff it is a maximal justified
model of \Pi.
Proof: It follows Theorem 2.9 and the fact that, as shown
in [21], the well-founded model, a stable model , and a
regular model of \Pi coincide with the least, a fixpoint, and
a maximal normal alternating fixpoint of \Pi respectively.Let \Pi R be a revised program and N a fixpoint of \Pi R .
Then the characteristic interpretation of N is defined as
where
and
Further, we use NP and N -
P to denote the set of all assumptions
in N whose corresponding literals are from P
and -
respectively.
Lemma 9.1: Let CI(N be the characteristic
interpretation of N . Then
Proof: The construction of \Pi R and the comparison of (4.1)
and (4.2) clearly indicate that for any assumption set
and
Since N is a fixpoint of \Pi R , (9.2) implies that
By (9.1), this implies that
Lemma 9.2: Let \Pi R be the revised program of \Pi, FR be
a set of assumed literals such that -
The proof is straightforward.
Lemma 3.2 Assume be a partial model of \Pi
such that each literal in T is positively justified wrt M .
Then L is negatively shadow-justified wrt
is negatively justified wrt M .
Proof: Assume L is negatively justified wrt M then, by
Lemma 2.3,
be the well-founded model of \Pi M
which is obtained from \Pi by deleting notL if L 2 F . For
each literal L 2 T , since L is positively justified wrt M ,
consequently, \Pi M ' L, which implies L 2 Tw ,
and T ' Tw , and
This implies, together with (9.5), that
Tw 6' L:
By Theorem 2.6 (1) L 2 Fw and therefore, L is negatively
shadow-justified wrt M .Now we define a justified partial model of \Pi as a CJ
model of \Pi such that there exists no CJ model
of \Pi and T ae T 0 .
Assume three-valued interpretation of
\Pi. Then we define the characteristic assumption set of M
as
The following lemma establishes a one-to-one correspondence
between the fixpoint of \Pi R and the justified partial
model of \Pi.
Lemma 9.3: Let \Pi R be the revised program of \Pi. Then
1. N is a fixpoint of \Pi R only if CI(N ) is a justified
partial model of \Pi; and
2. CA(M ) is a fixpoint of \Pi R if is a justified
partial model of \Pi.
Proof: (1). Assume N is a fixpoint of \Pi R , CI(N
g. Then by (9.1),
By the construction of \Pi R
\Pi NP ' L if and only if \Pi R N ' -
By Lemma 9.1 and (9.8), F (N
fLj\Pi NP 6' Lg: That is,
iff L is negatively justified wrt CI(N )
( by Lemma 2.3)
Thus, L 2 F (N ) if and only if L is negatively justified
with respect to CI(N ) and \Pi.
Assume L, and by
Ng. Therefore, L is positively justified with respect to
Since every clause with L 2 L \Pi as the head is semi-
normalized, T (N ) contains no pair of complementary literals

Assume (1) L is positively justified and (2) :L is negatively
shadow-justified, both with respect to CI(N ). We
now show that L 2 T (N ), that is, to show that \Pi R N ' L.
By the structure of \Pi R , it suffices to show that not:L 2 N .
Then
N 6' :L for N is a fixpoint
of \Pi R
if \Pi R
:L by (9.2)
if \Pi F (N) 6' :L by
Since :L is negatively justified wrt \Pi F , \Pi F 6' :L.
It follows that CI(N ) is a consistent-and-negatively-
justified partial model.
Assume CI(N ) is not a justified partial model. Then
there exists a consistent-and-negatively-justified partial
model of \Pi such that
We will show that there exists at least one literal
that :L is contained in T which contradicts
T 0 is consistent. Assume L is in T
fore, L is positively justified with respect to M 0 . Without
loosing generality, we assume there exists a clause
in \Pi such that L
n. Thus, there exists a clause
notLm+n ; not -
in \Pi R . Since L
, and not -
n. The fact that L 62 T and
implies that \Pi R N 6' L. Since C is a clause in \Pi R , this
implies that not:L is not contained in N . Since N is a
fixpoint of \Pi R , \Pi R
therefore, by (9.1), :L 2 T .
This contradicts that
justified partial model of \Pi
and
We will show that N is a fixpoint of \Pi R .
First, we show that
Lg:
this amount to show that
only if \Pi R
L:
However,
only if \Pi F 6' L by Lemma 2.3
if and only if \Pi R N 6' -
L by
Now we show that
Assume L is in T . Then L is positively justified with respect
to M , and therefore,
Since T is consistent, :L 62 T and hence not:L 2 NP . By
Lemma 9.2, \Pi R
which implies,
Now we need only to show that NP ' fnotLj\Pi R
Lg.
Assume not, then there exists an L such that L 62 T and
Ng. Therefore, L is positively justified wrt M . Since L is
not in T , there are only two cases.
Case 1: :L is in T .
Since :L is in T , not:L is not in N . But every clause
with L as the head in \Pi R has not:L in its body which
contradicts that \Pi R
Case 2: L is positively justified through some literals not
contained in T .
By induction on the steps through which L is derived
from \Pi R N , there must be at least one literal L j such that
positively justified wrt M . This leads to Case 1.
imply that N is a fixpoint of \Pi R . 2
Lemma 9.4: Let \Pi R be the revised program of \Pi; and
be the well-founded
models of \Pi and \Pi R respectively. Then for any literal L 2
1.
2. L 2 F \Pi if and only if L 2 FR .
Proof: First we present an iterative approach to computing
the well-founded model of \Pi [26]. Assume T
as the program obtained from \Pi n by
1. deleting all clauses with L in the body if L 2 Fn ,
2. deleting all clauses with notL in the body if L 2
and
3. deleting all clauses with L as the head if L 2 Fn .
Further, let
where N is the set of all involved negations. Then
We also assume that TRn ; FRn , and \Pi Rn are defined as
above for \Pi R . Since for any given N of assumed negations,
only if \Pi R N ' -
L, it is sufficient to show,
and we are to show by induction, that
Basis It is trivial.
Hypothesis We assume that for any k - n,
Induction We need to show that
Since
it is sufficient to show that
was deleted from \Pi n if and only if
was deleted from
\Pi Rn .
Assume L / was deleted from \Pi n . Then,
there are three cases:
Case 1:
Case 2:
Case 3: L 2 Fn .
By the induction hypothesis, the three corresponding cases
for \Pi Rn are
Case 1:
Case 2: -
Case 3: L 2 FRn .
In each case, L /
will be deleted
from \Pi Rn .
Assume L /
deleted
from \Pi Rn . Then there are five cases
Case 1:
Case 2: -
Case 3:
Case 4:
Case 5: :L 2 TRn .
Similar to the only-if part, the hypothesis implies that the
first three corresponding cases for \Pi n are
Case 1:
Case 2:
Case 3: L 2 Fn .
In each case, L / will be deleted from \Pi Rn .
If as in Case 3, then, by (9.3), -
which is the same as in Case 2. Further, in case 5, i.e.,
since every clause with :L
as the head in \Pi R is semi-normalized. This means any
clause with L as the head had be deleted from \Pi Rn\Gamma1 which
contradicts that L /
notL is in \Pi Rn .
This completes the proof. 2
Theorem 4.2 Let \Pi R the revised program of \Pi,
the well-founded model of \Pi R , and
where
Then M is the unique skeptical model of \Pi.
be the well-founded semantics
of \Pi. By (9.4) and Lemma 9.4,
is the well-founded model of \Pi and
is also the well-founded model of \Pi F . Obvi-
ously, we also have
TR "
First, we show the following three facts.
Fact 1 L 2 F if and only if L is negatively justified wrt M
and \Pi.
iff \Pi R
TR 6' -
L for MR is a justified model
of \Pi R
iff \Pi R
L by (9.14) and the
construction of \Pi R
iff L is negatively justified wrt M and \Pi.
Fact 2 L 2 T if and only if L is positively justified wrt M
and :L is negatively shadow-justified wrt M .
Assume L is positively justified wrt M and :L is negatively
shadow-justified wrt M . Then
since \Pi R
This implies, by Lemma 9.2
It follows that L 2 T .
Assume hence L is true in the well-founded
semantics of \Pi R . The deriving process of L under the well-founded
semantics clearly indicates that L is positively justified
wrt M and \Pi.
Since M \Pi is the well-founded model of \Pi F , any L 2 F \Pi
is negatively shadow-justified wrt M and \Pi. Because L 2
TR and every clause with L as the head in \Pi R is semi-
normalized, :L 2 F \Pi . It follows that :L is negatively
shadow-justified wrt M and \Pi.
Fact 3 T does not contains a pair of complementary literals

It follows from the fact that every clause with L as the
head in \Pi R is semi-normalized, and therefore, L 2 TR only
Facts 1, 2, and 3 imply that M is a CJ partial model.
be a CJ partial model of \Pi. Then we
need only to show M - N , i.e.,
First, we show F ' FN .
be a justified partial model of \Pi such
that T 0 ' TN . Then, by Lemma 9.3, CA(N 0 ) is a fixpoint
of \Pi R , and therefore,
since MR is a well-founded model of \Pi R . It follows that
only if L is positively justified wrt M
and :L is negatively shadow-justified wrt M , it is straight-forward
to show that T ' TN . 2
Theorem 4.4
1. If N is an L-maximal fixpoint of \Pi R then
is a maximal CJ partial model of \Pi,
Ngi.
2. If hT ; F i is a maximal CJ partial model of \Pi then
is an L-maximal fixpoint
of \Pi R .
Proof: It follows Lemma 9.3 and the definition of the L-
maximal fixpoint. 2
Theorem 5.2
1. Both SCS and CCS satisfy N-cumulativity, negative-
justification, relevance, and conservatism, but not simplicity

2. The CCS satisfies preservation but the SCS does not.
3. Neither SCS nor CCS satisfies coherence.
Proof: N-cumulativity is satisfied by both coherence semantics
simply because is a CJ partial model
of \Pi if and only if M is a CJ partial model of \Pi F 0
for any
Assume L is negatively justified wrt SEM (\Pi), where
SEM is either SCS or CCS. Then for any CJ partial
model M such that SEM (\Pi) - M , L is also negatively
justified wrt M and therefore, notL is contained in M .
This implies that notL 2 SEM (\Pi).
Conservatism follows from the fact that M is a justified
model of \Pi if and only if there exits a CJ partial model M 0
such that M 0 - M .
The proof for both SRS and CRS satisfy relevance is not
difficult but rather tedious and thus omitted.
The CCS satisfies preservation because for any
contradiction-free program \Pi, M is a maximal CJ partial
model of \Pi if and only if M is a maximal justified model
of \Pi.
All negative statements are supported by various examples
in the paper. 2

Acknowledgments

The authors would like to thank J-uergen Dix and anonymous
reviewers for providing many constructive comments.
This work is partially supported by grants from the National
Science and Engineering Research Council of Canada
and by the ISIS, Fujitsu Labs, Numazu, Japan. This paper
is based on the technical report Coherence Approach to
Logic Program Revision, ISIS-RR-94-19E, Fujitsu Labora-
tories, 1994. A preliminary version of this paper appears
in the Proc. of the 12th International Conference on Logic
Programming, Page 167-181, June 1995. The work of the
first author was performed while visiting the ISIS, Fujitsu
Labs, Numazu, Japan.



--R

Scenario Semantics of Extended Logic Programs.

A framework for representing and characterizing semantics of logic programs.
A classification theory of semantics of normal logic programs: II.
Negations as hypotheses: An abductive foundation for logic programming.
An argumentation semantics for logic programming with explicit negation.
Revision.
The alternating fixpoints of logic programs with negation.
Logical programs with classical negation.
The stable model semantics for logic programming.
Extended well founded semantics for logic programs with negations.
Uniform proofs as a foundation for logic programming.

Contradiction removal within well founded semantics.

Stable models and non-determinism in logic programs with negation
Unrestricted logic programs or if stratification is the cure
Skeptical reason maintenance and belief revision.
Revision by Expansion in Logic Programs.
A three-valued semantics of deductive databases and logic programs
On the equivalence of semantics for normal logic programs.
Iterative belief revision in extended logic programming.
Logic programming with assumption denials.
Autoepistemic logic of first order and its expressive power.
Justification rules and justified model semantics.
Autoepistemic circumscription and logic programming.
--TR

--CTR
Chiaki Sakama , Katsumi Inoue, An abductive framework for computing knowledge base updates, Theory and Practice of Logic Programming, v.3 n.6, p.671-715, November
logic programming;knowledge representation;nonmonotonic reasoning;belief revision