# Argumentative Characterizations of
(Extended) Disjunctive Logic Programs

Jesse Heyninck Ofer Arieli Department of Computer Science School of Computer
Science Open Universiteit, The Netherlands Tel-Aviv Academic College, Israel

###### Abstract

This paper continues an established line of research about the relations
between argumentation theory, particularly assumption-based argumentation, and
different kinds of logic programs. In particular, we extend known result of
Caminada, Schultz and Toni by showing that assumption-based argumentation can
represent not only normal logic programs, but also disjunctive logic programs
and their extensions. For this, we consider some inference rules for
disjunction that the core logic of the argumentation frameworks should
respect, and show the correspondence to the handling of disjunctions in the
heads of the logic programs’ rules.

##  1 Introduction

Logic programming (LP) and assumption-based argumentation (ABA) are two
primary methods for knowledge representation and non-monotonic reasoning,
originated from similar intuitions and applied in different contexts. In fact,
to a large extent, the introduction of ABA systems was motivated by an
argumentative interpretation of LP semantics [7]. The former provides a Dung-
style representation [15] of coherent sets of formulas that admits other sets
of formulas as their contraries, and the latter combines reasoning based on
strict inference rules with an interpretation of negation as ‘failure to prove
the converse’ [28].

The similar ground of LP and ABA calls upon translation methods for revealing
the exact relations between them, and for importing reasoning methods from one
formalism to the other. For example, argumentative characterizations of logic
programming have been proven useful for explanation [35, 36] and visualization
[34] of inferences in logic programming. Among the works that relate LP and
ABA we recall the one of Schulz and Toni [37, 38] that provides a one-to-one
correspondence between the 3-valued stable models for normal logic programs
[30] and complete labelings for ABA frameworks. Caminada and Schulz [9, 10]
show the equivalence between ABA semantics and normal logic programs. A recent
work by Wakaki [42] shows that that answer sets of a (non-disjunctive)
extended logic programs can be captured by stable extensions of the translated
ABA frameworks. These works are restricted to logic programs, where atoms or
their (classical) negations are allowed in the head of the rules.111In a
follow-up work [43], which is based in the results in the short version of
this work [25], Wakaki also discusses disjunctive information. We shall refer
to that work in the related work section. Yet, a faithful modeling of real-
world problems often requires to cope with _incomplete knowledge_ , which is
not possible in the scope of such logic programs. This is a primary motivation
in the introduction of _disjunctive logic programs_ , where disjunctions are
allowed in the heads of the rules and negations may occur in their bodies, and
_extended disjunctive logic programs_ , where a classical negation is also
permitted (both in the rules bodies and their heads).

Under usual complexity assumptions, disjunctive logic programs were shown to
be strictly more expressive than normal logic programs [18, 24]. Moreover, in
the last decades they have been efficiently implemented and widely applied,
and so become a key technology in knowledge representation (see e.g. [39]).
Therefore, in this paper we set out to generalize the argumentative
characterization of logic programming for disjunctive logic programs and their
extended variations. For this, we incorporate the ideas in [1, 2, 26],
generalizing standard ABA frameworks to propositional formulas (as the
defeasible or strict assumption at hand), expressed and evaluated in Tarskian
logics. This allows to augment the underlying core logic of the ABA framework
with inference rules for handling disjunctive assertions, and so associate the
stable extensions of such frameworks with the stable models of the
corresponding disjunctive logic program.

The rest of this work is organized as follows: In the next section we review
some basic notions behind assumption-based argumentation and disjunctive logic
programming. In Section 3, which is the main part of the paper, we show how
(the stable models of) the latter can be represented by (the stable extensions
of) the former. The converse is discussed in Section 4. In Section 5 we
provide some negative results, showing that this correspondence does not carry
on to models and extensions that are not necessary two-valued and stable (at
least as far as our translation is concerned). On the other hand, as shown in
Section 6, our results are easily generalized to extended disjunctive logic
programs, where a classical negation is also allowed, in a addition to the
negation-as-failure connective. In Section 7 we discuss some related work and
conclude.222This is an updated and extended version of the conference paper in
[25].

##  2 Preliminaries

We denote by ${\mathcal{L}}$ a propositional language. Atomic formulas in
${\mathcal{L}}$ are denoted by $p,q,r$ (possibly indexed), compound formulas
are denoted by $\psi,\phi,\sigma$, and sets of formulas in ${\mathcal{L}}$ are
denoted by $\Gamma,\Delta,\Theta,\Lambda$. We shall assume that
${\mathcal{L}}$ contains a conjunction (denoted as usual in logic programing
by a comma), disjunction $\vee$, implication $\rightarrow$, a negation
operator $\sim$, and propositional constants F, T for falsity and truth. When
considering extended disjunctive logic programs, we shall assume that the
language also contains another kind of negation, denoted $\neg$ (the exact
meaning of each connective will be defined in what follows). Also, we denote
$\sim\\!\Gamma=\\{\sim\\!\gamma\mid\gamma\in\Gamma\\}$. The powerset of
$\Gamma$ is denoted $\wp(\Gamma)$.

###  2.1 Assumption-Based Argumentation

###### Definition 1

A (propositional) logic for a language ${\mathcal{L}}$ is a pair
${\mathfrak{L}}={\langle{\mathcal{L}},\vdash\rangle}$, where $\vdash$ is a
(Tarskian) consequence relation for ${\mathcal{L}}$, that is, a binary
relation between sets of formulas and formulas in ${\mathcal{L}}$, which is
reflexive (if $\psi\in\Gamma$ then $\Gamma\vdash\psi$), monotonic (if
$\Gamma\vdash\psi$ and $\Gamma\subseteq\Gamma^{\prime}$, then
$\Gamma^{\prime}\vdash\psi$), and transitive (if $\Gamma\vdash\psi$ and
$\Gamma^{\prime},\psi\vdash\phi$, then $\Gamma,\Gamma^{\prime}\vdash\phi$).

The next definition, adapted from [26], generalizes the definition in [7] of
assumption-based frameworks.

###### Definition 2

An _assumption-based framework_ (ABF, for short) is a tuple ${\sf
ABF}={\langle\mathfrak{L},\Gamma,\Lambda,-\rangle}$, where:

  * •

${\mathfrak{L}}={\langle{\mathcal{L}},\vdash\rangle}$ is a propositional
logic.

  * •

$\Gamma$ (the _strict assumptions_) and $\Lambda$ (the _candidate or
defeasible assumptions_) are distinct countable sets of
$\mathcal{L}$-formulas, where the former is assumed to be $\vdash$-consistent
(i,.e, $\Gamma\not\vdash{\sf F}$) and the latter is assumed to be nonempty.

  * •

$-:\Lambda\rightarrow\wp(\mathcal{L})$ is a contrariness operator, assigning a
finite set of ${\mathcal{L}}$-formulas to every defeasible assumption in
$\Lambda$.

###### Note 1

Unlike the setting of [7], an ABF may be based on any propositional logic
$\mathfrak{L}$. Also, the strict as well as the candidate assumptions are
formulas that may not be just atomic. Concerning the contrariness operator,
note that it is not a connective of ${\mathcal{L}}$, as it is restricted only
to the candidate assumptions.

Defeasible assertions in an ABF may be attacked by counterarguments.

###### Definition 3

Let ${\sf ABF}={\langle\mathfrak{L},\Gamma,\Lambda,-\rangle}$ be an
assumption-based framework, $\Delta,\Theta\subseteq\Lambda$, and
$\psi\in\Lambda$. We say that $\Delta$ _attacks_ $\psi$ iff
$\Gamma,\Delta\vdash\phi$ for some $\phi\in-\psi$. Accordingly, $\Delta$
attacks $\Theta$ if $\Delta$ attacks some $\psi\in\Theta$.

The last definition gives rise to the following adaptation to ABFs of the
usual semantics for abstract argumentation frameworks [15].

###### Definition 4

([7]) Let ${\sf ABF}={\langle\mathfrak{L},\Gamma,\Lambda,-\rangle}$ be an
assumption-based framework, and let $\Delta\subseteq\Lambda$. Then $\Delta$ is
_conflict-free_ iff there is no $\Delta^{\prime}\subseteq\Delta$ that attacks
some $\psi\in\Delta$. We say that $\Delta$ is _stable_ in ${\sf ABF}$ iff it
is conflict-free, and attacks every $\psi\in\Lambda\setminus\Delta$. The set
of stable sets of ${\sf ABF}$ is denoted by ${\sf Stb}({\sf ABF})$.333In many
presentations of assumption-based argumentation, extensions are required to be
closed, i.e., they should contain any assumption they imply. Since the
translation below will always give rise to the so-called _flat_ ABFs (that is,
ABFs for which a set of assumptions can never imply assumptions outside the
set; See Note 4 below), closure of extensions is trivially satisfied in our
case.

###### Example 1

Let ${\bf ABF}=\langle\mathfrak{L}_{\sf MP},\\{{\sim\\!q}\rightarrow
p\\},\\{{\sim\\!p},\>{\sim\\!q}\\},-\rangle$, where $-{\sim\\!p}=p$ and
$-{\sim\\!q}=q$, and where $\mathfrak{L}_{\sf MP}$ consists of the sole
inference rule Modus Ponens:

$\left.\begin{array}[]{lll}\mbox{[{\sf MP}]}\
&\displaystyle\frac{\phi_{1},\ldots,\phi_{n}\rightarrow\psi\hskip
17.07164pt\phi_{1}\hskip 14.22636pt\phi_{2}\hskip 8.53581pt\cdots\hskip
8.53581pt\phi_{n}}{\psi}\end{array}\right.$

This gives rise to the following argumentation graph, where a directed arrow
represents an attack of the set at the origin of the arrow on the set at the
arrow’s end.

$\\{\sim\\!p\\}$$\\{\sim\\!q\\}$$\\{{\sim\\!p},\>{\sim\\!q}\\}$

The sole stable set of assumptions in this case is $\\{{\sim\\!q}\\}$.

###  2.2 Disjunctive Logic Programs

###### Definition 5

A disjunctive logic normal program $\pi$ is a finite set of expressions
(rules) of the form

$(\star)\hskip
42.67912ptq_{1},\ldots,q_{m},{\sim\\!r_{1}},\ldots,{\sim\\!r_{k}}\rightarrow
p_{1}\lor\ldots\lor p_{n}$

where $p_{1}\lor\ldots\lor p_{n}$ is called the head of the rule, and
$q_{1},\ldots,q_{m},\sim\\!r_{1},\ldots,\sim\\!r_{k}$ is its body. When each
head of a rule in $\pi$ is either empty or consists of an atomic formula
(i.e., $n\leq 1$), we say that $\pi$ is a normal logic program. A logic
program $\pi$ is positive, if $k=0$ for every rule in $\pi$. We denote by
${\cal A}(\pi)$ the set of atomic formulas that appear in $\pi$.

Intuitively, the rule in $(\star)$ indicates that if $q_{i}$ holds for every
$i\leq i\leq m$ and $r_{i}$ is not provable for every $1\leq i\leq k$ , then
either of the $p_{i}$’s, for $1\leq i\leq n$, should hold. In what follows,
unless otherwise stated, when referring to a logic program we shall mean that
it is disjunctive. The semantics of a logic program $\pi$ is defined as
follows:

###### Definition 6

Let $M$ be set of atomic formulas, $p,p_{i},q_{j}$ atomic formulas, and
$l_{j}\in\\{q_{j},\sim\\!q_{j}\\}$ literals. We denote:

  * •

$M\models p$ iff $p\in M$,

  * •

$M\models\>\sim\\!p$ iff $p\not\in M$,

  * •

$M\models p_{1}\vee\ldots\vee p_{n}$ iff $M\models p_{i}$ for some $1\leq
i\leq n$,

  * •

$M\models l_{1},\ldots,l_{m}$ iff $M\models l_{j}$ for every $1\leq j\leq m$,

  * •

$M\models l_{1},\ldots,l_{m}\rightarrow p_{1}\vee\ldots\vee p_{n}$ iff either
$M\models p_{1}\vee\ldots\vee p_{n}$ or $M\not\models l_{1},\ldots,l_{m}$ (the
latter means that it is not the case that $M\models l_{1},\ldots,l_{m}$).

When $M\models\psi$, we say that $M$ satisfies $\psi$. Given a logic program
$\pi$, we denote by $M\models\pi$ that $M$ satisfies every $\psi\in\pi$. In
that case, we say that $M$ is a model of $\pi$.

Thus, a model of a rule either falsifies at least one of the assumptions in
the rule’s body, or validates at least one of the disjuncts in the rule’s
head. A particular family of models is defined next.

###### Definition 7

Let $\pi$ be a disjunctive logic program and let $M\subseteq{\cal A}(\pi)$.

  * •

The Gelfond-Lifschitz reduct [21] of $\pi$ with respect to $M$ is the
disjunctive logic program $\pi^{M}$, where $q_{1},\ldots,q_{m}\rightarrow
p_{1}\lor\ldots\lor p_{n}\in\pi^{M}$ iff there is a rule
$q_{1},\ldots,q_{m},\sim\\!r_{1},\ldots,\sim\\!r_{k}\rightarrow
p_{1}\lor\ldots\lor p_{n}\in\pi$ and $r_{i}\not\in M$ for every $1\leqslant
i\leqslant k$.

  * •

$M$ is a stable model of $\pi$ iff it is a $\subseteq$-minimal model of
$\pi^{M}$.

###### Example 2

Consider the disjunctive logic program: $\pi_{1}=\\{{\sim\\!p}\rightarrow
q\lor r\\}$. Below are the different combinations of atoms in this case and
their reducts. The two stable models of $\pi_{1}$ are marked by a gray
background.

