An Abductive Semantics for Disjunctive Logic
Programs and its Proof Procedure
Jia-Huai You, Li Yan Yuan, Randy Goebel

Department of Computing Science
University of Alberta
Edmonton, Alberta, Canada T6G 2H1

fyou, yuan, goebelg@cs.ualberta.ca
Abstract. While it is well-known how normal logic programs may be
viewed as a form of abduction and argumentation, the problem of how
disjunctive programs may be used for abductive reasoning is rarely discussed.
In this paper we propose an abductive semantics for disjunctive
logic programs with default negation and show that Eshghi and Kowalski
's abductive proof procedure for normal programs can be adopted to
compute abductive solutions for disjunctive programs.
1 Introduction

In the simplest form abduction is the problem:
From A and A / B,

infer B as a possible explanation of A.

Nonmonotonic reasoning has been explored as a form of abductive reasoning.
In particular, default assumptions in logic programs have been treated as abductive
hypotheses and a number of reasoning mechanisms and semantics have been
proposed [7, 10, 16, 18, 19]. Chief among these is Eshghi and Kowalski's formulation
of an elegant abductive proof procedure for normal programs where default
assumptions are viewed as abducibles. Kakas et al. presented a comprehensive
exploration of abductive logic programming [16, 17]. A fundamental insight is
that abductive reasoning embodies an argumentation approach to logic program
semantics. Dung [8], as well as Bondarenko et al. [2], subsequently showed that
nonmonotonic reasoning in general is a form of argumentation using default
assumptions.
There are important applications of abductive reasoning with disjunctive programs.
For example, in AI planning and scheduling, in general we are interested
in whether there is a plan that achieves the goal, and whether there is a schedule
that satisfies the specified constraints. Such a solution corresponds to an explanation
(abducibles in a plan, for example) to an observation (the goal to be

achieved) in abduction. Furthermore, since abduction is a form of hypothetical
reasoning, it embodies a form of learning and prediction; e.g., one is often able
to abductively complete partial descriptions given as observations. For example,
suppose a robot has two hands, the left being designed to be capable of picking
up a block and placing it down in the same orientation, and the right rotating it.
Now suppose an observation is made that the block's orientation is changed and
that either the left or right hand is broken.

1

An explanation of this observation
must include a prediction that it is the left hand that is broken.
We note that the static semantics for disjunctive programs [24] is not designed
to be capable of accommodating these kind of applications.
Despite well understood results in relating normal programs with abduction,
and in more general cases, relating more general inference systems with abduction
and argumentation [2], the problem of how disjunctive programs may be
viewed as abduction is still open. For example, Dung showed in [5] that acyclic

disjunctive programs can be interpreted as abductive programs in the sense of
Eshghi and Kowalski, but he left the question open as what constitutes an abductive
semantics for the class of all disjunctive programs. The main problem is
that the method used in Dung's approach, which is based on a program transformation
called shifting, does not even preserve the minimal model semantics
for positive disjunctive programs. The problem has been noticed by a number
of authors in dealing with disjunctive default (e.g. [12, 26]).
In this paper we show a simple extension of the various abductive semantics
for normal programs to disjunctive programs. The central idea is to augment the
standard first order deduction relation by the inclusion of an additional inference
rule, called the rule of assumption commitment, which resolves an assumption
and a classic disjunction. Its ground form is:
not OE
OE  /

\Gamma \Gamma \Gamma

/

This inference rule is similar to that of resolution (or called disjunction elimination
 in natural deduction). That is, if one identifies not OE with :OE, it becomes
the resolution inference rule. Intuitively, it means that if we assume not OE we
can strengthen our assumption in an attempt to derive additional information.
For example, with the following disjunctive program

pay cash(x; y)  pay by credit(x; y) /

1

Here the term observation is used in a broad sense, not necessarily an act of physically
observing something.

where  is interpreted as epistemic disjunction (or, as exclusive as possible). The
observation that bob pays cash to greg (pay cash(bob; greg)) is explained by the
assumption that bob does not pay greg by credit,

