Assumption-based argumentation for extended disjunctive logic programming and its relation to nonmonotonic reasoning

Abstract

The motivation of this study is that Reiter’s default theory as well as assumption-based argumentation frameworks corresponding to default theories have difficulties in handling disjunctive information, while a disjunctive default theory (ddt) avoids them. This paper presents the semantic correspondence between generalized assumption-based argumentation (ABA) and extended disjunctive logic programming as well as the correspondence between ABA and nonmonotonic reasoning approaches such as disjunctive default logic and prioritized circumscription. To overcome the above-mentioned difficulties of ABA frameworks corresponding to default theories, we propose an assumption-based framework (ABF) translated from an extended disjunctive logic program (EDLP) since an EDLP can be translated into a ddt. Our ABF incorporates explicit negation and the connective of disjunction “|” to Heyninck and Arieli’s ABF induced by a disjunctive logic program. In this paper, first, we show how arguments are constructed from disjunctive rules in our proposed ABF. Then, we show the correspondence between answer sets of an EDLP P and stable extensions of the ABF translated from P with trivialization rules. After defining rationality postulates, we show answer sets of a consistent EDLP are captured by consistent stable extensions of the translated ABF with no trivialization rules. Finally, we show the correspondence between ABA and disjunctive default logic (resp. prioritized circumscription). The relation between ABA and possible model semantics of EDLPs is also discussed.

Keywords

Assumption-based argumentation extended disjunctive logic programs disjunctive default logic arguments prioritized circumscription

1. Introduction

1.1. Background

Disjunctive information is often required in reasoning and argumentation to solve problems in our daily life. In nonmonotonic reasoning, Gelfond et al. [16] proposed disjunctive default logic as a generalization of Reiter’s default logic [27] to overcome problems of default logic in handling disjunctive information. To this end, they use the symbol “|” as the connective of disjunction in a disjunctive default theory instead of the classical “∨” used in a default theory, where $P \lor Q$ means “ $P \lor Q$ is known”, while $P | Q$ means “P is known or Q is known”.1

¹
Semantically, the latter requires an extension to contain one of the two disjunctive terms, rather than the disjunction [16].

They also showed that an extended disjunctive logic program (EDLP) [15] which may include disjunction using the connective “|” in rule head as well as two kinds of negation (i.e. classical negation “¬” and negation-as-failure “

not

”) can be translated into a disjunctive default theory. In contrast, in the context of formal argumentation, Beirlaen et al. [2,3] presented the extended ASPIC

^{+}

framework where disjunctive reasoning is integrated in structured argumentation with defeasible rules [25] by incorporating reasoning by cases inference scheme [2]. In their framework, an argument is allowed to have a disjunctive conclusion, while disjunction is expressed by using the classical connective “∨”. However, they did not show the relationship between their framework and other approaches in nonmonotonic reasoning such as a disjunctive default theory. Consider the following example [3] shown by them.

Example 1 (Kyoto protocol).

There are two candidates for an upcoming presidential election. The candidates had a debate in the capital. They were asked what measures are to be taken in order for the country to reach the Kyoto protocol objectives for reducing greenhouse gas emissions. The first candidate, a member of the purple party, argued that if she wins the election, she will reach the objectives by supporting investments in renewable energy. The second candidate, a member of the yellow party, argued that if she wins the election, she will reach the objectives by supporting sustainable farming methods. We have reasons to believe that, no matter which candidate wins the election, the Kyoto protocol objectives will be reached. If the purple candidate wins, she will support investments in renewable energy ( $p \Rightarrow r$ ), which would in turn result in meeting the Kyoto objectives ( $r \Rightarrow k$ ). Similarly, if the yellow candidate wins, she will support sustainable farming methods ( $y \Rightarrow f$ ), which would result in meeting the Kyoto objectives ( $f \Rightarrow k$ ). Since one of the two candidates is going to win ( $p \lor y$ ), we can reason by cases to conclude that the Kyoto objectives will be reached (k).

Beirlaen et al. [3] represented the information shown above in terms of the knowledge base $K_{1} = ({p \Rightarrow r, r \Rightarrow k, y \Rightarrow f, f \Rightarrow k}, {p \lor y}$ ) which consists of defeasible rules in ASPIC $^{+}$ [24,25] and the classical formula $p \lor y$ as facts. Their formulation derives the intended result k, however, a problem happens when $K_{1}$ is translated into a default theory. In fact, $ψ \Rightarrow ϕ$ encodes the normal default $\frac{ψ : ϕ}{ϕ}$ , then $K_{1}$ is expressed by the default theory $D_{1}$ : $\begin{matrix} D_{1} = {\frac{p : r}{r}, \frac{r : k}{k}, \frac{y : f}{f}, \frac{f : k}{k}, p \lor y} . \end{matrix}$ $D_{1}$ has a single extension, consisting of the disjunction $p \lor y$ and its logical consequences, where the four defaults “don’t work”. Thus the result is contrary to what we would expect.

Moreover, regarding ABA as another structured argumentation system, Lehtonen et al. [19] recently presented the ABA framework instantiated with a propositional default theory. However the ABA framework corresponding to $D_{1}$ which is constructed according to Lehtonen et al.’s definition cannot derive the expected result k under the stable (resp. grounded) semantics as well (see details in Section 6).

Notice that the disjunctive information s.t. “one of the two candidates is going to win” is expressed by $p \lor y$ in $K_{1}$ and $D_{1}$ . In a precise sense, however, it means that the election will yield a result s.t. either “that the purple candidate wins is known” or “that the yellow candidate wins is known”. Hence it should be expressed by $p | y$ rather than $p \lor y$ , that requires an extension to contain one of the two disjunctive terms rather than the disjunction due to [16]. Therefore, to solve the aforementioned problem arising in $D_{1}$ , let us represent the information by the disjunctive default theory $D_{2}$ : $\begin{matrix} D_{2} = {\frac{p : r}{r}, \frac{r : k}{k}, \frac{y : f}{f}, \frac{f : k}{k}, p | y}, \end{matrix}$ or the associated EDLP $P_{1} = {r \leftarrow p, not \neg r, k \leftarrow r, not \neg k, f \leftarrow y, not \neg f, k \leftarrow f, not \neg k, p | y \leftarrow}$ [16]. Then $P_{1}$ has two answer sets $S_{1} = {p, r, k}$ and $S_{2} = {y, f, k}$ , while $D_{2}$ has two extensions $E_{1}$ and $E_{2}$ such that $k \in S_{i} \subseteq E_{i} (i = 1, 2)$ , where $E_{i}$ consists of atoms from $S_{i}$ as well as the logical consequences derived from them. These results agree with our expectation that the Kyoto protocol objectives will be reached no matter which candidate wins the election. □

In regard to the relation between assumption-based argumentation and (disjunctive) default logic, Bondarenko et al. firstly showed in [5, Theorem 3.16] that there is a one-to-one correspondence between extensions of Reiter’s default theory and stable extensions of the corresponding assumption-based framework (ABF,2

²
In this paper, we use the abbreviation “ABF” to primarily denote assumption-based framework but sometimes ABA framework in different approaches [5,10,18,19,32,33] though it may refer to the respectively defined framework based on ABA in each approach.

for short). This denotes that the expected result k of the Kyoto protocol problem shown above is never obtained from stable extensions of their ABF corresponding to

D_{1}

based on their theorem. Besides, Bondarenko et al. [5] showed nothing about the relationship between ABA and disjunctive default logic. Hence, to solve such problems of ABFs corresponding to default theories in handling disjunctive information, it is required to find the relationship between ABFs and disjunctive default theories.

Recently, Heyninck and Arieli [18] proposed a generalized assumption-based framework induced by a disjunctive logic program (DLP), where disjunction using the connective “∨” in rule head as well as one kind of negation, i.e. negation-as-failure (NAF) are allowed to appear. Hence though their ABF induced by a DLP has a contrariness operator $\bar{} \bar{}$ such that $\overline{not p} = p$ for every atom p, its language does not contain explicit negation. Then they showed a one-to-one correspondence between the stable models of a DLP [26] and the stable assumption extensions of the ABF induced by a DLP. In their work, however, there are several open problems left to be explored. First, the semantic relationship between their ABF induced by a DLP and approaches of nonmonotonic reasoning such as a disjunctive default theory is not considered in [18]. Second, they did not show how to construct an argument from disjunctive rules in a DLP nor took account of argument extensions in their ABF.

In logic programming, EDLPs [15] were proposed by Gelfond and Lifschitz to extend DLPs for knowledge representation by not only allowing classical negation (i.e. explicit negation) along with negation-as-failure but also using “|” instead of “∨”. At the same time, it is shown in [16] that an EDLP can be embedded into a disjunctive default theory (ddt, for short) which uses “|” as the connective of disjunction. In contrast, in formal argumentation, generally an assumption-based framework is capable of containing explicit negation in its language [9,10,12], but the ABFs corresponding to Reiter’s default theories have difficulties in handling disjunctive information. To our best knowledge, however, there is no study to show the relationship between ABFs and EDLPs as well as the relationship between ABFs and ddts to overcome such difficulties of ABFs discussed above.

1.2. Purpose of this paper

The purpose of this paper is first to investigate the semantic relationship between ABFs and EDLPs as well as the relationships between ABFs and other approaches in nonmonotonic reasoning (e.g. disjunctive default logic [16], prioritized circumscription [20,23]) that have not been studied, and second to show how to construct an argument in ABFs from disjunctive rules in (E)DLPs. We use the answer set semantics [15] and the paraconsistent stable model semantics [28] of EDLPs neither of which is two-valued for characterizing stable extensions of ABFs translated from EDLPs.

Regarding ABFs whose languages contain explicit negation, however, we should pay attention to avoid consistency problems which sometimes have occurred in applications of argumentation due to explicit negation contained in the language. To this end, so far, rationality postulates [6] were proposed as principles which rule-based argumentation systems should satisfy to avoid anomalous outcomes. In fact, in structured argumentation systems such as ASPIC $^{+}$ and ABA frameworks whose languages contain explicit negation, conditions under which each system satisfies rationality postulates were proposed [1,12,24,25].

As for recent ABA applications containing explicit negation, Schulz and Toni [31] proposed the approach of justifying answer sets of an extended logic program (ELP) using argumentation. In their approach, they used the ABA framework $A B A_{P}$ instantiated with an ELP P. Though an ELP may contain classical negation, they took account of neither rationality postulates [6,12] nor consistency in ABA, and they claimed in their theorems [31, Theorem 1 and Theorem 2] that there is a one-to-one correspondence between answer sets of a consistent ELP P and the stable extensions of $A B A_{P}$ . In other words, their theorems claim that any ABA framework instantiated with a consistent ELP will never produce inconsistent stable extensions. However, there exist counterexamples to their theorems as shown in [33]. This means that anomalous outcomes may be obtained in applications of argumentation based on their theorems (e.g., there exists the inconsistent stable extension in $A B A_{P}$ instantiated with the given consistent ELP P which expresses the knowledge of the slightly modified Married John Example [33, Example 1], [6]).

Therefore, to achieve the above-mentioned purpose of this study, this paper proposes an assumption-based framework translated from an EDLP, which incorporates explicit negation as well as the connective “|” instead of “∨” in Heyninck and Arieli’s ABF induced by a DLP while avoiding consistency problems that arise in Schulz and Toni’s approach. Contributions of this study are as follows:

First, we define an argument in the ABF translated from a given EDLP which is constructed from disjunctive rules of the EDLP based on three inference rules provided in our ABF. Second, we show not only a one-to-one correspondence between p-stable models of an EDLP P and stable argument extensions (resp. stable assumption extensions) of the ABF translated from P but also a one-to-one correspondence between answer sets of an EDLP P and stable argument extensions (resp. stable assumption extensions) of the ABF translated from P with trivialization rules. Third, since our ABF incorporates explicit negation ¬, we define rationality postulates and consistency in our ABFs to avoid anomalous outcomes. Then we show answer sets of a consistent EDLP can be captured by consistent stable extensions of the translated ABF with no trivialization rules. This is useful for ABA applications containing explicit negation. Fourth, we show the new results about the relationship between ABA and disjunctive default logic [16] which enables us to overcome the difficulties of the ABF corresponding to a default logic in handling disjunctive information as well as the relationship between ABA and prioritized circumscription [20,23]. These results have not been shown so far to the best of our knowledge. Finally, we show how the possible model semantics of EDLPs [30] which is different from answer set semantics [15] is also captured by our ABFs translated from EDLPs. Appendix shows the correspondence between the semantics of ELPs [15,28] and stable assumption extensions of the associated ABA frameworks.

This paper is an extended and revised version of the paper [34], where not only Theorems 13, 14 and 15 in Section 4.1 but also Section 4.2, Section 5 and Appendix are newly introduced. Every proof sketch in [34] is replaced with a full proof while introducing new propositions, lemmas and two tables in this paper. Revisions are made throughout the paper and new considerations3

³
For example, the difference between DLPs and NDPs as shown in Eample 4, the interesting results under the skeptical semantics (e.g. grounded) in Example 8, and the relation between our ABF and a standard ABA as shown in Proposition 8, etc.

are often added. The rest of this paper is organized as follows. Section 2 shows preliminaries where new propositions proved in Appendix are mentioned. Section 3 presents an ABF translated from an EDLP, the definition of its argument, the semantic relationship between an EDLP and the corresponding ABF, the notion of consistency in ABFs, and the semantic relationship between a consistent EDLP and the corresponding consistent ABF. Section 4 shows the relationships between our proposed ABFs and nonmonotonic reasoning formalisms such as disjunctive default logic and prioritized circumscription. Section 5 shows the correspondence between the possible model semantics of EDLPs and ABA semantics of our ABFs. Section 6 discusses related work. Section 7 presents conclusions. Appendix contains new propositions relating ELPs and ABFs.

2. Preliminaries

2.1. Assumption-based argumentation

An ABA framework [5,9,10] is a tuple $⟨ L, R, A, \bar{} \bar{} ⟩$ , where ( $L, R$ ) is a deductive system, consisting of a formal language (a set of sentences) $L$ and a set $R$ of inference rules of the form: $b_{0} \leftarrow b_{1}, \dots, b_{m} (b_{i} \in L for 0 ⩽ i ⩽ m$ ), $A \subseteq L$ is a (non-empty) set of assumptions, and $\bar{} \bar{}$ is a total mapping from $A$ into $L$ , which we call a contrariness operator. $\overline{α}$ is referred to as the contrary of $α \in A$ . For a rule $r \in R$ of the form $b_{0} \leftarrow b_{1}, \dots, b_{m}$ , let the head be $head (r) = b_{0}$ and the body be $body (r) = {b_{1}, \dots, b_{m}}$ . We enforce that ABA frameworks are flat, namely assumptions in $A$ do not appear in the heads of rules in $R$ . In an ABA framework, arguments and $attacks$ are defined as follows.

Definition 1 ([10,11]).

Let $⟨ L, R, A, \bar{} \bar{} ⟩$ be an ABA framework. An argument for the conclusion (or claim) $c \in L$ supported by $K \subseteq A$ ( $K ⊢ c$ in short) is a (finite) tree with nodes labelled by sentences in $L$ or by the special symbol $τ \notin L$ representing “true”, such that

the root is labelled by c,

for every node N

if N is a leaf then N is labelled by an assumption in $A$ or by τ;

if N is not a leaf and $b_{0}$ is the label of N, then there is an inference rule $b_{0} \leftarrow b_{1}, \dots, b_{m} (m ⩾ 0$ ) and either $m = 0$ and the child of N is labelled by τ or $m > 0$ and N has m children, labelled by $b_{1}, \dots, b_{m}$ respectively,

K is the set of all assumptions labelling the leaves.

attacks

between arguments and

attacks

between sets of assumptions are defined respectively as follows.

An argument $K_{1} ⊢ c_{1}$ $attacks$ an argument $K_{2} ⊢ c_{2}$ iff $c_{1} = \overline{α}$ for some $α \in K_{2}$ .