$i$ | $M_{i}$ | $\pi_{1}^{M_{i}}$ | $i$ | $M_{i}$ | $\pi_{1}^{M_{i}}$
---|---|---|---|---|---
$1$ | $\emptyset$ | $\\{\rightarrow q\lor r\\}$ | $5$ | $q$ | $\\{\rightarrow q\lor r\\}$
$2$ | $p$ | $\emptyset$ | $6$ | $r$ | $\\{\rightarrow q\lor r\\}$
$3$ |  $p$, $q$ | $\emptyset$ | $7$ |  $q$, $r$ | $\\{\rightarrow q\lor r\\}$
$4$ |  $p$, $r$ | $\emptyset$ | $8$ |  $q$, $r$, $p$ | $\emptyset$

Thus, $\\{q\\}$ and $\\{r\\}$ are the (only) stable models of $\pi_{1}$.

##  3 From DLP to ABA

Given a disjunctive logic program $\pi$, we show a one-to-one correspondence
between the stable models of $\pi$ onto the stable extensions of an ABA
framework that is induced from $\pi$. First, we describe the translation and
then prove its correctness.

###  3.1 The Translation

All the ABA frameworks that are induced from disjunctive logic programs will
be based on the same core logic, which is constructed by the three inference
rules Modus Ponens (${\sf MP}$), Resolution (${\sf Res}$) and Reasoning by
Cases (${\sf RBC}$):

$\left.\begin{array}[]{lll}\mbox{[{\sf
MP}]}&\displaystyle\frac{\phi_{1},\ldots,\phi_{n}\rightarrow\psi\hskip
17.07164pt\phi_{1}\hskip 14.22636pt\phi_{2}\hskip 8.53581pt\cdots\hskip
8.53581pt\phi_{n}}{\psi}\vskip 12.0pt plus 4.0pt minus 4.0pt\\\ \mbox{[{\sf
Res}]}&\displaystyle\frac{\psi^{\prime}_{1}\vee\ldots\vee\psi^{\prime}_{m}\vee\phi_{1}\vee\ldots\vee\phi_{n}\vee\psi^{\prime\prime}_{1}\vee\ldots\vee\psi^{\prime\prime}_{k}\hskip
17.07164pt\sim\\!\phi_{1}\hskip 8.53581pt\cdots\hskip
8.53581pt\sim\\!\phi_{n}}{\psi^{\prime}_{1}\vee\ldots\vee\psi^{\prime}_{m}\vee\ldots\vee\psi^{\prime\prime}_{1}\vee\ldots\vee\psi^{\prime\prime}_{k}}\vskip
12.0pt plus 4.0pt minus 4.0pt\\\ \mbox{[{\sf
RBC}]}&\displaystyle\frac{\begin{array}[]{c}\phi_{1}\\\ \vdots\\\
\psi\end{array}\hskip 19.91692pt\begin{array}[]{c}\phi_{2}\\\ \vdots\\\
\psi\end{array}\hskip 14.22636pt\begin{array}[]{c}\\\ \\\
\cdots\end{array}\hskip 14.22636pt\begin{array}[]{c}\phi_{n}\\\ \vdots\\\
\psi\end{array}\hskip 19.91692pt\begin{array}[]{c}\\\ \\\
\phi_{1}\vee\ldots\vee\phi_{n}\end{array}}{\psi}\end{array}\right.$

In what follows we denote by
${\mathfrak{L}}={\langle{\mathcal{L}},\vdash\rangle}$ the logic based on the
language ${\mathcal{L}}$ which consists of disjunctions of atoms
($p_{1}\lor\ldots\lor p_{n}$ for $n\geq 1$), negated atoms ($\sim\\!p$), or
formulas of the forms of the program rules in Definition 5. Accordingly, we
shall use only fragments of the inference rules above, in which in [Res] and
[RBC] the formulas $\psi,\psi_{i}$ are disjunctions of atomic formulas and
$\phi_{i}$ are atomic formulas. In [MP], $\psi$ is a disjunction of atomic
formulas and $\phi_{i}\in\\{p_{i},\sim\\!p_{i}\\}$ are literals. Now, we
denote $\Delta\vdash\phi$ iff $\phi$ is either in $\Delta$ or is derivable
from $\Delta$ using the inference rules above. In other words,
$\Delta\vdash\phi$ iff $\phi\in{\sf Cn}_{\mathfrak{L}}(\Delta)$, where ${\sf
Cn}_{\mathfrak{L}}(\Delta)$ is the ${\mathfrak{L}}$-based transitive closure
of $\Delta$ (namely, the $\subseteq$-smallest set that contains $\Delta$ and
is closed under [MP], [Res] and [RBC]).

###### Note 2

For any $\phi\in{\sf Cn}_{\mathfrak{L}}(\Delta)$, if $\phi$ is not of the form
$p_{1}\lor\ldots\lor p_{n}$ then $\phi\in\Delta$.

###### Note 3

Since the rule $\rightarrow\psi$ is identified with ${\sf T}\rightarrow\psi$,
[MP] implicitly implies Reflexivity [Ref]:
$\displaystyle\frac{\rightarrow\psi}{\psi}$.

###### Definition 8

The assumption-based argumentation framework that is induced by a disjunctive
logic program $\pi$ is defined by: ${\sf
ABF}(\pi)={\langle{\mathfrak{L}},\pi,\sim\\!{\cal A}(\pi),-\rangle}$, where
$-\\!\sim\\!p=\\{p\\}$ for every $p\in{\cal A}(\pi)$.

###### Example 3

Let $\pi_{2}=\\{{\rightarrow\\!p\lor q},\ {p\rightarrow q},\ {q\rightarrow
p}\\}$. The attack diagram of the induced assumption-based argumentation
framework ${\sf ABF}(\pi_{2})$ is shown in Figure 1(a).

$\\{\sim\\!p\\}$$\\{\sim\\!q\\}$$\emptyset$ (a)

$\\{\sim\\!p\\}$$\\{\sim\\!q\\}$ (b)

Figure 1: Attack diagrams for Examples 3, 6c (left) and Example 6b (right)

In the notations of Definition 2, we have: $\Gamma=\pi_{2}$ and
$\Lambda=\\{{\sim\\!p},{\sim\\!q}\\}$. To see, e.g., that the set
$\\{\sim\\!p\\}$ attacks itself, note that by [MP] on $\rightarrow p\vee q$ we
conclude $\Gamma\vdash p\vee q$, and by [Res] it holds that
$\Gamma,{\sim\\!p}\vdash q$. Thus, since $q\rightarrow p\in\Gamma$, by [MP] we
get $\Gamma,{\sim\\!p}\vdash p$, namely:
$\Gamma,{\sim\\!p}\vdash{-\\!\sim\\!p}$. From similar reasons
$\\{{\sim\\!q}\\}$ attacks itself. For the attacks of $\emptyset$ on
$\\{{\sim\\!p}\\}$ and $\\{{\sim\\!q}\\}$ we also need [RBC].

Note that in this case $\\{p,q\\}$ is the stable model of $\pi_{2}$
(Definition 7) and $\emptyset$ is the stable extension of ${\sf ABF}(\pi_{2})$
(Definition 4).

###### Example 4

Logic programs and their induced ABFs from earlier examples are the following:

  * a)

The assumption-based argumentation framework considered in Example 1 is
induced from the logic program $\\{{\sim\\!q}\rightarrow p\\}$.555In this case
$\mathfrak{L}_{\sf MP}$ is used instead of the extended logic $\mathfrak{L}$,
but as shown in [9, 10], for normal logic programs this representation is
sufficient for the correspondence between LPs and the induced ABA frameworks,
shown below.

  * b)

Figure 2 depicts (a fragment of) the graph of the assumption-based
argumentation framework that is induced by the logic program
$\pi_{1}=\\{{\sim\\!p}\rightarrow q\lor r\\}$ from Example 2. This framework
has two stable extensions: $\\{\sim\\!q,\sim\\!p\\}$ and
$\\{\sim\\!r,\sim\\!p\\}$.

$\\{{\sim\\!q},\>\sim\\!r,\>{\sim\\!p}\\}$$\\{{\sim\\!q},\>{\sim\\!p}\\}$$\\{{\sim\\!r},\>{\sim\\!p}\\}$$\\{{\sim\\!r}\\}$$\\{{\sim\\!q}\\}$
Figure 2: Attack diagrams for Examples 2 and 4

###### Definition 9

Let $\pi$ be a disjunctive logic program and let $\Theta\subseteq{\cal
A}(\pi)$. We denote:

  * •

${\lfloor\sim\\!\Theta\rfloor}=\Theta$ (Thus ${\lfloor\cdot\rfloor}$
eliminates the leading $\sim$ from the formulas in the set)

  * •

If $\Delta\subseteq\>\sim\\!{\cal A}(\pi)$ then $\underline{\Delta}={\cal
A}(\pi)\setminus{\lfloor\Delta\rfloor}$

  * •

If $\Delta\subseteq{\cal A}(\pi)$ then $\overline{\Delta}=\>\sim\\!({\cal
A}(\pi)\setminus\Delta$)

In other words, $\underline{\Delta}$ (respectively, $\overline{\Delta}$) takes
the complementary set of $\Delta$ and removes (respectively, adds) the
negation-as-failure operator from (respectively, to) the prefix of its
formulas.

###### Example 5

Consider again the program $\pi_{2}$ of Example 3, and let
$\Delta={\sim\\!{\cal A}}(\pi_{2})=\\{{\sim\\!p},{\sim\\!q\\}}$. Then
$\underline{\Delta}=\emptyset$ and $\overline{\emptyset}=\Delta$.

The semantic correspondence between a logic program and the induced ABF is
obtained by the following results:

  1. 1.

If $\Delta$ is a stable extension of ${\sf ABF}(\pi)$, then
$\underline{\Delta}$ is a stable model of $\pi$, and

  2. 2.

If $\Delta$ is a stable model of $\pi$, then $\overline{\Delta}$ is a stable
extension of ${\sf ABF}(\pi)$.

Before showing these results, we first provide some examples and notes
concerning related results.

###### Example 6

As noted in the introduction, Caminada and Schulz [9, 10] consider the
correspondence between ABA frameworks and normal logic programs. In our
notations, the ABF that they associate with a normal logic program $\pi$ is
${\sf ABF}_{{\sf Norm}}(\pi)={\langle{\mathfrak{L}}_{\sf MP},\pi,{\sim\\!{\cal
A}(\pi)},-\rangle}$ constructed as in Definition 8, except that
${\mathfrak{L}}_{\sf MP}$ is defined by Modus Ponens only.

  * a)

To see that ${\sf ABF}_{{\sf Norm}}$ is not adequate for disjunctive logic
programs, consider the program $\pi_{3}=\\{{\rightarrow p\lor q}\\}$. This
program has two stable models: $\\{p\\}$ and $\\{q\\}$. However, the only
stable extension of ${\sf ABF}_{{\sf Norm}}(\pi_{3})$ is
$\\{\sim\\!p,\sim\\!q\\}$. We can enforce $\\{\sim\\!p\\}$ and
$\\{\sim\\!q\\}$ being stable models by requiring that
$\pi_{3}\cup\\{\sim\\!p\\}\vdash q$ and $\pi_{3}\cup\\{\sim\\!q\\}\vdash p$.
For this, we need the resolution rule ${\sf[Res]}$.

  * b)

Adding only ${\sf[Res]}$ to ${\mathfrak{L}}_{\sf MP}$ (i.e, without [RBC]) as
the inference rules for the logic is yet not sufficient. To see this, consider
again the program $\pi_{2}$ from Example 3. Recall that $\\{p,q\\}$ is the
sole stable model of $\pi_{2}$. The attack graph of the ABF based on [MP] and
[Res] is shown in Figure 1(b), thus there is no stable extension in this case.

  * c)

Example 3 shows that for the ABF that is induced from $\pi_{2}$ according to
Definition 8 (using all the three inference rules considered at the beginning
of this section) the correspondence between the stable model of $\pi_{2}$ and
the stable extension of ${\sf ABF}(\pi_{2})$ is preserved and thus the
translation is adequate for $\pi_{2}$. This is not a coincidence, as indicated
before this example, and as we show in the next section.

###### Note 4

The translation in Definition 8 always gives rise to a so-called _flat_ ABF,
that is, an ABF for which there is no $\Delta\subseteq\Lambda$ and
$\psi\in\Lambda\setminus\Delta$ such that $\Gamma,\Delta\vdash\psi$. This is
shown in the following proposition:

###### Proposition 1

For every disjunctive logic program $\pi$ and the induced assumption-based
argumentation framework ${\sf
ABF}(\pi)={\langle\mathfrak{L},\Gamma,\Lambda,-\rangle}={\langle{\mathfrak{L}},\pi,\sim\\!{\cal
A}(\pi),-\rangle}$, if $\Delta\subseteq\Lambda$ and $\Gamma,\Delta\vdash\psi$,
then $\psi\not\in\Lambda\setminus\Delta$.

Proof. Since $\Lambda$ consists only of formulas of the form ${\sim\\!p}$, we
can restrict our attention to such formulas. Suppose that
$\Gamma,\Delta\vdash\psi$ for some $\Delta\subseteq\Lambda$. Since $\Lambda$
contains only formulas of the form ${\sim\\!p}$, and since $\Gamma=\pi$, then
by Note 2, if $\Gamma,\Delta\vdash\>\sim\\!p$, necessarily
$\sim\\!p\in\Delta$. $\Box$

###  3.2 Proof of Correctness

The correctness of the translation follows from Propositions 2 and 3 below.
First, we need some definitions and lemmas. In what follows ${\mathfrak{L}}$
denotes the logic defined in Section 3.1, and $\pi$ is an arbitrary
disjunctive logic program.