not pay by credit(bob; greg);

which resolves with the above disjunction to yield pay cash(bob; greg).

The approach taken here falls into the general frameworks of abduction and
argumentation [2, 8, 17] in that a specific inference system (using the above inference
rule) is adopted for the purpose of capturing the meaning of the epistemic
disjunction initially formulated by Gelfond and Lifschitz. The most interesting
result out of such an adoption is a new semantics that extends the stable
semantics for disjunctive programs in the same way as regular/preferential semantics
extends the stable semantics for normal programs. Furthermore, with
partial evaluation as pre-processing [3], Eshghi and Kowalski's abductive proof
procedure, with a mechanism of positive loop checking, can be used to compute
abductive solutions for a disjunctive program. For example, if an AI planning
problem is formulated as a disjunctive program, one can use the Eshghi-Kowalski
abductive proof procedure to answer the question whether a goal is achievable.
The procedure computes the abducibles, in the backward chaining fashion, that
are needed in order to achieve the goal. The procedure is sound but not complete
with respect to the new semantics.

2

This seems to be the first backward
chaining proof procedure for any semantics for disjunctive programs. The stable
semantics in principle does not possess a top down proof procedure for the simple
reason that it does not have the locality property; i.e. a backward chaining
proof may be wrong simply due to nonexistence of a stable model. Almost all
current implementations of the static semantics reply on a bottom-up generation
of minimal models. Logic programming has been identified with a goal-oriented
programming paradigm. An implementation of a nonmonotonic semantics could
benefit from the techniques used in implementing Prolog [4]. Thus, the existence
of a top down proof procedure is a significant feature for any semantics.
It is important to mention the three remarkable facts about Eshghi and
Kowalski's procedure. First, it is conceptually simple--all it needs, on top of a
traditional negation-as-failure proof procedure, is a mechanism to handle two
kinds of (negative dependency) loops. Secondly, it is now known that this procedure
is sound, and complete as well with a mechanism of positive loop checking,
for a number of independently proposed but equivalent semantics for normal
programs (cf. [7, 13, 20, 30]). This includes the preferential semantics based
on abduction [7], the regular semantics [29] and the partial stable semantics
[25] using model-theoretic approachs, and a stronger version of the stable class

2

The procedure becomes complete when properly combined with a complete resolution
procedure.

semantics [1]. Perhaps more importantly, this procedure can be implemented
efficiently, and this efficiency could be comparable with that of a completely top
down proof procedure for the well-founded semantics.

3

An interesting conclusion
is that the efficiency of credulous reasoning (w.r.t. one model) based on a weaker
notion of stable models, i.e., regular models, is largely comparable with the efficiency
of the reasoning using the well-founded semantics when query answering
is based on a backward chaining proof.
The next section sets the stage for disjunctive programs to be interpreted
as abductive programs. Section 3 shows, using Dung's preferred extension as
an example, that any abductive semantics for normal programs can be simply
extended to disjunctive programs. This specifically yields a new abductive
semantics for disjunctive programs. Section 4 gives an elegant fixpoint characterization
of the minimal model semantics, stable semantics, and the new semantics
in terms of the extended inference relation. Section 5 shows a result which enables
the use of Eshghi-Kowalski's abductive proof procedure for the proposed
semantics, with Section 6 containing additional related work and additional remarks.

2 Disjunctive Logic Programming as Abduction

In general, an abductive framework is a triple hP; Ab; ICi where P is a first order
theory, Ab is the set of abducibles, and IC the set of first order formulas serving
as integrity constraints.
We restrict to a special class of abductive frameworks which correspond to
disjunctive programs. For each ordinary predicate atom OE = p(t 1 ; :::; t n ), not OE

denotes the corresponding abducible atom not p(t 1 ; :::; t n ). We let P be a first
order theory that consists of the clauses of the form

ff 1  :::  ff k / fi 1 ; :::; fi m ; not fl 1 ; :::; not fl n