For $Δ, Δ^{'} \subseteq A$ , and $α \in A$ , Δ $attacks$ α iff Δ enables the construction of an argument for conclusion $\overline{α}$ . Accordingly, Δ $attacks$ $Δ^{'}$ if Δ $attacks$ some $α \in Δ^{'}$ .

A set of arguments $Args$ is conflict-free iff $∄ A, B \in Args$ such that $A attacks B$ . $Args$ defends an argument A iff each argument that attacks A is attacked by an argument in $Args$ . On the other hand, a set of assumptions Δ is conflict-free iff Δ does not attack itself. Δ defends $α \in A$ iff each $Δ^{'} \subseteq A$ that attacks α is attacked by Δ.

Let $A F_{F} = (A R, attacks)$ be the abstract argumentation (AA) framework [8] generated from an ABA framework $F$ , where $A R$ is the set of all arguments such that $a \in A R$ iff an argument $a : K ⊢ c$ is in $F$ , and $(a, b) \in attacks$ in $A F_{F}$ iff a $attacks$ b in $F$ [11].

Let $σ \in {complete, preferred, grounded, stable, ideal}$ be the name of the argumentation semantics. The ABA semantics is given by σ argument extensions as well as by σ assumption extensions. A σ argument extension $Args \subseteq A R$ and a σ assumption extension $Δ \subseteq A$ are defined respectively as follows.

$Args \subseteq A R$ is: admissible iff $Args$ is conflict-free and defends all its elements; a complete argument extension iff $Args$ is admissible and contains all arguments it defends; a preferred (resp. grounded) argument extension iff it is a (subset-)maximal (resp. (subset-)minimal) complete argument extension; a stable argument extension iff it is conflict-free and attacks every argument in $A R ∖ Args$ ; an ideal argument extension iff it is a (subset-)maximal complete argument extension that is contained in each preferred argument extension. In contrast, $Δ \subseteq A$ is: admissible iff Δ is conflict-free and defends all its elements; a complete assumption extension iff Δ is admissible and contains all assumptions it defends; a preferred (resp. grounded) assumption extension iff it is a (subset-)maximal (resp. (subset-)minimal) complete assumption extension; a stable assumption extension iff it is conflict-free and attacks every $ψ \in A ∖ Δ$ ; an ideal assumption extension iff it is a (subset-)maximal complete assumption extension that is contained in each preferred assumption extension.

There is a one-to-one correspondence between σ argument extensions and σ assumption extensions.

Let claim $(A g)$ be the conclusion (or claim) of an argument $A g$ . The conclusion of a set of arguments $E$ is defined as $Concs (E) = {c \in L | c = claim (A g) for an argument A g \in E}$ .

Rationality postulates [6] are stated in terms of ABA in [12] as follows.

Definition 2 (Rationality postulates [12]).

Let $⟨ L, R, A, \bar{} \bar{} ⟩$ be a flat ABA framework, where $\bar{} \bar{}$ has the property such that contraries of assumptions are not assumptions. A set $X \subseteq L$ is said to be contradictory iff X is contradictory w.r.t. $\bar{} \bar{}$ , i.e. there exists an assumption $α \in A$ such that ${α, \overline{α}} \subseteq X$ ; or X is contradictory w.r.t. ¬, i.e. there exists $s \in L$ such that ${s, \neg s} \subseteq X$ if $L$ contains an explicit negation operator ¬. Let $C N_{R} : 2^{L} \to 2^{L}$ be a consequence operator. For a set $X \subseteq L$ , $C N_{R} (X)$ is the smallest set such that $X \subseteq C N_{R} (X)$ , and for each rule $r \in R$ , if $body (r) \subseteq C N_{R} (X)$ then $head (r) \in C N_{R} (X)$ . X is closed iff $X = C N_{R} (X)$ . A set $X \subseteq L$ is said to be inconsistent iff its closure $C N_{R} (X)$ is contradictory. X is said to be consistent iff it is not inconsistent. A flat ABA framework $F = ⟨ L, R, A, \bar{} \bar{} ⟩$ is said to satisfy the consistency-property (resp. the closure-property) if for each complete extension $E$ of $A F_{F}$ generated from $F$ , $Concs (E)$ is consistent (resp. $Concs (E)$ is closed).

We say that a set of arguments $E$ is consistent if $Concs (E)$ is consistent [33].

In [6], rationality postulates are defined using notions such as direct consistency, indirect consistency and closure-property. If we use the notions, it may be said that under σ argumentation semantics, $A F_{F}$ satisfies closure iff for each σ-extension $E$ of $A F_{F}$ , $Concs (E) = C N_{R} (Concs (E))$ ; $A F_{F}$ satisfies direct consistency iff for each σ-extension $E$ , $Concs (E)$ is not contradictory; and $A F_{F}$ satisfies indirect consistency iff for each σ-extension $E$ , $Concs (E)$ is consistent, that is, $C N_{R} (Concs (E))$ is not contradictory.

Heyninck and Arieli [18] proposed (generalized) assumption-based frameworks as follows. Let $L$ be a propositional language, $p, p_{i} \in L$ be atomic formulas (or atoms, for short), $ψ, ϕ \in L$ be compound formulas and $Γ, Γ^{'}, Λ \subseteq L$ be sets of formulas. $L$ contains conjunction “,” disjunction “∨”, implication “→”, a negation operator “∼”, and a propositional constant $T$ for truth.

A (propositional) logic for a language $L$ [17,18] is a pair $L =$ ( $L, ⊩$ ), where ⊩ is a (Tarskian) consequence relation for $L$ [36], which is a binary relation between sets of formulas and formulas in $L$ satisfying the conditions such that it is reflexive (if $ψ \in Γ$ then $Γ ⊩ ψ$ ), monotonic (if $Γ ⊩ ψ$ and $Γ \subseteq Γ^{'}$ , then $Γ^{'} ⊩ ψ$ ), and transitive (if $Γ ⊩ ψ$ and $Γ^{'} \cup {ψ} ⊩ ϕ$ , then $Γ \cup Γ^{'} ⊩ ϕ$ ). The $L$ -based transitive closure of a set Γ of $L$ -formulas is ${Cn}_{L} (Γ) = {ψ \in L | Γ ⊩ ψ}$ [17]. Let $℘ (\cdot)$ be the powerset operator.

Definition 3 (Assumption-based frameworks [18]).

An assumption-based framework is a tuple $ABF = ⟨ L, Γ, Λ, - ⟩$ , where $L = ⟨ L, ⊩ ⟩$ is a (propositional) Tarskian logic for a propositional language $L$ , Γ (the strict assumptions) and Λ (the candidate or defeasible assumptions) where $Λ \neq {}$ are distinct countable sets of $L$ -formulas, and −: $Λ \to ℘ (L)$ is a contrariness operator, assigning a finite set of $L$ -formulas to every defeasible assumption in Λ.

In $ABF$ , $attacks$ is defined as follows: For $Δ, Θ \subseteq Λ$ and $ψ \in Λ$ , Δ $attacks$ ψ iff $Γ \cup Δ ⊩ ϕ$ for some $ϕ \in - ψ$ . Accordingly, Δ $attacks$ Θ if Δ $attacks$ some $ψ \in Θ$ .

The usual semantics in AA frameworks [8] is adapted to their ABFs as follows.

Definition 4 (ABF semantics [5]).

Let $ABF = ⟨ L, Γ, Λ, - ⟩$ be an assumption-based framework and let $Δ \subseteq Λ$ . A set of defeasible assumptions Δ is closed iff $Δ = {α \in Λ | Γ \cup Δ ⊩ α}$ . $ABF$ is said to be flat iff every set of defeasible assumptions Δ is closed. Then Δ is conflict-free iff there is no $Δ^{'} \subseteq Δ$ that attacks some $ψ \in Δ$ . Δ is stable iff it is closed, conflict-free and attacks every $ψ \in Λ ∖ Δ$ .

2.2. Disjunctive logic programs

A disjunctive logic program (DLP) [26] is a finite set of rules of the form4

⁴
A disjunctive logic program (DLP) defined in this paper is different from a normal disjunctive logic program (NDP) defined in Section 2.3. This is because we later consider transformation to disjunctive default theories, in which not a DLP but an NDP can be transformed to a disjunctive default theory. Details about this are discussed in Example 4.

\begin{aligned} (1) & p_{1} \lor \dots \lor p_{k} \leftarrow p_{k + 1}, \dots, p_{m}, not p_{m + 1}, \dots, not p_{n}, \end{aligned}

where

n ⩾ m ⩾ k > 0

. Each

p_{i}

(

1 ⩽ i ⩽ n

) is a ground atom. The symbol

not

⁵

Gelfond and Lifschitz [15] use the symbol $not$ to denote the negation-as-failure (NAF), while Przymusinski [26] uses the symbol ∼ to denote NAF. This paper uses Gelfond and Lifschitz’s notation due to the purpose of this study.

is the negation-as-failure (NAF) operator. An atom preceded by

not

is called a NAF-atom. Let P be a DLP and

{HB}_{P}

be the Herbrand base of P, i.e. the (finite) set of all ground atoms in the language of P. Let

M \subseteq {HB}_{P}

. A set M satisfies a ground rule of the form (1) if

{p_{k + 1}, \dots, p_{m}} \subseteq M

and

{p_{m + 1}, \dots, p_{n}} \cap M = \emptyset

imply

{p_{1}, \dots, p_{k}} \cap M \neq \emptyset

. M is a model of P if it satisfies every ground rule in P. The reduct of P w.r.t. M is the DLP

P^{M} = {p_{1} \lor \dots \lor p_{k} \leftarrow p_{k + 1}, \dots, p_{m} | there is a rule of the form p_{1} \lor \dots \lor p_{k} \leftarrow p_{k + 1}, \dots, p_{m}, not p_{m + 1}, \dots, not p_{n} in P s . t . {p_{m + 1}, \dots, p_{n}} \cap M = \emptyset}

. Then M is a stable model of P if it is a ⊆-minimal model of

P^{M}

[14,26].

In [18], stable models of a DLP P are defined based on $A (P) \subseteq {HB}_{P}$ , where $A (P)$ is the set of atomic formulas that appear in P, and the symbol ∼ is used instead of $not$ to denote NAF. Heyninck and Arieli [18] denoted by $L = ⟨ L_{DLP}, ⊩ ⟩$ the logic for the language $L_{DLP}$ consisting of disjunctions of atoms ( $p_{1} \lor \dots \lor p_{n}$ , for $n ⩾ 1$ ), NAF-atoms ( $not p$ ) and rules of the form (1) of a DLP, where ⊩ is constructed for $L_{DLP}$ by three inference rules: Modus Ponens (MP), Resolution (Res) and Reasoning by Cases (RBC). (The precise form of these inference rules will be described later in Remark 1.)

The ABF induced by a DLP P is defined by ABF( $P) = ⟨ L, P, \sim A (P), - ⟩$ [18], where $L = ⟨ L_{DLP}, ⊩ ⟩$ , $\sim A (P) = {not p | p \in A (P)}$ , and $- not p = {p}$ for every $p \in A (P)$ . All the ABFs induced by DLPs are based on the same core logic $L = ⟨ L_{DLP}, ⊩ ⟩$ . Heyninck and Arieli showed a one-to-one correspondence between stable models of a DLP P and stable assumption extensions of ABF(P) as follows. Proposition 1 ([18, Proposition 2 and Proposition 3]).

Let P be a finite DLP and $M \subseteq A (P)$ . If M is a stable model of P, then $\overline{M} = {not p | p \in (A (P) ∖ M)}$ is a stable (assumption) extension of ABF(P). Conversely if $E$ is a stable (assumption) extension of ABF(P), then $\underline{E} = {p \in A (P) | not p \notin E}$ is a stable model of P.

2.3. Extended disjunctive logic programs

We consider a finite propositional extended disjunctive logic program (EDLP) [15] in this paper. An EDLP is a finite set of rules of the form: $\begin{aligned} (2) & L_{1} | \dots | L_{k} \leftarrow L_{k + 1}, \dots, L_{m}, not L_{m + 1}, \dots, not L_{n}, \end{aligned}$ where $n ⩾ m ⩾ k > 0$ . Each $L_{i}$ ( $1 ⩽ i ⩽ n$ ) is a ground literal, that is, either a ground atom A (i.e. a propositional variable) or $\neg A$ preceded by classical negation “¬”, where $\neg A$ is called a negative literal. $not$ denotes the negation-as-failure (NAF) as before, and $not L$ is called a NAF-literal. The left (resp. right) part of ← is the head (resp. the body). $body (r)$ denotes the body of a rule r from an EDLP. The symbol “|” is used to distinguish disjunction in the head of a rule from disjunction “∨” used in classical logic. An EDLP is called a normal disjunctive logic program (NDP) if ¬ does not occur in it, while an EDLP is called an extended logic program (ELP) if it contains no disjunction ( $k = 1$ ). An ELP is called a normal logic program (NLP) if ¬ does not occur in it. Let $L i t_{P}$ (resp. $H B_{P}$ ) be the set of all ground literals (resp. all ground atoms) in the language of an EDLP P. When an EDLP P is an NDP (or NLP), $L i t_{P}$ reduces to ${HB}_{P}$ .

The semantics of an EDLP is given by answer sets [15].

Definition 5 (answer sets).

Let $S \subseteq L i t_{P}$ . First, let P be a not-free EDLP (i.e. $m = n$ for each rule in P). Then, S is an answer set of P if S is a minimal set (w.r.t. ⊆) satisfying the two conditions (i), (ii):

For each rule $L_{1} | \dots | L_{k} \leftarrow L_{k + 1}, \dots, L_{m}$ in P, if ${L_{k + 1}, \dots, L_{m}} \subseteq S$ , then $L_{i} \in S$ for some i ( $1 ⩽ i ⩽ k$ ).

If S contains a pair of literals L and $\neg L$ , then $S = L i t_{P}$ .

Second, let P be any EDLP. The reduct $P^{S}$ of P w.r.t. S is the not-free EDLP $P^{S}$ such that $P^{S} = {L_{1} | \dots | L_{k} \leftarrow L_{k + 1}, \dots, L_{m} |$ there is a rule of the form $L_{1} | \dots | L_{k} \leftarrow L_{k + 1}, \dots L_{m}, not L_{m + 1}, \dots not L_{n}$ $in P s . t . {L_{m + 1}, \dots, L_{n}} \cap S = \emptyset}$ . Then S is an answer set of P if S is the answer set of $P^{S}$ .

An answer set S is consistent if $S \neq L i t_{P}$ ; otherwise S is contradictory. An EDLP P having a consistent answer set is consistent; otherwise P is inconsistent under answer set semantics.

It is considered, for an answer set S and a literal L, (i) $S ⊧ L$ iff $L \in S$ , (ii) $S ⊧ not L$ iff $L \notin S$ .

A literal $L \in L i t_{P}$ is interpreted “unknown” under the answer set semantics if $L \notin S$ and $\neg L \notin S$ for any answer set S of an EDLP P.

The following example illustrates the difference between “|” and “∨” in logic programming.

Example 2.
The EDLP ${p | \neg p \leftarrow}$ has two answer sets ${p}$ and ${\neg p}$ . If we use ∨ instead of |, however, ${p \lor \neg p \leftarrow}$ is logically equivalent to ${p \leftarrow p}$ under classical logic, which has the minimal model (stable model) ${}$ . Hence, | and ∨ have different meanings in general.

The semantics of an EDLP is also given by (four-valued) paraconsistent stable models (or p-stable models6
⁶
In this paper, the term “p-stable models” is used not as an abbreviation of partial stable model semantics by Przymusinski [26] but as that of paraconsistent stable model semantics by Sakama and Inoue [28]. In [28], a p-stable model is defined for an EDLP whose rule head uses ∨ rather than |. However notice that, a p-stable model is defined regardless the connective of disjunction used in rule head (e.g. “∨”, “|”).

) [28], which are regarded as answer sets defined without the condition (ii) in Definition 5, denoting that we don’t get the trivialization or deductive explosion of inconsistent (p-stable) models.
Definition 6 (p-stable models).

Let $M \subseteq L i t_{P}$ . First, let P be a not-free EDLP (i.e. $m = n$ for each rule). Then, M is a p-stable model of P if M is a minimal set (w.r.t. ⊆) satisfying the following condition: For each rule $L_{1} | \dots | L_{k} \leftarrow L_{k + 1}, \dots, L_{m}$ in P, if ${L_{k + 1}, \dots, L_{m}} \subseteq M$ , then $L_{i} \in M$ for some i ( $1 ⩽ i ⩽ k$ ). Second, let P be any EDLP. The reduct $P^{M}$ of P w.r.t. M is the not-free EDLP $P^{M}$ defined in Definition 5. Then M is a p-stable model of P if M is a p-stable model of $P^{M}$ .

In [28], $I \subseteq L i t_{P}$ is considered as an interpretation which is defined as a function $I : L i t_{P} \to {t, f, ⊤, ⊥}$ , where $t, f, ⊤, ⊥$ are the four-valued truth values denoting true, false, contradictory, and undefined. Then, the truth value $I (L)$ is assigned to each literal $L \in L i t_{P}$ such that:

(i) $I (L) = t$ if $L \in I$ and $\neg L \notin I$ , (ii) $I (L) = f$ if $L \notin I$ and $\neg L \in I$ ,

(iii) $I (L) = ⊤$ if both $L \in I$ and $\neg L \in I$ , (iv) $I (L) = ⊥$ otherwise.

A p-stable model M is inconsistent if M contains a pair of complementary literals (in other words, there exists a literal $L \in M$ s.t. $M (L) = ⊤$ ); otherwise M is consistent. An EDLP P is consistent if P has a consistent p-stable model; otherwise P is inconsistent under paraconsistent stable model semantics.

Example 3.
Consider the EDLP $P = {\neg p \leftarrow, p \leftarrow, q \leftarrow}$ . P has the inconsistent answer set $L i t_{P}$ which is contradictory both w.r.t. p and q. P has also the inconsistent p-stable model $M = {\neg p, p, q}$ , where contradiction is localized w.r.t. p, and the consistent information about q is obtained (i.e. $M (p) = ⊤$ , $M (q) = t$ ). This shows that a p-stable model is paraconsistent even if it is inconsistent.

Gelfond et al. [16] proposed a disjunctive default theory (ddt, for short), which is a set of disjunctive defaults whose form is $\frac{α : β_{1}, \dots, β_{m}}{γ_{1} | γ_{2} | \dots | γ_{n}}$ . The semantics of a ddt is given by extensions which are generalization of Reiter’s extensions for a default theory [27]. Regarding logic programming, they showed in the following theorem that a propositional EDLP P can be translated into a disjunctive default theory $emb (P)$ by replacing every rule in P of the form (2) with the disjunctive default $\begin{matrix} \frac{L_{k + 1} \land \dots \land L_{m} : \neg L_{m + 1}, \dots, \neg L_{n}}{L_{1} | \dots | L_{k}} . \end{matrix}$

The intuition behind the disjunctive default can be “if each of $L_{k + 1}, \dots, L_{m}$ is believed and if each of $\neg L_{m + 1}, \dots, \neg L_{n}$ can be consistently believed, then $L_{i}$ is believed for some i ( $1 ⩽ i ⩽ k$ )”.

The disjunctive defaults of this form are used to compute extensions of the ddt $emb (P)$ . There exists the correspondence between answer sets of an EDLP P and extensions of $emb (P)$ as follows.
Theorem 1 ([16, Theorem 7.2]).

Let P be a propositional EDLP. Then S is an answer set of P iff S is the set of all literals from an extension of the disjunctive default theory $emb (P)$ .

Let $F (P) = ⟨ L_{P}, P, A_{P}, \bar{} \bar{} ⟩$ be the ABA framework translated from an ELP P, where ${NAF}_{P} = {not L | L \in L i t_{P}}$ , $L_{P} = L i t_{P} \cup {NAF}_{P}$ , $A_{P} = {NAF}_{P}$ , and $\overline{not L} = L$ for each $not L \in A_{P}$ . Given $M \subseteq L i t_{P}$ , let $Δ_{M} = {not L | L \in L i t_{P} ∖ M}$ .7

⁷
In [32], $\neg . C M$ is used rather than $Δ_{M}$ to refer to the set ${not L | L \in L i t_{P} ∖ M}$ . However for notational convenience, $Δ_{M}$ is used instead of $\neg . C M$ to refer to this set in this paper.

Let

P_{t r} \overset{def}{=} P \cup {L \leftarrow p, \neg p | p \in L i t_{P}, L \in L i t_{P}}

be the ELP obtained from an ELP P by incorporating the trivialization rules [28]. It was shown that answer sets (resp. paraconsistent stable models) of an ELP P can be captured by stable argument extensions of the ABA framework translated from the ELP

P_{t r}

(resp. P) as follows.

Theorem 2 ([32, Theorem 3]).

Let P be an ELP and $M \subseteq L i t_{P}$ . Then M is a p-stable model of P iff there is a stable (argument) extension $E$ of the ABA framework $F (P)$ such that $M \cup Δ_{M} = Concs (E)$ (in other words, $M = Concs (E) \cap L i t_{P}$ ).

Theorem 3 ([32, Theorem 4]).

Let P be an ELP and $S \subseteq L i t_{P}$ . Then S is an answer set of P iff there is a stable (argument) extension $E_{t r}$ of the ABA framework $F (P_{t r})$ such that $S \cup Δ_{S} = Concs (E_{t r})$ (in other words, $S = Concs (E_{t r}) \cap L i t_{P}$ ).

For a consistent ELP, the following theorem holds.

Theorem 4 ([33, Theorem 5]).

Let P be a consistent ELP and $S \subseteq L i t_{P}$ . Then S is an answer set of P iff there is a consistent stable (argument) extension $E$ of the ABA framework $F (P)$ such that $S \cup Δ_{S} = Concs (E)$ .

Notice that $Δ_{M}$ in Theorem 2 (resp. $Δ_{S}$ in Theorem 3) is a stable assumption extension of the ABA framework $F (P)$ (resp. $F (P_{t r})$ ), while $Δ_{S}$ in Theorem 4 is a consistent stable assumption extension of the ABF $F (P)$ due to Proposition 12, Proposition 13 and Proposition 14 as proved in Appendix respectively.

3. ABA for extended disjunctive logic programming

3.1. Assumption-based frameworks translated from EDLPs

We propose an assumption-based framework (ABF) translated from an EDLP, which incorporates explicit negation along with | instead of ∨ in Heyninck and Arieli’s ABF induced by a DLP to achieve our purpose shown in the introduction. An ABF translated from an EDLP is based on the logic constructed by three inference rules: Modus Ponens (MP), Resolution (Res) and Reasoning by Cases (RBC): $\begin{array}{rcl} [MP] & \frac{ψ \leftarrow ϕ_{1}, \dots, ϕ_{n} ϕ_{1} ϕ_{2} \dots ϕ_{n}}{ψ} \\ [Res] & \frac{ψ_{1}^{'} | \dots | ψ_{m}^{'} | ℓ_{1} | \dots | ℓ_{n} | ψ_{1}^{″} | \dots | ψ_{k}^{″} not ℓ_{1} \dots not ℓ_{n}}{ψ_{1}^{'} | \dots | ψ_{m}^{'} | ψ_{1}^{″} | \dots | ψ_{k}^{″}} \\ ℓ_{1} ℓ_{2} ℓ_{n} \\ ⋮ ⋮ ⋮ \\ [RBC] & \frac{ψ ψ \dots ψ ℓ_{1} | \dots | ℓ_{n}}{ψ} \end{array}$ where | is the connective of a disjunction, $ℓ_{i}$ is a propositional literal, each $ϕ_{i} \in {ℓ_{i}, not ℓ_{i}}$ is a propositional literal or its NAF-literal, and ψ, $ψ_{i}$ are disjunctions of propositional literals using |. $ψ \leftarrow ϕ_{1}, \dots, ϕ_{n}$ is a rule of the form (2). Since $ψ \leftarrow$ is identified with $ψ \leftarrow T$ , $[MP]$ implies Reflexivity: $[Ref] \frac{ψ \leftarrow}{ψ}$ .

Definition 7.
We denote by $L = ⟨ L_{EDLP}, ⊩ ⟩$ the logic for the language $L_{EDLP}$ which consists of disjunctions of propositional literals ( $ℓ_{1} | \dots | ℓ_{n}$ , for $n ⩾ 1$ ), NAF-literals ( $not ℓ$ ) and rules of the form (2) of an EDLP, where ⊩ is constructed for $L_{EDLP}$ by three inference rules: Modus Ponens (MP), Resolution (Res) and Reasoning by Cases (RBC) above. In other words, ⊩ denotes derivability using three inference rules: $[MP]$ (including $[Ref]$ ), $[Res]$ and $[RBC]$ .
Remark 1.
Heyninck and Arieli’s ABF [18] is based on the logic $L = ⟨ L_{DLP}, ⊩ ⟩$ , where ⊩ is constructed for $L_{DLP}$ by three inference rules: $[MP]$ , $[Res]$ and $[RBC]$ having the restricted forms such that | (resp. a literal $ℓ_{i}$ ) is replaced with ∨ (resp. an atom $p_{i}$ ), each $ϕ_{i} \in {p_{i}, not p_{i}}$ is an atom or a NAF-atom, and ψ, $ψ_{i}$ are disjunctions of atoms ( $p_{1} \lor \dots \lor p_{n}$ , for $n ⩾ 1$ ).

$Σ ⊩ φ$ holds iff φ is either in Σ or is derived from Σ using the three inference rules above. According to Definition 3, $Σ ⊩ φ$ iff $φ \in {Cn}_{L} (Σ)$ , where ${Cn}_{L} (Σ)$ is the $L$ -based transitive closure of Σ (namely, the ⊆-smallest set that contains Σ and is closed under $[MP]$ , $[Res]$ and $[RBC]$ ). Notice that for any $φ \in {Cn}_{L} (Σ)$ , if φ is not of the form $ℓ_{1} | \dots | ℓ_{n}$ , then $φ \in Σ$ .

For a special ABF $= ⟨ L, Γ, Λ, - ⟩$ such that each defeasible assumption from Λ has a unique contrary (i.e. $| - α | = 1$ 8
⁸
For a set S, $| S |$ denotes the cardinality of S.

for $\forall α \in Λ$ ), we may denote such an ABF by a tuple $⟨ L, Γ, Λ$ , $\bar{} \bar{} ⟩$ , where $\bar{} \bar{}$ is a total mapping from Λ into $L$ , and $\overline{α} \in L$ is the contrary of $α \in Λ$ .

In what follows, let ${NAF}_{P} = {not ℓ | ℓ \in {Lit}_{P}}$ and $L_{P} = L i t_{P} \cup {NAF}_{P}$ for an EDLP P. We are now ready to define an ABF translated from an EDLP.
Definition 8.
Let P be an EDLP. The assumption-based framework (ABF) translated from P is defined by ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ , where $L = ⟨ L_{EDLP}, ⊩ ⟩$ , $A_{P} = {NAF}_{P} = {not ℓ | ℓ \in {Lit}_{P}}$ , and $\overline{not ℓ} = ℓ$ for every $not ℓ \in A_{P}$ .

In the following, we show the ABF translated from an EDLP P is always flat.
Proposition 2.
ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ translated from an EDLP P is flat.
Proof.
Let $Δ \subseteq A_{P}$ . Since ⊩ is reflexive, it holds that (i) $P \cup Δ ⊩ α$ for $\forall α \in Δ$ . On the other hand, it holds that (ii) $P \cup Δ ⊮ β$ for $\forall β \in A_{P} ∖ Δ$ , since NAF-literals, which is the only form the defeasible assumptions in ABF(P) can take, do not occur in the heads of rules from P. Then due to (i),(ii), it holds that $Δ = {α \in A_{P} | P \cup Δ ⊩ α}$ for $\forall Δ \subseteq A_{P}$ . Thus ABF(P) is flat. □

In ABF(P), the semantics is given by assumption extensions as follows.
Definition 9.
Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P. Let $Δ \subseteq A_{P}$ and $α \in A_{P}$ . Δ is conflict-free iff there is no $Δ^{'} \subseteq Δ$ that attacks some $ψ \in Δ$ . Δ defends α iff each $Δ^{'}$ that attacks α is attacked by Δ. Then Δ is: admissible iff Δ is conflict-free and defends all its elements; a complete assumption extension iff Δ is admissible and contains all assumptions it defends; a preferred (resp. grounded) assumption extension iff it is a (subset-)maximal (resp. (subset-)minimal) complete assumption extension; a stable assumption extension iff it is is conflict-free and attacks every $ψ \in A_{P} ∖ Δ$ ; an ideal assumption extension iff it is a (subset-)maximal complete assumption extension that is contained in each preferred assumption extension.

In ABF(P), consistency of a set of literals and NAF-literals $X \subseteq L_{P}$ is defined using a consequence operator ${CN}_{P}$ which is adapted from the $C N_{R}$ operator found in standard ABA. Definition 10.
Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P, where $L = ⟨ L_{EDLP}, ⊩ ⟩$ . For a set $X \subseteq L_{P} = L i t_{P} \cup {NAF}_{P}$ , X is said to be contradictory iff X is contradictory w.r.t. $\bar{} \bar{}$ , i.e. there exists an assumption $α \in A_{P}$ s.t. ${α, \overline{α}} \subseteq X$ ; or X is contradictory w.r.t. ¬, i.e. there exists $s \in L_{P}$ s.t. ${s, \neg s} \subseteq X$ . Let ${CN}_{P} : ℘ (L_{P}) \to ℘ (L_{P})$ be a consequence operator such that for $X \subseteq L_{P}$ , $\begin{matrix} {CN}_{P} (X) \overset{def}{=} {ϕ \in L_{P} | P \cup X ⊩ ϕ} = {Cn}_{L} (P \cup X) \cap L_{P} . \end{matrix}$

${CN}_{P} (X)$ is said to be the closure of X. X is said to be closed w.r.t. ${CN}_{P}$ iff $X = {CN}_{P} (X)$ . A set $X \subseteq L_{P}$ is said to be inconsistent iff the closure ${CN}_{P} (X)$ is contradictory. X is said to be consistent iff it is not inconsistent.

3.2. Correspondence between answer sets of an EDLP and stable assumption extensions

Proposition 1 for a DLP [18] is generalized to Proposition 4 and Proposition 5 for an EDLP shown below. To this end, firstly as the extension of Proposition 1, we prepare the following corollary for a DLP whose stable models are defined based on $H B_{P}$ .

Corollary 1.
The extended ABF induced by a DLP P is defined by ABF( $P) = ⟨ L, P, \sim H B_{P}, - ⟩$ , where $L = ⟨ L_{DLP}, ⊩ ⟩$ , $\sim H B_{P} = {not p | p \in H B_{P}}$ and $- not p = {p}$ for every $p \in H B_{P}$ . Let $M \subseteq H B_{P}$ . (i) If M is a stable model of P, then $Δ = {not p | p \in ({HB}_{P} ∖ M)}$ is a stable assumption extension of ABF(P). (ii) Conversely if Δ is a stable assumption extension of ABF(P), then $M = {p \in {HB}_{P} | not p \notin Δ}$ is a stable model of P.
Proof.
Let $Δ_{A (P)} = {not p | p \in (H B_{P} ∖ A (P))}$ .
Let M be a stable model of P, where $M \subseteq A (P) \subseteq H B_{P}$ . Then for $\overline{M} = {not p | p \in (A (P) ∖ M)}$ , it holds that $\overline{M} \cup Δ_{A (P)} = Δ = {not p | p \in (H P_{P} ∖ M)}$ . Based on [18, Corollary 1], it holds that, $\begin{array}{r} for p \in A (P), p \in M iff p \in {Cn}_{L} (P \cup \overline{M}) iff p \in {Cn}_{L} (P \cup Δ) . Hence, \end{array}$

$for p \in {HB}_{P}, p \in M iff p \in {Cn}_{L} (P \cup Δ) iff P \cup Δ ⊩ p .$

Thus Δ is conflict-free and attacks every $not p \notin Δ$ for $p \in H B_{P}$ , which means that Δ is a stable assumption extension of ABF(P).

Conversely, let $Δ \subseteq {HB}_{P}$ be a stable assumption extension of ABF(P). Then for $\forall α \in {not p \notin Δ | p \in H B_{P}}$ , Δ attacks α. This means that, $P \cup Δ ⊩ p$ , that is, $p \in {Cn}_{L} (P \cup Δ)$ for $not p \notin Δ$ where $p \in H B_{P}$ .

On the other hand, based on [18, Corollary 1], it holds that, for a stable model M of P, $\begin{aligned} (3) & \begin{aligned} p \in M iff p \in {Cn}_{L} (P \cup \overline{M}) for p \in A (P) \\ iff p \in {Cn}_{L} (P \cup \overline{M} \cup Δ_{A (P)}) = {Cn}_{L} (P \cup Δ) for p \in H B_{P} . \end{aligned} \end{aligned}$

Thus it holds that, $p \in M$ for $not p \notin Δ$ and $p \in H B_{P}$ where Δ is a stable assumption extension. □

Next, Corollary 1 for a DLP is mapped to Proposition 3 for an NDP based on two lemmas about DLPs and NDPs as follows.
Lemma 1.
Let P be a propositional NDP and $P_{D}$ be the DLP translated from P which is obtained by replacing a rule: $p_{1} | \dots | p_{k} \leftarrow p_{k + 1}, \dots, p_{m}, not p_{m + 1}, \dots, not p_{n}$ from P with the rule $p_{1} \lor \dots \lor p_{k} \leftarrow p_{k + 1}, \dots, p_{m}, not p_{m + 1}, \dots, not p_{n}$ , where ${HB}_{P_{D}} = {HB}_{P}$ . Let $M \subseteq H B_{P}$ . Then M is an answer set of P iff M is a stable model of $P_{D}$ .
Proof.
Given $M \subseteq H B_{P}$ , it holds that, ${p_{1}, \dots, p_{k}} \cap M \neq \emptyset$ iff $p_{i} \in M$ for some i ( $1 ⩽ i ⩽ k$ ).

This is used in the following proof.

⇒: Suppose that $M \subseteq H B_{P}$ is an answer set of P. First, let P be a not-free NDP (i.e., $m = n$ in (2)). Since M is an answer set of P, M is a ⊆-minimal set satisfying the condition such that if ${p_{k + 1}, \dots, p_{m}} \subseteq M$ , then some $p_{i} \in M$ ( $1 ⩽ i ⩽ k$ ) for each rule $p_{1} | \dots | p_{k} \leftarrow p_{k + 1}, \dots, p_{m}$ in P. Hence M is a ⊆-minimal set satisfying the condition such that if ${p_{k + 1}, \dots, p_{m}} \subseteq M$ , then ${p_{1}, \dots, p_{k}} \cap M \neq \emptyset$ for each rule $p_{1} \lor \dots \lor p_{k} \leftarrow p_{k + 1}, \dots, p_{m}$ in $P_{D}$ , which means that M is a ⊆-minimal model of $P_{D}$ . Now since ${(P_{D})}^{M} = P_{D}$ holds for the not-free $P_{D}$ , M is a stable model of $P_{D}$ . Second, let P be any NDP. Since M is an answer set of P, M is an answer set of the not-free NDP $P^{M}$ . Therefore, M is a stable model of the not-free DLP ${(P_{D})}^{M}$ , which means that M is a ⊆-minimal model of the DLP ${({(P_{D})}^{M})}^{M} = {(P_{D})}^{M}$ . Hence M is a stable model of $P_{D}$ .

⇐: Suppose that $M \subseteq H B_{P}$ is a stable model of $P_{D}$ . First, let $P_{D}$ be the not-free DLP (i.e., $m = n$ in (1)). Since M is a stable model of the not-free $P_{D}$ , M is a ⊆-minimal model of ${(P_{D})}^{M} = P_{D}$ which satisfies the condition such that if ${p_{k + 1}, \dots, p_{m}} \subseteq M$ , then ${p_{1}, \dots, p_{k}} \cap M \neq \emptyset$ for each rule $p_{1} \lor \dots \lor p_{k} \leftarrow p_{k + 1}, \dots, p_{m}$ in ${(P_{D})}^{M} = P_{D}$ . Therefore, M is a ⊆-minimal set of P satisfying the condition such that if ${p_{k + 1}, \dots, p_{m}} \subseteq M$ , then some $p_{i} \in M$ ( $1 ⩽ i ⩽ k$ ) for each rule $p_{1} | \dots | p_{k} \leftarrow p_{k + 1}, \dots, p_{m}$ in P, which means that M is an answer set of the not-free NDP P. Second, let $P_{D}$ be any DLP. Since M is a stable model of $P_{D}$ , M is a ⊆-minimal model of the DLP ${(P_{D})}^{M}$ which is not-free. Hence M is a ⊆-minimal set satisfying the condition such that if ${p_{k + 1}, \dots, p_{m}} \subseteq M$ , then ${p_{1}, \dots, p_{k}} \cap M \neq \emptyset$ for each rule $p_{1} \lor \dots \lor p_{k} \leftarrow p_{k + 1}, \dots, p_{m}$ in ${(P_{D})}^{M}$ , which means that, M is a ⊆-minimal set satisfying the condition such that if ${p_{k + 1}, \dots, p_{m}} \subseteq M$ , then some $p_{i} \in M$ ( $1 ⩽ i ⩽ k$ ) for each rule $p_{1} | \dots | p_{k} \leftarrow p_{k + 1}, \dots, p_{m}$ in $P^{M}$ . Therefore M is an answer set of $P^{M}$ . Hence M is an answer set of P. □

Though Lemma 1 holds, the difference between NDPs and DLPs appears when considering their relation to (disjunctive) default logic as shown in the following example. This implies that an NDP can be transformed to a disjunctive default theory but a DLP can never be done so.
Example 4.
Heyninck and Arieli considered the DLP $π_{1} = {p \lor q \leftarrow, q \leftarrow p, p \leftarrow q}$ in [18, Example 1], which has the unique stable model $M = {p, q}$ . By replacing ∨ with | in $π_{1}$ , we obtain the NDP $π_{2} = {p | q \leftarrow, q \leftarrow p, p \leftarrow q}$ which has the unique answer set $S = {p, q}$ . Then thanks to Gelfond et al.’s Theorem 1 [16, Theorem 7.2], $π_{2}$ can be translated into the disjunctive default theory $d_{2}$ (namely, $e m b (π_{2})$ ) below. Instead, $π_{1}$ is expressed by the standard default theory $d_{1}$ as follows since it uses the connective ∨ rather than | in rule head. $\begin{matrix} d_{1} = {\frac{p :}{q}, \frac{q :}{p}, p \lor q}, d_{2} = {\frac{p :}{q}, \frac{q :}{p}, p | q} . \end{matrix}$ As a result, $d_{1}$ has the unique extension $E_{1}$ consisting of $p \lor q$ and its logical consequences based on Reiter’s default theory [27], while $d_{2}$ has the unique extension $E_{2}$ consisting of p, q and their logical consequences based on Gelfond et al.’s disjunctive default theory [16]. Therefore there is no relationship between $E_{1}$ and M, while there is the correspondence between $E_{2}$ and S such that $S = E_{2} \cap L i t_{π_{2}}$ . Thus the default theory $d_{1}$ corresponding to the DLP $π_{1}$ has the same difficulty as $D_{1}$ addressed in Example 1, while the disjunctive default theory $d_{2}$ corresponding to the NDP $π_{2}$ avoids such a difficulty.

The following lemma is also needed to obtain Proposition 3 for an NDP.
Lemma 2.
Let $M \subseteq H B_{P}$ be an answer set of an NDP P and let $Δ_{M} = {not L | L \in {HB}_{P} ∖ M}$ . Then $p \in M$ iff $p \in {Cn}_{L} (P \cup Δ_{M})$ for $p \in {HB}_{P}$ .
Proof.
Let $P_{D}$ be the DLP translated from an NDP P as defined in Lemma 1.

$p \in M$ iff $p \in {Cn}_{L} (P_{D} \cup Δ_{M})$ for $p \in {HB}_{P}$ , where $L = ⟨ L_{DLP}, ⊩ ⟩$ , (due to Lemma 1 and (3))

iff $p \in {Cn}_{L} (P \cup Δ_{M})$ for $p \in {HB}_{P}$ , where $L = ⟨ L_{EDLP}, ⊩ ⟩$ . □
Proposition 3.
Let P be an NDP, $M \subseteq H B_{P}$ , and ABF $(P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ , where $L = ⟨ L_{EDLP}, ⊩ ⟩$ . (i) If M is an answer set of P, then $Δ = {not p | p \in ({HB}_{P} ∖ M)}$ is a stable assumption extension of ABF(P). (ii) Conversely if Δ is a stable assumption extension of ABF(P), then $M = {p \in {HB}_{P} | not p \notin Δ}$ is an answer set of P.
Proof.
This follows from Corollary 1 for a DLP based on Lemma 1 and Lemma 2. □

Now, we show that p-stable models (resp. answer sets) of an EDLP P are captured by stable assumption extensions of the ABF translated from P (resp. $P_{t r}$ ). To this end, the notation “+” [15,28] is used.

A positive form of an EDLP P [28] is the NDP $P^{+}$ which is obtained by replacing each negative literal $\neg L$ in P (where L is an atom) with a corresponding newly introduced atom $L^{'}$ (called the positive form of $\neg L$ [15]) in $P^{+}$ . Let $M^{+}$ be an answer set of such $P^{+}$ . Then the following lemma holds by definition.
Lemma 3.
Let P be an EDLP and $P^{+}$ be its positive form. Let $M \subseteq L i t_{P}$ . Then M is a p-stable model iff $M^{+}$ is an answer set of $P^{+}$ .
Proposition 4.
Let ABF $(P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P and $M \subseteq L i t_{P}$ .

If M is a p-stable model of P, then $Δ = {not ℓ | ℓ \in (L i t_{P} ∖ M)}$ is a stable assumption extension of ABF(P). Conversely if Δ is a stable assumption extension of ABF(P), then $M = {ℓ \in L i t_{P} | not ℓ \notin Δ}$ is a p-stable model of P.
Proof.
Let $P^{+}$ be the NDP which is the positive form of an EDLP P. For a set $S \subseteq L i t_{P}$ , let $S^{+}$ be the set obtained by replacing each negative literal $\neg L$ in S with a newly introduced atom $L^{'}$ . Then the Herbrand base ${HB}_{P^{+}}$ of $P^{+}$ is ${(L i t_{P})}^{+}$ . Moreover, if a set $U^{+} \subseteq {HB}_{P^{+}}$ is given, we denote by U the set obtained by replacing each newly introduced atom $L^{'} \in U^{+}$ with the corresponding original literal $\neg L \in L i t_{P}$ .
Let M be a p-stable model of an EDLP P. Then due to Lemma 3, $M^{+}$ is an answer set of the NDP $P^{+}$ . Hence $Δ_{M^{+}} = {not p | p \in ({HB}_{P^{+}} ∖ M^{+})}$ is a stable assumption extension of ABF( $P^{+}$ ) due to Proposition 3. Thus $Δ = Δ_{M} = {not ℓ | ℓ \in (L i t_{P} ∖ M)}$ is a stable assumption extension of ABF(P).

Conversely, let $Δ = Δ_{M} = {not ℓ | ℓ \in (L i t_{P} ∖ M)}$ be a stable assumption extension of ABF(P). Then $Δ_{M^{+}} = {not p | p \in ({HB}_{P^{+}} ∖ M^{+})} = {not p | p \in {(L i t_{P} ∖ M)}^{+})}$ is a stable assumption extension of ABF( $P^{+}$ ). Thus due to Proposition 3, $M^{+} = {p \in {HB}_{P^{+}} | not p \notin Δ_{M^{+}}}$ is the answer set of the NDP $P^{+}$ . Hence $M = {ℓ \in L i t_{P} | not ℓ \notin Δ_{M}}$ where $Δ = Δ_{M}$ is a p-stable model of P due to Lemma 3. □

Proposition 5.
Let P be an EDLP, $S \subseteq L i t_{P}$ and ABF( $P_{t r}) = ⟨ L, P_{t r}, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from the EDLP $P_{t r} = P \cup {L \leftarrow p, \neg p | p \in L i t_{P}, L \in L i t_{P}}$ , where $L_{P_{t r}} = L_{P}$ . If S is an answer set of P, then $Δ = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ is a stable assumption extension of ABF( $P_{t r}$ ). Conversely if Δ is a stable assumption extension of ABF( $P_{t r}$ ), then $S = {ℓ \in L i t_{P} | not ℓ \notin Δ}$ is an answer set of P.
Proof.
[28, Theorem 3.5] shows that S is an answer set of an EDLP P iff S is p-stable model of $P_{t r}$ . Then this follows from Proposition 4 based on [28, Theorem 3.5]. □

${CN}_{P} (Δ)$ gives us the conclusion of an assumption extension Δ. In Proposition 6 below, we show the relationship between answer sets (or p-stable models) of an EDLP and the conclusions of assumption extensions of the translated ABF.
Lemma 4.
Let M be a p-stable model of an EDLP P and $Δ_{M} = {not ℓ | ℓ \in (L i t_{P} ∖ M)}$ . Then

$ℓ \in M$ iff $ℓ \in {Cn}_{L} (P \cup Δ_{M})$ for $ℓ \in L i t_{P}$ .
Proof.
This follows from Lemma 2 based on the renaming technique used in the proof of Proposition 4. □
Proposition 6.
Let P be an EDLP, M (resp. S) be a p-stable model (resp. an answer set) of P, and $Δ_{M} = {not ℓ | ℓ \in (L i t_{P} ∖ M)}$ (resp. $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ ) be the stable assumption extension of ABF(P) (resp. ABF( $P_{t r}$ )). Then it holds that, ${CN}_{P} (Δ_{M}) = M \cup Δ_{M}$ , and ${CN}_{P_{t r}} (Δ_{S}) = S \cup Δ_{S}$ .
Proof.

Let M be a p-stable model of an EDLP P. Then for $ℓ \in L i t_{P}$ , it holds that $ℓ \in M$ iff $ℓ \in {Cn}_{L} (P \cup Δ_{M})$ iff $ℓ \in {CN}_{P} (Δ_{M})$ according to Lemma 4. Besides $not ℓ \in Δ_{M}$ iff $not ℓ \in {CN}_{P} (Δ_{M})$ . Hence ${CN}_{P} (Δ_{M}) = M \cup Δ_{M}$ holds.

Let S be an answer set of P. Then S is a p-stable model of $P_{t r}$ due to [28, Theorem 3.5]. Besides $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ is the stable assumption extension of ABF( $P_{t r}$ ) due to Proposition 5. Then by applying the result of Item 1 to a p-stable model S of $P_{t r}$ , we obtain ${CN}_{P_{t r}} (Δ_{S}) = S \cup Δ_{S}$ . □

In all examples shown in this paper, we assume that $L i t_{P}$ i.e. the set of all ground literals in the language of an EDLP P coincides with the set ${L | L or \neg L appears in P}$ 9
⁹
This assumption is also used in all examples given in [32,33] though it is not stated there.

where $\neg \neg L = L$ . Example 5 (Cont. Example 1 ).

Consider Kyoto protocol problem. For the EDLP $P_{1}$ , $L i t_{P_{1}} = {p, r, y, f, k, \neg p, \neg r, \neg y, \neg f, \neg k}$ , and ${(P_{1})}_{t r} = P_{1} \cup {L \leftarrow p, \neg p | p \in L i t_{P_{1}}, L \in L i t_{P_{1}}}$ . Answer sets of ${(P_{1})}_{t r}$ coincide with those of $P_{1}$ , that is, $S_{1} = {p, r, k}$ and $S_{2} = {y, f, k}$ . According to Proposition 5, ABF( ${(P_{1})}_{t r}$ ) (resp. ABF( $P_{1}$ )) has two stable assumption extensions $Δ_{1}$ and $Δ_{2}$ such that $\begin{aligned} Δ_{1} = {not y, not f, not \neg p, not \neg r, not \neg y, not \neg f, not \neg k}, \\ Δ_{2} = {not p, not r, not \neg p, not \neg r, not \neg y, not \neg f, not \neg k} . \end{aligned}$ The conclusion of each assumption extension $Δ_{i}$ defined as ${CN}_{P_{1}} (Δ_{i})$ ( $i = 1, 2$ ) is obtained as follows: $\begin{aligned} {CN}_{P_{1}} (Δ_{1}) = {p, r, k, not y, not f, not \neg p, not \neg r, not \neg y, not \neg f, not \neg k} = S_{1} \cup Δ_{1}, \\ {CN}_{P_{1}} (Δ_{2}) = {y, f, k, not p, not r, not \neg p, not \neg r, not \neg y, not \neg f, not \neg k} = S_{2} \cup Δ_{2} . \end{aligned}$ As a result, the expected result is successfully obtained since $k \in {CN}_{P_{1}} (Δ_{i})$ ( $i = 1, 2$ ).

Example 6.
Consider logic programs $P = {a \leftarrow, \neg a \leftarrow, b \leftarrow not b}$ and $Q = {\neg a \leftarrow, a \leftarrow not b}$ shown in [28, Example 3.4]. Both are inconsistent under the answer set semantics (resp. under the p-stable model semantics) since P has the unique answer set $S = L i t_{P}$ (resp. no p-stable model), while Q has no answer set (resp. only the inconsistent p-stable model $M = {\neg a, a}$ ). Correspondingly, ABF $(P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ has no stable assumption extension (though it has the unique complete, preferred and grounded assumption extension ${not \neg b}$ which is inconsistent since ${CN}_{P} ({not \neg b}) = {a, \neg a, not \neg b}$ ), while ABF( $P_{t r}) = ⟨ L, P_{t r}, A_{P}, \bar{} \bar{} ⟩$ has the unique stable assumption extension $Δ = {}$ which is inconsistent since ${CN}_{P_{t r}} (Δ) = L i t_{P} = {a, \neg a, b, \neg b} = S \cup Δ$ . In contrast, ABF $(Q)$ has the unique stable (resp. complete, preferred and grounded) assumption extension $Δ^{'} = {not b, not \neg b}$ which is inconsistent since ${CN}_{Q} (Δ^{'}) = {a, \neg a, not b, not \neg b} = M \cup Δ^{'}$ , while ABF( $Q_{t r}$ ) has no stable assumption extension.

3.3. Arguments and argument extensions in ABFs translated from EDLPs

Given an (E)DLP, it is impossible to capture its semantics by using arguments constructed based on Definition 1. The reason is as follows. For example, consider the EDLP $P = {p | q \leftarrow}$ which has two answer sets, ${p}$ and ${q}$ (or the DLP $P_{D} = {p \lor q \leftarrow}$ which has two stable models, ${p}$ and ${q}$ ). Then if we use Definition 1 in the ABA framework $F (P)$ (or $F (P_{D})$ ) instantiated with P (or $P_{D}$ ), we may construct the tree which has the root labelled by $p | q$ (or $p \lor q$ ) and the unique child labelled τ together with two one-node-trees whose roots are labelled by either $not p$ or $not q$ , but no other trees. As a result, since there exists no attacks among these three arguments, there is the unique argument extension $E$ consisting of these arguments s.t. $Concs (E) = {p | q, not p, not q}$ (or s.t. $Concs (E) = {p \lor q, not p, not q}$ ) under any σ semantics in the ABF $F (P)$ (or $F (P_{D})$ ). Thus two answer sets shown above can never be captured based on Definition 1. In contrast, in ABF(P) (or in ABF( $P_{D}$ )), we can use the inference rule $[Res]$ . Hence, if there is the aforementioned tree whose root is labelled by $p | q$ , thanks to the inference rule $[Res]$ , we can construct two trees furthermore, each of which has the root labelled by p (resp. q) as well as two children such that one is the child tree whose root is labelled by $p | q$ and the other is the child labelled by the defeasible assumption $not q$ (resp. $not p$ ). As a result, two arguments (i.e. trees) whose roots are labelled by either p or q attack each other, which enables us to capture two answer sets of P. The same goes for ABF( $P_{D}$ ) to capture two stable models of $P_{D}$ . Thus, this example illustrates that Definition 1 has the difficulty to deal with disjunctive rules in the ABA framework $F (P)$ (resp. $F (P_{D})$ ), whereas inference rules provided in ABF(P) (resp. ABF( $P_{D}$ )) are useful to construct arguments using disjunctive rules. (Furthermore, see details in Example 7 as shown below.)

In what follows, arguments and attacks in the ABF translated from an EDLP P are defined.

Definition 11.
Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P, where $L = ⟨ L_{EDLP}, ⊩ ⟩$ . Ψ belonging to $L_{EDLP}$ is said to be a defeasible consequence of P and $K \subseteq A_{P}$ if $P \cup K ⊩ Ψ$ in which any assumption contained in K is used to derive Ψ. K is said to be a support for Ψ w.r.t. P.

$P \cup K ⊩ Ψ$ addressed above is represented by a tree structure $T_{Ψ} (K)$ as follows.
Definition 12.
Let $L = ⟨ L_{EDLP}, ⊩ ⟩$ and ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P. Let $T_{Ψ} (K)$ denote $P \cup K ⊩ Ψ$ where K is the support for a defeasible consequence Ψ w.r.t. P. In other words, $T_{Ψ} (K)$ is a (finite) tree with a root node labelled by Ψ (having a support K) defined as follows.
The cases using no inference rules:

For $not ℓ \in A_{P}$ , there is a one-node tree $T_{Ψ} (K)$ whose root node is labelled by $Ψ = not ℓ$ and $K = {not ℓ}$ .

For a rule $r \in P$ , there is a one-node tree $T_{Ψ} (K)$ whose root node is labelled by $Ψ = r$ and $K = \emptyset$ .

The cases using inference rules:

i. For a rule $ψ \leftarrow \in P$ , by [ $Ref$ ], there is a tree $T_{ψ} (K)$ whose root node N is labelled by ψ and N has a unique child node, namely a one-node tree $T_{r} (\emptyset)$ where $r = ψ \leftarrow$ . Then $K = \emptyset$ .

ii. For a rule $ψ \leftarrow ϕ_{1}, \dots, ϕ_{n}$ in P, if for each $ϕ_{i}$ ( $1 ⩽ i ⩽ n$ ), there exists a tree $T_{ϕ_{i}} (K_{i})$ with the root node $N_{i}$ labelled by $ϕ_{i}$ , then by [ $MP$ ], there is a tree $T_{ψ} (K)$ with the root node N labelled by ψ and N has a child $N_{0}$ labelled by $r = ψ \leftarrow ϕ_{1}, \dots, ϕ_{n}$ which is a one-node tree $T_{r} (\emptyset)$ as well as n children $N_{i}$ ( $1 ⩽ i ⩽ n$ ) where $N_{i}$ is the root of a tree $T_{ϕ_{i}} (K_{i})$ . Then $K = ⋃_{i} K_{i}$ .

Let $Φ = ψ_{1}^{'} | \dots | ψ_{m}^{'} | ℓ_{1} | \dots | ℓ_{n} | ψ_{1}^{″} | \dots | ψ_{k}^{″}$ and $Ψ = ψ_{1}^{'} | \dots | ψ_{m}^{'} | ψ_{1}^{″} | \dots | ψ_{k}^{″}$ ,

where $ℓ_{i} \in L i t_{P}$ ( $1 ⩽ i ⩽ n$ ). If there is a tree $T_{Φ} (K^{'})$ with the root node $N_{0}$ labelled by Φ, then by [ $Res$ ], there is a tree $T_{Ψ} (K)$ with the root node N labelled by Ψ and N has a child $N_{0}$ as well as n children $N_{1}, \dots N_{n}$ each of which is a one-node tree $T_{ϕ_{i}} ({ϕ_{i}})$ where $ϕ_{i} = not ℓ_{i}$ ( $1 ⩽ i ⩽ n$ ). Then $K = K^{'} \cup ⋃_{i = 1}^{n} {not ℓ_{i}}$ .

Let ( $ℓ_{i} \dots ψ)$ 10
¹⁰
This is depicted vertically in the inference rule of [ $RBC$ ].

denote the reasoning for the case $ℓ_{i}$ and $T_{ℓ_{i}} (\emptyset)$ be a one-node tree whose root is labelled by $ℓ_{i}$ . Suppose that
there is a tree $T_{Φ} (K^{'})$ whose root node $N_{0}$ is labelled by $Φ = ℓ_{1} | \dots | ℓ_{n}$ ; and

for each $ℓ_{i}$ ( $1 ⩽ i ⩽ n$ ), there exists reasoning for a case $ℓ_{i}$ such that ( $ℓ_{i} \dots ψ)$ , namely $P \cup {ℓ_{i}} \cup K_{i} ⊩ ψ$ for $\exists K_{i} \subseteq A_{P}$ , which is represented by a tree $T_{ψ} (K_{i})$ constructed by newly introducing a tree $T_{ℓ_{i}} (\emptyset)$ in this definition.
Then by [ $RBC$ ], there is a tree $T_{ψ} (K)$ with the root node N labelled by ψ and N has the child $N_{0}$ as well as n children $N_{1}, \dots N_{n}$ where each $N_{i}$ ( $1 ⩽ i ⩽ n$ ) is the root of a tree $T_{ψ} (K_{i})$ for the case $ℓ_{i}$ . Thus $K = K^{'} \cup ⋃_{i = 1}^{n} {K_{i}}$ . □

Given ABF(P), the set of all trees $T_{Ψ} (K)$ is uniquely determined based on Definition 12.

In ABF(P), an argument is defined as a special tree $T_{ϕ} (K)$ whose root is labelled by a literal or a NAF-literal $ϕ \in L_{P}$ , and the attack relation attacks is defined as usual.
Definition 13.
Let ABF( $P) = ⟨ L, P, A_{P}$ , $\bar{} \bar{} ⟩$ be the ABF translated from an EDLP P and $ϕ \in L_{P} = L i t_{P} \cup {NAF}_{P}$ . Then in ABF(P),
an argument for a conclusion (or claim) ϕ supported by $K \subseteq A_{P}$ ( $K ⊢ ϕ$ , for short) is a (finite) tree $T_{ϕ} (K)$ whose root node is labelled by $ϕ \in L_{P}$ .

$K_{1} ⊢ ϕ_{1}$ $attacks$ $K_{2} ⊢ ϕ_{2}$ iff $ϕ_{1} = \overline{α}$ for some $α \in K_{2}$ .

Notation 1.
Given an EDLP P, we often use a unique name to denote an argument $K ⊢ ϕ$ in ABF(P), e.g. $a : K ⊢ ϕ$ is an argument with name a. With an abuse of notation [31, Notation 3], the name of an argument sometimes stands for the whole argument, for example, a denotes the argument $a : K ⊢ ϕ$ .

Let $A F = (A R, attacks)$ be the abstract argumentation (AA) framework generated from ABF(P), where $A R$ is the set of all arguments such that $a \in A R$ iff an argument $a : K ⊢ ϕ$ is in ABF(P), and $(a, b) \in attacks$ in $A F$ iff $a attacks b$ in ABF(P).

Fig. 1.
Arguments of ABF(P) for $P = {p | q \leftarrow}$ in Ex. 7

Fig. 2.
$A F = (A R, a t t a c k s)$ in Ex. 7

The semantics is also given by argument extensions in ABF(P) as follows.
Definition 14.
Let ABF $(P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P, $A R$ be the set of arguments generated from ABF(P), and $A rgs \subseteq A R$ . $A rgs$ is conflict-free iff $∄ A, B \in A rgs$ such that $A attacks B$ . $A rgs$ defends an argument A iff each argument that attacks A is attacked by an argument in $A rgs$ . Then $A rgs \subseteq A R$ is: admissible iff $A rgs$ is conflict-free and defends all its elements; a complete argument extension iff $A rgs$ is admissible and contains all arguments it defends; a preferred (resp. grounded) argument extension iff it is a (subset-)maximal (resp. (subset-)minimal) complete argument extension; a stable argument extension iff it is conflict-free and attacks every argument in $A R ∖ A rgs$ ; an ideal argument extension iff it is a (subset-)maximal complete argument extension that is contained in each preferred argument extension.
Example 7.
Consider the EDLP $P = {p | q \leftarrow}$ . Then ABF(P) has four arguments $A_{i}$ ( $1 ⩽ i ⩽ 4$ ): $\begin{array}{r} A_{1} : {not q} ⊢ p, A_{2} : {not p} ⊢ q, A_{3} : {not p} ⊢ not p, A_{4} : {not q} ⊢ not q, \end{array}$ whose tree structures are shown in Fig. 1. Fig. 2 shows the AA framework $A F = (A R, attacks)$ for the ABF. It has two argument extensions $E_{1}$ , $E_{2}$ under stable and preferred semantics as follows: $\begin{array}{r} E_{1} = {A_{1}, A_{4}}, E_{1} = {A_{2}, A_{3}}, where Concs (E_{1}) = {p, not q}, Concs (E_{2}) = {q, not p} . \end{array}$

Let $σ \in {complete, preferred, grounded, stable, ideal}$ . It is shown that there is a one-to-one correspondence between σ argument extensions and σ assumption extensions of ABF(P) for an EDLP P.
Definition 15.
Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P, and $A R$ be the set of all arguments that can be generated from ABF(P). $Asms 2 Args : ℘ (A_{P}) \to ℘ (A R)$ and $Args 2 Asms : ℘ (A R) \to ℘ (A_{P})$ are functions such that $\begin{aligned} Asms 2 Args (A s m s) = {K ⊢ ϕ \in A R | K \subseteq A s m s}, \\ Args 2 Asms (A rgs) = {α \in A_{P} | α \in K for an argument K ⊢ ϕ \in A rgs} . \end{aligned}$
Theorem 5.
Let ABF $(P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P, and $A R$ be the set of all arguments generated from ABF(P). The following holds.
If $A s m s \subseteq A_{P}$ is a σ assumption extension, then $Asms 2 Args (A s m s)$ is a σ argument extension.

If $A rgs \subseteq A R$ is a σ argument extension, then $Args 2 Asms (A rgs)$ is a σ assumption extension.

Proof.
In case $σ = stable$ , this is proved as follows.
Let $A s m s \subseteq A_{P}$ be a stable assumption extension and $A rgs = Asms 2 Args (A s m s)$ .
Since $A s m s$ is conflict-free, every argument constructed from $A s m s$ (i.e. $K ⊢ ϕ$ where $K \subseteq A s m s$ ) does not attack any assumption in $A s m s$ . In other words, any argument in $A rgs$ does not attack any argument constructed from $A s m s$ . This means that $A rgs$ is conflict-free.

Since $A s m s$ is a stable assumption extension, $A s m s$ attacks any assumption in $A_{P} ∖ A s m s$ . Let $B = (K_{B} ⊢ ϕ)$ be any argument in $A R ∖ A rgs$ , where $K_{B} ⊈ A s m s$ and $(A_{P} ∖ A s m s) \cap K_{B} \neq \emptyset$ . Then $A s m s$ attacks $(A_{P} ∖ A s m s) \cap K_{B}$ . Therefore $A s m s$ attacks B, denoting that $A rgs$ attacks B. Hence $A rgs$ attacks any argument in $A R ∖ A rgs$ .
Due to (i) and (ii), $A rgs$ is conflict-free and attacks every argument in $A R ∖ A rgs$ . Thus $A rgs$ is a stable argument extension.

Let $A rgs \subseteq A R$ be a stable argument extension and $A s m s = Args 2 Asms (A rgs)$ .
$A rgs$ is conflict-free since $A rgs$ is a stable assumption extension. Suppose $A s m s$ is not conflict-free. That is, $A s m s$ attacks some assumption $\exists α \in A s m s$ . Then it is possible to construct some argument based on $A s m s$ (say $A =$ ( $K_{A} ⊢ ϕ$ ) where $K_{A} \subseteq A s m s$ ) whose conclusion ϕ is the contrary of some assumption α in $A s m s$ , i.e. $ϕ = \overline{α}$ for $\exists α \in A s m s$ . The argument A cannot be a member of $A rgs$ (otherwise $A rgs$ would not be conflict-free). Hence $A \in A R ∖ A rgs$ . Besides for $\forall α \in K_{A} \subseteq A s m s$ , $A rgs$ does not attack α since $A rgs$ is conflict-free. This means that $A rgs$ cannot attack the argument $A \in A R ∖ A rgs$ . Hence $A rgs$ is not a stable argument extension. Contradiction. Therefore $A s m s$ is conflict-free.

Suppose there exists some assumption $α \in A_{P} ∖ A s m s$ which $A s m s$ does not attack. Due to $α \notin A s m s$ , there is no argument in $A rgs$ whose support contains α. Hence $({α} ⊢ α) \in A R ∖ A rgs$ . Since $A rgs$ is a stable argument extension, there exists some argument $B = (K_{B} ⊢ ϕ) \in A rgs$ with $ϕ = \overline{α}$ and $K_{B} \subseteq A s m s$ which attacks the argument ${α} ⊢ α$ . This means that $A rgs$ attacks ${α} ⊢ α$ . In other words, $A s m s$ attacks $α \in A_{P} ∖ A s m s$ . Contradiction.
Due to (i) and (ii), $A s m s$ is conflict-free and it attacks every assumption $α \in A_{P} ∖ A s m s$ . Therefore $A s m s$ is a stable assumption extension.
The other cases are proved in a similar way to the proof in [32, Theorem 2]. □

When an ELP P with no disjunction is given, an argument $K ⊢ ϕ$ in the ABA framework $F (P)$ is the tree constructed in accordance with Definition 1, whereas in ABF(P), an argument $K ⊢ ϕ$ is the tree $T_{Ψ} (K)$ defined by Definition 12, which is constructed by using only the inference rule $[MP]$ (including $[Ref]$ ). Though the tree structure of $K ⊢ ϕ$ in the ABA framework $F (P)$ is different from that of $K ⊢ ϕ$ in ABF(P), they are semantically equivalent as follows.
Proposition 7.
Let P be an ELP, $ϕ \in L_{P}$ , and $K \subseteq A_{P} = {NAF}_{P}$ . Then $K ⊢ ϕ$ is an argument of the ABA framework $F (P) = ⟨ L_{P}, P, A_{P}, \bar{} \bar{} ⟩$ iff there is an argument $K ⊢ ϕ$ of ABF( $P) = ⟨ L, P, A_{P}$ , $\bar{} \bar{} ⟩$ , where $L = ⟨ L_{EDLP}, ⊩ ⟩$ .
Proof.
We denote by $⊢_{MP}$ derivability using modus ponens on ← as the only inference rule in the ABA framework $F (P)$ . When used on $P \cup K$ for $K \subseteq {NAF}_{P}$ , $⊢_{MP}$ treats NAF literals purely syntactically [31]. On the other hand, we denote by $⊩_{MP}$ derivability using only the inference rule $[MP]$ in ABF(P). Then

$K ⊢ ϕ$ is an argument in the ABA framework $F (P)$ , where K is a support for $ϕ \in L_{P} = L_{P}$

iff $P \cup K ⊢_{MP} ϕ$ w.r.t. a support $K \subseteq A_{P}$ for ϕ (due to [31, Lemma 2])

iff $P \cup K ⊩_{MP} ϕ$ w.r.t. a support $K \subseteq A_{P}$ for ϕ in ABF(P)

iff $P \cup K ⊩ ϕ$ w.r.t. a support $K \subseteq A_{P}$ for ϕ in ABF(P)

iff $K ⊢ ϕ$ is an argument in ABF(P). □

The following proposition denotes that, given an ELP, the same abstract argumentation framework is obtained regardless of whether arguments are constructed according to either Definition 1 or Definition 12.
Proposition 8.
Given an ELP P, the abstract argumentation (AA) framework generated from the ABA framework $F (P)$ coincides with the AA framework generated from ABF(P).
Proof.
Given an ELP P, let $A F_{1} = (A R_{1}, {attacks}_{1})$ be the AA framework generated from the ABF $F (P) = ⟨ L_{P}, P, A_{P}, \bar{} \bar{} ⟩$ and $A F_{2} = (A R_{2}, {attacks}_{2})$ be the AA framework generated from ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ .
Then, $a \in A R_{1}$ iff there exists ( $a : K ⊢ ϕ$ ) in $F (P)$ where $K \subseteq A_{P}$ and $ϕ \in L_{P}$

iff there exists ( $a : K ⊢ ϕ$ ) in $ABF (P)$ where $K \subseteq A_{P}$ and $ϕ \in L_{P}$ due to Proposition 7

iff $a \in A R_{2}$ .

$(a, b) \in {attacks}_{1}$ iff a $attacks$ b in $F (P)$ iff ( $a : K ⊢ ϕ$ ) $attacks$ ( $b : K^{'} ⊢ ϕ^{'}$ ) in $F (P)$

iff there exist ( $a : K ⊢ ϕ$ ) and ( $b : K^{'} ⊢ ϕ^{'}$ ) s.t. $not ϕ \in K^{'}$ in $F (P)$

iff there exist ( $a : K ⊢ ϕ$ ) and ( $b : K^{'} ⊢ ϕ^{'}$ ) s.t. $not ϕ \in K^{'}$ in $ABF (P)$ due to Proposition 7

iff ( $a : K ⊢ ϕ$ ) $attacks$ ( $b : K^{'} ⊢ ϕ^{'}$ ) in $ABF (P)$

iff a $attacks$ b in $ABF (P)$ iff $(a, b) \in {attacks}_{2}$ .
Thanks to (1) and (2), $A R_{1} = A R_{2}$ as well as ${attacks}_{1} = {attacks}_{2}$ hold. Hence $A F_{1} = A F_{2}$ . □
3.4. Correspondence between answer sets of an EDLP and stable argument extensions

In ABF(P) translated from an EDLP P, the conclusion of a set of arguments $E$ is defined as: $\begin{array}{r} Concs (E) = {ϕ \in L_{P} | ϕ is a conclusion (or claim) of an argument contained in E} . \end{array}$

First of all, we show there is a one-to-one correspondence between answer sets of an NDP P and stable argument extensions of the ABF translated from P.

Theorem 6.
Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an NDP P where $L = ⟨ L_{EDLP}, ⊩ ⟩$ . Let $M \subseteq H B_{P}$ and $E \subseteq A R$ , where $A R$ is the set of all arguments generated from ABF(P). Then M is an answer set of an NDP P iff there is a stable argument extension $E$ of ABF(P) such that $M \cup Δ_{M} = Concs (E) = {CN}_{P} (Δ_{M})$ , where $Δ_{M} = {not p | p \in ({HB}_{P} ∖ M)}$ is a stable assumption extension of ABF(P).
Proof.
Let ${NAF}_{P} = {not p | p \in {HB}_{P}}$ and $Δ_{M} \subseteq {NAF}_{P}$ . Firstly we show that due to the form of inference rules, $P \cup Δ_{M} ⊩ not p$ iff $not p \in Δ_{M}$ . In other words,

$\begin{aligned} (4) & not p \in {Cn}_{L} (P \cup Δ_{M}) iff not p \in Δ_{M}, \end{aligned}$

which is needed below to prove the equivalences given in this theorem.

⇒: Let M be an answer set of an NDP P. Then there exists the stable assumption extension $Δ_{M}$ of ABF(P) such that $Δ_{M} = {not p | p \in ({HB}_{P} ∖ M)}$ due to Proposition 3(i). Hence due to Theorem 5, there exists the stable argument extension $E = Asms 2 Args (Δ_{M}) = {K ⊢ ϕ | K \subseteq Δ_{M}, L_{P} = {HB}_{P} \cup {NAF}_{P}}$ . Thus for M, $Δ_{M}$ and $E = Asms 2 Args (Δ_{M})$ , it holds that

$Concs (E) = {ϕ \in L_{P} | K ⊢ ϕ is constructed from Δ_{M}, where K \subseteq Δ_{M} and ϕ \in L_{P} = {HB}_{P} \cup {NAF}_{P}}$

$= {ϕ \in L_{P} | P \cup Δ_{M} ⊩ ϕ} = {ϕ \in L_{P} | ϕ \in {Cn}_{L} (P \cup Δ_{M})} = M \cup Δ_{M}$ . (due to Lemma 2 and (4))

⇐: Let $E$ be a stable argument extension of ABF(P) translated from an NDP P. Then due to Theorem 5, there is the stable assumption extension Δ of ABF(P) such that $Δ = Args 2 Asms (E) = {α | α \in K for K ⊢ ϕ in E} = ⋃_{i} K_{i}$ for $K_{i} ⊢ ϕ_{i} \in E$ . Moreover, corresponding to this stable assumption extension Δ, there is the answer set M of the NDP P such that $M = {p \in {HB}_{P} | not p \notin Δ)}$ due to Proposition 3(ii), while for this answer set M, $Δ_{M} = {not p \in {NAF}_{P} | p \notin M}$ is the stable assumption extension of ABF(P) due to Proposition 3(i). Thus obviously $Δ_{M} = Δ$ . Then for a stable argument extension $E$ , $Δ = ⋃_{i} K_{i}$ s.t. $K_{i} ⊢ ϕ_{i} \in E$ , $M = {p \in {HB}_{P} | not p \notin Δ}$ and $Δ_{M} = Δ$ , it holds that

$\begin{aligned} Concs (E) & = {ϕ | K ⊢ ϕ \in E for ϕ \in L_{P} = {HB}_{P} \cup {NAF}_{P}} \\ = {ϕ \in L_{P} | P \cup Δ ⊩ ϕ for Δ = ⋃_{i} K_{i} where K_{i} ⊢ ϕ_{i} \in E} \\ = {ϕ \in L_{P} | P \cup Δ_{M} ⊩ ϕ for M = {p \in {HB}_{P} | not p \notin Δ_{M} = Δ}} \\ = {ϕ \in L_{P} | ϕ \in {Cn}_{L} (P \cup Δ_{M})} = M \cup Δ_{M} . (due to Lemma 2 and (4)) \end{aligned}$ □

Based on Theorem 6, we show that there is a one-to-one correspondence between answer sets (resp. p-stable models) of an EDLP P and stable argument extensions of ABF( $P_{t r}$ ) (resp. ABF(P)) as follows, though Propositions 5 and 4 show the similar correspondences for stable assumption extensions of the respective ABFs.
Theorem 7.
Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P. Let $M \subseteq L i t_{P}$ and $E \subseteq A R$ , where $A R$ is the set of all arguments generated from ABF(P). Then M is a p-stable model of an EDLP P iff there is a stable argument extension $E$ of ABF(P) such that $M \cup Δ_{M} = Concs (E) = {CN}_{P} (Δ_{M})$ , where $Δ_{M}$ is a stable assumption extension of ABF(P).
Proof.
Let $P^{+}$ be the NDP which is the positive form [28] of an EDLP P. Like the proof of Proposition 4, for a set $S \subseteq L i t_{P}$ , let $S^{+}$ be the set obtained by replacing each negative literal $\neg L$ in S with the newly introduced atom $L^{'}$ . Thus Herbrand base $H B_{P^{+}}$ of the NDP $P^{+}$ is ${(L i t_{P})}^{+}$ . Then for ABF(P) translated from an EDLP P and ABF( $P^{+}$ ) translated from the NDP $P^{+}$ , it holds that, there is a stable argument extension $E$ of ABF $(P)$ if and only if there is a stable argument extension $E^{+}$ of ABF $(P^{+})$ such that $\begin{aligned} (5) & Concs (E^{+}) = Concs {(E)}^{+} . \end{aligned}$

Moreover, due to Lemma 3, $\begin{aligned} (6) & M is a p-stable model of an EDLP P iff M^{+} is an answer set of the NDP P^{+} . \end{aligned}$

On the other hand, based on Theorem 6 as well as (5), it holds that, $\begin{array}{r} M^{+} is an answer set of the NDP P^{+} \end{array}$ iff there is a stable argument extension $E^{+}$ along with a stable assumption extension $Δ_{M^{+}}$ of ABF $(P^{+})$ $\begin{aligned} such that M^{+} \cup Δ_{M^{+}} = Concs (E^{+}), \\ where Δ_{M^{+}} = {not a | a \in H B_{P^{+}} ∖ M^{+}} = {not a | a \in L i t_{P}^{+} ∖ M^{+}} = Δ_{M}^{+}, \\ M^{+} \cup Δ_{M^{+}} = {(M \cup Δ_{M})}^{+} for M \subseteq L i t_{P}, and Δ_{M^{+}} = Δ_{M}^{+} \end{aligned}$ iff there is a stable argument extension $E$ along with a stable assumption extension $Δ_{M}$ of ABF $(P)$ $\begin{aligned} (7) & such that M \cup Δ_{M} = Concs (E), where Δ_{M} = {not L | L \in L i t_{P} ∖ M} . \end{aligned}$

Hence from (6) and (7), it follows that, M is a p-stable model of an EDLP P iff there is a stable argument extension $E$ along with a stable assumption extension $Δ_{M}$ of ABF $(P)$ such that $M \cup Δ_{M} = Concs (E)$ . □
Theorem 8.
Let P be an EDLP and ABF( $P_{t r}) = ⟨ L, P_{t r}, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from the EDLP $P_{t r} = P \cup {L \leftarrow p, \neg p | p \in L i t_{P}, L \in L i t_{P}}$ , where $L i t_{P_{t r}} = L i t_{P}$ , $A_{P} = {NAF}_{P} = {not ℓ | ℓ \in {Lit}_{P}}$ , and $\overline{not ℓ} = ℓ$ for every $not ℓ \in A_{P}$ . Let $S \subseteq L i t_{P}$ and $E_{t r} \subseteq A R$ for the set $A R$ of all arguments generated from ABF( $P_{t r}$ ). Then S is an answer set of an EDLP P iff there is a stable argument extension $E_{t r}$ of ABF( $P_{t r}$ ) such that $S \cup Δ_{S} = Concs (E_{t r}) = {CN}_{P_{t r}} (Δ_{S})$ , where $Δ_{S}$ is a stable assumption extension of ABF( $P_{t r}$ ).
Proof.
The following (i) and (ii) hold according to [28, Theorem 3.5] and Theorem 7 respectively.

(i) S is an answer set of an EDLP P iff S is p-stable model of $P_{t r}$ .

(ii) S is a p-stable model of an EDLP $P_{t r}$ iff there is a stable argument extension $E_{t r}$ of ABF( $P_{t r}$ )

such that $S \cup Δ_{S} = Concs (E_{t r})$ , where $Δ_{S}$ is a stable assumption extension of ABF( $P_{t r}$ ).

Hence this theorem follows from both (i) and (ii). □

Theorems 7 and 8 for an EDLP are the generalization of Theorems 2 and 3 for an ELP respectively.
Example 8 (Cont. Example 1 ).

To solve the Kyoto protocol problem in argumentation, we construct ABF( $P_{1}$ ) from $P_{1} = {r \leftarrow p, not \neg r, k \leftarrow r, not \neg k, f \leftarrow y, not \neg f, k \leftarrow f, not \neg k, p | y \leftarrow}$ . Arguments and $attacks$ in ABF( $P_{1}$ ) are obtained as follows: $\begin{aligned} A_{1} : {not y} ⊢ p, A_{2} : {not p} ⊢ y, A_{3} : {not y, not \neg r} ⊢ r, \\ A_{4} : {not p, not \neg f} ⊢ f, A_{5} : {not y, not \neg r, not \neg k} ⊢ k, \\ A_{6} : {not p, not \neg f, not \neg k} ⊢ k, A_{7} : {not \neg r, not \neg f, not \neg k} ⊢ k, \\ A_{8} : {not p} ⊢ not p, A_{9} : {not y} ⊢ not y, A_{10} : {not r} ⊢ not r, \\ A_{11} : {not f} ⊢ not f, A_{12} : {not k} ⊢ not k, A_{13} : {not \neg p} ⊢ not \neg p, \\ A_{14} : {not \neg y} ⊢ not \neg y, A_{15} : {not \neg r} ⊢ not \neg r, \\ A_{16} : {not \neg f} ⊢ not \neg f, A_{17} : {not \neg k} ⊢ not \neg k; \\ attacks = {(A_{1}, A_{2}), (A_{1}, A_{4}), (A_{1}, A_{6}), (A_{1}, A_{8}), (A_{2}, A_{1}), (A_{2}, A_{3}), (A_{2}, A_{5}), (A_{2}, A_{9}), \\ (A_{3}, A_{10}), (A_{4}, A_{11}), (A_{5}, A_{12}), (A_{6}, A_{12}), (A_{7}, A_{12})} . \end{aligned}$ Fig. 3 shows $A_{3}$ which is constructed based on [ $Ref$ ], [ $MP$ ] and [ $Res$ ]. Each $A_{i}$ ( $1 ⩽ i ⩽ 6$ ) uses [ $Res$ ]. But $A_{7}$ uses [ $RBC$ ] instead of [ $Res$ ]. Arguments in ABF( $P_{1}$ ) coincide with those in ABF( ${(P_{1})}_{t r}$ ).

Then ABF( ${(P_{1})}_{t r}$ ) (resp. ABF( $P_{1}$ )) has two stable (resp. preferred) argument extensions: $\begin{aligned} E_{1} = {A_{1}, A_{3}, A_{5}, A_{7}, A_{9}, A_{11}} \cup {A_{i} | 13 ⩽ i ⩽ 17}, \\ E_{2} = {A_{2}, A_{4}, A_{6}, A_{7}, A_{8}, A_{10}} \cup {A_{i} | 13 ⩽ i ⩽ 17}, \end{aligned}$

where $Concs (E_{1}) = {p, r, k, not y, not f} \cup U$ , $Concs (E_{2}) = {y, f, k, not p, not r} \cup U$ ,

for $U = Concs ({A_{i} | 13 ⩽ i ⩽ 17}) = {not \neg p, not \neg y, not \neg r, not \neg f, not \neg k}$ .

Hence the expected result is successfully obtained since $k \in Concs (E_{i})$ for $\forall E_{i}$ ( $i = 1, 2$ ).

On the other hand, under the grounded and ideal semantics as the skeptical semantics, ABF( $P_{1}$ ) has the unique argument extension $E_{3}$ : $\begin{array}{r} E_{3} = {A_{7}} \cup {A_{i} | 13 ⩽ i ⩽ 17}, where Concs (E_{3}) = {k} \cup U . \end{array}$ Then as a skeptical consequence, we obtain the result such that $k \in Concs (E_{3})$ due to $A_{7} \in E_{3}$ where the argument $A_{7}$ is constructed using [ $RBC$ ], that meets our expectation based on reasoning by cases addressed in Example 1.

Fig. 3.

$A_{3}$ : ${not y, not \neg r} ⊢ r$ in Example 8.

Example 9.

Consider the EDLP $P_{2} = {\neg p | q \leftarrow, q \leftarrow \neg p, not \neg q, \neg p \leftarrow q, not p}$ , where $L i t_{P_{2}} = {p, q, \neg p, \neg q}$ . $P_{2}$ is not head-cycle-free11

¹¹

The dependency graph of an EDLP P is a directed graph where each literal is a node and where there is an edge from L to $L^{'}$ iff there is a rule in which a literal L is not preceded by the $not$ operator in the body and $L^{'}$ appears in the head. An EDLP is head-cycle free iff its dependency graph does not contain directed cycles that go through two literals that belong to the head of the same rule [4].

but a general EDLP [4,13]. This means that the knowledge expressed by

P_{2}

is unlikely to be expressed by ELPs in general due to complexity results shown in [4,13].

P_{2}

has the unique answer set

S = {\neg p, q}

, which is its unique p-stable model.

In contrast, ABF( $P_{2}$ ) translated from $P_{2}$ has the unique stable assumption extension $Δ_{S} = {not p, not \neg q}$ , while it has the following arguments: $\begin{aligned} A_{1} : {not p} ⊢ \neg p, A_{2} : {not \neg q} ⊢ q, A_{3} : {not q} ⊢ \neg p, A_{4} : {not \neg p} ⊢ q, \\ A_{5} : {not \neg q, not p} ⊢ \neg p, A_{6} : {not p, not \neg q} ⊢ q, A_{7} : {not \neg p, not p} ⊢ \neg p, \\ A_{8} : {not q, not \neg q} ⊢ q, A_{9} : {not \neg p} ⊢ not \neg p, A_{10} : {not q} ⊢ not q, \\ A_{11} : {not p} ⊢ not p, A_{12} : {not \neg q} ⊢ not \neg q, and \\ attacks = {(A_{1}, A_{4}), (A_{1}, A_{7}), (A_{1}, A_{9}), (A_{2}, A_{3}), (A_{2}, A_{8}), (A_{2}, A_{10}), (A_{3}, A_{4}), (A_{3}, A_{7}), \\ (A_{3}, A_{9}), (A_{4}, A_{3}), (A_{4}, A_{8}), (A_{4}, A_{10}), (A_{5}, A_{4}), (A_{5}, A_{7}), (A_{5}, A_{9}), (A_{6}, A_{3}), \\ (A_{6}, A_{8}), (A_{6}, A_{10}), (A_{7}, A_{4}), (A_{7}, A_{7}), (A_{7}, A_{9}), (A_{8}, A_{3}), (A_{8}, A_{8}), (A_{8}, A_{10})} . \end{aligned}$ Fig. 4 shows the tree structure of the argument $A_{1} : {not p} ⊢ \neg p$ which is constructed based on the inference rules: [ $Ref$ ], [ $MP$ ] and [ $RBC$ ]. In this case, arguments in ABF( $P_{2}$ ) coincide with those in ABF( ${(P_{2})}_{t r}$ ). Then ABF( $P_{2}$ ) (resp. ABF( ${(P_{2})}_{t r}$ )) has the following unique stable argument extension: $\begin{array}{r} E = {A_{1}, A_{2}, A_{5}, A_{6}, A_{11}, A_{12}}, where Concs (E) = {\neg p, q, not p, not \neg q} = S \cup Δ_{S} \end{array}$ for the answer set S of $P_{2}$ and the stable assumption extension $Δ_{S}$ of ABF( $P_{2}$ ).

Fig. 4.

$A_{1}$ : ${not p} ⊢ \neg p$ in Example 9.

Example 10.

Consider the EDLP $P_{3} = {\neg a | b \leftarrow not \neg b, a \leftarrow not c}$ .

It has the unique answer set $S = {a, b}$ , while it has two p-stable models $M_{1} = {a, b} = S$ and $M_{2} = {a, \neg a}$ , where $M_{1}$ is consistent but $M_{2}$ is inconsistent due to $M_{2} (a) = ⊤$ .

Let ABF( $P_{3}$ ) be the ABF translated from $P_{3}$ , which has arguments and $attacks$ as follows: $\begin{aligned} A_{1} : {not c} ⊢ a, A_{2} : {not b, not \neg b} ⊢ \neg a, A_{3} : {not \neg a, not \neg b} ⊢ b, \\ A_{4} : {not a} ⊢ not a, A_{5} : {not b} ⊢ not b, A_{6} : {not c} ⊢ not c, \\ A_{7} : {not \neg a} ⊢ not \neg a, A_{8} : {not \neg b} ⊢ not \neg b, \\ A_{9} : {not \neg c} ⊢ not \neg c, and attacks = {(A_{1}, A_{4}), (A_{2}, A_{3}), (A_{2}, A_{7}), (A_{3}, A_{2}), (A_{3}, A_{5})} . \end{aligned}$ Then ABF( $P_{3}$ ) has two stable argument extensions $E_{1}, E_{2}$ as follows. $\begin{aligned} E_{1} = {A_{1}, A_{3}, A_{6}, A_{7}, A_{8}, A_{9}}, E_{2} = {A_{1}, A_{2}, A_{5}, A_{6}, A_{8}, A_{9}}, \\ where Concs (E_{1}) = {a, b, not c, not \neg a, not \neg b, not \neg c} = M_{1} \cup Δ_{M_{1}}, \\ Concs (E_{2}) = {a, \neg a, not b, not c, not \neg b, not \neg c} = M_{2} \cup Δ_{M_{2}}, \end{aligned}$ in which $Δ_{M_{1}}$ and $Δ_{M_{2}}$ are stable assumption extensions of ABF( $P_{3}$ ) such that

$Δ_{M_{1}} = {not c, not \neg a, not \neg b, not \neg c}, Δ_{M_{2}} = {not b, not c, not \neg b, not \neg c} .$

In contrast, ABF( ${(P_{3})}_{t r}$ ) has the arguments $A_{i}$ ( $1 ⩽ i ⩽ 9$ ) along with $A_{j}$ ( $10 ⩽ j ⩽ 15$ ) shown below: $\begin{aligned} A_{10} : {not b, not \neg b, not c} ⊢ a, A_{11} : {not b, not \neg b, not c} ⊢ b, \\ A_{12} : {not b, not \neg b, not c} ⊢ c, A_{13} : {not b, not \neg b, not c} ⊢ \neg a, \\ A_{14} : {not b, not \neg b, not c} ⊢ \neg b, A_{15} : {not b, not \neg b, not c} ⊢ \neg c . \end{aligned}$ As a result, ABF( ${(P_{3})}_{t r}$ ) has the unique stable argument extensions as follows:

$E_{t r} = {A_{1}, A_{3}, A_{6}, A_{7}, A_{8}, A_{9}} = E_{1}$ ,

$where Concs (E_{t r}) = {a, b, not c, not \neg a, not \neg b, not \neg c} = S \cup Δ_{S},$

for the unique answer set S of $P_{3}$ and the unique stable assumption extension $Δ_{S}$ of ABF( ${(P_{3})}_{t r}$ ).

Remark 2.

In Example 8, [ $Ref$ ] is used to construct each $A_{i} (1 ⩽ i ⩽ 7)$ . Thus we need [ $Ref$ ]. Without [ $MP$ ], we cannot build $A_{i} (3 ⩽ i ⩽ 7)$ , which means we cannot infer k. Thus we need [ $MP$ ]. In Example 9, [ $RBC$ ] is used to construct $A_{1}, A_{2}, A_{5}, A_{6}$ . Hence without [ $RBC$ ], we cannot construct these arguments, which means ABF( $P_{2}$ ) has no stable extension. Thus we need [ $RBC$ ]. In Example 10, without [ $Res$ ], we cannot construct $A_{3}$ along with $A_{2}$ . Thus we need [ $Res$ ].

3.5. Correspondence between answer sets of a consistent EDLP and consistent stable extensions

Rationality postulates are defined in ABF(P) translated from an EDLP P like Definition 2. In what follows, we show that such ABF(P) always satisfies the closure-property (or direct consistency postulate [6]) under the stable semantics.

Definition 16 (Rationality postulates).

Given an EDLP P, ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ is said to satisfy the consistency-property (resp. the closure-property) under the σ semantics if for each σ argument extension $E$ of the AA framework ${AF}_{F}$ generated from $F = ABF (P$ ), $Concs (E)$ is consistent (resp. $Concs (E)$ is closed w.r.t. ${CN}_{P}$ ).

Theorem 9.
Let $F$ be ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ translated from an EDLP P and $E$ be a stable argument extension of $A F_{F}$ generated from $F = ABF (P$ ).
$F$ satisfies the closure-property under the stable semantics.

$F$ satisfies the consistency-property under the stable semantics

iff for every $E$ , $Concs (E)$ is consistent

iff for every $E$ , $Concs (E)$ is not contradictory w.r.t. explicit negation ¬.

Proof.

Let M be a p-stable model of P and $E$ be a stable argument extension of $F = ABF (P$ ) satisfying $M \cup Δ_{M} = Concs (E)$ . Then

$\begin{aligned} (8) & {CN}_{P} (M \cup Δ_{M}) = {ϕ \in L_{P} | P \cup M \cup Δ_{M} ⊩ ϕ} = Δ_{M} \cup {ℓ \in L i t_{P} | P \cup M \cup Δ_{M} ⊩ ℓ} . \end{aligned}$

Due to Lemma 4 and the transitive closure property of ${Cn}_{L}$ , it holds that, for $ℓ \in L i t_{P}$ ,

$ℓ \in M iff ℓ \in {Cn}_{L} (P \cup Δ_{M}) iff ℓ \in {Cn}_{L} (P \cup Δ_{M} \cup ⋃_{ℓ \in M} {ℓ}) = {Cn}_{L} (P \cup Δ_{M} \cup M)$ .

$\begin{aligned} (9) & Hence, ℓ \in M iff P \cup M \cup Δ_{M} ⊩ ℓ for ℓ \in L i t_{P} . \end{aligned}$

Then, (9) means that $M = {ℓ \in L i t_{P} | P \cup M \cup Δ_{M} ⊩ ℓ}$ .

As a result, (8) leads to ${CN}_{P} (M \cup Δ_{M}) = M \cup Δ_{M}$ , namely, ${CN}_{P} (Concs (E)) = Concs (E)$ .

Thus $F$ satisfies the closure-property under the stable semantics.

$F$ satisfies the consistency-property under the stable semantics

iff for every $E$ , $Concs (E)$ is consistent (due to Definition 16)

iff for every $E$ , ${CN}_{P} (Concs (E))$ is not contradictory (due to Definition 10)

iff for every $E$ , $Concs (E)$ is not contradictory (due to Item (1), ${CN}_{P} (Concs (E)) = Concs (E)$ )

iff for every $E$ , $Concs (E)$ is not contradictory w.r.t. explicit negation ¬

(since every stable argument extension is not contradictory w.r.t. $\bar{} \bar{}$ ). □

Given an EDLP P, the notions of consistent argument extensions and consistency in ABF(P) are defined like [33, Definitions 6, 7] as follows.
Definition 17 (Consistent argument extensions).

Given an EDLP P, let $E$ be a σ argument extension of ABF( $P) = ⟨ L, P, A_{P}$ , $\bar{} \bar{} ⟩$ . Then $E$ is said to be consistent if $Concs (E)$ is not contradictory w.r.t. ¬; otherwise it is inconsistent.

Definition 18 (Consistency in ABFs translated from EDLPs).

Given an EDLP P, ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ is said to be consistent under σ semantics if ABF(P) has a consistent σ argument extension (or a consistent σ assumption extension); otherwise it is inconsistent.

We show that there is a one-to-one correspondence between answer sets of a consistent EDLP P and the consistent stable argument extensions of ABF(P) translated from P, which is a generalization of Theorem 4 for a consistent ELP. To prove it, we provide the following lemma regarding a consistent EDLP.

Lemma 5.
Let P be an EDLP. M is a consistent answer set of P iff there is a consistent p-stable model M of P.
Proof.
⇐: Let S be a consistent p-stable model of P. Then S does not contain a pair of complementary literals. Since S is also a p-stable model of the reduct $P^{S}$ according to Definition 5, S is a minimal set satisfying the condition (i) for $P^{S}$ which is the not-free EDLP. Then since S does not contain a pair of complementary literals, S is also a minimal set satisfying both conditions (i) and (ii) for $P^{S}$ . This denotes that S is the answer set of $P^{S}$ which does not contain a pair of complementary literals. Thus S is the answer set of $P^{S}$ and it is not $L i t_{P}$ . Hence since the answer set S of $P^{S}$ which is not $L i t_{P}$ is the answer set of P, S is the consistent answer set of P.

⇒: The converse is proved in a similar way. □

Hereby given a consistent EDLP, we can obtain the following proposition and theorem. Proposition 9.
Let P be a consistent EDLP and ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from P. Then S is an answer set of P iff there is a consistent stable assumption extension $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ ) of ABF(P).
Proof.
Suppose that S is an answer set of a consistent EDLP P. Then based on Definition 5, S is a consistent answer set of P, which means that S is a consistent p-stable model of P due to Lemma 5. Then corresponding to a p-stable model S of P which is consistent, there is a stable assumption extension $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ of ABF(P) where ${CN}_{P} (Δ_{S}) = S \cup Δ_{S}$ based on Proposition 4 and Proposition 6. Now, since S is a consistent answer set, ${CN}_{P} (Δ_{S}) = S \cup Δ_{S}$ is not contradictory according to Definition 10. This means that $Δ_{S}$ is consistent. Therefore, there is a consistent stable assumption extension $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ of ABF(P). The converse is also proved in a similar way. □
Theorem 10.
Let P be a consistent EDLP and ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from P. Then S is an answer set of P iff there is a consistent stable argument extension $E$ of ABF(P) such that $S \cup Δ_{S} = Concs (E) = {CN}_{P} (Δ_{S})$ , where $Δ_{S}$ is the consistent stable assumption extension of ABF(P).
Proof.
Suppose that $E$ is a consistent stable argument extension of ABF(P). Then $Concs (E)$ is consistent, i.e. not contradictory w.r.t. ¬ due to Definition 10 since $E$ is conflict-free. Moreover, based on Theorem 7, there is the p-stable model S of P corresponding to this $E$ such that $S \cup Δ_{S} = Concs (E)$ , where $Δ_{S}$ is a stable assumption extension of ABF(P). Since $Concs (E)$ is not contradictory w.r.t. ¬, in other words, it does not contain a pair of complementary literals, $Concs (E) = S \cup Δ_{S}$ as well as the p-stable model S are consistent. Hence due to Lemma 5, S is the consistent answer set of P. As a result, S is the answer set of the consistent EDLP P. The converse is also proved in a similar way. □
Corollary 2.
Let P be a consistent EDLP. The following holds.

(1) $E$ is a consistent stable extension of ABF(P) iff $E$ is a stable extension of ABF( $P_{t r}$ ).

(2) ABF( $P_{t r}$ ) satisfies the rationality postulates under the stable semantics.
Proof.
(1) follows from Theorem 10 as well as Theorem 8 for a consistent EDLP P. (2) directly follows from (1). □
Example 11 (Innocent unless proved guilty).

Consider the EDLP $P_{4}$ [26], which states that everyone is pronounced not guilty unless proven otherwise: $\begin{matrix} P_{4} = {innocent | guilty \leftarrow charged, \neg guilty \leftarrow not proven, charged \leftarrow} . \end{matrix}$

Let $i, g, c, p$ be the abbreviations for innocent, guilty, charged, proven respectively. $P_{4}$ has the unique answer set $S = {c, i, \neg g}$ , where p (i.e. $proven$ ) is interpreted “unknown” under the answer set semantics. In contrast, $P_{4}$ has two p-stable models, $M_{1} = {c, i, \neg g}$ and $M_{2} = {c, g, \neg g}$ . $M_{1} = S$ is consistent whose truth values are $M_{1} (c) = t$ , $M_{1} (i) = t$ , $M_{1} (g) = f$ , $M_{1} (p) = ⊥$ , while $M_{2}$ is inconsistent due to $M_{2} (g) = ⊤$ . To solve this problem in argumentation, we construct ABF( $P_{4}$ ), which has arguments: $\begin{aligned} A_{1} : {} ⊢ c, A_{2} : {not g} ⊢ i, A_{3} : {not i} ⊢ g, A_{4} : {not p} ⊢ \neg g, \\ A_{5} : {not i} ⊢ not i, A_{6} : {not g} ⊢ not g, A_{7} : {not c} ⊢ not c, \\ A_{8} : {not p} ⊢ not p, A_{9} : {not \neg i} ⊢ not \neg i, A_{10} : {not \neg g} ⊢ not \neg g, \\ A_{11} : {not \neg c} ⊢ not \neg c, A_{12} : {not \neg p} ⊢ not \neg p, \\ and attacks = {(A_{1}, A_{7}), (A_{2}, A_{3}), (A_{2}, A_{5}), (A_{3}, A_{2}), (A_{3}, A_{6}), (A_{4}, A_{10})}, where | attacks | = 6 . \end{aligned}$ Then ABF( $P_{4}$ ) has two stable argument extensions, $E_{1}$ and $E_{2}$ : $\begin{matrix} E_{1} = {A_{1}, A_{2}, A_{4}, A_{6}, A_{8}, A_{9}, A_{11}, A_{12}}, E_{2} = {A_{1}, A_{3}, A_{4}, A_{5}, A_{8}, A_{9}, A_{11}, A_{12}}, \end{matrix}$ where $Concs (E_{1}) = {c, i, \neg g, not g, not p, not \neg i, not \neg c, not \neg p}$ with $Concs (E_{1}) \cap L i t_{P_{4}} = S$ ,

$Concs (E_{2}) = {c, g, \neg g, not i, not p, not \neg i, not \neg c, not \neg p}$ with $Concs (E_{2}) \cap L i t_{P_{4}} = M_{2}$ .

Thus $E_{1}$ is consistent but $E_{2}$ is inconsistent. Hence ABF( $P_{4}$ ) is consistent under the stable semantics.

In contrast, ABF( ${(P_{4})}_{t r}$ ) has the unique stable argument extension $E_{1}$ due to six additionally introduced arguments to $A_{i} (1 ⩽ i ⩽ 12)$ and $| attacks | = 26$ .

Using ABF( $P_{4}$ ), we can decide that the attorney-at-law having the argument $A_{4}$ for the claim $\neg g$ wins and the prosecutor having $A_{3}$ for g loses since $A_{4} \in E_{1}$ and $A_{3} \notin E_{1}$ for its unique consistent extension $E_{1}$ . Therefore $\neg g$ is decided.

4. Relation to nonmonotonic reasoning

4.1. Correspondence between disjunctive default logic and assumption-based argumentation

A disjunctive default theory (ddt, for short) [16] is a set of disjunctive defaults of the form: $\begin{matrix} \frac{α : β_{1}, \dots, β_{m}}{γ_{1} | \dots | γ_{n}}, \end{matrix}$ where $α, β_{1}, \dots, β_{m}, γ_{1}, \dots, γ_{n} (m, n ⩾ 0)$ are quantifier-free formulas. Formula α is the prerequisite of the default, $β_{1}, \dots, β_{m}$ are its justifications, and $γ_{1}, \dots, γ_{n}$ are its consequents. If the prerequisite α in the form is the formula true, it will be dropped; if, in addition, $m = 0$ , then we write the default as $γ_{1} | \dots | γ_{n}$ .

The semantics of a ddt is given by extensions defined as follows.

Definition 19 ([16, Definition 5.1]).

Let D be a disjunctive default theory, and let E be a set of sentences. E is an extension for D if it is one of the minimal deductively closed sets of sentences $E^{'}$ satisfying the condition: For any ground instance having the above form of any default from D, if $α \in E^{'}$ and $\neg β_{1}, \dots, \neg β_{m} \notin E$ then, for some i ( $(1 ⩽ i ⩽ n)$ , then, $γ_{i} \in E^{'}$ . A theorem is a sentence that belongs to all extensions.

Observe that for standard (nondisjunctive) default theories, this definition gives Reiter’s extensions [27].

The definition of an extension for a ddt are also described based on the concept of reduct [16]. To this end, a disjunctive rule of the form $\frac{α}{γ_{1} | \dots | γ_{n}}$ is defined. Then it is said that a theory E is closed under a disjunctive rule if, whenever $α \in E$ , then there exist i, $1 ⩽ i ⩽ n$ , $γ_{i} \in E$ .

Definition 20 ([16, Definition 5.2]).

Let D be a ddt and let E be a set of sentences. The reduct of D w.r.t. E, denoted $D^{E}$ , is the set of inference rules defined as follows: An inference rule $\frac{α}{γ_{1} | \dots | γ_{n}}$ is in $D^{E}$ if for some $β_{1}, \dots, β_{m}$ such that $\neg β_{i} \notin E$ , $1 ⩽ i ⩽ m$ , the default $\frac{α : β_{1}, \dots, β_{m}}{γ_{1} | \dots | γ_{n}}$ is in D.

Using the reduct $D^{E}$ , another definition of an extension for a ddt is given by the following theorem.

Theorem 11 ([16, Theorem 5.3]).

A set of sentences E is an extension for a ddt D if and only if E is a minimal set closed under propositional consequence and under the rules from $D^{E}$ .

In what follows, we show the semantic relationship between ddts and assumption-based frameworks.

Theorem 12.
Let P be an EDLP and ABF( $P_{t r}$ ) be the ABF translated from $P_{t r}$ .

S is the set of all literals from an extension of a disjunctive default theory $emb (P)$

iff there is a stable argument extension $E_{t r}$ of ABF( $P_{t r}$ ) such that $S = Concs (E_{t r}) \cap L i t_{P}$

iff there is a stable assumption extension Δ of ABF( $P_{t r}$ ) such that $S = {CN}_{P_{t r}} (Δ) \cap L i t_{P}$ .
Proof.
Based on Theorem 1 [16, Theorem 7.2], this theorem directly follows from Theorem 8 for an argument extension $E_{t r}$ (resp. from Proposition 5 for an assumption extension Δ). □

For a consistent EDLP, the following theorem holds.
Theorem 13.
Let P be a consistent EDLP and ABF(P) be the ABF translated from P.

S is the set of all literals from an extension of a disjunctive default theory $emb (P)$

iff there is a consistent stable argument extension $E$ of ABF(P) such that $S = Concs (E) \cap L i t_{P}$

iff there is a consistent stable assumption extension Δ of ABF(P) such that $S = {CN}_{P} (Δ) \cap L i t_{P}$ .
Proof.
Based on Theorem 1 [16, Theorem 7.2], this theorem directly follows from Theorem 10. □

Given a nondisjunctive EDLP, i.e. an ELP P (resp. a consistent ELP P), Theorem 12 (resp. Theorem 13) also holds for the disjunctive default theory $emb (P)$ and ABF( $P_{t r}$ ) (resp. ABF(P)). For such a special case, however, we can show the relationship between a standard (nondisjunctive) default theory which gives Reiter’s extensions and a standard ABA framework translated from an ELP as follows.
Theorem 14.
Let P be an ELP and $F (P_{t r})$ be the ABA framework (ABF) translated from $P_{t r}$ .

S is the set of all literals from an extension of a default theory $emb (P)$

iff there is a stable argument extension $E_{t r}$ of the ABF $F (P_{t r})$ such that $S = Concs (E_{t r}) \cap L i t_{P}$

iff there is a stable assumption extension Δ of the ABF $F (P_{t r})$ such that $S = C N_{P_{t r}} (Δ) \cap L i t_{P}$ ,

where $C N_{P_{t r}}$ is the consequence operator for the ABF $F (P_{t r})$ defined in Definition 2 .
Proof.
Based on Theorem 1 [16, Theorem 7.2], this theorem directly follows from Theorem 3 for an argument extension $E_{t r}$ (resp. from Proposition 13 for an assumption extension Δ). □
Theorem 15.
Let P be a consistent ELP and $F (P)$ be the ABA framework translated from P.

S is the set of all literals from an extension of a default theory $emb (P)$

iff there is a consistent stable argument extension $E$ of the ABF $F (P)$ such that $S = Concs (E) \cap L i t_{P}$

iff there is a consistent stable assumption extension Δ of the ABF $F (P)$ such that $S = C N_{P} (Δ) \cap L i t_{P}$

where $C N_{P}$ is the consequence operator for the ABF $F (P)$ defined in Definition 2 .
Proof.
Based on Theorem 1 [16, Theorem 7.2], this theorem directly follows from Theorem 4 for an argument extension $E$ (resp. from Proposition 14 for an assumption extension Δ). □

The following example shows that we can successfully obtain the expected result k of the Kyoto protocol problem based on our assumption-based framework corresponding to the ddt $D_{2}$ thanks to Theorem 12. It should be noted here that this solution of the problem can never be obtained based on the existing works of ABA [5,19] corresponding to the default theory $D_{1}$ as discussed in the introduction. Example 12 (Cont. Example 1 ).

The disjunctive default theory $D_{2}$ has two extensions $E_{1}$ and $E_{2}$ such that $k \in E_{i} (i = 1, 2)$ , where $S_{E_{1}} = {p, r, k} \subseteq E_{1}$ (resp. $S_{E_{2}} = {y, f, k} \subseteq E_{2}$ ) is the set of all literals from $E_{1}$ (resp. $E_{2}$ ). On the other hand, $D_{2}$ is the ddt emb( $P_{1}$ ) in which the $EDLP P_{1}$ can be embedded. Then according to Example 8, ABF( ${(P_{1})}_{t r})$ coincides with ABF( $P_{1}$ ), and it hods that $k \in Concs (E_{i}) (i = 1, 2)$ for two stable argument extensions $E_{1}$ and $E_{2}$ of ABF( $P_{1}$ ), where $Concs (E_{1}) \cap L i t_{P_{1}} = S_{E_{1}} = {p, r, k}$ and $Concs (E_{2}) \cap L i t_{P_{1}} = S_{E_{2}} = {y, f, k}$ . Similarly, according to Example 5, it hods that $k \in {CN}_{P_{1}} (Δ_{i})$ ( $i = 1, 2$ ) for each stable assumption extension $Δ_{i}$ of ABF( $P_{1}$ ), where ${CN}_{P_{1}} (Δ_{i}) \cap L i t_{P_{1}} = S_{E_{i}}$ .

4.2. Correspondence between prioritized circumscription and assumption-based argumentation

Circumscription [20,22,23] is a form of nonmonotonic reasoning, which was proposed to formalize the human commonsense reasoning under incomplete information. Commonsense knowledge including preferences is also often used in human argumentation. Then Bondarenko et al. showed in [5, Theorem 6.7] that Herbrand models of parallel circumscription can be captured by sets of assumptions of a corresponding assumption-based framework. Nonetheless, though preferences can be handled not in parallel circumscription but in prioritized circumscription, no study has shown a correspondence between the semantics of prioritized circumscription and the ABA semantics to the best of our knowledge. In what follows, we show new results about the relationships between them.

We first review the framework of circumscription. The following definition is due to [20]. Given a first order theory T, let P and Z be joint tuples of predicate constants from T, where P is a tuple of predicate constants $P_{1}, \dots, P_{m}$ . Let $T (P, Z)$ be a theory containing P and Z. The circumscription of P in $T (P, Z)$ with variable Z is defined by a second order formula as follows: $\begin{matrix} Circum (T; P; Z) \overset{def}{=} T (P, Z) \land \neg \exists p z (T (p, z) \land p < P), \end{matrix}$ where $p, z$ are tuples of predicate variables similar to $P, Z$ , and $p < P$ denotes the following formula: $\begin{matrix} ⋀_{i = 1}^{m} \forall x (p_{i} (x) \supset P_{i} (x)) \land \neg ⋀_{i = 1}^{m} \forall x (P_{i} (x) \supset p_{i} (x)), \end{matrix}$ where $P = ⟨ P_{1}, \dots, P_{m} ⟩$ . The formula of circumscription expresses that P has a minimal possible extension under the condition $T (P, Z)$ where Z is allowed to vary in the process of minimization [20]. Due to the respective roles in the process of minimization, each $P_{i}$ ( $1 ⩽ i ⩽ m$ ) is called a minimized predicate, while each predicate in Z is called a variable predicate. Q denotes the rest of the predicates occurring in T, called the fixed predicates. This version of circumscription is called parallel circumscription.

If P is decomposed into disjoint parts $P^{1}, \dots, P^{k}$ , and the members of $P^{i}$ are assigned a higher priority than the members of $P^{j}$ for $i < j$ , then prioritized circumscription of $P^{1} > \dots > P^{k}$ in T with variable Z is denoted by $Circum (T; P^{1} > \dots > P^{k}; Z)$ , which is also defined by a second order formula [20,23]. Parallel circumscription coincides with prioritized circumscription for $k = 1$ .

The semantics of circumscription is given based on the preorder $⩽^{P^{1} > \dots > P^{k}; Z}$ defined as follows.

For a structure M, let $| M |$ be its universe and $M ⟦ C ⟧$ the interpretation of a predicate constant C. For a tuple P of predicate constants, $M_{1} ⟦ P ⟧ \subseteq M_{2} ⟦ P ⟧$ denotes $M_{1} ⟦ P_{i} ⟧ \subseteq M_{2} ⟦ P_{i} ⟧$ for every $P_{i}$ in P.

Definition 21 ([20]).

Let $P^{1}, \dots, P^{k}$ be k disjoint parts of minimized predicates P. For any two structures $M_{1}$ , $M_{2}$ , we write $M_{1} ⩽^{P^{1} > \dots > P^{k}; Z} M_{2}$ if

$| M_{1} | = | M_{2} |$ ,

$M_{1} ⟦ K ⟧ = M_{2} ⟦ K ⟧$ , for every constant K in Q,

$M_{1} ⟦ P^{1} ⟧ \subseteq M_{2} ⟦ P^{1} ⟧$ ,

For every $i ⩽ k$ , if for every $1 ⩽ j ⩽ i - 1$ , $M_{1} ⟦ P^{j} ⟧ = M_{2} ⟦ P^{j} ⟧$ , then $M_{1} ⟦ P^{i} ⟧ \subseteq M_{2} ⟦ P^{i} ⟧$ .

⩽^{P; Z}

stands for the preorder

⩽^{P^{1} > \dots > P^{k}; Z}

for

k = 1

. Then a structure M is a model of

Circum (T; P; Z)

iff M is minimal in the class of models of T with respect to

⩽^{P; Z}

. A structure M is a model of

Circum (T; P^{1} > \dots > P^{k}; Z)

iff M is minimal in the class of models of T with respect to

⩽^{P^{1} > \dots > P^{k}; Z}

In a nutshell, the idea of the circumscriptive theory is that human nonmonotonic reasoning under incomplete knowledge (e.g. commonsense knowledge) with preferences is based on the most preferable models which are minimal ones w.r.t. $⩽^{P^{1} > \dots > P^{k}; Z}$ among models of the knowledge base T.

In this paper, we consider a first order theory T without function symbols. We assume that T is given by a set of clauses of the form: $\begin{matrix} A_{1} \lor \dots \lor A_{ℓ} \lor \neg B_{1} \lor \dots \lor \neg B_{m}, \end{matrix}$ where $A_{i}$ ( $1 ⩽ i ⩽ ℓ; ℓ ⩾ 0$ ) and $B_{j}$ ( $1 ⩽ j ⩽ m; m ⩾ 0$ ) are atoms and every variable in the formula is assumed to be universally quantified at the front. We also restrict our attention to Herbrand models of T, which has the effect of introducing both the domain closure assumption and the unique name assumption into T, and then reasoning with T reduces to the propositional level. Let Σ be a set of clauses. Then $T h (Σ)$ stands for a set of clauses which are theorems of Σ. A clause in $T h (Σ)$ which is not properly subsumed12

¹²
It is said that a clause $C_{1}$ subsumes a clause $C_{2}$ if $C_{1} θ \subseteq C_{2}$ holds for some substitution θ [29].

by any theorem in

T h (Σ)

is called a

characteristic clause

μ T h (Σ)

denotes the set of all characteristic clauses in

T h (Σ)

. t stands for a tuple of ground terms occurring in the Herbrand universe of T. Parallel circumscription is transformed into an EDLP [29] as follows.

Definition 22 ([29]).

Given $Circum (T; P; Z)$ , an EDLP $Π_{α}$ 13

¹³
In this study, any rule from an EDLP has the form (2). So if a rule r whose head is empty, i.e. “ $\leftarrow body (r)$ ” is generated in the transformation, then $Π_{α}$ has the rule $“ α \leftarrow body (r), not α$ ” instead of r both of which are semantically equivalent each other under the answer set semantics, where α is a newly introduced atom that does not appear in the language.

is constructed as follows, where

p_{1}, \dots, p_{s}

z_{1}, \dots, z_{t}

, and

q_{1}, \dots, q_{u}

are atoms whose predicates belong to

P, Z

, and Q respectively.

For any clause in T of the form: $\begin{aligned} p_{1} & \lor \dots \lor p_{ℓ} \lor z_{1} \lor \dots \lor z_{m} \lor q_{1} \lor \dots \lor q_{n} \lor \neg p_{ℓ + 1} \lor \dots \lor \neg p_{s} \lor \neg z_{m + 1} \lor \dots \\ \lor \neg z_{t} \lor \neg q_{n + 1} \lor \dots \lor \neg q_{u}, \end{aligned}$

$Π_{α}$ has the rule: $\begin{aligned} z_{1} | \dots | z_{m} | q_{1} | \dots | q_{n} \leftarrow p_{ℓ + 1}, \dots, p_{s}, z_{m + 1}, \dots, z_{t}, q_{n + 1}, \dots, q_{u}, not p_{1}, \dots, not p_{ℓ} . \end{aligned}$

For every clause in $μ T h (T)$ of the form: $\begin{matrix} p_{1} \lor \dots \lor p_{ℓ} \lor q_{1} \lor \dots \lor q_{n} \lor \neg q_{n + 1} \lor \dots \lor \neg q_{u}, \end{matrix}$ $Π_{α}$ has the rule: $p_{1} | \dots | p_{ℓ} | q_{1} | \dots | q_{n} \leftarrow q_{n + 1}, \dots, q_{u}$ .

For any atom $p, z$ , and q from $P, Z$ , and Q respectively,

$Π_{α}$ has the rule: $\begin{aligned} \neg p \leftarrow not p, \\ z | \neg z \leftarrow, q | \neg q \leftarrow . \end{aligned}$

The following theorem presents that there is a one-to-one correspondence between models of parallel circumscription and answer sets of $Π_{α}$ .

Theorem 16 ([29]).

Let $Π_{α}$ be the EDLP translated from $Circum (T; P; Z)$ . Then M is a model of $Circum (T; P; Z)$ iff M is an answer set of $Π_{α}$ .

Proposition 10.
Any answer set of an EDLP $Π_{α}$ is consistent.
Proof.
In $Π_{α}$ , classical negation ¬ appears only in rules constructed according to item 3 in Definition 22. Thus any answer set of $Π_{α}$ never contains both a and $\neg a$ for any atom a from $P, Z$ and Q. □

In [20, Theorem 2], the following equivalence is shown: $\begin{aligned} (10) & Circum (T; P^{1} > \dots > P^{k}; Z) = ⋀_{i = 1}^{k} Circum (T; P^{i}; P^{i + 1}, \dots, P^{k}, Z) . \end{aligned}$

Based on (10), prioritized circumscription is transformed into an EDLP [35] as follows.
Definition 23 ([35, Definition 3.11]).

Given prioritized circumscription: $\begin{matrix} Circum (T (P^{1} \dots P^{k}, Z, Q); P^{1} > P^{2} > \dots > P^{k}; Z), \end{matrix}$ where $P^{r} (1 ⩽ r ⩽ k)$ , Z, Q are tuples of predicate symbols such as $⟨ {(P^{r})}_{1}, \dots, {(P^{r})}_{ℓ_{r}} ⟩$ , $⟨ Z_{1}, \dots, Z_{m} ⟩$ ,

$⟨ Q_{1}, \dots, Q_{n} ⟩$ , an EDLP $Π_{β}$ is constructed in two steps as follows:

According to (10), a given prioritized circumscription is represented by the conjunction of k parallel circumscriptions. So, let every ith $(1 ⩽ i ⩽ k)$ parallel circumscription: $\begin{matrix} Circum (T (P^{1} \dots P^{k}, Z, Q); P^{i}; P^{i + 1}, \dots, P^{k}, Z) \end{matrix}$ be transformed in such a way that all predicate symbols occurring in it are renamed by using $P i^{1}, \dots, P i^{k}$ , $Z i$ , $Q i$ instead of $P^{1}, \dots, P^{k}$ , Z,Q, which leads to the ith renamed parallel circumscription as follows: $\begin{aligned} (11) & Circum (T i; P i^{i}; P i^{i + 1}, \dots, P i^{k}, Z i), \end{aligned}$ where $T i$ denotes $T (P i^{1}, \dots, P i^{k}, Z i, Q i)$ , and $P i^{r}$ , $Z i$ , $Q i$ are tuples of predicate symbols such as $⟨ {(P i^{r})}_{1}, \dots, {(P i^{r})}_{ℓ_{r}} ⟩$ , $⟨ {(Z i)}_{1}, \dots, {(Z i)}_{m} ⟩$ , $⟨ {(Q i)}_{1}, \dots, {(Q i)}_{n} ⟩$ .

$Π_{β}$ consists of all rules from ${(Π_{α})}^{1}, \dots, {(Π_{α})}^{k}$ and $Π_{γ}$ where

each ${(Π_{α})}^{i} (1 ⩽ i ⩽ k)$ is an EDLP which is constructed from the ith renamed parallel circumscription (11) according to Definition 22.

$Π_{γ}$ is a set of rules (i.e. an ELP) as follows:

For any predicate u from $P, Z, Q$ and any t, $\begin{matrix} u (t) \leftarrow u_{i} (t), \neg u (t) \leftarrow \neg u_{i} (t) . (1 ⩽ i ⩽ k) \end{matrix}$ where u and $u_{i}$ stand for any predicate symbol of ${(P^{r})}_{f}, Z_{g}, Q_{h}$ and any one of ${(P i^{r})}_{f}, {(Z i)}_{g}, {(Q i)}_{h}$ ( $1 ⩽ f ⩽ ℓ_{r}, 1 ⩽ g ⩽ m, 1 ⩽ h ⩽ n$ ).

In what follows, $HB$ denotes Herbrand base of T and ${HB}_{e} = HB \cup {\neg p | p \in HB}$ . The following theorem shows that there is a one-to-one correspondence between models of prioritized circumscription and answer sets of $Π_{β}$ .

Theorem 17.
Let $Π_{β}$ be the EDLP translated from $Circum (T; P^{1} > P^{2} > \dots > P^{k}; Z)$ . Then M is a model of $Circum (T; P^{1} > P^{2} > \dots > P^{k}; Z)$ iff there is a consistent answer set S of $Π_{β}$ such that $M = S \cap {HB}_{e}$ .
Proof.
Let $A S (Π)$ be a set of all answer sets of a finite ground EDLP Π. We use the following notations.
${Acircum}^{i} \overset{def}{=} ⋀_{j = 1}^{i} {Circum}_{j}$ , where ${Circum}_{i} \overset{def}{=} Circum (T; P^{i}; P^{i + 1}, \dots, P^{k}; Z)$ .

${(Π_{γ})}^{i} \overset{def}{=} {ℓ \leftarrow ℓ^{i} ∣ ℓ \leftarrow ℓ^{i} \in Π_{γ}}$ , where a literal ℓ in ${Circum}_{i}$ is renamed to the literal $ℓ^{i}$ in the ith renamed $Circum (T i; P i^{i}; P i^{i + 1}, \dots, P i^{k}, Z i)$ .

${(Π_{α γ})}^{i} \overset{def}{=} {(Π_{α})}^{i} \cup {(Π_{γ})}^{i}$ .

${(Π_{β})}^{i} \overset{def}{=} ⋃_{j = 1}^{i} ({(Π_{α γ})}^{j})$ .

$S_{α γ}^{i}$ denotes an answer set of ${(Π_{α γ})}^{i}$ , namely $S_{α γ}^{i} \in A S ({(Π_{α γ})}^{i})$ .

For a set S of literals, we say that S is consistent if S does not contain both p and $\neg p$ for an atom p.

Then, $M^{i}$ is a model of ${Circum}_{i} = Circum (T; P^{i}; P^{i + 1}, \dots, P^{k}; Z) (1 ⩽ i ⩽ k)$

iff there is a consistent answer set $M^{i}$ of ${(Π_{α})}^{i}$ translated from ${Circum}_{i}$ (due to Theorem 16)

$\begin{aligned} (12) & iff there is a consistent answer set S_{α γ}^{i} of {(Π_{α γ})}^{i} such that M^{i} = S_{α γ}^{i} \cap {HB}_{e} . \end{aligned}$

Hence, M is a model of $Circum (T; P^{1} > P^{2} > \dots > P^{k}; Z)$

iff M is a model of ${Acircum}^{k} = ⋀_{j = 1}^{k} {Circum}_{j}$ (due to (10))

iff there is a consistent set $S = ⋃_{j = 1}^{k} S_{α γ}^{j}$ for $S_{α γ}^{j} \in A S ({(Π_{α γ})}^{j}) (1 ⩽ j ⩽ k)$ such that $M = S \cap {HB}_{e}$

(due to (12))

iff there is a consistent answer set $S = ⋃_{j = 1}^{k} S_{α γ}^{j}$ of ${(Π_{β})}^{k}$ such that $M = S \cap {HB}_{e}$

iff there is a consistent answer set S of $Π_{β} = {(Π_{β})}^{k}$ translated from

$Circum (T; P^{1} > P^{2} > \dots > P^{k}; Z)$ such that $M = S \cap {HB}_{e}$ . □

Therefore thanks to Theorem 10, the semantics of prioritized circumscription (resp. parallel circumscription) can be captured by argumentation based on Theorem 17 (resp. Theorem 16) as follows.
Theorem 18.
Let $Π_{α}$ be the EDLP translated from $Circum (T; P; Z)$ .

Then M is a model of $Circum (T; P; Z)$ iff there is a consistent stable argument extension $E$ of ABF( $Π_{α}) = ⟨ L, Π_{α}, A_{Π_{α}}, \bar{} \bar{} ⟩$ such that $M = Concs (E) \cap {HB}_{e}$ .
Proof.
Based on Theorem 16, Theorem 10, and Proposition 10,

M is a model of $Circum (T; P; Z)$ iff M is a (consistent) answer set of $Π_{α}$

iff there is a consistent stable argument extension $E$ of ABF( $Π_{α}$ ) such that $M = Concs (E) \cap {HB}_{e}$ . □
Theorem 19.
Let $Π_{β}$ be the EDLP translated from $Circum (T; P^{1} > P^{2} > \dots > P^{k}; Z)$ .

Then M is a model of $Circum (T; P^{1} > P^{2} > \dots > P^{k}; Z)$ iff there is a consistent stable argument extension $E$ of ABF( $Π_{β}) = ⟨ L, Π_{β}, A_{Π_{β}}, \bar{} \bar{} ⟩$ such that $M = Concs (E) \cap {HB}_{e}$ .
Proof.
Based on Theorem 17 and Theorem 10,

M is a model of $Circum (T; P^{1} > \dots > P^{k}; Z)$

iff there is a consistent answer set S of $Π_{β}$ such that $M = S \cap {HB}_{e}$

iff there is a consistent stable argument extension $E$ of ABF( $Π_{β}$ ) such that $S \cup Δ_{S} = Concs (E)$ and

$M = S \cap {HB}_{e}$

iff there is a consistent stable argument extension $E$ of ABF( $Π_{β}$ ) such that $M = Concs (E) \cap {HB}_{e}$

(due to $M = S \cap {HB}_{e} = (S \cup Δ_{S}) \cap {HB}_{e} = Concs (E) \cap {HB}_{e}$ ). □

Theorem 19 (resp. Theorem 17) indicates that reasoning in prioritized circumscription can be computed based on assumption-based argumentation (resp. answer set programming). Example 13.
Consider prioritized circumscription given in [35, Example 3.9]: $\begin{matrix} Circum ({p \lor q, q \lor r}; p > q; r) . \end{matrix}$ It has two models $M_{1} = {\neg p, q, r}$ and $M_{2} = {\neg p, q, \neg r}$ . Based on Theorem 17, these models can be obtained from answer sets of the EDLP $Π_{β} = {(Π_{α})}_{1} \cup {(Π_{α})}_{2} \cup Π_{γ}$ translated from it. In this case, $\begin{aligned} {(Π_{α})}^{1} = {q 1 \leftarrow not p 1, q 1 | r 1 \leftarrow, \neg p 1 \leftarrow not p 1, q 1 | \neg q 1 \leftarrow, r 1 | \neg r 1 \leftarrow}, \\ {(Π_{α})}^{2} = {p 2 \leftarrow not q 2, r 2 \leftarrow not q 2, p 2 | q 2 \leftarrow, \neg q 2 \leftarrow not q 2, r 2 | \neg r 2 \leftarrow, p 2 | \neg p 2 \leftarrow}, \\ Π_{γ} = {p \leftarrow p 1, q \leftarrow q 1, r \leftarrow r 1, \neg p \leftarrow \neg p 1, \neg q \leftarrow \neg q 1, \neg r \leftarrow \neg r 1, \\ p \leftarrow p 2, q \leftarrow q 2, r \leftarrow r 2, \neg p \leftarrow \neg p 2, \neg q \leftarrow \neg q 2, \neg r \leftarrow \neg r 2} . \end{aligned}$ where ${HB}_{e} = {p, q, r, \neg p, \neg q, \neg r}$ . Then $Π_{β}$ has two answer sets $S_{1}$ and $S_{2}$ [35]:

$\begin{matrix} S_{1} = {\neg p, q, r, \neg p 1, q 1, r 1, \neg p 2, q 2, r 2}, S_{2} = {\neg p, q, \neg r, \neg p 1, q 1, \neg r 1, \neg p 2, q 2, \neg r 2}, \end{matrix}$

where $S_{1} \cap {HB}_{e} = {\neg p, q, r} = M_{1}$ , $S_{2} \cap {HB}_{e} = {\neg p, q, \neg r} = M_{2}$ .

Thus, models of $Circum ({p \lor q, q \lor r}; p > q; r)$ are computed based on answer set semantics.

On the other hand, based on Theorem 19, these models are also obtained in argumentation as follows.

Consider ABF( $Π_{β}) = ⟨ L, Π_{β}, A_{Π_{β}}, \bar{} \bar{} ⟩$ translated from $Π_{β}$ . It has arguments and attacks as follows: $\begin{aligned} A_{1} : {not p 1} ⊢ q 1, A_{2} : {not r 1} ⊢ q 1, A_{3} : {not q 1} ⊢ r 1, A_{4} : {not p 1} ⊢ \neg p 1, \\ A_{5} : {not q 1} ⊢ \neg q 1, A_{6} : {not \neg q 1} ⊢ q 1, A_{7} : {not r 1} ⊢ \neg r 1, \\ A_{8} : {not \neg r 1} ⊢ r 1, A_{9} : {not q 2} ⊢ p 2, A_{10} : {not q 2} ⊢ r 2, \\ A_{11} : {not p 2} ⊢ q 2, A_{12} : {not q 2} ⊢ \neg q 2, A_{13} : {not r 2} ⊢ \neg r 2, \\ A_{14} : {not \neg r 2} ⊢ r 2, A_{15} : {not \neg p 2} ⊢ p 2, A_{16} : {not p 2} ⊢ \neg p 2, \\ A_{17} : {not q 2} ⊢ p, A_{18} : {not \neg p 2} ⊢ p, A_{19} : {not p 1} ⊢ q, \\ A_{20} : {not r 1} ⊢ q, A_{21} : {not \neg q 1} ⊢ q, A_{22} : {not p 2} ⊢ q, A_{23} : {not q 1} ⊢ r, \\ A_{24} : {not \neg r 1} ⊢ r, A_{25} : {not q 2} ⊢ r, A_{26} : {not \neg r 2} ⊢ r, A_{27} : {not p 1} ⊢ \neg p, \\ A_{28} : {not p 2} ⊢ \neg p, A_{29} : {not q 1} ⊢ \neg q, A_{30} : {not q 2} ⊢ \neg q, \\ A_{31} : {not r 1} ⊢ \neg r, A_{32} : {not r 2} ⊢ \neg r, \\ A_{ℓ_{i}} : {not x} ⊢ not x, where x \in {p, q, r, \neg p, \neg q, \neg r} for 33 ⩽ ℓ_{i} ⩽ 38, \\ A_{m_{i}} : {not x 1} ⊢ not x 1, where x 1 \in {p 1, q 1, r 1, \neg p 1, \neg q 1, \neg r 1} for 39 ⩽ m_{i} ⩽ 44, \\ A_{n_{i}} : {not x 2} ⊢ not x 2, where x 2 \in {p 2, q 2, r 2, \neg p 2, \neg q 2, \neg r 2} for 45 ⩽ n_{i} ⩽ 50), and \end{aligned}$
Fig. 5.
The graphic representation of arguments and $attacks$ in ABF( $Π_{β}$ ).

$\begin{aligned} attacks = & {(A_{1}, A_{3}), (A_{1}, A_{5}), (A_{1}, A_{23}), (A_{1}, A_{29}), (A_{1}, A_{40}), (A_{2}, A_{3}), (A_{2}, A_{5}), (A_{2}, A_{23}), \\ (A_{2}, A_{29}), (A_{2}, A_{40}), (A_{3}, A_{2}), (A_{3}, A_{7}), (A_{3}, A_{20}), (A_{3}, A_{31}), (A_{3}, A_{41}), (A_{4}, A_{42}), \\ (A_{5}, A_{6}), (A_{5}, A_{21}), (A_{5}, A_{43}), (A_{6}, A_{3}), (A_{6}, A_{5}), (A_{6}, A_{23}), (A_{6}, A_{29}), (A_{6}, A_{40}), \\ (A_{7}, A_{8}), (A_{7}, A_{24}), (A_{7}, A_{44}), (A_{8}, A_{2}), (A_{8}, A_{7}), (A_{8}, A_{20}), (A_{8}, A_{31}), (A_{8}, A_{41}), \\ (A_{9}, A_{11}), (A_{9}, A_{16}), (A_{9}, A_{22}), (A_{9}, A_{28}), (A_{9}, A_{45}), (A_{10}, A_{13}), (A_{10}, A_{32}), (A_{10}, A_{50}), \\ (A_{11}, A_{9}), (A_{11}, A_{10}), (A_{11}, A_{12}), (A_{11}, A_{17}), (A_{11}, A_{25}), (A_{11}, A_{30}), (A_{11}, A_{46}), \\ (A_{12}, A_{49}), (A_{13}, A_{14}), (A_{13}, A_{26}), (A_{13}, A_{50}), (A_{14}, A_{13}), (A_{14}, A_{32}), (A_{14}, A_{50}), \\ (A_{15}, A_{11}), (A_{15}, A_{16}), (A_{15}, A_{22}), (A_{15}, A_{28}), (A_{15}, A_{45}), (A_{16}, A_{15}), (A_{16}, A_{18}), \\ (A_{16}, A_{48}), (A_{17}, A_{33}), (A_{18}, A_{33}), (A_{19}, A_{34}), (A_{20}, A_{34}), (A_{21}, A_{34}), (A_{22}, A_{34}), \\ (A_{23}, A_{35}), (A_{24}, A_{35}), (A_{25}, A_{35}), (A_{26}, A_{35}), (A_{27}, A_{36}), (A_{28}, A_{36}), (A_{29}, A_{37}), \\ (A_{30}, A_{37}), (A_{31}, A_{38}), (A_{32}, A_{38})} . \end{aligned}$

Fig. 5 shows the graphic representation of the AA framework generated from ABF( $Π_{β}$ ).

ABF( $Π_{β}$ ) has six stable argument extensions $E_{i}$ ( $1 ⩽ i ⩽ 6$ ), in which both $E_{1}$ and $E_{2}$ shown below are consistent, but the others are inconsistent: $\begin{aligned} E_{1} = & {A_{1}, A_{4}, A_{6}, A_{8}, A_{11}, A_{14}, A_{16}, A_{19}, A_{21}, A_{22}, A_{24}, A_{26}, A_{27}, A_{28}, A_{33}, A_{37}, A_{38}, A_{39}, \\ A_{43}, A_{44}, A_{45}, A_{47}, A_{49}}, \\ E_{2} = & {A_{1}, A_{2}, A_{4}, A_{6}, A_{7}, A_{11}, A_{13}, A_{16}, A_{19}, A_{20}, A_{21}, A_{22}, A_{27}, A_{28}, A_{31}, A_{32}, A_{33}, A_{35}, \\ A_{37}, A_{39}, A_{41}, A_{43}, A_{45}, A_{47}, A_{49}}, \end{aligned}$ where $Concs (E_{1}) \cap {HB}_{e} = {\neg p, q, r} = M_{1}$ , $Concs (E_{2}) \cap {HB}_{e} = {\neg p, q, \neg r} = M_{2}$ . Thus, models of $Circum ({p \lor q, q \lor r}; p > q; r)$ are computed based on assumption-based argumentation.

5. Relation to the possible model semantics of EDLPs

Minimality-based semantics interprets disjunctions as exclusive as possible as addressed in [30]. Instead, to freely specify both inclusive and exclusive interpretations of disjunctions, the possible model semantics of an EDLP was introduced by Sakama and Inoue [30].

In this paper, we restrict our attention to a consistent possible model which does not contain a pair of complementary literals L and $\neg L$ . In the possible model semantics, a split program14

¹⁴
A split program of an EDLP can be encoded by choice rules supported in recent ASP solvers (e.g. clingo) [21].

of an EDLP P is defined as a ground ELP obtained from P by replacing every ground disjunctive rule

r : L_{1} | \dots | L_{ℓ} \leftarrow Γ

from P with the nondisjunctive rules in

R \subseteq {Split}_{r}

, where

\begin{array}{r} {Split}_{r} = {L_{i} \leftarrow Γ | Γ = body (r) for r \in P, i = 1, \dots, ℓ} \end{array}

and R is a non-empty subset of

{Split}_{r}

. Each rule in

{Split}_{r}

is called a split rule of r. We denote by

s p (P)

a split program of an EDLP P as defined as follows: given an EDLP

P = ⋃_{j} {r_{j}}

, where

r_{j}

is a rule,

\begin{array}{r} s p (P) = ⋃_{j} R_{r_{j}}, where each r_{j} is replaced with R_{r_{j}} s.t. R_{r_{j}} \subseteq {Split}_{r_{j}} and R_{r_{j}} \neq \emptyset . \end{array}

P has multiple split programs in general. Then, a consistent possible model of P is defined as a consistent answer set of a split program of P. It should be noticed that a possible model of P is not always minimal among possible models of P. Any consistent answer set of P is a consistent possible model of P but not vice versa [30]. An EDLP is consistent under the possible model semantics iff it has a consistent possible model; otherwise it is inconsistent.

The possible models of an EDLP can be captured by stable extensions of a standard ABA framework since each of its split programs is an ELP as follows.

Theorem 20.

Let P be an EDLP and $s p (P)$ a split program of P. Then S is a consistent possible model of P iff there is a split program $s p (P)$ which has a consistent stable argument extension $E$ of the ABA framework $F (s p (P)) = ⟨ L_{P}, s p (P), A_{P}, \bar{} \bar{} ⟩$ such that $S \cup Δ_{S} = Concs (E)$ (in other words, $S = Concs (E) \cap L i t_{P}$ ), where $Δ_{S}$ is a consistent stable assumption extension of the ABF $F (s p (P))$ .

Proof.

S is a consistent possible model of P

iff there is a split program $s p (P)$ which has a consistent answer set S

(due to the definition of a consistent possible model)

iff there is a consistent stable argument extension $E$ of the ABA framework $F (s p (P))$ such that

$S \cup Δ_{S} = Concs (E)$ , (due to Theorem 4)

where $Δ_{S}$ is a consistent stable assumption extension of the ABF $F (s p (P))$ due to Proposition 14. □

In what follows, we define an argument possible-extension (an argument p-extension, for short) and an assumption possible-extension (an assumption p-extension, for short) of ABF(P) which introduces the idea of possible models of an EDLP P in ABA.

Definition 24.

Let P be an EDLP, $s p (P)$ a split program of P and ABF $(s p (P)) = ⟨ L, s p (P), A_{P}, \bar{} \bar{} ⟩$ . We say that $E$ is a stable argument possible-extension (or a stable argument p-extension, for short) of ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ if $E$ is a stable argument extension of ABF $(s p (P))$ for some ELP $s p (P)$ ; and $E$ is a consistent stable argument possible-extension (or a consistent stable argument p-extension) of ABF(P) if $E$ is a consistent stable argument extension of ABF( $s p (P)$ ) for some ELP $s p (P)$ .

Similarly, we say that Δ is a stable assumption possible-extension (or a stable assumption p-extension, for short) of ABF(P) if Δ is a stable assumption extension of ABF $(s p (P))$ for some ELP $s p (P)$ ; and Δ is a consistent stable assumption possible-extension (or a consistent stable assumption p-extension) of ABF(P) if Δ is a consistent stable assumption extension of ABF( $s p (P)$ ) for some ELP $s p (P)$ .

Notice that only the inference rule $[MP]$ is needed to compute p-extensions of ABF(P) because any $s p (P)$ contains no disjunction. Regarding p-extensions, the following proposition and theorem hold.

Proposition 11.

Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P. Then S is a consistent possible model of P iff there is a consistent stable assumption p-extension $Δ_{S}$ of ABF(P) such that $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ where ${CN}_{s p (P)} (Δ_{S}) = S \cup Δ_{S}$ for some split program $s p (P)$ .

Proof.

S is a consistent possible model of P

iff there is a split program $s p (P)$ which has a consistent answer set S (due to its definition)

iff there is a consistent stable assumption extension $Δ_{S}$ of ABF( $s p (P)$ ) for a split program $s p (P)$ s.t.

$Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ where ${CN}_{s p (P)} (Δ_{S}) = S \cup Δ_{S}$ is consistent (due to Proposition 9)

iff there is a consistent stable assumption p-extension $Δ_{S}$ of ABF(P) such that

$Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ where ${CN}_{s p (P)} (Δ_{S}) = S \cup Δ_{S}$ for some $s p (P)$ . □

Theorem 21.

Let ABF( $P) = ⟨ L, P, A_{P}, \bar{} \bar{} ⟩$ be the ABF translated from an EDLP P. S is a consistent possible model of P iff there is a consistent stable argument p-extension $E$ of ABF(P) such that $S \cup Δ_{S} = Concs (E)$ , where $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ is a consistent stable assumption p-extension of ABF(P).

Proof.

S is a consistent possible model of P

iff there is a consistent stable argument extension $E$ along with the consistent stable assumption

extension $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ of ABF( $s p (P)$ ) for some split program $s p (P)$ such that

$Concs (E) = S \cup Δ_{S} = {CN}_{s p (P)} (Δ_{S})$ which is consistent (due to Proposition 11 and Theorem 10)

iff there is a consistent stable argument p-extension $E$ of ABF(P) such that $S \cup Δ_{S} = Concs (E)$ ,

where $Δ_{S} = {not ℓ | ℓ \in (L i t_{P} ∖ S)}$ is a consistent stable assumption p-extension of ABF(P). □

For an EDLP P with no disjunction, Proposition 11 reduces to Proposition 14, while Theorem 21 reduces to Theorem 4 respectively.

The following example shows that there is a case that needs the inclusive interpretation of disjunction though Kyoto protocol problem in Section 1 needs the exclusive interpretation of the disjunction $p | y$ . Example 14 (Taxi fare problem).

Consider the following problem.

Each of Jack and Mary takes a taxi if it is available. Suppose that a taxi is available, where its fare is v dollars. If they share it, each may pay only the half of v (say hv) for a taxi fare; otherwise anyone who takes it should pay v dollars.

This situation can be represented by the following EDLP $P_{5}$ , where j (resp. m) denotes that Jack (resp. Mary) takes a taxi, $t x$ denotes that a taxi is available, and v (resp. $h v$ ) denotes that a person who takes a taxi pays v (resp. $h v$ ) dollars: $\begin{matrix} P_{5} = {j | m \leftarrow t x, t x \leftarrow, h v \leftarrow j, m, v \leftarrow j, not m, v \leftarrow m, not j} . \end{matrix}$

$P_{5}$ has two answer sets $S_{1} = {t x, j, v}$ and $S_{2} = {t x, m, v}$ , where $S_{1}$ (resp. $S_{2}$ ) shows the case that $Jack$ (resp. $Mary$ ) pays v dollar due to taking a taxi alone.

On the other hand, $P_{5}$ has three split programs: $π_{1} = π \cup {j \leftarrow t x}$ , $π_{2} = π \cup {m \leftarrow t x}$ and $π_{3} = π \cup {j \leftarrow t x, m \leftarrow t x}$ , where $π = {v \leftarrow j, not m, v \leftarrow m, not j, h v \leftarrow j, m, t x \leftarrow}$ . Since each $π_{i}$ has the unique answer set $S_{i}$ ( $1 ⩽ i ⩽ 3$ ), $P_{5}$ has three possible models $S_{1}$ , $S_{2}$ along with $S_{3} = {t x, j, m, h v}$ which corresponds to the third case such that both of $Jack$ and $Mary$ pay $hv$ dollars thanks to sharing a taxi. Notice that $S_{3}$ is not the answer set of $P_{5}$ .15

¹⁵
However, when the problem is expressed by the EDLP $P_{5}^{'} = P_{5} \cup {j | \neg j \leftarrow, m | \neg m \leftarrow}$ instead of $P_{5}$ , $P_{5}^{'}$ has three answer sets, $S_{1}^{'} = {t x, j, v, \neg m}$ , $S_{2}^{'} = {t x, m, v, \neg j}$ and $S_{3} = {t x, j, m, h v}$ corresponding to three cases.

In contrast, the same goes for argumentation under the stable semantics. First we construct ABF( $P_{5}$ ) translated from $P_{5}$ (resp. ABF( $π_{i}$ ) translated from $π_{i}$ ( $1 ⩽ i ⩽ 3$ )). In this case, every extension of the respective ABF is consistent since each language does not include explicit negation. Then, ABF( $π_{1}$ ) (resp. ABF( $π_{2}$ ), ABF( $π_{3}$ )) has the unique stable assumption extension $Δ_{1} = {not m, not h v}$ (resp. $Δ_{2} = {not j, not h v}$ , $Δ_{3} = {not v}$ ), where ${CN}_{π_{1}} (Δ_{1}) = {CN}_{P_{5}} (Δ_{1}) = {t x, j, v} \cup Δ_{1} = S_{1} \cup Δ_{1}$ , ${CN}_{π_{2}} (Δ_{2}) = {CN}_{P_{5}} (Δ_{2}) = {t x, m, v} \cup Δ_{2} = S_{2} \cup Δ_{2}$ and ${CN}_{π_{3}} (Δ_{3}) = {t x, j, m, h v} \cup Δ_{3} = S_{3} \cup Δ_{3} \neq {CN}_{P_{5}} (Δ_{3})$ . Similarly, ABF( $π_{1}$ ) (resp. ABF( $π_{2}$ ), ABF( $π_{3}$ )) has the unique stable argument extension $E_{1}$ (resp. $E_{2}$ , $E_{3}$ ), where $Concs (E_{i}) = S_{i} \cup Δ_{i}$ ( $1 ⩽ i ⩽ 3$ ). Hence ABF( $P_{5}$ ) has three stable assumption p-extensions $Δ_{i}$ ( $1 ⩽ i ⩽ 3$ ) along with three argument p-extensions $E_{i}$ ( $1 ⩽ i ⩽ 3$ ), while it has two stable assumption extensions $Δ_{1}, Δ_{2}$ along with two argument extensions $E_{1}, E_{2}$ .

6. Related work

Beirlaen et al.’s extended ASPIC $^{+}$ framework [2,3] as well as Heyninck and Arieli’s ABF induced by a DLP [18] can handle disjunctive information in argumentation. Moreover, it is shown that Heyninck and Arieli’s ABF induced by a DLP can capture stable model semantics of a DLP as shown in Proposition 1 [18, Proposition 2 and Proposition 3]. However the semantic correspondence to a disjunctive default theory is not shown in both Beirlaen et al.’s work and Heyninck and Arieli’s work. Notice here that Example 4 illustrates that an NDP (i.e. an EDLP having no classical negation) can be transformed to a disjunctive default theory, whereas a DLP used in Heyninck and Arieli’s ABF can neither be done so nor has the semantic correspondence to a default theory. In contrast, our approach based on a translation from an EDLP can capture not only the answer set semantics of an EDLP but also the semantics of a disjunctive default theory as shown in Theorem 8 (or Proposition 5) and Theorem 12. These are written in Table 1 and Table 2 in which existing work is shown in italic letter with proper references. Regarding the problem of how to construct arguments under the given disjunctive information, Beirlaen et al. [2,3] allowed arguments to have disjunctive conclusions, while Heyninck and Arieli [18] neither defined arguments nor took account of argument extensions in their ABFs. In contrast, in our ABFs, arguments are defined as trees due to Definition 12 but they are not allowed to have disjunctive conclusions according to Definition 13. Notice here that Heyninck and Arieli’s ABF has also three inference rules: $[MP]$ , $[Res]$ and $[RBC]$ like our ABFs though the classical ∨ is used instead of |. Then, thanks to our approach, it is possible to construct trees and define arguments in their ABF based on the slightly modified Definition 12 by replacing | with ∨. As a result, we may obtain a new theorem for a DLP P showing the correspondence between stable models of P and stable argument extensions of their ABF(P). Though it is possible to fill in the open box of Table 1 with such a theorem for a DLP, its details are omitted in this paper.

Table 1
Correspondence between LP and ABA

LP ABA

Class Semantics Assumption extensions Argument extensions

ELP p-stable models Proposition 12 Theorem 2 [32]

answer sets Proposition 13 Proposition 14 Theorem 3 [32] Theorem 4 [33]

DLP stable models Proposition 1 [18]

NDP answer sets Proposition 3 Theorem 6

EDLP p-stable models Proposition 4 Theorem 7

answer sets Proposition 5 Proposition 9 Theorem 8 Theorem 10

possible models Proposition 11 Theorem 21

LP	ABA
ELP	p-stable models	Proposition 12	Theorem 2 [32]
answer sets	Proposition 13 Proposition 14	Theorem 3 [32] Theorem 4 [33]
DLP	stable models	Proposition 1 [18]
NDP	answer sets	Proposition 3	Theorem 6
EDLP	p-stable models	Proposition 4	Theorem 7
answer sets	Proposition 5 Proposition 9	Theorem 8 Theorem 10
possible models	Proposition 11	Theorem 21

Table 2

Correspondence between NMR and ABA

NMR		EDLP	ABA

Formalisms	Semantics	Answer sets	Argument extensions
disjunctive default theory	extensions	Theorem 1 [16]	Theorem 12 Theorem 13
parallel circumscription	models	Theorem 16 [29]	Theorem 18
prioritized circumscription	models	Theorem 17	Theorem 19

Lehtonen et al. [19] presented algorithms for reasoning in a default logic instantiation of ABA, where they defined the assumption-based argumentation framework (ABF) corresponding to a propositional default theory. In [19, Example 1], they showed the ABF corresponding a default theory which contains disjunctive formulas. However when the ABF corresponding to the default theory $D_{1}$ is constructed according to [19, Definition 1], the ABF has the same difficulty as $D_{1}$ addressed in Example 1. The reason is as follows: In their approach, given $(L_{p}, R_{p})$ as a deductive system for propositional logic, the ABF corresponding to $D_{1}$ is $F = (L, R, W, A, \bar{} \bar{})$ , where $L = L_{p} \cup {M α ∣ α \in L_{p}}$ , $R = R_{p} \cup {r \leftarrow p, M r, k \leftarrow r, M k, f \leftarrow y, M f, k \leftarrow f, M k}$ , $W = D_{1} \cap L_{p} = {p \lor y}$ , $A = {M r, M k, M f}$ and a mapping function $\bar{} \bar{}$ defined by $\overline{M x} = \neg x$ for all $M x \in A$ . Besides, $A \subseteq A$ attacks $B \subseteq A$ iff $W \cup A ⊢_{R} \neg b$ for some $M b \in B$ , where $⊢_{R}$ denotes derivability via $R$ . Then since there is no attacks between any two sets of assumptions, the ABF F has a unique assumption extension $A$ under the stable (resp. grounded, complete) semantics, from which the expected result k is never derived under each semantics due to [19, Proposition 1]. In contrast, in our approach based on the disjunctive default theory $D_{2}$ which has the associated EDLP $P_{1}$ , Example 12 shows that we can obtain the expected result k from the stable extensions $E_{i}$ of the ABF translated from the EDLP $P_{1}$ which correspond to the extensions $E_{i} (i = 1, 2)$ of the ddt $D_{2} = emb (P_{1})$ based on Theorem 12, Theorem 8 and Proposition 5. Moreover, interestingly, Example 8 shows that the skeptical result meant by the problem is obtained under the skeptical semantics (i.e. the grounded and ideal semantics) in our ABF.

Bondarenko et al. [5] showed a correspondence between Reiter’s default extensions and stable extensions of the corresponding assumption-based framework (ABF) in [5, Theorem 3.16]. This indicates that Kyoto protocol problem shown in Example 1 cannot be solved under the stable semantics in their ABF corresponding to the default theory $D_{1}$ . Disjunctive default theories are not considered in [5]. Moreover, in [5, Theorem 6.7], Bondarenko et al. showed a correspondence between models of parallel circumscription: $Circum (T; P; Z)$ (i.e. $P, Z$ -minimal models of T) and maximal conflict-free extensions of the corresponding ABF, assuming that T is a first order theory without function symbols, T satisfies unique names axioms and domain closure axioms, and every model of T is a Herbrand model of T. However, they showed nothing about a semantic correspondence between prioritized circumscription and assumption-based frameworks. In contrast, this paper shows a correspondence between Herbrand models of parallel circumscription and stable argument extensions of our ABF in Theorem 18 as well as a correspondence between Herbrand models of prioritized circumscription and stable argument extensions of our ABF in Theorem 19 (see Table 2). Regarding logic programming, they showed a correspondence between stable models of an NLP and the stable extensions of the corresponding ABF in [5, Theorem 3.13]. Their theorem is, however, the special case of Proposition 13 for an ELP, Proposition 1 for a DLP, Proposition 3 for an NDP, and Proposition 5 for an EDLP.

Caminada and Schulz [7] showed the equivalence between various ABA semantics and various semantics of NLPs. NLPs prohibiting both disjunction and classical negation are less expressive than DLPs and ELPs. Hence a faithful modeling of real world problems often becomes impossible in the scope of NLPs.

7. Conclusion

We proposed an assumption-based framework (ABF) translated from an extended disjunctive logic program (EDLP), which incorporates explicit negation as well as | rather than ∨ in Heyninck and Arieli’s ABF induced by a DLP. Thanks to our proposed ABFs, the new results about the semantic relationships between logic programming (LP) and ABA as well as nonmonotonic reasoning (NMR) and ABA are obtained. That is, as for LP, the answer set semantics of an EDLP can be captured by the stable extensions of the ABF translated from an EDLP with trivialization rules, while as for NMR, extensions of a disjunctive default theory (resp. models of prioritized circumscription) can be captured by the stable extensions of the ABF translated from the EDLP corresponding to a given disjunctive default theory (resp. the EDLP corresponding to a given prioritized circumscription). Moreover, as another relationship to LP, it is shown that the possible model semantics of an EDLP is captured by the possible extensions under stable semantics of the ABF translated from an EDLP (see Table 1 and Table 2).

In the study of nonmonotonic reasoning, disjunctive default logic [16] was proposed as a generalization of default logic [27] to overcome difficulties of default logic in handling disjunctive information. In fact, defaults do not work in the default theory $D_{1}$ expressing the Kyoto protocol problem [3] as well as in $d_{1}$ corresponding to the DLP $π_{1}$ [18, Example 1] shown in Example 4 due to lack of the capability to reason by cases in these default theories. As a result, $D_{1}$ as well as the ABFs instantiated with $D_{1}$ [5,19] reveal difficulties such that the expected result cannot be obtained from them as discussed in Section 1 and Section 6. In contrast, in our approach, the expected result k is successfully obtained not only from the stable extensions of the ABF translated from the EDLP $P_{1}$ which correspond to the extensions of the disjunctive default theory $D_{2} = emb (P_{1})$ as shown in Example 12 but also from the extension(s) under the skeptical semantics (i.e. the grounded and ideal) as well as under the preferred semantics in our proposed ABF as shown in Example 8. Thus based on our ABFs corresponding to disjunctive default theories via EDLPs, our approach can overcome difficulties of assumption-based frameworks corresponding to default theories (e.g. [5,19]) in handling disjunctive information.

To sum up, as for argument extensions, Theorem 2 [32, Theorem 3] and Theorem 3 [32, Theorem 4] for an ELP (resp. Theorem 4 [33, Theorem 5] for a consistent ELP) in standard ABA frameworks are broadened to Theorem 7 and Theorem 8 for an EDLP (resp. Theorem 10 for a consistent EDLP) in generalized ABA frameworks, i.e. ABFs translated from EDLPs. Similarly as for assumption extensions, Proposition 12 and Proposition 13 (resp. Proposition 14) for the standard ABA framework instantiated with an ELP (resp. a consistent ELP) as well as Proposition 1 [18, Proposition 2 and Proposition 3] for the ABF induced by a DLP are generalized to Proposition 4 and Proposition 5 (resp. Proposition 9) for the respective ABFs translated from EDLPs (resp. a consistent EDLP). These are summarized in Table 1.

As one of practical advantages of our approach, even if disjunctive information exists, we can directly use dialectic proof procedures [9,11] since the AA framework [8] can be generated from our ABF treating disjunctive information.

In (extended) disjunctive logic programming, the existence of disjunction generally increases the expressive power of logic programs while brings computational penalty [13]. By analogy, argumentation in ABFs translated from (E)DLPs increases the expressive power of ABF while it would introduce additional complexity. Hence, the analysis of complexity is left for future work. Moreover, our future work is to explore and find the more general correspondence between Assumption-based frameworks and disjunctive default theories without intervening EDLPs.

Footnotes

Acknowledgements

The author would like to thank Chiaki Sakama and the anonymous reviewers of the paper for their valuable comments and suggestions.

New theorems for an ELP

References

Arieli,

Borg,

Heyninck and

Straßer, Logic-based approaches to formal argumentation, IfCoLog Journal of Logics and their Applications 8(6) (2021), 1793–1898.

Beirlaen,

Heyninck and

Straßer, Reasoning by cases in structured argumentation, in: Proceedings of the 2017 ACM Symposium on Applied Computing, ACM, 2017, pp. 989–994.

Beirlaen,

Heyninck and

Straßer, A critical assessment of Pollock’s work on logic-based argumentation with suppositions, in: Proceedings of the 17th International Workshop on Non-monotonic Reasoning (NMR-2018), 2018, pp. 63–72.

Ben-Eliyahu and

Dechter, Propositional semantics for disjunctive logic programs, Annals of Mathematics and Artificial Intelligence 12(1–2) (1994), 53–87. doi:10.1007/BF01530761.

Bondarenko,

P.M.

Dung,

R.A.

Kowalski and

Toni, An abstract, argumentation-theoretic approach to default reasoning, Artificial Intelligence 93 (1997), 63–101. doi:10.1016/S0004-3702(97)00015-5.

Caminada and

Amgoud, On the evaluation of argumentation formalisms, Artificial Intelligence 171(5–6) (2007), 286–310. doi:10.1016/j.artint.2007.02.003.

Caminada and

Schulz, On the equivalence between assumption-based argumentation and logic programming, Journal of Artificial Intelligence Research 60 (2017), 779–825. doi:10.1613/jair.5581.

P.M.

Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77(2) (1995), 321–358. doi:10.1016/0004-3702(94)00041-X.

P.M.

Dung,

R.A.

Kowalski and

Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence 170(2) (2006), 114–159. doi:10.1016/j.artint.2005.07.002.

10.

P.M.

Dung,

R.A.

Kowalski and

Toni, Assumption-based argumentation, in: Argumentation in Artificial Intelligence, Springer-Verlag, 2009, pp. 199–218. doi:10.1007/978-0-387-98197-0_10.

11.

P.M.

Dung,

Mancarella and

Toni, Computing ideal sceptical argumentation, Artificial Intelligence 171 (2007), 642–674. doi:10.1016/j.artint.2007.05.003.

12.

P.M.

Dung and

P.M.

Thang, Closure and consistency in logic-associated argumentation, Journal of Artificial Intelligence Research 49 (2014), 79–109. doi:10.1613/jair.4107.

13.

Eiter and

Gottlob, Complexity results for disjunctive logic programming and application to nonmonotonic logics, in: Logic Programming, Proceedings of the 10th International Symposium (ILPS-1993), MIT Press, 1993, pp. 266–278.

14.

Gelfond and

Lifschitz, The stable model semantics for logic programming, in: Logic Programming, Proceedings of the Fifth International Conference and Symposium (ICLP/SLP-1988), MIT Press, 1988, pp. 1070–1080.

15.

Gelfond and

Lifschitz, Classical negation in logic programs and disjunctive databases, New Generation Computing 9 (1991), 365–385. doi:10.1007/BF03037169.

16.

Gelfond,

Lifschitz,

Przymusinska and

Truszczynski, Disjunctive defaults, in: Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR-1991), 1991, pp. 230–237.

17.

Heyninck and

Arieli, On the semantics of simple contrapositive assumption-based argumentation frameworks, in: Proceedings of the Seventh International Conference on Computational Models of Argument (COMMA-2018), IOS Press, 2018, pp. 9–20.

18.

Heyninck and

Arieli, An argumentative characterization of disjunctive logic programming, in: Proceedings of the 19th EPIA Conference on Artificial Intelligence (EPIA-2019), 2019, pp. 526–538.

19.

Lehtonen,

J.P.

Wallner and

Järvisalo, Algorithms for reasoning in a default logic instantiation of assumption-based argumentation, in: Proceedings of the 9th International Conference on Computational Models of Argument (COMMA-2022), IOS Press, 2022, pp. 236–247.

20.

Lifschitz, Computing circumscription, in: Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI-1985), 1985, pp. 121–127.

21.

V.W.

Marek,

Niemelä and

Truszczynski, Logic programs with monotone abstract constraint atoms, Theory and Practice of Logic Programming 8(2) (2008), 167–199. doi:10.1017/S147106840700302X.

22.

McCarthy, Circumscription – a form of non-monotonic reasoning, Artificial Intelligence 13 (1980), 27–39. doi:10.1016/0004-3702(80)90011-9.

23.

McCarthy, Applications of circumscription to formalizing commonsense knowledge, Artificial Intelligence 28 (1986), 89–116. doi:10.1016/0004-3702(86)90032-9.

24.

Modgil and

Prakken, The ASPIC+ framework for structured argumentation: A tutorial, Argument and Computation 5(3) (2014), 31–62. doi:10.1080/19462166.2013.869766.

25.

Prakken, An abstract framework for argumentation with structured arguments, Argument and Computation 1(2) (2010), 93–124. doi:10.1080/19462160903564592.

26.

T.C.

Przymusinski, Stable semantics for disjunctive programs, New Generation Computing 9 (1991), 401–424. doi:10.1007/BF03037171.

27.

Reiter, A logic for default reasoning, Artificial Intelligence 13 (1980), 81–132. doi:10.1016/0004-3702(80)90014-4.

28.

Sakama and

Inoue, Paraconsistent stable semantics for extended disjunctive programs, Journal of Logic and Computation 5(3) (1995), 265–285. doi:10.1093/logcom/5.3.265.

29.

Sakama and

Inoue, Embedding circumscriptive theories in general disjunctive programs, in: Proceedings of the Third International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-1995), 1995, pp. 344–357. doi:10.1007/3-540-59487-6_25.

30.

Sakama and

Inoue, Abductive logic programming and disjunctive logic programming: their relationship and transferability, Journal of Logic and Computation 44(1–3) (2000), 75–100. doi:10.1016/S0743-1066(99)00073-4.

31.

Schulz and

Toni, Justifying answer sets using argumentation, Theory and Practice of Logic Programming 16(1) (2016), 59–110. doi:10.1017/S1471068414000702.

32.

Wakaki, Assumption-based argumentation equipped with preferences and its application to decision-making, practical reasoning, and epistemic reasoning, Journal of Computational Intelligence 33(4) (2017), 706–736. doi:10.1111/coin.12111.

33.

Wakaki, Consistency in assumption-based argumentation, in: Proceedings of the 8th International Conference on Computational Models of Argument (COMMA-2020), IOS Press, 2020, pp. 371–382.

34.

Wakaki, Assumption-based argumentation for extended disjunctive logic programming, in: Proceedings of the 12th International Symposium on Foundations of Information and Knowledge Systems (FoIKS-2022), 2022, pp. 35–54.

35.

Wakaki and

Satoh, Compiling prioritized circumscription into extended logic programs, in: Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-1997), 1997, pp. 182–187.

36.

https://arxiv.org/pdf/2106.10966.pdf.

LP		ABA

Class	Semantics	Assumption extensions	Argument extensions
ELP	p-stable models	Proposition 12	Theorem 2 [32]
ELP	answer sets	Proposition 13 Proposition 14	Theorem 3 [32] Theorem 4 [33]
DLP	stable models	Proposition 1 [18]
NDP	answer sets	Proposition 3	Theorem 6
EDLP	p-stable models	Proposition 4	Theorem 7
	answer sets	Proposition 5 Proposition 9	Theorem 8 Theorem 10
	possible models	Proposition 11	Theorem 21

Assumption-based argumentation for extended disjunctive logic programming and its relation to nonmonotonic reasoning

Abstract

Keywords

1. Introduction

1.1. Background

1 Semantically, the latter requires an extension to contain one of the two disjunctive terms, rather than the disjunction [16].

2 In this paper, we use the abbreviation “ABF” to primarily denote assumption-based framework but sometimes ABA framework in different approaches [5,10,18,19,32,33] though it may refer to the respectively defined framework based on ABA in each approach.

3 For example, the difference between DLPs and NDPs as shown in Eample 4, the interesting results under the skeptical semantics (e.g. grounded) in Example 8, and the relation between our ABF and a standard ABA as shown in Proposition 8, etc.

2.1. Assumption-based argumentation

Definition 1 ([10,11]).

Definition 2 (Rationality postulates [12]).

Definition 3 (Assumption-based frameworks [18]).

Definition 4 (ABF semantics [5]).

2.2. Disjunctive logic programs

2.3. Extended disjunctive logic programs

Definition 5 (answer sets).

7 In [32], ¬ . C M is used rather than Δ M to refer to the set { not L | L ∈ L i t P ∖ M } . However for notational convenience, Δ M is used instead of ¬ . C M to refer to this set in this paper.

Theorem 3 ([32, Theorem 4]).

Theorem 4 ([33, Theorem 5]).

3. ABA for extended disjunctive logic programming

3.1. Assumption-based frameworks translated from EDLPs

Definition 16 (Rationality postulates).

Definition 18 (Consistency in ABFs translated from EDLPs).

4. Relation to nonmonotonic reasoning

4.1. Correspondence between disjunctive default logic and assumption-based argumentation

Definition 19 ([16, Definition 5.1]).

Definition 20 ([16, Definition 5.2]).

Theorem 11 ([16, Theorem 5.3]).

4.2. Correspondence between prioritized circumscription and assumption-based argumentation

Definition 21 ([20]).

12 It is said that a clause C 1 subsumes a clause C 2 if C 1 θ ⊆ C 2 holds for some substitution θ [29].

14 A split program of an EDLP can be encoded by choice rules supported in recent ASP solvers (e.g. clingo) [21].

15 However, when the problem is expressed by the EDLP P 5 ′ = P 5 ∪ { j | ¬ j ← , m | ¬ m ← } instead of P 5 , P 5 ′ has three answer sets, S 1 ′ = { t x , j , v , ¬ m } , S 2 ′ = { t x , m , v , ¬ j } and S 3 = { t x , j , m , h v } corresponding to three cases.

Footnotes

Acknowledgements

New theorems for an ELP

References

¹
Semantically, the latter requires an extension to contain one of the two disjunctive terms, rather than the disjunction [16].

²
In this paper, we use the abbreviation “ABF” to primarily denote assumption-based framework but sometimes ABA framework in different approaches [5,10,18,19,32,33] though it may refer to the respectively defined framework based on ABA in each approach.

³
For example, the difference between DLPs and NDPs as shown in Eample 4, the interesting results under the skeptical semantics (e.g. grounded) in Example 8, and the relation between our ABF and a standard ABA as shown in Proposition 8, etc.

⁷
In [32], $\neg . C M$ is used rather than $Δ_{M}$ to refer to the set ${not L | L \in L i t_{P} ∖ M}$ . However for notational convenience, $Δ_{M}$ is used instead of $\neg . C M$ to refer to this set in this paper.

¹²
It is said that a clause $C_{1}$ subsumes a clause $C_{2}$ if $C_{1} θ \subseteq C_{2}$ holds for some substitution θ [29].

¹⁴
A split program of an EDLP can be encoded by choice rules supported in recent ASP solvers (e.g. clingo) [21].