We start with the following soundness and completeness result.

###### Lemma 1

Let $\Delta$ be a set of ${\mathcal{L}}$-formulas of the form ${\sim\\!p}$ or
$q_{1},\ldots,q_{m},{\sim\\!r_{1}},\ldots,{\sim\\!r_{k}}\rightarrow
p_{1}\lor\ldots\lor p_{n}$. Then:

  * a)

If $\psi\in{\sf Cn}_{\mathfrak{L}}(\Delta)$ then $M\models\psi$ for every $M$
such that $M\models\Delta$.

  * b)

If $\psi=r_{1}\lor\ldots\lor r_{m}$ and $M\models\psi$ for every $M$ such that
$M\models\Delta$, then $\psi\in{\sf Cn}_{\mathfrak{L}}(\Delta)$.

###### Note 5

Part (b) of Lemma 1 does not hold for any formula $\psi$, but only for a
disjunction of atoms. To see this, let $\Delta=\\{{\sim\\!s},\>{p\rightarrow
s}\\}$. The only $M\subseteq\\{p,s\\}$ such that $M\models\Delta$ is
$M=\emptyset$. Thus, for every $M$ such that $M\models\Delta$ it holds that
$M\models\>\sim\\!p$. However, $\sim\\!p$ cannot be derived from $\Delta$
using ${\sf[MP]}$, ${\sf[Res]}$ and ${\sf[RBC]}$.

Proof. We prove Part (a) of the lemma by induction on the number of
applications of the inference rules in the derivation of $\psi\in{\sf
Cn}_{\mathfrak{L}}(\Delta)$.

For the base step, no inference rule is applied in the derivation of $\psi$,
thus $\psi\in\Delta$. Since $M\models\Delta$, we have that $M\models\psi$.

For the induction step, we consider three cases, each one corresponds to an
application of a different inference rule in the last step of the derivation
of $\psi$:

  1. 1.

Suppose that the last step in the derivation of $\psi$ is an application of
Resolution. Then $\psi=p^{\prime}_{1}\vee\ldots\vee
p^{\prime}_{m}\vee\ldots\vee p^{\prime\prime}_{1}\vee\ldots\vee
p^{\prime\prime}_{k}$ is obtained by [Res] from $p^{\prime}_{1}\vee\ldots\vee
p^{\prime}_{m}\vee q_{1}\vee\ldots\vee q_{n}\vee
p^{\prime\prime}_{1}\vee\ldots\vee p^{\prime\prime}_{k}$ and ${\sim\\!q_{i}}$
$(i=1,\ldots,n)$. Suppose that $M\models\Delta$. Since ${\sim\\!q_{i}}\in{\sf
Cn}_{\mathfrak{L}}(\Delta)$ iff ${\sim\\!q_{i}}\in\Delta$ and since
$M\models\Delta$, we have $M\models{\sim\\!q_{i}}$ $(i=1,\ldots,n)$, thus
$M\not\models q_{i}$ $(i=1,\ldots,n)$. By the induction hypothesis, $M\models
p^{\prime}_{1}\vee\ldots\vee p^{\prime}_{m}\vee q_{1}\vee\ldots\vee q_{n}\vee
p^{\prime\prime}_{1}\vee\ldots\vee p^{\prime\prime}_{k}$. By Definition 6,
then, $M\models p^{\prime}_{i}$ for some $1\leq i\leq m$, or $M\models
p^{\prime\prime}_{j}$ for some $1\leq j\leq k$. By Definition 6 again,
$M\models\psi$.

  2. 2.

Suppose that the last step in the derivation of $\psi$ is an application of
Reasoning by Cases, and let $M\models\Delta$. By induction hypothesis,
$M\models p_{1}\vee\ldots\vee p_{n}$, and $M\models\psi$ in case that
$M\models p_{j}$ for some $1\leq j\leq n$. But by Definition 6 the former
assumption means that there is some $1\leq j\leq n$ for which $M\models
p_{j}$, therefore $M\models\psi$.

  3. 3.

Suppose that the last step in the derivation of $\psi$ is an application of
Modus Ponens, and let $M\models\Delta$. By induction hypothesis $M\models
l_{i}$, where $l_{i}\in\\{p_{i},{\sim\\!p_{i}}\\}$ for $i=1,\ldots,n$. Thus,
by Definition 6, $M\models l_{1},\ldots,l_{n}$. On the other hand, by
induction hypothesis again, $M\models l_{1},\ldots,l_{n}\rightarrow\psi$. By
Definition 6 this is possible only if $M\models\psi$.

We now turn to Part (b) of the lemma. Suppose that $M\models\psi$ for every
$M$ such that $M\models\Delta$, yet $\psi\not\in{\sf
Cn}_{\mathfrak{L}}(\Delta)$ (where $\psi=r_{1}\lor\ldots\lor r_{m}$ for some
$m\geqslant 1$). We show that this leads to a contradiction by constructing an
$M^{\prime}$ for which $M^{\prime}\models\Delta$ but
$M^{\prime}\not\models\psi$. For this, we consider the following set of the
minimal disjunctions of a set of formulas ${\cal S}$:

${\sf MD}({\cal S})=\\{q_{1}\lor\ldots\lor q_{n}\in{\cal
S}\mid\not\exists\\{i_{1},\ldots,i_{m}\\}\subsetneq\\{1,\ldots,n\\}\text{ s.t.
}q_{i_{1}}\lor\ldots\lor q_{i_{m}}\in{\cal S}\\}.$

We first show that if $q_{1}\lor\ldots\lor q_{n}\in{\sf MD}({\sf
Cn}_{\mathfrak{L}}(\Delta))$ then there is an $1\leqslant i\leqslant n$ such
that $q_{i}\not\in\\{r_{1},\ldots,r_{m}\\}$ and ${\sim\\!q_{i}}\not\in\Delta$.
Indeed, suppose first for a contradiction that $q_{1}\lor\ldots\lor
q_{n}\in{\sf MD}({\sf Cn}_{\mathfrak{L}}(\Delta))$, yet for every
$1<i\leqslant n$ either $q_{i}\in\\{r_{1},\ldots,r_{m}\\}$ or
${\sim\\!q_{i}}\in\Delta$. In that case, by ${{\sf[Res]}}$,
$r_{1}\lor\ldots\lor r_{m}\in{\sf Cn}_{\mathfrak{L}}(\Delta)$, contradicting
the original supposition that $r_{1}\lor\ldots\lor r_{m}\not\in{\sf
Cn}_{\mathfrak{L}}(\Delta)$. Suppose now, again towards a contradiction, that
$q_{1}\lor\ldots\lor q_{n}\in{\sf MD}({\sf Cn}_{\mathfrak{L}}(\Delta))$, yet
for every $1\leqslant i\leqslant n$, ${\sim\\!q_{i}}\in\Delta$. In that case,
by ${{\sf[Res]}}$ again, $q_{i}\in{\sf Cn}_{\mathfrak{L}}(\Delta)$ (for every
$i$), but this, together with the assumption the $\sim\\!q_{i}\in\Delta$ (for
every $i$), contradicts the assumption that there is an $M$ such that
$M\models\Delta$.

We thus showed that in any case, if $q_{1}\lor\ldots\lor q_{n}\in{\sf MD}({\sf
Cn}_{\mathfrak{L}}(\Delta))$, then there is an $1\leqslant i\leqslant n$ such
that $q_{i}\not\in\\{r_{1},\ldots,r_{m}\\}$ and $\sim\\!q_{i}\not\in\Delta$.

We now construct the model $M^{\prime}$ such that $M^{\prime}\models\Delta$
and $M^{\prime}\not\models r_{1}\lor\ldots\lor r_{m}$: Let $M^{\prime}$
contain exactly one $q_{i}$ with $1\leqslant i\leqslant n$ and
$q_{i}\not\in\\{r_{1},\ldots,r_{m}\\}$ and ${\sim\\!q_{i}}\not\in\Delta$ for
every $q_{1}\lor\ldots\lor q_{n}\in{\sf MD}({\sf Cn}_{\mathfrak{L}}(\Delta))$.
(If there is more than one such $i$, take $i$ which is minimal among
$1\leqslant i\leqslant n$.) As shown above, there is at least one such $i$ for
every formula $q_{1}\lor\ldots\lor q_{n}\in{\sf MD}({\sf
Cn}_{\mathfrak{L}}(\Delta))$.

We now show that (1) $M^{\prime}\models\Delta$ and (2) $M^{\prime}\not\models
r_{1}\lor\ldots\lor r_{m}$.

Item (1): Suppose that $\phi\in{\sf Cn}_{\mathfrak{L}}(\Delta)$. We have to
consider two possibilities: $\phi={\sim\\!s}$ or $\phi=q_{1}\lor\ldots\lor
q_{n}$. In the first case, by construction, $s\not\in M^{\prime}$ and thus
$M^{\prime}\models\>\sim\\!s$. In the second case, there is a
$q_{i_{1}}\lor\ldots\lor q_{i_{m}}\in{\sf MD}({\sf
Cn}_{\mathfrak{L}}(\Delta))$ such that
$\\{i_{1},\ldots,i_{m}\\}\subseteq\\{1,\ldots,n\\}$. By construction, there is
a $1\leqslant j\leqslant m$ such that $q_{i_{j}}\in M^{\prime}$. Thus,
$M\models q_{1}\lor\ldots\lor q_{n}$.

Item (2): By construction $r_{i}\not\in M^{\prime}$ $(i=1,\ldots,m)$, thus
$M^{\prime}\not\models r_{1}\lor\ldots\lor r_{m}$. $\Box$

###### Lemma 2