where ff i 's and fi i 's are atoms, and not fl i 's are abducibles (also called assumptions)
.

We may denote the above clause by A / B; not C where A is the set of the
atoms in the head of the clause, B the set of the atoms in the body, and not C

the set of the assumptions in the body.

3

This is not a claim on the complexity of the semantics, which is known to be intractable
for the former and tractable for the latter. This claim merely reflects the
fact that as far as backward chaining proof is concerned, the behaviors of these two
semantics are quite similar: odd (negative dependency) loops are treated exactly the
same in both semantics, and for any even loop, a procedure for the well-founded
semantics assigns (tentatively) the value undefined based on the current loop, and
a procedure for the regular semantics simply indicates "in a model". In either case,
no further derivation beyond the loop is performed.

In the literature, disjunction is usually expressed by j, which is sometimes
called epistemic disjunction. The intuitive meaning of epistemic disjunction is
that it be interpreted as exclusive as possible. Here we replace it by classic
disjunction . Its intended meaning is enforced by the underlying abductive
semantics.
Note that since such a clause is just a first order formula, the first order
derivation relation ` is applicable. For example, with P consisting of

a  b / not c
a / b
b / a

we have P ` a / not c, P [ fnot cg ` a, etc. In Dung's terminology, not c is
evidence for a.

Further, we let

IC = f?/ (OE 1  :::  OE n ); not OE 1 ; :::; not OE n j n  1g
When n = 1, the constraints in IC become those for normal programs.
The special atom ? denotes a violation of a constraint. Although it embodies
a meaning of inconsistency, it is not the same as logical inconsistency; in
particular, its presence in a theory does not trivialize the theory by concluding
anything. We argue that this is an advantage of logic programming, as a notion
of "local inconsistency" may be accommodated.
For the purpose of abductive reasoning with disjunctive programs, we augment
the standard first order derivation relation by a new, resolution-like inference
rule:

Rule of Assumption Commitment (RAC):

not OE
OE 1  :::  OE n

\Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma \Gamma

oe(OE 1  :::  OE i\Gamma1  OE i+1  :::  OE n )
where OE is an atom, OE j 's are literals, and OE and OE i are unifiable with m.g.u. oe.

When n = 1, the resolvent is ?.

This inference rule says that if one assumes not OE, one may well commit it
to :OE in an attempt to derive additional information. In the sequel, we use ` d

to denote the standard first order derivation relation augmented by the above
rule of inference. Note that ` d is a monotonic relation.
We say that a set E of abducibles is an explanation of an atom OE if

P [ E ` d OE and P [ E [ IC 6 ` d ?

Example 1. Consider the situation where a block x is putdown onto the table or
onto another block y.
on table(x)  on block(x; y) / putdown(x)
putdown(a) /

Suppose we see that a is on block b. Then E = fnot on table(a)g forms an
explanation.
An interesting aspect of abductive reasoning is about prediction. As a specific
form of prediction, it is about completing, or enriching, the initially specified,
incomplete information.
Example 2. Consider the popular, broken-hand example originally discussed in
the context of default reasoning [23]: We know either the left hand is broken or
the right hand is broken, and in general, a hand is usable if not broken. The given
information is incomplete as we don't know which hand is broken and which is
not (perhaps both could have been broken).
For the purpose of demonstrating the point of augmenting partial information,
we further assume that the left hand being usable leads to the use of it
that results in moving a block; and the use of the right hand leads to moving
the table.
lh broken  rh broken /

lh usable / not lh broken
rh usable / not rh broken
move block / lh usable
move table / rh usable

Now suppose we observe that the block is moved from its original location
(and suppose we cannot see any operations). Under the closed world assumption
for operations (namely, no other operations other the ones performed by the
program may be performed), we can predict that it is the right hand that is
broken.
3 Abductive Semantics for Disjunctive Programs

In this section we demonstrate that an abductive semantics for normal programs
can be simply extended to disjunctive programs by augmenting only the underlying
derivation relation by RAC. We do this for Dung's semantics based on
preferred extensions, as there is an additional interest in a fixpoint characterization
and in the adoption of Eshghi and Kowalski's proof procedure.

In the sequel, for the sake of convenience, our technical exploration will be
based on ground programs. Also, since given an abductive framework hP; Ab; ICi,

both Ab and IC are fixed, we only mention P .
In the following definition, we paraphrase Dung's definition of a preferred
extension. But by adopting ` d , a new semantics for disjunctive programs is
obtained automatically.
First, we need some terminology: an assumption set S is called ?-consistent

if P [ S 6 ` d ?.

Definition1. Let P be a disjunctive program. An assumption not OE is said to
be acceptable w.r.t. an assumption set S if for any assumption set S

0

such that

P [ S

0

` d OE, we have P [ S ` d ��, for some not �� 2 S

0

.
A preferred extension E is a maximal assumption set that is ?-consistent,

and for every not OE 2 E, not OE is acceptable w.r.t. E.

In terms of argumentation (see, for example, [2, 8, 16, 28]), not OE is acceptable
w.r.t. S if any assumption set S

0

that attacks not OE is counter-attacked by S

itself.
Note that the definition is precisely that of Dung's if we use ` instead of ` d .
In fact, for normal programs, ` d coincides with ` since RAC has no real effect.
Because of this, the properties of preferred extensions for normal programs can
be easily extended to disjunctive programs. For example, it is easy to show that
there is at least one preferred extension for any disjunctive program.
Dung uses the Barber's paradox to illustrate the drawback of the stable
semantics for the case of normal programs [7]. To illustrate the same point for
disjunctive programs, we extend the example to a disjunctive program.

Example 3. Consider the disjunctive program:

shave(bob; x) / not shave(x; x)
pay cash(y; x)  pay by credit(y; x) / shave(x; y)
accepted(x; y) / pay cash(x; y)
accepted(x; y) / pay by credit(x; y)

This program intuitively says that bob shaves those who do not shave themselves;
If x shaves y then y pays x by cash or credit; either way is accepted.
Assume there is another person, called greg. Then clearly, we should conclude

bob shaves greg, and greg pays bob by cash or by credit, either way is accepted.
This program has no stable model. But it has two preferred extensions,
both containing not shave(greg; greg). In addition, one of the two contains

not pay cash(greg; bob) and the other not pay by credit(greg; bob). Thus, if we
know greg pays cash to bob, then the abductive solution is that we must assume
that greg does not pay bob by credit.

The use of the inference rule RAC may be viewed as semantically shifting
disjunctive clauses in a program P . Recall that the idea of shifting a clause

A / B; not C (e.g. see [5, 12]) is to syntactically transform such a clause to a
set of normal clauses where, for each atom OE in A there is a normal clause with

OE as the head and any other atom �� in A is removed to the body as not ��. More
formally, given a clause R:
A / B; not C

the set of normal clauses obtained by shifting R, denoted R shift is:

R shift = fOE / B; not C

0

: OE 2 A; not C

0

= not C [ fnot �� : �� 2 A; �� 6= OEgg

Given a disjunctive program P , we denote by P shift the set of all normal clauses
obtained by shifting all the clauses in P .
It is known that this technique is too strong to capture even the minimal
model semantics of a positive disjunctive program (cf. [12, 26]).
Example 4. Programs with head-cycles are often used to illustrate the difficulties
with syntactically shifting a program. Consider, for example, the following
program P :

a  b  c /

a / b
b / a

The program has a head-cycle between a and b. In terms of stratification, a

should be one level higher than b (by the second clause) and b should be one
level higher than a (by the third clause); but a and b also appear in the same
head of a clause; hence the term head-cycle.

The program has two minimal models, fcg and fa; bg, which correspond to
the two preferred extensions, E 1 = fnot a; not bg and E 2 = fnot cg. Let us
verify that E 1 is a preferred extension. The smallest assumption set that attacks

not a is fnot cg (i.e. P [ fnot cg ` d a), which is counter-attacked by E 1 itself
(i.e. P [ E 1 ` d c).

The normal program P shift consists of the following clauses:

a / not b; not c
b / not a; not c
c / not a; not b
a / b
b / a
P shift however does not have any stable model.

We now show that there is one-to-one relationship between a type of preferred
extensions, called stable extensions, and stable models. We first recall the
definition of a stable model.
A stable model M of a disjunctive program P is a set of atoms, which is a
minimal model of the following transformed program:

PM = fA / B : A / B; not C 2 P; and 8(not fl) 2 not C; fl 62 Mg

Similar to the case of normal programs [7], we define a stable extension S of
a disjunctive program P as a total preferred extension of P : for any ordinary
atom OE, either not OE 2 S or P [ S ` d OE

The stable models of a disjunctive program, and in particular the minimal
models of a positive disjunctive program, are expressible as stable extensions.

Theorem 2. Let P be a disjunctive program and M be a set of atoms. M is a
stable model of P iff SM is a stable extension of P where SM = fnot OE : OE 62 Mg.

2

This result provides another way to understand the results by Eiter and Gottlob
as well as by Marek et al. [9, 14, 22]: disjunctive default logic falls into the
same complexity level as default logic. In Gottlob's explanation of these complexity
levels, this can be said rather plainly as: for disjunctive programs epistemic
disjunction does not present one more source of computational difficulty than
classic disjunction.
4 A Fixpoint Characterization

We show that some of the results presented in [30], namely the results that
regular models/preferred extensions are maximal normal alternating fixpoints
of a suitable operator for normal programs, can be extended to the case of
disjunctive programs. This yields an elegant fixpoint characterization of all three
semantics: minimal models for positive disjunctive programs, stable models, as
well as preferred extensions, for disjunctive programs.
We define a function FP over sets S of assumptions as:

FP (S) = fnot OE : OE is an ordinary atom such that P [ S 6 ` d OEg:

It is easy to check that this function has the following property (called antimonotonicity)
:

S 1 ` S 2 ) FP (S 2 ) ` FP (S 1 )
This holds because the derivation relation ` d is monotonic; more information
that we have, less information we do not derive. Then, the composite function
that applies FP twice, denoted F

2

P , is monotonic. That is,

S 1 ` S 2 ) F

2

P (S 1 ) ` F

2

P (S 2 )

A fixpoint of the function F

2

P is called an alternating fixpoint of FP (or simply,

P ; cf. [1, 11, 30]). An alternating fixpoint S is called normal if S ` FP (S). For
credulous reasoning, we are interested in maximal normal alternating fixpoints.
On the other hand, Dung's preferred extensions are, by definition, the fixpoints
of the following operator over sets of assumptions:

DP (S) = fnot OE j not OE is acceptable w.r.t. Sg:

Note that F

2

P depends only on a derivation relation. As a result, the operation
of extending an assumption set using F

2

P is rather mechanical. On the other hand,
the definition of DP , which is based on the notion of acceptability, is less direct.
However, we will show that these two operators are equivalent. First, let us see
an example.

Example 5. Consider the following disjunctive program:

a  b / not a; not b
c / not d

It is easy to show that S = fnot dg is a maximal normal alternating fixpoint.
First, FP (S) = fnot d; not a; not bg. Then, F

2

P (S) = fnot dg. Further, S `

FP (S). Thus, S is a normal alternating fixpoint.
In addition, it is easy to see that S is the only normal alternating fixpoint.
For example, S

0

= fnot d; not ag is not an alternating fixpoint, since

FP (S

0

) = fnot d; not a; not bg and F

2

P (S

0

) = fnot dg. Further, though S

00

=

fnot d; not a; not bg is an alternating fixpoint but it is not normal. Thus, S is
trivially maximal.

S is also a preferred extension. This is more tedious to verify, since one has to
consider, for each assumption not OE, all the possible assumption sets that may
attack not OE, and for each such assumption set that does attack not OE, whether
it is counter-attacked by S. We leave this to the reader to verify.
We now show that there is one-to-one correspondence between maximal normal
alternating fixpoints and preferred extensions. First, we have a lemma.

Lemma 3. Let P be a disjunctive program and S be an assumption set. Then,

F

2

P (S) = DP (S). 2

For an alternating fixpoint S = F

2

P (S), the normality condition S ` FP (S)
ensures consistency. E.g. in the above example, fnot d; not a; not bg is an alternating
fixpoint, but it is not ?-consistent and thus it is not normal.
From this lemma, it is easy to show

Theorem 4. Let P be a disjunctive program and S be an assumption set. Then,

S is a preferred extension of P iff S is a maximal normal alternating fixpoint of

P .

As a corollary of this theorem, stable models of a disjunctive program (and
minimal models of a positive disjunctive program) are a particular type of maximal
normal alternating fixpoints; namely, they are fixpoints of FP (which are
then trivially fixpoints of F

2

P ).

Corollary 5. Let P be a disjunctive program and S be an assumption set. Then,

S is a stable extension of P iff S is a fixpoint of FP .
5 Proof Procedure

In this section we show that the extensions of a head-cycle free disjunctive program
 P are precisely those of the normal program P shift . This result enables
the use of Eshghi and Kowalski's abductive proof procedure to answer queries,
soundly, using the normal program obtained by shifting.
This result can be seen as an extension of those presented by Dung in [8]
on the use of Eshghi and Kowalski's proof procedure for disjunctive programs.
Dung's result relies on two restrictions. The first is that a program should be
head-cycle free, the same as ours. The other is that there should be no default
negation going through recursion. Our result does not need this second restriction.

First, let us look at an example.

Example 6. Consider disjunctive program P = fa  b / not ag. P is head-cycle
free simply because there is no positive body literal in the clause. The normal
program obtained by shifting is P shift :

a / not a; not b
b / not a

Clearly, both P and P shift have the same unique preferred extension, fnot ag.

Now we show the relationship between the extensions of a head-cycle free
disjunctive program P and those of its normal transformation P shift . As there
seems to be a particular interest in this result, we provide a proof sketch here.

Theorem 6. Let P be a finite ground, head-cylce free disjunctive program, and

P shift be the normal program obtained by shifting. Then, an assumption set S is
a preferred extension of P iff it is a preferred extension of P shift .
Proof Sketch: We only show the ) part. Without loss of generality, we assume
that the given program P is free of positive body literals. This is because partial
evaluation [3] can reduce them.

We show that, for any assumption not OE, if not OE is acceptable w.r.t. S using
program P and under ` d , then not OE is acceptable w.r.t. S using P shift and
under `.

The if clause in this statement is: for any assumption set W such that P [

W ` d OE, we have P [ S ` ��, for some not �� 2 W .
The conclusion part is: for any assumption set W such that P shift [ W ` OE,

we have P shift [ S ` ��, for some not �� 2 W .
Suppose W is such that P shift [ W ` OE. Then, there is a clause OE /

not C; not Rest in P shift , where not C [ not Rest ` W and not Rest denotes
the set of assumptions shifted from the head of the clause fOEg [ Rest / not C

in P . Then, it is easy to see there is a sequence of derivation steps using
RAC that resolve fOEg [ Rest / with those assumptions in not Rest to yield

OE. Thus, P [ W ` d OE. It then follows from the if clause in the statement
above that P [ S ` d ��, for some not �� 2 W . This implies there is a clause

f��g[Rest

0

/ not D in P such that not D ` S and f��g[Rest

0

/ resolves with
the assumptions in not Rest

0

(not Rest

0

` S) to yield ��. Then, clearly, the corresponding
shifted clause �� / not D; not Rest

0

derives ��. That is, P shift [S ` ��,

for some not �� 2 W . This shows the conclusion part. 2
There is something of further interest in this result: a finite ground disjunctive
program can be pre-processed by partial evaluation [3] to reduce all the
positive body literals in a program so that the resulting program is trivially
head-cycle free.

4

Thus, the Eshghi-Kowalski proof procedure plus partial evaluation
provides a proof theory for the abductive semantics proposed in this paper.
The soundness of such a proof theory is easy to verify, mainly due to the
fact that partial evaluation is semantics preserving for the semantics proposed
in this paper, and the semantics proposed here reduces to preferential/regular
semantics, for which the Eshghi-Kowalski procedure is sound and complete (with
positive loop checking). However, because disjunction cannot be simulated completely
by normal programs, a procedure for normal programs cannot be complete
in general for disjunctive programs.

Example 7. First, consider the following, head-cycle free, program P :

a  b
c / a
c / b
The program has two preferred extensions fnot ag and fnot bg. Its shifted

4

If a program P is nonground, partial evaluation may not terminate. Even it can be
made to terminate for finite ground programs, the process is in general intractable.

program, P shift , consists of

a / not b
b / not a
c / a
c / b

It has the same preferred extensions.
Given the query

/ c

the Eshghi-Kowalski procedure will construct two proofs (by backtracking), one
with abducible not b and the other with not a. The Eshghi-Kowalski procedure
is complete in this case.
However, the situation changes if we add two clauses fa / not a; b / not bg

into P , denoted it by P

0

. P

0

has one preferred extension, ;, and P

0

` d c.

Now P

0

shift is:

a / not a
b / not b
a / not b
b / not a
c / a
c / b

Although it has the same preferred extension as P

0

, it is no longer the case
that P

0

shift ` d c, and the Eshghi-Kowalski procedure cannot answer the query

/ c using P

0

shift .
To make it a complete proof procedure, the Eshghi-Kowalski procedure should
be combined a linear resolution procedure. In this case, even head-cyclic programs
can be handled, since partial evaluation is a form of resolution procedure.
Recently, it has come to our attention that, in an unpublished manuscript
[6], Dung defined a procedure that combines Eshghi-Kowalski procedure with a
form of linear resolution, SLI-resolution of Lobo et al.'s [21]. The relationship
between this procedure and our semantics is currently being investigated.
6 Related Work and Final Remarks

Work by Inoue and Sakama [15, 15] yields important insights into a different
aspect of the problem; how to represent abductive programs by (extended) disjunctive
programs. In [15], they proposed a transformation from the former to
the latter, and in [27], they showed, in general, an abductive program can be
viewed as a disjunctive program with priorities. Our work is about a proposal of
an abductive/argumentation framework for disjunctive programs. Further, our

abductive semantics for disjunctive programs reduces to the regular/preferential
semantics for normal programs. This is the key to applying Eshghi and Kowalski
's abductive proof procedure.
Dung shows that there is a natural abduction/argumentation interpretation
for explicit negation. His techniques can be applied to the semantics proposed
here. How to accommodate explicit negation in the Eshghi-Kowalski procedure
requires further investigation.
References

1. C. Baral and V. Subrahmanian. Stable and extension class theory for logic programs
and default logic. J. Automated Reasoning, pages 345--366, 1992.
2. A. Bondarenko, F. Toni, and R. Kowalski. An assumption-based framework for
nonmonotonic reasoning. In Proc. 2nd Int'l Workshop on LPNMR, pages 171--
189. MIT Press, 1993.
3. S. Brass and J. Dix. Disjunctive semantics based upon partinal and botton-up
evaluation. In Proc. 12th ICLP, pages 199--216, 1995.
4. W. Chen and D. Warren. Extending prolog with nonmonotonic reasoning. J. Logic
Programming, 27(2):169--183, 1996.
5. P. Dung. Acyclic disjunctive logic programs with abductive procedures as proof
procedure. In Proc. 1992 Fifth Generation Computer Systems, pages 555--561,
1992.
6. P. Dung. An abductive procedure for disjunctive logic programs. Unpublished
manuscript, 1993.
7. P. Dung. An argumentation theoretic foundation for logic programming. J. Logic
Programming, 22:151--177, 1995. A short version appeared in Proc. ICLP '91.

8. P. Dung. On the acceptability of argument and its fundamental rule in nonmonotonic
reasoning and logic programming and n-person game. Artificial Intelligence,
76, 1995. A short version appeared in Proc. IJCAI'93.

9. T. Eiter and G. Gottlob. On the computational cost of disjunctive logic programming:
propositional case. Annals of Mathematics and Artificial Intelligence,

15:289--324, 1993.
10. K. Eshghi and R.A. Kowalski. Abduction compared with negation by failure. In

Proc. 6th ICLP, pages 234--254. MIT Press, 1989.
11. A. Van Gelder. The alternating fixpoint of logic programs with negation. J. Computer
and System Sciences, pages 185--221, 1993. The preliminary version appeared
in PODS '89.

12. M. Gelfond, V. Lifschitz, H. Przymusinska, and M. Truszczynski. Disjunctive defaults.
In Proc. 2nd Int'l Conf. on Principle of Knowledge Representation and
Reasoning, pages 230--237, 1991.
13. L. Giordano, A. Marteli, and M. Sapino. A semantics for eshghi and kowalski's
abductive procedure. In Proc. 10th ICLP. MIT Press, 1993.
14. G. Gottlob. Complexity results for nonmonotonic logics. Journal of Logic and
Computation, 2:397--425, 1992.

15. K. Inoue and C. Sakama. Transforming abductive logic programs to disjunctive
programs. In Proc. 10th ICLP. MIT Press, 1993.
16. A. Kakas, R. Kowalski, and F. Toni. Abductive logic programming. J. Logic and
Computation, 2:719--770, 1992.
17. A. Kakas, R. Kowalski, and F. Toni. The role of abduction in logic programming.
In Handbook of Logic in Artificial Intelligence and Logic Programming. Oxford
University, 1995.
18. A. Kakas and P. Mancarella. Generalized stable models: a semantics for abduction.
In Proc. 9th ECAI, 1990.
19. A. Kakas and P. Mancarella. Stable theories for logic programs. In Proc. ILPS.

MIT Press, 1991.
20. A. Kakas and P. Mancarella. Preferred extensions are partial stable models. J.
Logic Programming, pages 341--348, 1992.
21. J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming.
MIT Press, 1992.
22. W. Marek, A. Rajasekar, and M. Truszczy'nski. Complexity of computing with
extended propositional logic programs. In H. Blair, W. Marek, A. Nerode, and
J. Remmel, editors, Proc. the Workshop on Structural Complexity and RecursionTheoretic
Methods in Logic Programming, pages 93--102, Washington DC, 1992.
Cornell University.
23. D. Poole. What the lottery paradox tells us about default reasoning. In Proc. KR
'89, pages 333--340, 1989.
24. T. C. Przymusinski. Static semantics for normal and disjunctive logic programs.

Annals of Mathematics and Artificial Intelligence, 1995.
25. D. Sacc`a and C. Zaniolo. Stable models and non-determinism in logic programs
with negation. In Proc. 9th ACM PODS, pages 205--217, 1990.
26. C. Sakama and K. Inoue. Relating disjunctive logic programs to default theories.
In Proc. 2nd Int'l Worshop on LPNMR, pages 266--282. MIT Press, 1993.
27. C. Sakama and K. Inoue. Representing priorities in logic programs. In Proc. Int'l
Conference and Symposium on Logic Programming. MIT Press, 1996.
28. J. You, R. Cartwright, and M. Li. Iterative belief revision in extended logic programming.
 Theoretical Computer Science, 170(1-2):383--406, 1996.
29. J. You and L. Yuan. A three-valued semantics for deductive databases and logic
programs. J. Computer and System Sciences, 49:334--361, 1994. A short version
appeared in Proc. PODS '90.

30. J. You and L. Yuan. On the equivalence of semantics for normal logic programs.

J. Logic Programming, 22(3):211--222, 1995.
This article was processed using the L

A

T E X macro package with LLNCS style