Let $\pi$ be a logic program. For every sets $M,N\subseteq{\cal A}(\pi)$, if
$N\setminus M\neq\emptyset$ then $N\not\models{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$.

Proof. Suppose that $N\setminus M\neq\emptyset$ and let $p\in N\setminus M$,
Then ${\sim\\!p}\in\overline{M}$ and thus ${\sim\\!p}\in{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. Since $N\models p$,
$N\not\models{\sim\\!p}$, and so $N\not\models{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. $\Box$

###### Lemma 3

Given a logic program $\pi$, if $M$ is a minimal model of a logic program
$\pi^{\prime}\subseteq\pi^{M}$, then for every $N\subset M$, $N\not\models{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$.

Proof. Let $\pi$ be a logic program and let $M$ be a minimal model of a logic
program $\pi^{\prime}\subseteq\pi^{M}$. We prove the lemma by induction on the
size of $M$. If $M=\emptyset$ the lemma trivially holds. Suppose now that the
lemma holds for every $N\subset M$ (i.e., for every such $N$, if
$N^{\prime}\subset N$ and $N^{\prime}$ is a minimal model of
$\pi^{\prime\prime}\subseteq\pi^{N}$, then $N^{\prime}\not\models{\sf
Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$), and assume towards a contradiction
that $N\subset M$ and $N\models{\sf Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$.

Since $M$ is a minimal model of $\pi^{\prime}\subseteq\pi^{M}$, there is a
some $p_{1},\ldots,p_{n}\rightarrow r_{1}\lor\ldots\lor r_{m}\in\pi^{\prime}$
s.t. $p_{i}\in N$ for every $1\leqslant i\leqslant n$ and $N\not\models
r_{1}\lor\ldots\lor r_{m}$. Let $\pi_{N}\subseteq\pi^{N}$ be the set of rules
in $\pi^{N}$ that are satisfied by $N$.

Suppose first that $N$ is a minimal model of $\pi_{N}$. Then, on one hand, by
the inductive hypothesis, there is no $N^{\prime}\subset N$ s.t.
$N^{\prime}\models{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$, and on the
other hand if there is some $N^{\prime}\subseteq{\cal A}(\pi)$ with
$N^{\prime}\not\subset N$, i.e. $N^{\prime}\setminus N\neq\emptyset$, then by
Lemma 2, $N^{\prime}\not\models{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$.
It thus follows that $N$ is the unique set of atoms such that $N\models{\sf
Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$. Now, by Lemma 1, this means that for
every $q$ it holds that $N\models q$ iff $q\in{\sf
Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$ (Indeed, the fact that $N\models q$
implies $q\in{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$ follows by Part (b)
of Lemma 1 and the uniqueness of $N$ established above, and the fact that
$q\in{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$ implies $N\models q$
follows by Part (a) of Lemma 1). Thus, $p_{i}\in{\sf
Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$. Since $p_{1},\ldots,p_{n}\rightarrow
r_{1}\lor\ldots\lor r_{m}\in\pi^{\prime}$, we have that
$p_{1},\ldots,p_{n},{\sim\\!q_{1}},\ldots,{\sim\\!q_{k}}\rightarrow
r_{1}\lor\ldots\lor r_{m}\in\pi$ (for some $q_{1},\ldots,q_{k}\in{\cal
A}(\pi)$). Notice that since $q_{i}\not\in M$ for any $1\leqslant i\leqslant
k$ and $N\subset M$, $q_{i}\not\in N$ for any $1\leqslant i\leqslant k$, and
so ${\sim\\!q_{i}}\in\overline{N}$ for any $1\leqslant i\leqslant k$. Hence,
$r_{1}\lor\ldots\lor r_{m}\in{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$ by
[MP]. Thus, $N\models r_{i}$ for some $1\leqslant i\leqslant m$, which
contradicts the assumption that $N\not\models r_{1}\lor\ldots\lor r_{m}$.

Suppose now that there is some $N^{\prime}\subset N$ that satisfies $\pi_{N}$.
Let $N^{\prime}$ be a minimal such model. By Lemma 2,
$N^{\prime}\not\models{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$. Let $p\in
N\setminus N^{\prime}$. Suppose first that $p\in\\{p_{1},\ldots,p_{n}\\}$. In
that case $N^{\prime}$ would trivially satisfy $p_{1},\ldots,p_{n}\rightarrow
r_{1}\lor\ldots\lor r_{m}\in\pi$. Since $M$ is the minimal model of
$\pi^{\prime}$, this means that: ($\dagger$) There is some
$s_{1},\ldots,s_{n^{\prime}}\rightarrow t_{1}\lor\ldots\lor
t_{m^{\prime}}\in\pi^{\prime}$ s.t. $N^{\prime}\models s_{i}$ for every
$1\leqslant i\leqslant n^{\prime}$, $N^{\prime}\not\models t_{i}$ for any
$1\leqslant i\leqslant m^{\prime}$ and $p_{1},\ldots,p_{n}\rightarrow
r_{1}\lor\ldots\lor r_{m}$ is different than
$s_{1},\ldots,s_{n^{\prime}}\rightarrow t_{1}\lor\ldots\lor t_{m^{\prime}}$.

Now, since $s_{1},\ldots,s_{n^{\prime}}\rightarrow t_{1}\lor\ldots\lor
t_{m^{\prime}}\in\pi^{\prime}$, there is some
$s_{1},\ldots,s_{n^{\prime}},{\sim\\!u_{1}},\ldots,{\sim\\!u_{k^{\prime}}}\rightarrow
t_{1}\lor\ldots\lor t_{m^{\prime}}\in\pi$ s.t. $u_{i}\not\in M$ for every
$1\leqslant i\leqslant k^{\prime}$. Since $N^{\prime}\subset M$, $u_{i}\not\in
N^{\prime}$ for every $1\leqslant i\leqslant k^{\prime}$ and so
${\sim\\!u_{i}}\in\overline{N^{\prime}}$ for every $1\leqslant i\leqslant
k^{\prime}$. By the inductive hypothesis, $N^{\prime}$ is the unique set of
literals s.t. $N^{\prime}\models{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$
and thus by Part (b) of Lemma 1, $s_{1},\ldots,s_{n^{\prime}}\in{\sf
Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$ (since $N^{\prime}\models s_{i}$ for
every $1\leqslant i\leqslant n^{\prime}$ and $N^{\prime}$ is the unique set of
atoms s.t. $N^{\prime}\models{\sf Cn}_{\mathfrak{L}}(\overline{N}\cup\pi)$).
But then by [MP], $t_{1}\lor\ldots\lor t_{m^{\prime}}\in{\sf
Cn}_{\mathfrak{L}}(\overline{N^{\prime}}\cup\pi)$, which means that
$N^{\prime}\models t_{1}\lor\ldots\lor t_{m^{\prime}}$. This contradicts
($\dagger$).

Suppose now that $N^{\prime}\models p_{i}$ for every $1\leqslant i\leqslant
n$. As shown previously in the proof, by the inductive hypothesis and Lemma 2,
$N^{\prime}$ is the unique set of literals s.t. $N^{\prime}\models{\sf
Cn}_{\mathfrak{L}}(\overline{N^{\prime}}\cup\pi)$. Again, as before, by Lemma
1, this means that $N^{\prime}\models q$ iff $q\in{\sf
Cn}_{\mathfrak{L}}(\overline{N^{\prime}}\cup\pi)$. Since
$p_{1},\ldots,p_{n}\rightarrow r_{1}\lor\ldots\lor r_{m}\in\pi^{M}$, there are
$q_{1}\ldots q_{k}\in{\cal A}(\pi)$ for which
$p_{1},\ldots,p_{n},\sim\\!q_{1},\ldots,\sim\\!q_{k}\rightarrow
r_{1}\lor\ldots\lor r_{m}\in\pi$. Since $q_{i}\not\in M$ for any $1\leqslant
i\leqslant k$ and $N^{\prime}\subset M$, necessarily $q_{i}\not\in N^{\prime}$
for any $1\leqslant i\leqslant k$, and so
${\sim\\!q_{i}}\in\overline{N^{\prime}}$ for any $1\leqslant i\leqslant k$. By
[MP], $r_{1}\lor\ldots\lor r_{m}\in{\sf
Cn}_{\mathfrak{L}}(\overline{N^{\prime}}\cup\pi)$ . Thus, $N^{\prime}\models
r_{i}$ for some $1\leqslant i\leqslant m$. Since $N^{\prime}\subset N$ (and
$N^{\prime}\models r_{i}$ implies that $r_{i}\in N^{\prime}$), $N\models
r_{i}$. This again contradicts the assumption that $N\not\models
r_{1}\lor\ldots\lor r_{m}$. $\Box$

###### Lemma 4

Let $M$ be a stable model of $\pi$. Then $M=\min_{\subseteq}\\{N\subseteq{\cal
A}(\pi)\mid N\models{\sf Cn}_{\mathfrak{L}}(\pi\cup\overline{M})\\}$.

Proof. Let $M$ be a stable model of $\pi$. We first show that $M\models{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. Let $\psi\in{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. Then it has an
${\mathfrak{L}}$-derivation ${\sf D}_{\mathfrak{L}}(\psi)$. We show by
induction on the size of ${\sf D}_{\mathfrak{L}}(\psi)$ that $M\models\psi$.

For the base step, no inference rule is applied in ${\sf
D}_{\mathfrak{L}}(\psi)$, thus $\psi={\sim\\!\phi}\in\overline{M}$. Since this
means that $\phi\not\in M$, we have that $M\models\psi$.

For the induction step, we consider three cases, each one corresponds to an
application of a different inference rule in the last step of ${\sf
D}_{\mathfrak{L}}(\psi)$:

  1. 1.

Suppose that the last step in ${\sf D}_{\mathfrak{L}}(\psi)$ is an application
of Resolution. Then $\psi=p^{\prime}_{1}\vee\ldots\vee
p^{\prime}_{m}\vee\ldots\vee p^{\prime\prime}_{1}\vee\ldots\vee
p^{\prime\prime}_{k}$ is obtained by [Res] from $p^{\prime}_{1}\vee\ldots\vee
p^{\prime}_{m}\vee q_{1}\vee\ldots\vee q_{n}\vee
p^{\prime\prime}_{1}\vee\ldots\vee p^{\prime\prime}_{k}$ and ${\sim\\!q_{i}}$
$(i=1,\ldots,n)$. Since ${\sim\\!q_{i}}\in{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$ means that
${\sim\\!q_{i}}\in\overline{M}$, we have $q_{i}\not\in M$ for every
$i=1,\ldots,n$. By the induction hypothesis, $M\models
p^{\prime}_{1}\vee\ldots\vee p^{\prime}_{m}\vee q_{1}\vee\ldots\vee q_{n}\vee
p^{\prime\prime}_{1}\vee\ldots\vee p^{\prime\prime}_{k}$. Thus, by Definition
6, $M\models p^{\prime}_{i}$ for some $1\leq i\leq m$, or $M\models
p^{\prime\prime}_{j}$ for some $1\leq j\leq k$. By Definition 6 again,
$M\models\psi$.

  2. 2.

Suppose that the last step in ${\sf D}_{\mathfrak{L}}(\psi)$ is an application
of Reasoning by Cases. By induction hypothesis we know that $M\models
p_{1}\vee\ldots\vee p_{n}$, and that $M\models\psi$ in case that $M\models
p_{j}$ for some $1\leq j\leq n$. But by Definition 6 the former assumption
means that there is some $1\leq j\leq n$ for which $M\models p_{j}$, therefore
$M\models\psi$.

  3. 3.

Suppose that the last step in ${\sf D}_{\mathfrak{L}}(\psi)$ is an application
of Modus Ponens on
$p_{1},\ldots,p_{n},{\sim\\!q_{1}},\ldots,{\sim\\!q_{m}}\allowbreak\rightarrow
r_{1}\lor\ldots\lor r_{k}\in\pi$. By induction hypothesis $M\models p_{i}$,
for every $1\leqslant i\leqslant n$. Also, for every $1\leqslant i\leqslant
m$, ${\sim\\!q_{i}}\in{\sf Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$ implies
$q_{i}\not\in M$. Thus, $p_{1},\ldots,p_{n}\rightarrow r_{1}\lor\ldots\lor
r_{l}\in\pi^{M}$. Since $M$ is a model of $\pi^{M}$, $M\models r_{i}$ for some
$1\leqslant i\leqslant k$. Thus, $M\models r_{1}\lor\ldots\lor r_{k}$.

We have shown that $M\models{\sf Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. By
Lemma 2, for no $N\subseteq{\cal A}(\pi)$ such that $N\setminus
M\neq\emptyset$ it holds that $N\models{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. Thus, if there is some
$N\subseteq{\cal A}(\pi)$ such that $N\models
Cn_{\mathfrak{L}}(\overline{M}\cup\pi)$, then $N\subseteq M$. But if $N\subset
M$, by Lemma 3 we have that $N\not\models{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. Thus, $M$ is the unique subset of
${\cal A}(\pi)$ which is a model of ${\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. $\Box$

###### Corollary 1

Let $M$ be a stable model of $\pi$. Then $p\in M$ iff $p\in{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$.

Proof. Suppose first that $p\in M$. Thus $M\models p$. Since by Lemma 4 $M$ is
the unique model of ${\sf Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$, by Lemma 1
it holds that $M\models p$ implies that $p\in{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. For the converse, suppose that
$p\in{\sf Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$. By Lemma 4, $M\models{\sf
Cn}_{\mathfrak{L}}(\overline{M}\cup\pi)$, and so $M\models p$. $\Box$

###### Lemma 5

Let $\pi$ be a disjunctive logic program, $\Delta\subseteq{\sim\\!{\cal
A}}(\pi)$, and $r_{1}\lor\ldots\lor r_{k}\in{\sf
Cn}_{\mathfrak{L}}(\pi\cup\Delta)$. If $M$ is a model of
$\pi^{{\lfloor\Delta\rfloor}}$ and $M\subseteq{\lfloor\Delta\rfloor}$, then
$r_{i}\in M$ for some $1\leqslant i\leqslant k$.

Proof. We show by induction on the number of steps used in deriving
$r_{1}\lor\ldots\lor r_{k}$ from $\pi\cup\Delta$, that $r_{1}\lor\ldots\lor
r_{k}\in{\sf Cn}_{\mathfrak{L}}(\pi\cup\Delta)$ implies that $M\models
r_{1}\lor\ldots\lor r_{k}$. This means that $M\models r_{i}$ for some
$1\leqslant i\leqslant k$, and so $r_{i}\in M$ for that $i$.

For the base step, since every element of $\Delta$ is of the form
${\sim\\!p}$, we have that $r_{1}\lor\ldots\lor r_{k}\not\in\Delta$. Thus,
$r_{1}\lor\ldots\lor r_{k}$ is obtained from some rule
${\sim\\!q_{1}},\ldots,{\sim\\!q_{m}}\rightarrow r_{1}\lor\ldots\lor
r_{k}\in\pi$, where ${\sim\\!q_{1}},\ldots,{\sim\\!q_{m}}\in\Delta$. In that
case, since (1) $M\subseteq\underline{\Delta}$; (2) $M$ is a model of
$\pi^{{\lfloor\Delta\rfloor}}$; and (3) $\rightarrow r_{1}\lor\ldots\lor
r_{k}\in\pi^{{\lfloor\Delta\rfloor}}$, by Definition 7 there is a $1\leqslant
i\leqslant l$ such that $r_{i}\in M$.

For the induction step, suppose that the claim holds for every
$r_{1}\lor\ldots\lor r_{k}$ that is derived from $\Delta$ using $n$ or less
derivation steps. We consider three cases:

  * •

$r_{1}\lor\ldots\lor r_{k}$ is obtained by applying [MP] to the rule
$p_{1},\ldots,p_{n},{\sim\\!q_{1}},\ldots,{\sim\\!q_{m}}\rightarrow
r_{1}\lor\ldots\lor r_{k}$. In this case,
${\sim\\!q_{1}},\ldots,{\sim\\!q_{m}}\in\Delta$ and so
$q_{i}\not\in\underline{\Delta}$ for any $1\leqslant i\leqslant m$. It follows
that $p_{1},\ldots,p_{n}\rightarrow r_{1}\lor\ldots\lor
r_{k}\in\pi^{{\lfloor\Delta\rfloor}}$. Let now $M$ be a model of
$\pi^{{\lfloor\Delta\rfloor}}$ such that $M\subseteq{\lfloor\Delta\rfloor}$.
By the induction hypothesis, $p_{i}\in{\sf Cn}_{\mathfrak{L}}(\pi\cup\Delta)$
implies that $p_{i}\in M$ (for every $1\leqslant i\leqslant n$). Thus, since
$M$ is a model of $\pi^{{\lfloor\Delta\rfloor}}$, $r_{i}\in M$ for some
$1\leqslant i\leqslant l$.

  * •

$r_{1}\lor\ldots\lor r_{k}$ is obtained by applying [Res] from
$r_{1}\lor\ldots\lor r_{k}\lor r_{k+1}\lor\ldots r_{n}$ and
${\sim\\!r}_{k+1},\ldots,{\sim\\!r}_{n}$. Suppose furthermore that
$M\subseteq{\lfloor\Delta\rfloor}$ is a model of
$\pi^{{\lfloor\Delta\rfloor}}$. By the induction hypothesis and since
$r_{1}\lor\ldots\lor r_{k}\lor r_{k+1}\lor\ldots r_{n}\in{\sf
Cn}_{\mathfrak{L}}(\pi\cup\Delta)$, we have that $r_{i}\in M$ for some
$1\leqslant i\leqslant n$. Since $\sim\\!r_{i}\in\Delta$ for $k+1\leqslant
i\leqslant n$ and $M\subseteq{\lfloor\Delta\rfloor}$, $r_{i}\not\in M$ for
every $k+1\leqslant i\leqslant n$. This means that $r_{i}\in M$ for some
$1\leqslant i\leqslant k$.

  * •

$r_{1}\lor\ldots\lor r_{k}$ is obtained by applying [RBC], since
$s_{1}\lor\ldots\lor s_{n}\in{\sf Cn}_{\mathfrak{L}}(\pi\cup\Delta)$ and since
$r_{1}\lor\ldots\lor r_{k}\in{\sf Cn}_{\mathfrak{L}}(\pi\cup{\\{\rightarrow
s_{i}\\}}\cup\Delta)$ for every $1\leqslant i\leqslant n$. By the induction
hypothesis, ($\dagger$): for every $1\leqslant i\leqslant n$ and every model
$M^{\prime}$ of $(\pi\cup{\\{\rightarrow s_{i}\\}})^{{\lfloor\Delta\rfloor}}$
such that $M^{\prime}\subseteq\underline{\Delta}$, we have that
$r_{1}\lor\ldots\lor r_{k}\in{\sf Cn}_{\mathfrak{L}}(\pi\cup{\\{\rightarrow
s_{i}\\}}\cup\Delta)$ implies $r_{i}\in M^{\prime}$ for some $1\leqslant
i\leqslant k$. Now, since $s_{1}\lor\ldots\lor s_{n}\in{\sf
Cn}_{\mathfrak{L}}(\pi\cup\Delta)$, by the induction hypothesis this means
that $s_{j}\in M$ for some $1\leqslant j\leqslant n$ for every model $M$ of
$\pi^{{\lfloor\Delta\rfloor}}$. In other words, $M$ is a model of
$\pi^{{\lfloor\Delta\rfloor}}$ iff it is a model of $(\pi\cup\\{\rightarrow
s_{j}\\})^{{\lfloor\Delta\rfloor}}=\pi^{{\lfloor\Delta\rfloor}}\cup\\{\rightarrow
s_{j}\\}$ for some $1\leqslant j\leqslant n$. By $(\dagger)$, then, $r_{i}\in
M$ for some $1\leqslant i\leqslant k$. $\Box$

By the last lemma, in case that $k=1$, we therefore have:

###### Corollary 2

Let $\pi$ be a disjunctive logic program and
$\Delta\subseteq{\mathfrak{L}}(\pi\cup\Delta)$. If $M$ is a model of
$\pi^{{\lfloor\Delta\rfloor}}$ and $M\subseteq{\lfloor\Delta\rfloor}$, then
$r\in M$.

Now we can show the main results of this section.

###### Proposition 2

If $M$ is a stable model of $\pi$, then $\overline{M}$ is a stable extension
of ${\sf ABF}(\pi)$.

Proof. Suppose that $M$ is a stable model of $\pi$. We show first that
$\overline{M}$ is conflict-free in ${\sf ABF}(\pi)$. Otherwise, there is some
$\sim\\!p\in\overline{M}$ such that $\overline{M}\vdash p$. The former implies
that $p\not\in M$. But since $M$ is a model of $\pi^{M}$, by Corollary 2,
$\overline{M}\vdash p$ implies that $p\in M$, a contradiction to $p\not\in M$

We now show that $\overline{M}$ attacks every ${\sim\\!p}\in\>\sim\\!{\sf
Atom}(\pi)\setminus\overline{M}$. This means that we have to show that
$\overline{M}\vdash p$ for every $p\in M$. This follows from Corollary 1.
$\Box$

###### Proposition 3

If ${\cal E}$ is a stable extension of ${\sf ABF}(\pi)$, then
$\underline{{\cal E}}$ is a stable model of $\pi$.

Proof. We first show that $\underline{{\cal E}}$ is a model of
$\pi^{\underline{{\cal E}}}$. Indeed, let
$p_{1},\ldots,p_{n},\sim\\!q_{1},\ldots,\sim\\!q_{m}\rightarrow
r_{1}\lor\ldots\lor r_{k}\in\pi$. If $q_{j}\in\underline{{\cal E}}$ for some
$1\leq j\leq m$ we are done. Otherwise,
$q_{1},\ldots,q_{m}\not\in\underline{{\cal E}}$, and so
$p_{1},\ldots,p_{n}\rightarrow r_{1}\lor\ldots\lor
r_{k}\in\pi^{\underline{{\cal E}}}$. Again, if $p_{j}\not\in\underline{{\cal
E}}$ for some $1\leq j\leq n$ we are done. Thus,
$p_{1},\ldots,p_{n}\in\underline{{\cal E}}$. In other words,
${\sim\\!p_{1}},\ldots,{\sim\\!p_{n}}\not\in{\cal E}$ and
${\sim\\!q_{1}},\ldots,{\sim\\!q_{m}}\in{\cal E}$. Since ${\cal E}$ is a
stable extension of ${\sf ABF}(\pi)$, this means that ${\cal E}\vdash
r_{1}\lor\ldots\lor r_{k}$. Suppose now for a contradiction that
${\sim\\!r_{i}}\in{\cal E}$ for every $1\leqslant i\leqslant k$. Then by
[Res], ${\cal E}\vdash r_{i}$ for every $1\leqslant i\leqslant k$ and thus
${\cal E}$ attack itself, which contradicts the fact that ${\cal E}$ is
conflict-free. Consequently, there is at least one $1\leqslant i\leqslant k$
such that ${\sim\\!r_{i}}\not\in{\cal E}$, thus $r_{i}\in\underline{{\cal
E}}$, which means that $\underline{{\cal E}}$ satisfies
$p_{1},\ldots,p_{n}\sim\\!q_{1},\ldots,\sim\\!q_{m}\rightarrow
r_{1}\lor\ldots\lor r_{k}$.

To show the minimality of $\underline{{\cal E}}$, suppose that there is an
$M\subsetneq\underline{{\cal E}}$ that is a model of $\pi^{\underline{{\cal
E}}}$. Let $p\in\underline{{\cal E}}\setminus M$. Since $p\in\underline{{\cal
E}}$, ${\sim\\!p}\not\in{\cal E}$. Since ${\cal E}$ is stable, this means that
${\cal E}\vdash p$. By Corollary 2, any model of $\pi^{\underline{{\cal E}}}$
satisfies $p$, a contradiction to $p\not\in M$. $\Box$

##  4 From ABA to DLP

The main body of literature on ABA frameworks is concentrated on languages
that consist solely of formulas of the form $p_{1},\ldots,p_{n}\rightarrow p$
(where $p,p_{1},\ldots,p_{n}$ are atomic formulas). For such assumption-based
frameworks (or at least when the frameworks are flat) it has been shown that
there is a straightforward translation into normal logic programs that
preserve equivalence for all the commonly studied argumentation semantics (see
[9, 10]). To the best of our knowledge, the more complicated classes of ABA
frameworks that are considered in this paper for characterizing disjunctive
logic programming (and which are based on a logic allowing to reason with
disjunctive rules of the form
$p_{1},\ldots,p_{n},{\sim\\!q}_{1},\ldots,{\sim\\!q}_{m}\rightarrow
r_{1}\lor\ldots\lor r_{k}$) have not been investigated for other purposes
other than the translation of DLPs. We thus do not see any motivation for
investigating the reverse translation from these assumption-based frameworks
into disjunctive logic programs. We do believe, however, that it is
interesting to see if the more general class of assumption-based frameworks
based on an arbitrary propositional logic (as defined and studied in [1, 2,
26]) can be translated in a class of logic programs, probably more general
than disjunctive ones. This is a subject for a future work.

##  5 Beyond Two-Valued Stable Semantics

So far we have discussed two-valued stable models for (disjunctive) logic
programs and their correspondence to the stable extensions of the induced ABA
frameworks. In this section we check whether similar correspondence may be
established between other semantics of logic programs, such as three-valued
stable semantics, and other types of argumentative extensions.

For switching to a 3-valued semantics we add to the two propositional
constants ${\sf T}$ and ${\sf F}$, representing in the language ${\cal L}$ the
Boolean values, a third elements, denoted ${\sf U}$, which intuitively
represents uncertainty. These constants correspond, respectively, to the three
truth values of the underlying semantics, ${\sf t}$, ${\sf f}$, ${\sf u}$,
representing true, false and unknown values. As in Kleene’s semantics [27],
these values may be arranged in two orders:

  * •

a total order $\leq_{t}$, representing difference in the amount of truth that
each value represent, in which ${\sf f}<_{t}{\sf u}<_{t}{\sf t}$, and

  * •

a partial order $\leq_{i}$, representing difference in the amount of
information that each value depicts, in which ${\sf u}<_{i}{\sf f}$ and ${\sf
u}<_{i}{\sf t}$.

In what follows, we denote by $-$ the $\leq_{t}$-involution, namely $-{\sf
f}={\sf t},$-t = f, and $-{\sf u}={\sf u}$.

Accordingly, we extend the notion of interpretations of a logic program $\pi$
from subsets of ${\cal A}(\pi)$ (as in Definition 6) to pairs of subsets of
${\cal A}(\pi)$: A three-valued interpretation of a program $\pi$ is a pair
$M=(x,y)$, where $x\subseteq{\cal A}(\pi)$ is the set of the atoms that are
assigned the value ${\sf t}$ and $y\subseteq{\cal A}(\pi)$ is the set of atoms
assigned a value in $\\{{\sf t},{\sf u}\\}$. Clearly, in every such
interpretation it holds that $x\subseteq y$, and the $\\{{\sf t},{\sf
f}\\}$-valued interpretations of the previous sections may be viewed as three-
valued interpretations in which $x=y$.

Interpretations may be compared by two order relations, generalized from the
order relations among the truth values:

  1. 1.

the _truth order_ $\leq_{t}$, where $(x_{1},y_{1})\leq_{t}(x_{2},y_{2})$ iff
$x_{1}\subseteq x_{2}$ and $y_{1}\subseteq y_{2}$, and

  2. 2.

the _information order_ $\leq_{i}$, where $(x_{1},y_{1})\leq_{i}(x_{2},y_{1})$
iff $x_{1}\subseteq x_{2}$ and $y_{2}\subseteq y_{1}$.

The information order represents differences in the “precisions” of the
interpretations. Thus, the components of higher values according to this order
represent tighter evaluations. The truth order represents increased ‘positive’
evaluations. Truth assignments to complex formulas are then recursively
defined as in the next definition:

###### Definition 10

The truth assignments of a 3-valued interpretation $(x,y)$ are defined as
follows:

  * •

$(x,y)(p)=\begin{cases}{\sf t}&\text{ if }{p}\in x\text{ and }{p}\in y,\\\
{\sf u}&\text{ if }{p}\not\in x\text{ and }{p}\in y,\\\ {\sf f}&\text{ if
}{p}\not\in x\text{ and }{p}\not\in y,\\\ \end{cases}$

  * •

$(x,y)(\sim\\!\phi)=-(x,y)(\phi)$,

  * •

$(x,y)(\psi\land\phi)=lub_{\leq_{t}}\\{(x,y)(\phi),(x,y)(\psi)\\}$,

  * •

$(x,y)(\psi\lor\phi)=glb_{\leq_{t}}\\{(x,y)(\phi),(x,y)(\psi)\\}$.

The next definition is the three-valued counterpart of Definitions 6 and 7.

###### Definition 11

Let $\pi$ be a logic program and let $(x,y)$ be a 3-valued interpretation of
$\pi$.

  * •

$(x,y)$ is a _(3–valued) model_ of $\pi$, if for every
$\phi\rightarrow\psi\in\pi$, $(x,y)(\phi)\leq_{t}(x,y)(\psi)$.

  * •

The Gelfond-Lifschitz transformation [22] of a disjunctively normal dlp $\pi$
with respect to a 3-valued interpretation $(x,y)$, denoted $\pi^{(x,y)}$, is
the positive program obtained by replacing in every rule in $\pi$ of the form
$q_{1},\ldots,q_{m},{\sim\\!r_{1}},\ldots,{\sim\\!r_{k}}\rightarrow
p_{1}\lor\ldots\lor p_{n}$, any negated literal ${\sim\\!r_{i}}$ ($1\leq i\leq
k$) by: ${\sf F}$ if $(x,y)(r_{i})={\sf t}$, ${\sf T}$ if $(x,y)(r_{i})={\sf
f}$, and ${\sf U}$ if $(x,y)(r_{i})={\sf u}$. That is, replacing
${\sim\\!r_{i}}$ by the propositional constant that corresponds to
$(x,y)(\sim\\!r_{i})$.

  * •

An interpretation $(x,y)$ is a three-valued stable model of $\pi$, if it is a
$\leq_{t}$-minimal model of $\pi^{(x,y)}$.

Some specific types of 3-valued stable models are the following:

  * •

The well-founded models of $\pi$ are its $\leq_{i}$-minimal 3-valued stable
models [41].

  * •

The regular models of $\pi$ are its $\leq_{i}$-maximal 3-valued stable models
[19].

For normal logic programs, the well-founded model is guaranteed to exist and
be unique [30, 41].

###### Note 6

As shown in [37, 38], when $\pi$ is a normal logic program, its 3-valued
models considered above have some counterparts in terms of the induced
assumption-based argumentation framework ${\sf ABF}_{{\sf Norm}}(\pi)$,
described in Example 6. To recall these results, we first need to extend the
notions in Definition 4 with the following argumentative concepts:

###### Definition 12

Let ${\sf ABF}={\langle\mathfrak{L},\Gamma,\Lambda,-\rangle}$ be an
assumption-based framework and let $\Delta\subseteq\Lambda$. The set of all
the formulas in $\Lambda$ that are attacked by $\Delta$ is denoted by
$\Delta^{+}$, and the set of all the formulas in $\Lambda$ that are defended
by $\Delta$ (namely, the formulas whose attackers are in $\Delta^{+}$) is
denoted ${\sf Def}(\Delta)$. We say that $\Delta$ is a complete extension of
${\sf ABF}$, if it is conflict-free (Definition 4) and ${\sf
Def}(\Delta)=\Delta$ (namely, $\Delta$ defends exactly its own elements). A
$\subseteq$-maximally complete extension of ${\sf ABF}$ is called preferred
extension of ${\sf ABF}$, and a $\subseteq$-minimally complete extension of
${\sf ABF}$ is called grounded extension of ${\sf ABF}$.666Note that, using
the notations in Definition 12, $\Delta\subseteq\Lambda$ is a stable extension
of ${\sf ABF}$ according to Definition 4, iff $\Delta\cap\Delta^{+}=\emptyset$
(namely, $\Delta$ is conflict-free) and $\Delta\cup\Delta^{+}=\Lambda$.

In [37, 38] it was shown that the 3-valued stable models of a normal logic
program $\pi$ correspond to the complete extensions of ${\sf ABF}_{{\sf
Norm}}(\pi)$, the regular models of $\pi$ correspond to preferred extensions
of ${\sf ABF}_{{\sf Norm}}(\pi)$, and the well-founded model of $\pi$
corresponds to the grounded extension of ${\sf ABF}_{{\sf Norm}}(\pi)$. Using
the notations in Definition 9, these results can be expressed as follows:

  * •

If $(x,y)$ is a 3-valued stable (respectively: well-founded, regular) model of
a normal logic program $\pi$, then $\overline{y}$ is a complete (respectively:
preferred, grounded) extension of ${\sf ABF}_{{\sf Norm}}(\pi)$.

  * •

If ${\cal E}$ is a complete (respectively: preferred, grounded) extension of
${\sf ABF}_{{\sf Norm}}(\pi)$, where $\pi$ is a normal logic program, then
$({\lfloor{\cal E}^{+}\rfloor},\underline{{\cal E}})$ is a 3-valued stable
(respectively: well-founded, regular) model of $\pi$.

In other words, true atoms $p\in x$ on the LP-side correspond to attacked
negations of these atoms ${\sim\\!p}\in\overline{y}^{+}$ on the ABA-side,
whereas false atoms $p\in{\cal A}(\pi)\setminus y$ correspond to accepted
negations of these atoms ${\sim\\!p}\in\overline{y}$ on the ABA-side. We
illustrate this with an example:

###### Example 7

Consider the normal logic program $\pi_{4}=\\{{\sim\\!q}\rightarrow q,\
{\sim\\!r}\rightarrow s\\}$. This program has a single 3-valued stable model
$(\\{s\\},\\{s,q\\})$, in which $s$ is true, $q$ is undecided and $r$ is
false. The induced assumption-based framework is ${\sf ABF}_{{\sf
Norm}}(\pi_{4})={\langle\mathfrak{L}_{\sf
MP},\pi_{4},\\{{\sim\\!q},{\sim\\!r},{\sim\\!s}\\},-\rangle}$. (A fragment of)
its attack graph is the following:

$\\{{\sim\\!q}\\}$$\\{{\sim\\!r}\\}$$\\{{\sim\\!s}\\}$

${\sf ABF}_{{\sf Norm}}(\pi_{4})$ has a single preferred extension:
$\\{{\sim\\!r}\\}$, which attacks $\\{\sim\\!s\\}$. Intuitively (also
according to the 3-valued labeling semantics for this case, see [3]), this
makes ${\sim\\!r}$ true (i.e., $r$ is false), ${\sim\\!s}$ false (and so $s$
it true), and ${\sim\\!q}$ undecided (since it is neither accepted nor
attacked by ${\sim\\!r}$).777In general, an extension ${\cal
E}\subseteq\Lambda$ may be associated with a 3-valued ‘labeling’ in which the
element of ${\cal E}$ are accepted, the elements that are attacked by ${\cal
E}$ (those in ${\cal E}^{+}$) are rejected, and the other elements are
undecided (see, e.g., [3]). In the notations of Definition 10, then, this
corresponds to the 3-valued interpretation $({\cal E},\Lambda-{\cal E}^{+})$.
This corresponds to the 3-valued stable model of $\pi_{4}$, which is in-line
with the results stated above.

Next, we show that the correspondence described above, between 3-valued stable
models of logic programs and extensions of the induced argumentation
frameworks, does not carry on to disjunctives logic programs, at least not as
far as the translation in this paper is concerned.

###### Example 8

Consider the disjunctive logic program $\pi_{5}=\\{{\sim\\!q}\rightarrow q,\
q\rightarrow r\lor s\\}$. The 3-valued stable models of $\pi_{5}$ are
$(\emptyset,\\{q,r\\})$ and $(\emptyset,\\{q,s\\})$.

The assumption-based argumentation that is induced by $\pi_{5}$ is ${\sf
ABF}(\pi_{5})={\langle\mathfrak{L},\pi_{5},\\{{\sim\\!q},{\sim\\!r},{\sim\\!s}\\},-\rangle}$.
This results in the following (fragment of the) argumentation graph:

$\\{{\sim\\!q}\\}$$\\{{\sim\\!q},\>{\sim\\!r}\\}$$\\{{\sim\\!q},\>{\sim\\!s}\\}$$\\{{\sim\\!r}\\}$$\\{{\sim\\!s}\\}$

The unique complete and preferred set of assumptions in this case is
$\emptyset$. This set does not attack any assumption, thus corresponding to
$(\emptyset,\\{q,r,s\\})$. We thus see here that there is a discrepancy
between the following semantics that are preserved in case of normal logic
programs, namely: three-valued stable models of $\pi_{5}$ and complete
extensions of ${\sf ABF}(\pi_{5})$; well-founded models of $\pi_{5}$ and
grounded extensions of ${\sf ABF}(\pi_{5})$; regular models of $\pi_{5}$ and
preferred extensions of ${\sf ABF}(\pi_{5})$.

##  6 Extended Disjunctive Logic Programs

Intuitively, the connective $\sim$ may be understood as representing ‘negation
as failure’ (to prove the converse) [11]. This kind of negation is also known
as ‘weak negation’. Extended (disjunctive) logic programs are obtained by
introducing another negation connective, $\neg$, which acts as an explicit
(strong, classical) negation, and allowing literals (namely, atomic formulas
or their explicit negation) instead of the atoms in the rules $(\star)$ of
Definition 5. Formally, an extended disjunctive logic program $\pi$ is a
finite set of rules of the form

$(\star\star)\hskip
42.67912ptl_{1},\ldots,l_{m},{\sim\\!l_{m+1}},\ldots,{\sim\\!l_{m+k}}\rightarrow
l_{m+k+1}\lor\ldots\lor l_{m+k+n}$

where $m,k,n\geq 0$ and every $l_{i}$ $(1\leq i\leq m+k+n)$ is a literal, that
is: $l_{i}\in\\{p_{i},\neg p_{i}\\}$ for some $p_{i}\in{\cal A}(\pi)$.

Extended disjunctive logic programs may be reduced to disjunctive logic
programs by using a standard method in logic programming, viewing a literal of
the form $\neg p$ as a strangely written atomic formula. Under this view,
rules of the form $(\star\star)$ may be treated just as if they are of the
form $(\star)$. Relations between atomic formulas that correspond to positive
and negative occurrences of the same atomic assertion (namely without or with
a leading explicit negation, respectively) are made on the semantic level.
Indeed, while the semantics of disjunctive logic programs is two-valued (where
an atom $p$ is verified in a model $M$ if $p\in M$ and is falsified
otherwise), the semantics of extended disjunctive programs is four-valued. To
see this, given a rule $r$ of the form $(\star\star)$, replace every
occurrence of $p$ by $p^{+}$ and every occurrence of $\neg p$ by $p^{-}$.
Denote by $r^{\pm}$ by the resulting rule (and by $\pi^{\pm}$ the
corresponding program). Suppose that $M$ is a model of $r^{\pm}$. Then:

  * •

$p$ is true in $M$, if $p^{+}\in M$ and $p^{-}\not\in M$,

  * •

$p$ is false in $M$, if $p^{+}\not\in M$ and $p^{-}\in M$,

  * •

$p$ is contradictory in $M$, if $p^{+}\in M$ and $p^{-}\in M$,

  * •

$p$ is undecided in $M$, if $p^{+}\not\in M$ and $p^{-}\not\in M$.

The next example illustrates this distinction between the semantics of
disjunctive logic programs and extended disjunctive logic programs, and shows
how this is reflected by the stable extensions of the corresponding ABFs.

###### Example 9

  1. 1.

Let $\pi_{6}=\\{{\sim\\!p}\rightarrow\neg p\\}$. This program depicts a
‘closed world assumption’ [31] regarding $p$: Any statement that is true is
also known to be true, therefore, if $p$ is not known to be true, it must be
false. The conversion of $\pi_{6}$ to a normal logic program is
$\pi_{6}^{\pm}=\\{{\sim\\!p^{+}}\rightarrow p^{-}\\}$, the stable model is
$\\{p^{-}\\}$, which in turn is associated with the the two-valued stable
model of $\pi_{6}$, in which $p$ is false (see above). In the corresponding
assumption-based framework ${\sf
ABF}(\pi_{6})={\langle{\mathfrak{L}},\pi_{6}^{\pm},\\{{\sim\\!p}^{+},{\sim\\!p}^{-}\\},-\rangle}$
we have that $\\{{\sim\\!p}^{+}\\}$ attacks $\\{{\sim\\!p}^{-}\\}$, and so
$\\{{\sim\\!p}^{+}\\}$ is the unique stable model in this case (as indeed
indicated in Proposition 2).

Note that if $\pi_{6}$ is extended with $\\{p\\}$, the situation is reversed:
the sole stable extension of $(\pi_{6}\cup\\{p\\})^{\pm}$ is $\\{p^{+}\\}$,
and in the corresponding ABF we have that $\\{{\sim\\!p}^{+}\\}$ is attacked
by $\\{{\sim\\!p}^{-}\\}$. Thus, the latter is the unique stable extension in
this case, as expected.

  2. 2.

Consider the following extended disjunctive logic program:

$\pi_{7}=\\{\rightarrow\lnot p\lor\lnot q,\ {\sim\\!\\!\lnot p}\rightarrow p,\
{\sim\\!\\!\lnot q}\rightarrow q,\ p\rightarrow s,\ q\rightarrow s\\}.$

We obtain the following translated normal logic program:

$\pi_{7}^{\pm}=\\{\rightarrow p^{-}\lor q^{-},\ {\sim\\!p}^{-}\rightarrow
p^{+},\ {\sim\\!q}^{-}\rightarrow q^{+},\ p^{+}\rightarrow s^{+},\
q^{+}\rightarrow s^{+}\\}.$

The corresponding assumption-based framework is:

${\sf
ABF}(\pi_{7}^{\pm})={\langle{\mathfrak{L}},\pi_{7}^{\pm},\\{{\sim\\!p}^{+},{\sim\\!p}^{-},{\sim\\!q}^{+},{\sim\\!q}^{-},{\sim\\!s}^{+},{\sim\\!s}^{-}\\},-\rangle}.$

The resulting argumentation graph is the following:

$\\{\sim\\!q^{-}\\}$$\\{\sim\\!p^{-}\\}$$\\{\sim\\!q^{+}\\}$$\\{\sim\\!p^{+}\\}$$\\{\sim\\!s^{+}\\}$$\\{\sim\\!s^{-}\\}$

There are two stable sets of assumptions,
$\\{\sim\\!q^{-},\sim\\!p^{+},\sim\\!s^{-}\\}$ and
$\\{\sim\\!p^{-},\sim\\!q^{+},\sim\\!s^{-}\\}$, corresponding to the stable
models of $\pi_{7}^{\pm}$, $\\{p^{-},q^{+},s^{+}\\}$ and
$\\{q^{-},p^{+},s^{+}\\}$, which in turn correspond to the two stable models
of $\pi_{7}$ $\\{\lnot p,q,s\\}$ and $\\{\lnot q,p,s\\}$.

##  7 Related Work and Conclusion

This work generalizes translations from logic programming into assumption-
based argumentation to cover also (extended) disjunctive logic programs. Our
framework (as introduced in [25]) also serves as the base setting in [43],
where Wakaki shows a semantic correspondence between generalized assumption-
based argumentation (Definition 2), based on the logic in Section 3.1, and
extended disjunctive logic programming. The disjunction connective in the
rules’ heads which is considered in [43] is somewhat different than the
classical disjunction used here. Some rationality postulates and connections
to related non-monotonic formalisms, such as answer-set semantics and
disjunctive default theories, are discussed in [43].

A work with a similar motivation is presented in [44], where a representation
of DLPs by structured argumentation frameworks is proposed. In this framework,
the assumptions are disjunctions of negated atoms
${\sim\\!p}_{1}\lor\ldots\lor{\sim\\!p}_{n}$, instead of just negated atoms as
in our translation. Furthermore, unlike [44], we define our translation in
assumption-based argumentation, which means that meta-theoretical insights
(e.g., complexity results [14] or results on properties of the non-monotonic
consequence relations [2, 13, 26]), dialectical proof theories [16, 17], and
different implementations [12, 40] can be directly used.

A representation of disjunctive logic programming by _abstract argumentation_
is studied in [6]. In that translation, nodes in the argumentation framework
correspond to single assumptions ${\sim\\!p}$, as opposed to _sets_ of such
assumptions as in our translation. Because of this, the translation in [6] has
to allow for attacks on _sets of nodes_ , instead of just nodes, necessitating
a generalization of Dung’s abstract argumentation frameworks [15]. Since we
work in assumption-based argumentation, where nodes in the argumentation
framework correspond to sets of assumptions, the argumentation frameworks
generated by our translation are normal abstract argumentation frameworks.
This is important since in that way results and implementations for abstract
argumentation frameworks can be straightforwardly used and applied.

Another related, but more distant line of work, is concerned with the
integration of disjunctive reasoning in structured argumentation with
defeasible rules (see [4, 5]). We differ from this work both in the goal and
the form of the knowledge bases.

In future work, we plan to generalize our results to other semantics for
disjunctive logic programming, such as the disjunctive well-founded [8],
extended well-founded [32], stationary [29], and possible world semantics
[33]. Some of these semantics are based on ideas that are very similar to
ideas underlying some well-known argumentation semantics. Likewise, for
example, both the stationary semantics for disjunctive logic programming and
the preferred semantics from abstract argumentation [15] can be characterized
using three instead of two “truth values”. Indeed, as noted in Section 5, for
normal logic programs the correspondence between the 3-valued stable models
for normal logic programs [30] and complete labelings for ABA framework has
been proven by Caminada and Schulz in [9, 10]. On what conditions, if any, the
correspondence holds also for disjunctive logic programs, is still an open
question. Finally, we hope to extend our results to more expressive languages,
such as epistemic [20] and parametrized [23] logic programming.

## References

  * [1] Ofer Arieli and Jesse Heyninck.  Simple contrapositive assumption-based argumentation part II: Reasoning with preferences.  Journal of Approximate Reasoning, 139:28–53, 2021.
  * [2] Ofer Arieli and Jesse Heyninck.  Simple contrapositive assumption-based argumentation with partially-ordered preferences.  In Proc. KR’2023, 2023.  Accepted.
  * [3] Pietro Baroni, Martin W. Caminada, and Massimiliano Giacomin.  Abstract argumentation frameworks and their semantics.  In P. Baroni, D. Gabbay, M. Giacomin, and L. van der Torre, editors, Handbook of Formal Argumentation, volume 1, pages 159–236. College Publications, 2018.
  * [4] Mathieu Beirlaen, Jesse Heyninck, and Christian Straßer.  Reasoning by cases in structured argumentation.  In Proceedings of the 32nd ACM Symposium on Applied Computing (SAC’17), pages 989–994. ACM, 2017.
  * [5] Mathieu Beirlaen, Jesse Heyninck, and Christian Straßer.  A critical assessment of Pollock’s work on logic-based argumentation with suppositions.  In Proceedings of NMR’18, pages 63–72, 2018.
  * [6] Alexander Bochman.  Collective argumentation and disjunctive logic programming.  Journal of logic and computation, 13(3):405–428, 2003.
  * [7] Andrei Bondarenko, Phan Minh Dung, Robert Kowalski, and Francesca Toni.  An abstract, argumentation-theoretic approach to default reasoning.  Artificial Intelligence, 93(1):63–101, 1997.
  * [8] Stefan Brass and Jürgen Dix.  Characterizations of the disjunctive well-founded semantics: confluent calculi and iterated gcwa.  Journal of automated reasoning, 20(1-2):143–165, 1998.
  * [9] Martin Caminada and Claudia Schulz.  On the equivalence between assumption-based argumentation and logic programming.  Journal of Artificial Intelligence Research, 60:779–825, 2017.
  * [10] Martin Caminada and Claudia Schulz.  On the equivalence between assumption-based argumentation and logic programming (extended abstract).  In Proc. IJCAI’2018, pages 5578–5582. ijcai.org, 2018.
  * [11] Keith L. Clark.  Negation as failure.  In M. L. Ginsberg, editor, Readings in Nonmonotonic Reasoning, pages 311–325. Morgan Kaufmann, 1978.
  * [12] Robert Craven, Francesca Toni, and Matthew Williams.  Graph-based dispute derivations in assumption-based argumentation.  In International Workshop on Theorie and Applications of Formal Argumentation, pages 46–62. Springer, 2013.
  * [13] Kristijonas Čyras and Francesca Toni.  Non-monotonic inference properties for assumption-based argumentation.  In International Workshop on Theory and Applications of Formal Argumentation, pages 92–111. Springer, 2015.
  * [14] Yannis Dimopoulos, Bernhard Nebel, and Francesca Toni.  On the computational complexity of assumption-based argumentation for default reasoning.  Artificial Intelligence, 141(1-2):57–78, 2002.
  * [15] Phan Minh Dung.  On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games.  Artificial Intelligence, 77:321–358, 1995.
  * [16] Phan Minh Dung, Robert A Kowalski, and Francesca Toni.  Dialectic proof procedures for assumption-based, admissible argumentation.  Artificial Intelligence, 170(2):114–159, 2006.
  * [17] Phan Minh Dung, Paolo Mancarella, and Francesca Toni.  A dialectic procedure for sceptical, assumption-based argumentation.  144:145–156, 2006.
  * [18] Thomas Eiter, Georg Gottlob, and Heikki Mannila.  Disjunctive datalog.  ACM Transactions on Database Systems (TODS), 22(3):364–418, 1997\.
  * [19] Thomas Eiter, Nicola Leone, and Domenico Sacca.  On the partial semantics for disjunctive deductive databases.  Annals of Mathematics and Artificial Intelligence, 19(1-2):59–96, 1997.
  * [20] Michael Gelfond.  Logic programming and reasoning with incomplete information.  Annals of mathematics and artificial intelligence, 12(1-2):89–116, 1994.
  * [21] Michael Gelfond and Vladimir Lifschitz.  The stable model semantics for logic programming.  In Prog. ICLP’88, pages 1070–1080. MIT Press, 1988.
  * [22] Michael Gelfond and Vladimir Lifschitz.  Classical negation in logic programs and disjunctive databases.  New generation computing, 9(3-4):365–385, 1991.
  * [23] Ricardo Gonçalves and José Júlio Alferes.  Parametrized logic programming.  In European Workshop on Logics in Artificial Intelligence, pages 182–194. Springer, 2010.
  * [24] Georg Gottlob.  Complexity and expressive power of disjunctive logic programming (research overview).  In Proceedings of the 1994 International Symposium on Logic programming, pages 23–42. Mit Press, 1994.
  * [25] Jesse Heyninck and Ofer Arieli.  An argumentative characterization of disjunctive logic programming.  In Paulo Moura Oliveira, Paulo Novais, and Luís Paulo Reis, editors, Proceedings of the 19th EPIA Conference on Artificial Intelligence, Part II, volume 11805 of Lecture Notes in Computer Science, pages 526–538. Springer, 2019.
  * [26] Jesse Heyninck and Ofer Arieli.  Simple contrapositive assumption-based argumentation frameworks.  Journal of Approximate Reasoning, 121:103–124, 2020.
  * [27] S. C. Kleene.  Introduction to Metamathematics.  Van Nostrand, 1950.
  * [28] John W. Lloyd.  Foundations of Logic Programming.  Springer, 1987.
  * [29] Teodor Przymusinski.  Stationary semantics for normal and disjunctive logic programs.  In DOOD, volume 91. Citeseer, 1991.
  * [30] Teodor C. Przymusinski.  The well-founded semantics coincides with the three-valued stable semantics.  Fundam. Inform., 13(4):445–463, 1990.
  * [31] Raymond Reiter.  On closed world data bases.  In Hervé Gallaire and Jack Minker, editors, Logic and Data Bases, pages 119–140. 1978.
  * [32] Kenneth A Ross.  A procedural semantics for well-founded negation in logic programs.  The Journal of Logic Programming, 13(1):1–22, 1992.
  * [33] Chiaki Sakama.  Possible model semantics for disjunctive databases.  In Deductive and Object-Oriented Databases, pages 369–383. Elsevier, 1990.
  * [34] Claudia Schulz.  Graphical representation of assumption-based argumentation.  In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015\.
  * [35] Claudia Schulz, Ken Satoh, and Francesca Toni.  Characterising and explaining inconsistency in logic programs.  In International Conference on Logic Programming and Nonmonotonic Reasoning, pages 467–479. Springer, 2015.
  * [36] Claudia Schulz and Francesca Toni.  Justifying answer sets using argumentation.  Theory and Practice of Logic Programming, 16(1):59–110, 2016.
  * [37] Claudia Schulz and Francesca Toni.  Complete assumption labellings, 2017.
  * [38] Claudia Schulz and Francesca Toni.  Labellings for assumption-based and abstract argumentation.  J. Approximate Reasoning, 84:110–149, 2017.
  * [39] Ezgi Su.  Extensions of equilibrium logic by modal concepts.  PhD thesis, IRIT-Institut de recherche en informatique de Toulouse, 2015\.
  * [40] Francesca Toni.  A generalised framework for dispute derivations in assumption-based argumentation.  Artificial Intelligence, 195:1–43, 2013.
  * [41] Allen Van Gelder, Kenneth A Ross, and John S Schlipf.  The well-founded semantics for general logic programs.  Journal of the ACM, 38(3):619–649, 1991.
  * [42] Toshiko Wakaki.  Consistency in assumption-based argumentation.  In Henry Prakken, Stefano Bistarelli, Francesco Santini, and Carlo Taticchi, editors, Proceedings of the the 8th International Conference on Computational Models of Argument (COMMA’20), volume 326 of Frontiers in Artificial Intelligence and Applications, pages 371–382. IOS Press, 2020\.
  * [43] Toshiko Wakaki.  Assumption-based argumentation for extended disjunctive logic programming.  In Ivan Varzinczak, editor, Proceedings of the 12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS-2022), volume 13388 of Lecture Note in Computer Science, pages 35–54. Springer, 2022.
  * [44] Kewen Wang.  Argumentation-based abduction in disjunctive logic programming.  The Journal of Logic Programming, 45(1-3):105–141, 2000.


$\displaystyle\phantom{=}+\frac{1}{n({\bm{i}},k)}\sum_{j=2}^{n({\bm{i}},k)+1}\left(Z^{(k-1)}_{[k,1,j],U_{[k,1,j]}^{(k-1),n}(\nu_{1}),n}(\nu_{1})-Z^{(k-1)}_{[k,1,j],U_{[k,1,j],n}^{(k-1)}(\nu_{1}),n}\left(\nu_{2}\right)\right)\Big{|}\\{{\bm{S}}^{[k,1,j]}_{\llbracket
0,U_{[k,1],n}^{(k)}(\nu_{2})\rrbracket}={\bm{S}}^{[k,1]}_{\llbracket
0,U_{[k,1],n}^{(k)}(\nu_{2})\rrbracket}\\}.$

Now, by the choice of $\nu_{1}$, we know there is a random variable
$\epsilon(\nu_{1})$ such that
$U_{[k,1],n}^{(k)}(\nu_{2})=U_{[k,1],n}^{(k)}(\nu_{1})$ almost surely for all
$\nu_{2}$ such that $|\nu_{1}-\nu_{2}|\leq\epsilon(\nu_{1})$. Hence, for every
sample path, for $\nu_{2}$ close enough to $\nu_{1}$, we condition on
$\\{{\bm{S}}^{[k,1,j]}_{\llbracket
0,U_{[k,1],n}^{(k)}(\nu_{1})\rrbracket}={\bm{S}}^{[k,1]}_{\llbracket
0,U_{[k,1],n}^{(k)}(\nu_{1})\rrbracket}\\}$ above. From this it follows that
almost surely

${\lim\sup}_{\nu_{2}\uparrow\nu_{1}}\frac{\min_{u\in[N]}Z^{(k)}_{[k,1],u,n}(\nu_{1})-\min_{u\in[N]}Z^{(k)}_{[k,1],u,n}(\nu_{2})}{\nu_{1}-\nu_{2}}\leq
h^{(k)}_{[k,1],n}(U_{[k,1],n}^{(k)}(\nu_{1}),\nu_{1})$

hence (54) holds. The case $\nu_{1}<\nu_{2}$ works similarly.

By induction it can be verified that the right-hand side of (54) is bounded
for each $k$.

We have for $\nu_{1}\in\mathcal{V}$ and $\nu_{1}>\nu_{2}$

$\displaystyle\frac{\tilde{f}_{\bm{s}}(\nu_{1})-\tilde{f}_{\bm{s}}(\nu_{2})}{\nu_{1}-\nu_{2}}$
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{K}\frac{\min_{u\in[N]}Z_{[1,j],u,n}^{(k)}(\nu_{1})-\min_{u\in[N]}Z_{[1,j],u,n}^{(k)}(\nu_{2})}{\nu_{1}-\nu_{2}}\mathbbm{I}((\tilde{V}_{\bm{s}}(\nu_{1}),\tilde{V}_{\bm{s}}(\nu_{2}))\in[-1/2,1/2]^{2})\right]$
$\displaystyle+\mathbb{E}\left[\frac{V_{\bm{s}}(\nu_{1})-V_{\bm{s}}(\nu_{2})}{\nu_{1}-\nu_{2}}\mathbbm{I}((\tilde{V}_{\bm{s}}(\nu_{1}),\tilde{V}_{\bm{s}}(\nu_{2}))\notin[-1/2,1/2]^{2})\right].$

When $\nu_{2}\uparrow\nu_{1}$ by continuity and boundedness of the derivative
the first term goes to

$\sum_{k=1}^{K}\mathbb{E}_{\bm{s}}\left[h^{(k)}_{[k,1],n}\left(U^{(k)}_{[k,1],n}(\nu),\nu\right)\mathbbm{I}(\tilde{V}_{{\bm{s}}}(\nu)\in[-1/2,1/2])\right]$

while the second term goes to zero by continuity (of $\tilde{V}_{{\bm{s}}}$)
and boundedness, where in both cases the dominated convergence theorem was
used. ∎

######  Theorem 9.

Let $h_{m,[k,1],n}^{(k)},\;U_{m,[k,1],n}^{(k)}$ be independent versions (in
$m$) of $h_{[k,1],n}^{(k)},\;U_{[k,1],n}^{(k)}$, and

$h_{m}:\nu\mapsto\sum_{k=1}^{K}h_{m,[k,1],n}^{(k)}(U_{m,[k,1],n}^{(k)}(\nu),\nu).$

Let

$\alpha_{m}=\frac{1}{|\sum_{\ell=1}^{m}h_{\ell}(\nu_{\ell}({\bm{s}}))|}.$

Let $\mathcal{V}$ be the set of points where $\tilde{f}_{\bm{s}}$ is
differentiable. If $\inf_{\nu\in\mathcal{V}}d/d\nu\tilde{f}_{\bm{s}}(\nu)>0$,
then there is a unique point $\tilde{\nu}({\bm{s}})$ such that
$\tilde{f}_{{\bm{s}}}(\tilde{\nu}({\bm{s}}))=0$. If the derivative of
$f^{(K)}_{{\bm{s}},n}$ exists at $\tilde{\nu}({\bm{s}})$ and
$\mathbb{E}[V_{{\bm{s}}}(\tilde{\nu}({\bm{s}}))^{2}]>0$, we have

$\sqrt{m}(\nu_{m}({\bm{s}})-\tilde{\nu}({\bm{s}}))\stackrel{{\scriptstyle
d}}{{\rightarrow}}\mathcal{N}\left(0,\frac{\mathbb{E}[V_{{\bm{s}}}(\tilde{\nu}({\bm{s}}))^{2}]}{\left(\frac{d}{d\nu}f^{(K)}_{{\bm{s}},n}(\tilde{\nu}({\bm{s}}))\right)^{2}}\right).$
(55)

###### Proof.

The first statement is trivial as $\tilde{f}_{\bm{s}}$ has a positive
derivative wherever the derivative is defined. We show the second statement by
first verifying that the Robbins-Monro conditions hold almost surely, hence by
Corollary 1 we have that $\nu_{m}({\bm{s}})$ converges almost surely to
$\tilde{\nu}({\bm{s}})$. As for a constant $H<\infty$ we have $|h_{\ell}|\leq
H$ we have that $\sum_{\ell=1}^{m}\alpha_{\ell}\geq\sum_{\ell=1}^{m}1/(\ell
H)\rightarrow\infty$ almost surely. We verify that
$\sum_{\ell=1}^{m}\alpha_{\ell}^{2}\leq\infty$ almost surely. Let
$\xi_{\ell}=h_{\ell}(\nu_{\ell}({\bm{s}}))\leavevmode\nobreak\
-\mathbb{E}[h_{1}(\nu_{\ell}({\bm{s}}))]$ and
$\sigma^{2}_{\ell}=\mathbb{E}[\xi_{\ell}^{2}|\nu_{\ell}({\bm{s}})].$ By the
strong law of large numbers for martingales we have (by boundedness of
$\xi_{\ell}$) that almost surely

$\lim_{m\rightarrow\infty}\frac{\sum_{\ell=1}^{m}\xi_{\ell}}{\sum_{\ell=1}^{m}\sigma^{2}_{\ell}}\leavevmode\nobreak\
=\leavevmode\nobreak\ 0$ (56)

Letting $H_{\sigma}$ be such that $|\sigma^{2}_{\ell}|\leq H_{\sigma}$ for all
$\ell$ we can choose
$\epsilon\in(0,\inf_{\nu}\mathbb{E}[h_{1}(\nu)]/H_{\sigma})$ and have an
$M\in\mathbb{N}$ such that for all $m>M$

$\frac{1}{m}\sum_{\ell=1}^{m}h_{\ell}(\nu_{\ell}({\bm{s}}))>\inf_{\nu}\mathbb{E}[h_{1}(\nu)]-\epsilon
H_{\sigma}>0.$

We then conclude

$\sum_{\ell=1}^{\infty}\alpha_{\ell}^{2}\leq\sum_{\ell=1}^{M}\alpha_{\ell}^{2}+\sum_{\ell=M+1}^{\infty}\frac{1}{m^{2}(\frac{1}{m}\sum_{\ell=1}^{m}h_{\ell}(\nu_{\ell}({\bm{s}})))^{2}}<\sum_{\ell=1}^{M}\alpha_{\ell}^{2}+\sum_{\ell=M+1}^{\infty}\frac{1}{m^{2}(\inf_{\nu}\mathbb{E}[h_{1}(\nu)]-\epsilon
H_{\sigma})^{2}}<\infty.$

Hence it follows by Corollary 1 that $\nu_{m}({\bm{s}})\stackrel{{\scriptstyle
a.s.}}{{\rightarrow}}\tilde{\nu}({\bm{s}})$.

Now, if $\mathbb{P}(h_{\ell}((\tilde{\nu}({\bm{s}}))^{-})\neq
h_{\ell}((\tilde{\nu}({\bm{s}}))^{+}))>0$ the derivative of
$\tilde{f}_{\bm{s}}$ at $\tilde{\nu}$ would not exist, hence almost surely for
all $\ell$ we have
$h_{\ell}((\tilde{\nu}({\bm{s}}))^{-})=h_{\ell}((\tilde{\nu}({\bm{s}}))^{+})$
and combined with the above result it follows that
$h_{\ell}(\nu_{\ell}({\bm{s}}))\rightarrow h(\tilde{\nu}({\bm{s}}))$ (with
$h\stackrel{{\scriptstyle d}}{{=}}h_{1}$ independently) almost surely by
continuous mapping (noting that the set of discontinuity points of $h$ is
restricted to a deterministic set). By boundedness we also have
$\mathbb{E}[h_{\ell}(\nu_{\ell}({\bm{s}}))]\rightarrow\mathbb{E}[h(\tilde{\nu}({\bm{s}}))].$
Similarly, it can be shown that
$\sigma^{2}_{\ell}\rightarrow\mathbb{E}[\xi^{2}_{1}|\tilde{\nu}({\bm{s}})]=\sigma^{2}$
which is deterministic. Hence
$\frac{1}{m}\sum_{\ell=1}^{m}\sigma^{2}_{\ell}\rightarrow\sigma^{2}$ and by
(56) and continuous mapping we have

$m\alpha_{m}=\frac{m}{|\sum_{\ell=1}^{m}h_{\ell}(\nu_{\ell}({\bm{s}}))|}\rightarrow
1/\mathbb{E}[h_{1}(\tilde{\nu}({\bm{s}}))].$

The result follows along the lines of Lai and Robbins [1978], with three
additional remarks.

  * •

In order to use the representation (17) in Lai and Robbins [1978] the
recursion of the stochastic approximation has to be truncated earlier, to make
sure that the iterates $\nu_{\ell}({\bm{s}})$ remain in an interval around
$\tilde{\nu}({\bm{s}})$ where $\tilde{f}_{\bm{s}}$ is differentiable, so as to
use the mean value theorem.

  * •

The martingale central limit theorem (Theorem 2 in Brown [1971]) can be used
to show a central limit theorem result for the martingale
$\sum_{\ell}\epsilon_{\ell}$, as the running mean of the quadratic variation
process converges to a constant, we can show a central limit theorem result by
just dividing by $\sqrt{m}$.

  * •

A supremum law of iterated logarithm for martingales Fisher [1986] can be used
to show that the middle term in (29) in Lai and Robbins [1979] goes to zero
when divided by $\sqrt{m}.$

∎

##  Appendix B Notation Table

Symbol | Definition | Defined in
---|---|---
$a$ | Markov chain/arm | Sec. 2
$t,u$ | Time index | Sec. 2
${\bm{s}}^{a}_{h},{\bm{s}}^{a},{\bm{s}}$ | Initial state of an arm | Sec. 2
$\mathbb{E}_{\bm{s}},\mathbb{P}_{\bm{s}}$ | Transition kernel and expectation for the Markov chains, conditional on initial state ${\bm{s}}$ | Sec. 2
$\mathcal{H}$ | Set of histories | (1)
$R$ | Common reward function for the arms | Sec. 2
$\pi,\pi^{*}$ | Policy and optimal policy (resp.) for the family of alternative bandit processes | Sec. 2
$C({\bm{s}}^{a})$ | Total discounted absolute reward for sampling arm $a$, starting from state ${\bm{s}}^{a}$ | Sec. 2
$\mathbb{E}_{\pi}$ | Expectation operator under a fixed policy $\pi$ | Sec. 2
$\gamma$ | Discount factor | Sec. 2
$\nu({\bm{s}})$ | Gittins index for state ${\bm{s}}$ | Sec. 2
$\mathcal{F}_{t}^{a},\mathcal{F}_{t}$ | Natural filtration generated by ${\bm{S}}^{a}$ and ${\bm{S}}$ (resp.), including starting state | Sec. 2, 3.1
$\mathcal{T}^{a},\mathcal{T}$ | Set of stopping times w.r.t. $(\mathcal{F}_{t}^{a})_{t}$ or $(\mathcal{F}_{t})_{t}$ (resp.) | Sec. 2, 3.1
${\bm{S}}_{t}^{a},{\bm{S}}_{t}$ | State of Markov chain/arm $a$ and general arm (resp.) at time $t$ | Sec. 2, 3.1
$\tau$ | Stopping time, used to determine optimal stopping value | Sec. 2
$N$ | Sampling horizon for optimal stopping value | Sec. 3.1
$\mathcal{T}_{N}$ | Set of stopping times adapted to $\mathcal{F}_{t}$ and bounded by $N$ | Sec. 3.1
$g_{t}$ | Measurable real-valued cost function | Sec. 3.1
$Z_{t},Z^{(1)}_{t}$ | Cost $g_{t}({\bm{S}}_{\llbracket 0,t\rrbracket})$ of an arm up to time $t$ | Sec. 3.1
$Z_{t}^{(k+1)}$ | $Z_{t}^{(k)}-\mathbb{E}[\min_{u\in[N]}Z_{u}^{(k)}\mid\mathcal{F}_{t}]$ | Sec. 3.1
$K$ | Truncation point of number of nested expectations in optimal stopping approximation | Sec. 3.1
$Z^{(k+1)}_{{\bm{i}},t,n}$ | Sampling-based approximation of $Z^{(k+1)}_{t}$ | Sec. 3.2
$n({\bm{i}},k)$ | Number of simulated paths used to determine $Z^{(k+1)}_{{\bm{i}},t,n}$ | Sec. 3.2
$V_{n}^{(K)},V_{\bm{s}}(\nu),V_{{\bm{s}},m}(\nu)$ | Sampling-based approximation of $\sum_{k=1}^{K}\mathbb{E}[\min_{u\in[N]}Z_{u}^{(k)}]$ and $\sum_{k=1}^{K}\mathbb{E}_{\bm{s}}[\min_{u\in[N]}Z_{u}^{(k)}(\nu)]$ | Sec. 3.2, 4
$\sigma$ | Stopping time, used to truncate the support of the rewards | (15)
$R_{u},R_{\ell}$ | Upper and lower bound for reward support (resp.), induced by stopping time $\sigma$ | Sec. 4
$c$ | Constant, equal to $(1-\gamma)/(2(R_{u}-R_{\ell})(1-\gamma^{N}))$ | Sec. 4
$Z_{t}(\nu)$ | Cost $c\sum_{u=0}^{t\wedge\sigma-1}\gamma^{u}(\nu-R({\bm{S}}_{u}))$ of an arm up to the minimum of time $t$ and $\sigma$ | Sec. 4
$\nu_{\sigma}({\bm{s}})$ | Gittins index approximation found by truncation of horizon and reward support | (16)
$\nu_{m}({\bm{s}})$ | Stochastic approximation iterates for determining SBGIA | (18)
$\alpha_{m}$ | Step-size sequence | Sec. 4
$\nu_{M}({\bm{s}})$ | Sampling-based Gittins index approximation | Sec. 4
$\tilde{f}_{\bm{s}}(\nu)$ | Expectation of $\mathbb{E}_{\bm{s}}[V_{\bm{s}}(\nu)]$ | (19)
${f}_{\bm{s}}(\nu)$ | Optimal stopping value $\inf_{\tau\in\mathcal{T}_{N}}\mathbb{E}_{\bm{s}}[Z_{\tau}(\nu)]$ | (19)
$B(\delta,\xi)$ | Domain error bound, equal to $\xi+\delta$ | (20)
$\epsilon_{m}$ | Martingale difference sequence | (21)
$\bar{\nu}_{m},\underaccent{\bar}{\nu}_{m}$ | Stochastic approximation iterates bounding $\nu_{m}$ from above and below (resp.) | (22), (23)
$\mathcal{R}_{\bm{s}}$ | Set of roots of $\tilde{f}_{\bm{s}}$ | Sec. 4.2
$\tilde{\nu}({\bm{s}})$ | Root of $\tilde{f}_{\bm{s}}$ | Sec. 4.2
$h_{m}$ | Derivative of $V_{{\bm{s}},m}(\nu)$ | Th. 9
$\Psi_{t}$ | Sufficient statistics | Sec. 5.2.1
$\kappa_{t}$ | Effective number of observations | Sec. 5.2.1
$O_{t}^{a}$ | Outcome $t$ for distribution $a$ | Sec. 5.1
$\text{\boldmath$\mathbf{\theta}$}_{a}$ | Parameter for distribution $a$ | Sec. 5.1
$\Pi_{t}^{a},\hat{\Pi}_{t}^{a}$ | Posterior and approximate posterior (resp.) for $\text{\boldmath$\mathbf{\theta}$}_{a}$ based on $(O^{a}_{u})_{u=1}^{t}$ | Sec. 5.1, (51)