On the Accrual of Arguments in Defeasible Logic Programming

1 Introduction

In the last two decades, argumentation has evolved as a powerful paradigm to formalize commonsense qualitative reasoning. Several argumentation frameworks have been developed, notably Defeasible Logic Programming (DeLP) [Garc´ıa and Simari, 2004], a logic programming approach to argumentation which has proven to be successful for many real-world applications (e.g., [Ches˜nevar et al., 2006]).

The notion of accrual of arguments has received some attention from the argumentation community [Verheij, 1996; Prakken, 2005]. This notion is based on the intuitive idea that having more reasons or arguments for a given conclusion makes such a conclusion more credible. Modeling accrual of arguments is not a simple issue, and previous research [Prakken, 2005] has identified different principles that should hold for performing accrual of arguments in a sound way.

In this paper we propose an approach to model accrual of arguments in the context of DeLP. We show that accrued arguments can be conceptualized as structures which can be subject to a dialectical analysis similar to the one applied in conventional argumentation systems. We also analyze Prakken's principles in the context of our proposal, and describe some interesting features of our approach.

The rest of this paper is structured as follows. The next section briefly describes DeLP. Then, we present the notion of accrued structure, which plays a central role in our proposal.

∗Research partially supported by projects PIP 112-20080102798 (CONICET), 24/ZN10 and 24/N023 (UNS), and TIN200768005-C04-01 and TIN2006-15662-C02-02 (MEC, Spain).

Based on this notion, we then formalize the notions of attack and defeat among accrued structures. Next, we introduce the dialectical analysis on accrued structures, formalizing the notion of justified accrued structure. Then, we discuss related work and describe some significant features of our approach. Finally, we present the main conclusions obtained.

2 The DeLP system: a brief overview

Next we will briefly introduce DeLP (for full details see [Garc´ıa and Simari, 2004]). As we will see in the next section, DeLP will provide a natural context for modeling the accrual of arguments. We begin by introducing its language.

Definition 1 (DeLP Language). The DeLP language is defined in terms of three disjoint sets of clauses: a set of facts which are literals, a set of strict rules of the form L0 ←- L1, ..., Lk, and a set of defeasible rules of the form L0 -< L1, ..., Lk, where L0, . . . , Lk, with k > 0, are literals. In the language of DeLP, a literal "L" is a ground atom "A" or a negated ground atom "∼A", where "∼" represents the strong negation.

Pragmatically, facts and strict rules will be used to represent strict (non defeasible) information (e.g., mammal ←- dog) whereas defeasible rules will be used to represent tentative or weak information (e.g., flies -< bird).

Definition 2 (DeLP program). A DeLP program P is a finite set of facts, strict rules and defeasible rules. In a program P we will distinguish the subset Π of facts and strict rules, and the subset Δ of defeasible rules. When required, we will denote P as (Π, Δ).

Example 1. The following constitutes a DeLP program:

Definition 3 (Defeasible derivation). Let P be a DeLP program and L a ground literal. A defeasible derivation of L from P, consists of a finite sequence L1, . . . , Ln = L of ground literals, s.t. for each i, 1 ≤ i ≤ n, Li is a fact or there exists a rule Ri in P (strict or defeasible) with head Li and body B1, . . . ,Bm, s.t. each literal on the body of the rule is an element Lj of the sequence appearing before Li (j ≤ i).

We say that a given set of DeLP clauses is contradictory if and only if there exists a defeasible derivation for a pair of complementary literals (w.r.t. strong negation) from this set.

Definition 4 (Argument). Let P = (Π,Δ) be a DeLP program. We will say that 〈A, h〉 is an argument for a literal h from P, if A is a minimal set of defeasible rules (A⊆ Δ), such that: (1) there exists a defeasible derivation for h from Π∪A, and (2) the set Π ∪ A is non-contradictory.

Definition 5 (Subargument). An argument 〈B, q〉 is a subargument of an argument 〈A, h〉 if B ⊆ A.

Example 2. Consider the DeLP program in Ex. 1. Then h, g, a and d, b, c, a are defeasible derivations for a, 〈A1, a〉 = 〈{(a -< b, c), (b -< d)}, a〉 and 〈A2, a〉 = 〈{a -< g}, a〉 are arguments, and 〈{b -< d}, b〉 is a subargument of 〈A1, a〉.

The attack among arguments in DeLP is defined in terms of the notion of disagreement of literals. Given a DeLP program P = (Π,Δ), two literals h1 and h2 are in disagreement (or just disagree) iff the set Π ∪ {h1, h2} is contradictory. Then, given two arguments 〈A, h〉 and 〈B, k〉 in P, 〈B, k〉 attacks 〈A, h〉 at literal h′ iff there exist a subargument 〈A′ , h′ 〉 of 〈A, h〉 such that k and h′ disagree. The subargument 〈A′ , h′ 〉 is called the disagreement subargument.

3 Modeling the Accrual of Arguments

We will introduce next the notion of accrued structure in order to model the accrual of different arguments for the same conclusion.

Definition 6 (Accrued Structure). Let P be a DeLP program, and let Ω be a set of arguments in P supporting the same conclusion h, i.e., Ω = {〈A1, h〉, ..., 〈An, h〉}. We define the accrued structure for h (or just a-structure) from the set Ω (denoted Accrual(Ω)) as [Φ, h], where Φ = A1 ∪ ... ∪ An.

When Ω = ∅ we get the special accrued structure [∅, ϵ], representing the accrual of no argument.

Example 3. Consider the DeLP program P in Ex. 1. Let

〈A1, a〉= 〈{(a -< b, c), (b -< d)}, a〉,

• 〈A2, a〉= 〈{(a -< b, c), (b -< e)}, a〉,

〈A3, a〉= 〈{(a -< b, f ), (b -< e)}, a〉 and

• 〈A4, a〉= 〈{a -< g}, a〉 be arguments in P. Then Accrual({〈A1, a〉, 〈A4, a〉}) = [Φ1, a] where
• Φ1 = {(a -< b, c), (b -< d), (a -< g)} (Fig. 1a) Accrual({〈A1, a〉, 〈A3, a〉}) = [Φ2, a] where

Φ2 = {(a -< b, c), (a -< b, f), (b -< d), (b -< e)} (Fig. 1b)

Accrual({〈A1, a〉, 〈A2, a〉}) = [Φ3, a] where

• Φ3 = {(a -< b, c), (b -< d), (b -< e)} (Fig. 1c)

An a-structure for h can be seen as a special kind of argument which subsumes different chains of reasoning which provide support for h. For instance, the a-structure [Φ1, a] (Fig. 1a) provides two alternative chains of reasoning supporting a, both coming from each of the arguments accrued. The graphical representation of a-structures shows both strict and defeasible rules of the subsumed chains of reasoning (although the a-structure itself has only defeasible rules).

The case of [Φ2, a] in Ex. 3 illustrates an important feature of our notion of accrual. If two arguments for the same conclusion share some intermediate conclusion but support it in different ways, then by accruing them the reasons for the intermediate conclusion also accrue. Fig. 1b shows this situation for two different reasons for the intermediate conclusion b. The case of [Φ2, a] in Ex. 3 highlights another feature of our characterization of accrual. Although each of the arguments accrued stands for one chain of reasoning supporting a conclusion a, the resulting a-structure [Φ2, a] stands for four chains of reasoning for a (two of them are not explicitly present in the individual arguments accrued).

The case of [Φ3, a] in Ex. 3 (Fig. 1c) illustrates a situation similar to the previous one, but in this case the arguments involved share not only the intermediate conclusion b but also their topmost parts (more precisely the rule a -< b, c).

An important question that naturally emerges when considering the way we accrue arguments is what happens when accruing two arguments that are in conflict (for instance because they have contradictory intermediate conclusions). We will come back to this issue later.

Definition 7. Let [Φ, h] be an a-structure. Then the set of arguments in [Φ, h], denoted as Args([Φ, h]), is the set of all arguments 〈Ai, h〉 s.t. Ai ⊆ Φ. In particular, Args([∅, ϵ]) =def ∅.

Example 4. Consider the arguments and astructures presented in Ex. 3 (Fig. 1). Then Args([Φ3, a]) = {〈A1, a〉, 〈A2, a〉} and Args([Φ2, a]) = {〈A1, a〉, 〈A2, a〉, 〈A3, a〉, 〈{(a -< b, f ), (b -< d)}, a〉}.

Although Accrual and Args are not reverse operations (as illustrated by the case of [Φ2, a] in Exs. 3 and 4), we can ensure that the arguments accrued will always be among the arguments in the resulting a-structure. We can also ensure that by accruing the arguments in a given a-structure [Ψ, k] we always get [Ψ, k] as a result.

Property 1. Let Ω be a set of arguments for a given conclusion h. Then Args(Accrual(Ω)) ⊇ Ω. Besides, for any a-structure [Ψ, k] it holds that Accrual(Args([Ψ, k])) = [Ψ, k]. 1

Definition 8 (Maximal a-structure). Let P be a DeLP program. We say that an a-structure [Φ, h] is maximal iff

Args([Φ, h]) contains all arguments in P with conclusion h.

Example 5. Consider the DeLP program P in Ex. 1. Then [{(b -< d), (b -< e)}, b] is a maximal a-structure in P, whereas [{(b -< d)}, b] is not.

Next we will introduce the notion of narrowing of an astructure, which is analogous to the notion of narrowing in [Verheij, 1996]. Intuitively, a narrowing of an a-structure [Φ, h] is an a-structure [Θ, h] accounting for a subset of Args([Φ, h]).

Definition 9 (Narrowing of an a-structure). Let [Φ, h] and [Θ, h] be two a-structures. We say that [Θ, h] is a narrowing of [Φ, h] iff Args([Θ, h]) ⊆ Args([Φ, h]).

Example 6. Consider the a-structures [Φ2, a] and [Φ3, a] in Ex. 3. Then [Φ3, a] and [Φ2, a] itself are narrowings of [Φ2, a].

1 Proofs are not included for space reasons.

Next we will introduce the notion of accrued sub-structure, that is analogous to the notion of subargument but for astructures. Intuitively, an accrued sub-structure of an astructure [Φ, h] is an a-structure supporting an intermediate conclusion k of [Φ, h] and accounting for a subset of the reasons that support k in [Φ, h]. The one that accounts for all the reasons supporting k in [Φ, h] is called complete.

Definition 10 (a-substructure and complete a-substructure). Let [Φ, h] and [Θ, k] be two a-structures. Then we say that [Θ, k] is an accrued sub-structure (o just a-substructure) of [Φ, h] iff Θ ⊆ Φ. We also say that [Θ, k] is a complete asubstructure of [Φ, h] iff for any other a-substructure [Θ′ , k] of [Φ, h] it holds that Θ′ ⊂ Θ.

Example 7. Consider [Φ3, a] in Ex. 3. Then [{b -< d}, b], [{(b -< d), (b -< e)}, b] and [Φ3, a] itself are a-substructures of [Φ3, a]. Moreover, the two latter a-substructures are complete.

4 Conflict and Defeat

Next we will formalize the notion of attack between astructures, which differs from the notion of attack in argumentation frameworks in several respects. First, an astructure [Φ, h] generally stands for more than one chain of reasoning (argument) supporting the conclusion h. Besides, some intermediate conclusions in [Φ, h] could be shared by some, but not necessarily all the arguments in Args([Φ, h]). Thus, given two a-structures [Φ, h] and [Ψ, k], if the conclusion k of [Ψ, k] contradicts some intermediate conclusion h′ in [Φ, h], then only those arguments in Args([Φ, h]) involving h′ will be affected by the conflict.

Next we will define the notion of partial attack, where the attacking a-structure generally affects only a narrowing of the attacked one (that one containing exactly the arguments in the attacked a-structure affected by the conflict), and we will refer to this narrowing as the attacked narrowing.

Definition 11 (Partial Attack and Attacked Narrowing). Let [Φ, h] and [Ψ, k] be two a-structures. We say that [Ψ, k] partially attacks [Φ, h] at literal h′ , iff there exists a complete a-substructure [Φ′ , h′ ] of [Φ, h] s.t. k and h′ disagree. The a-substructure [Φ′ , h′ ] will be called the disagreement asubstructure. We will say that [Λ, h] is the attacked narrowing of [Φ, h] associated with the attack iff [Λ, h] is the minimal narrowing of [Φ, h] that has [Φ′ , h′ ] as an a-substructure.

Example 8. Consider a DeLP program P where:

Consider the a-structures [Φ, x] and [Ψ1,∼z] in Fig. 2, where Φ = {(x -< z), (z -< t), (z -< v), (y -< u)} and Ψ1 = {(∼z -< w), (∼z -< s), (s -< p)}. Then [Ψ1,∼z] partially attacks [Φ, x] with disagreement a-substructure [Φ′ , z] = [{(z -< t), (z -< v)}, z]. The attacked narrowing of [Φ, x] is [{(x -< z), (z -< t), (z -< v)}, x]. Graphically, this attack relation will be depicted with a dotted arrow (see Fig. 2).

4.1 Accrued Structures: Evaluation and Defeat

In order to decide if a partial attack really succeeds and constitutes a defeat we need a criterion to determine the relative strength (or conclusive force) of those a-structures in conflict. In general, such comparison criterion must be defined according to the application domain. In what follows, we will abstract from that criterion assuming the existence of a binary preference relation '≫' between a-structures.

Definition 12 (Partial Defeater). Let [Φ, h] and [Ψ, k] be two a-structures. Then we say that [Ψ, k] is a partial defeater of [Φ, h] (or equivalently that [Ψ, k] is a successful attack on [Φ, h]) iff 1) [Ψ, k] partially attacks [Φ, h] at literal h′ , where [Φ′ , h′ ] is the disagreement a-substructure, and 2) it is not the case that [Φ′ , h′ ] ≫ [Ψ, k].

Example 9. Consider the attack from [Ψ1, ∼z] against [Φ, x] with disagreement a-substructure [Φ′ , z] in Ex. 8 (Fig. 2), and let us assume that [Ψ1,∼z] ≫ [Φ′ , z]. Then the attack succeeds, constituting a defeat. Graphically, this defeat relation will be depicted with a continuous arrow (see Fig. 3).

Given an attack relation, we will identify two complementary narrowings associated with the attacked a-structure: the narrowing that becomes defeated as a consequence of the attack, and the narrowing that remains undefeated.

Definition 13 (Undefeated and Defeated narrowings). Let [Φ, h] and [Ψ, k] be two a-structures s.t. [Ψ, k] attacks [Φ, h]. Let [Λ, h] be the attacked narrowing of [Φ, h]. Then the defeated narrowing of [Φ, h] associated with the attack, denoted as N D w([Φ, h], [Ψ, k]), is defined by cases as follows: 1) N D w([Φ, h], [Ψ, k]) = [Λ, h], if [Ψ, k] is a partial defeater of [Φ, h], or 2) N D w ([Φ, h], [Ψ, k]) = [∅, ϵ], otherwise. The undefeated narrowing of [Φ, h] associated with the attack, denoted as N U w([Φ, h], [Ψ, k]), is the a-structure Accrual(Args([Φ, h]) \ Args(N D w ([Φ, h], [Ψ, k]))).

Example 10. Fig. 3 illustrates a successful attack from [Ψ1,∼z] against [Φ, x], as well as the defeated and undefeated narrowings of [Φ, x] associated with the attack. As another example, consider the attack from [Ψ2,∼x] = [{∼x -< q},∼x] against [Φ, x], with [Φ, x] itself as disagreement a-substructure, and let us assume that [Φ, x] ≫ [Ψ2,∼x]. In this case the attack does not succeed, and then [∅, ϵ] is the defeated narrowing and [Φ, x] is the undefeated narrowing (i.e., [Φ, x] remains completely undefeated).

4.2 Combined Attack

Until now we have considered only single attacks. When a single attack succeeds, a nonempty narrowing of the attacked a-structure becomes defeated. But two or more a-structures could simultaneously attack another, possibly affecting different narrowings of the target a-structure, and thus causing a bigger narrowing to become defeated (compared with the defeated narrowings associated with the individual attacks). Fig. 4a shows a combined attack from a-structures [Ψ1,∼z] and [Ψ3,∼y] against [Φ, x]. Even though each attacking astructure defeats only a proper narrowing of [Φ, x], the whole [Φ, x] becomes defeated after applying both attacks. Consider now the combined attack against [Φ, x] shown in Fig. 4b. One of the attacking a-structures ([Ψ1,∼z]) defeats a narrowing of [Φ, x] on its own, whereas the other ([Ψ2,∼x]) only attacks [Φ, x]. But suppose that, although [Φ, x] is stronger than [Ψ2,∼x] according to our criterion, [Ψ2,∼x] is stronger than [Φ′ , x] = [{y -< u}, x], a proper narrowing of [Φ, x]. That is possible as, in general, a narrowing of an a-structure is weaker than the a-structure itself. Then, when the a-structures [Ψ1,∼z] and [Ψ2,∼x] combine their attacks, they cause the whole [Φ, x] to become defeated (see Fig. 4b). The reason is that the successful attack of [Ψ1,∼z] weakens the target a-structure, allowing the attack of [Ψ2,∼x] to succeed.

The previous examples, together with the figures, suggests the following informal procedure to calculate the undefeated narrowing associated with a combined attack from a set of astructures Σ against an a-structure [Φ, x]. (1) Pick a defeater in Σ of [Φ, h] (if any) and apply it, obtaining an undefeated narrowing [Θ, h] of [Φ, h]. (2) Repeat step 1 taking the resulting a-structure [Θ, h] as the new target for defeaters, until there is no more defeaters for [Θ, h] in Σ.

Lets consider again the combined attack in Fig. 4a. We can arrive to the same result by selecting the defeaters in a different order, i.e., first [Ψ3,∼y] and then [Ψ1,∼z]. However, in other situations, different choices may cause different undefeated narrowings to remain undefeated in the end, an then, different outputs. This situation can only arise when, according to the preference relation, a given accrual is weaker than some of its narrowings. Consider the combined attack against [Φ, x] shown in Fig. 5, and assume that (unlike it was assumed in Fig. 4b) [Ψ2,∼x] ≫ [Φ, x]. Assume also that [{(x -< z), (z -< t), (z -< v)}, x] ≫ [Ψ2, ∼x]. Then as shown by Fig. 5 there exist two different choices in step 1 of the procedure, leading to two different results. In order to disambiguate this situation, and following the same strategy as in Prakken's approach, we restrict the order in which defeaters are applied so that deeper defeaters are applied first. 2

The purpose of the following definitions is to formally capture the notions of defeated and undefeated narrowings associated with a given combined attack. In particular, the first one formally captures the informal procedure given above (including the restriction on defeater application). In this definition we will use the term a-substructure defeater to refer to a defeater which attacks the target a-structure at an intermediate conclusion, i.e., that attacks a proper a-substructure of the target a-structure.

Definition 14 (Bottom-up sequential degradation). Let [Φ, h] be an a-structure and let Σ be a set of a-structures attacking [Φ, h]. A Sequential Degradation of [Φ, h], associated with the combined attack of the a-structures in Σ, consists of a finite sequence of narrowings of [Φ, h]:

provided there exists a finite sequence of a-structures in Σ:

where [Φ1, h] = [Φ, h], for each i, 1 ≤ i ≤ m, [Ψi, ki] partially defeats [Φi, h] with associated undefeated narrowing [Φi+1, h], [Φm+1, h] has not defeaters in Σ, and for any disagreement a-substructure [Λi, ki] associated with the attack of [Ψi, ki] against [Φi, h], it holds that [Λi, ki] has no a-substructure defeater in Σ, 1 ≤ i ≤ m.

Thus, according to definition 14, the sequences of defeat applications in Figs. 4a and 4b and the topmost in Fig. 5 correspond to bottom-up sequential degradations. On the other hand, the lowermost sequence of defeat applications in Fig. 5 is not a bottom-up sequential degradation. Note that the disagreement a-substructure associated with the attack of

2 Given a combined attack against an a-structure for x (like the one shown in Fig. 5), it is natural to consider all the conflicts affecting the individual reasons supporting x (deeper defeats) before the accrual for x is weighted against its rebutting defeater (the one supporting ∼x), since the "real" support for x (and thus, its strength) is not revealed until such deeper conflicts are considered and resolved.

[Ψ2,∼x] against [Φ, x], which is [Φ, x] itself, has [Ψ3,∼y] as a-substructure defeater. Interestingly, it can be shown that all bottom-up sequential degradations associated with a given combined attack converge to the same a-structure.

Property 2. Let [Φ, h] be an a-structure and let Σ be a set of a-structures attacking [Φ, h]. Let [Φ1, h], . . . , [Φm, h] and [Φ′1 , h], . . . , [Φ′n, h] be two bottom-up sequential degradations of [Φ, h] associated with the combined attack of the a-structures in Σ. Then [Φm, h] = [Φ′n, h].

Definition 15 (Undefeated and Defeated Narrowings associated with a Combined Attack). Let [Φ, h] be an astructure and let Σ be a set of a-structures attacking [Φ, h]. Let [Φ1, h], ..., [Φm+1, h] be a bottom-up sequential degradation of [Φ, h] associated with the combined attack of the a-structures in Σ. Then [Φm+1, h] is the undefeated narrowing of [Φ, h] associated with the combined attack, and Accrual(Args([Φ, h]) \ Args([Φm+1, h])) is its defeated narrowing.

Example 11. Consider the combined attack of [Ψ1,∼z] and [Ψ2, ∼x] against [Φ, x] shown in Fig. 4b. The associated undefeated narrowing of [Φ, x] is [∅, ϵ]. As another example, consider the combined attack against [Φ, x] shown in Fig. 5. The associated undefeated narrowing of [Φ, x] is [{(x -< z), (z -< t), (z -< v)}, x].

5 Dialectical Analysis for Accrued Structures

Given a DeLP program P and a maximal a-structure [Φ, h] we are interested in determining which is the final undefeated narrowing of [Φ, h] after considering all possible a-structures attacking it. As those attacking a-structures may also have other a-structures attacking them, this strategy prompts a recursive dialectical analysis formalized as follows.

Definition 16 (Accrued Dialectical Tree). Let [Φ, h] be a maximal a-structure. The accrued dialectical tree for [Φ, h], denoted T[Φ, h] , is defined as follows:

1. The root of the tree is labeled with [Φ, h].
2. Let N be an internal node labelled with [Θ, k]. Let Σ be the set of all disagreement a-substructures associated with the attacks in the path from the root to N. Let [Θi, ki] be an a-structure attacking [Θ, k] s.t. [Θi, ki] has no a-substructures in Σ. Then the node N has a child node Ni labelled with [Θi, ki]. If there is no astructure attacking [Θ, k] satisfying the above condition, then N is a leaf.

The condition involving the set Σ avoids the introduction of a new a-structure as a child of a node N if it is already present in the path from the root to N (resulting in a circularity). This requirement is needed to avoid fallacious reasoning, as discussed in [Garc´ıa and Simari, 2004].

Once the dialectical tree has been constructed, each combined attack is analyzed, from the deepest ones to the one against the root, to determine the undefeated narrowing of each node in the tree.

Definition 17 (Undefeated narrowing of a Node). Let T[Φ, h] be an accrued dialectical tree for [Φ, h]. Let N be a node of T[Φ, h] labelled with [Θ, k]. Then the undefeated narrowing of N is defined as follows:

1. If N is a leaf node, then the undefeated narrowing of N is its own label [Θ, k].
2. Otherwise (i.e., if N is an internal node), let M1, ..., Mn be the child nodes of N and let [Λi, k] be the undefeated narrowing of the a-structure labelling the child nodeMi, 1 ≤ i ≤ n. Then the undefeated narrowing of N is the undefeated narrowing of [Θ, k] associated with the combined attack involving all the [Λi, k], 1 ≤ i ≤ n.

Example 12. Fig. 6a shows the dialectical tree for [Φ, x]. Fig. 6b shows the dialectical tree for [Φ, x], where the undefeated narrowings of each node are highlighted. The preference relation is assumed the same as for sequential degradations in Figs. 4a and 4b. Additionally, we assume that [Ψ4,∼s] ≫ [{s -< p}, s], and thus [Ψ4,∼s] defeats a narrowing of [Ψ1,∼z]. We also assume that although [Ψ1,∼z] is preferred over [{(z -< t), (z -< v)}, z], the undefeated narrowing of [Ψ1,∼z] ([{∼z -< w},∼z]) is not, and thus its attack against [Φ, x] does not succeed.

Definition 18 (Justified a-structure). Let P be a DeLP program and let h be a literal. Let [Φ, h] be a maximal astructure for h such that the undefeated narrowing of [Φ, h] in T[Φ, h] is a non empty a-structure [Φ′ , h]. Then we say that [Φ′ , h] is a justified a-structure for its conclusion h.

According to the dialectical tree in Fig. 6b, [{(x -< z), (z -< t), (z -< v)}, x] is a justified a-structure for x.

The following property establishes that the a-structure emerging as a result of the above dialectical process cannot involve contradictory literals.

Property 3. Let P be a DeLP program, and let [Φ, h] be a justified a-structure w.r.t. P. Then there exist no intermediate conclusions k and r in [Φ, h] which are in disagreement.

6 Conclusions and RelatedWork

In this paper we have proposed a novel formalization to model the accrual of arguments based on the notion of accrued structure, which accounts for different arguments supporting a given conclusion. We have shown how accrued structures can be in conflict w.r.t. the notions of partial attack and defeat, from which defeated and undefeated narrowings can be identified. The notions of combined attack and sequential degradation were also defined, allowing us to characterize a dialectical process which has as an input a maximal a-structure [Φ, h], and gives as an output a justified a-structure (if any) which corresponds to a narrowing of [Φ, h].

In [Prakken, 2005], Prakken presents a formalization of accrual that is based on a combination of two widely recognized argument-based logics: Dung's abstract approach to argumentation [Dung, 1995] instantiated with Pollock's approach to the structure of arguments [Pollock, 1994]. Associated with his formalization, Prakken presents three principles that should hold for performing accrual of arguments in a sound way.

Lets analyze these principles of accrual in the context of our formalization. The first principle says that "accruals are sometimes weaker than their elements" due to the possibility that accruing reasons are not independent. This principle is satisfied since in our formalization no assumption on the preference relation is made. Indeed, we introduced the notion of bottom-up sequential degradation to obtain a sound result when calculating the undefeated narrowing (associated with a given combined attack) of an accrual that is weaker than its elements. The second principle states that "any 'larger' accrual that applies, makes all its 'lesser' versions inapplicable." Intuitively, that means that we should always accrue as many arguments as possible, even if in the end the accrual is outweighed by a conflicting accrual. This principle is trivially verified since the dialectical acceptance analysis only considers maximal a-structures. Finally, the third principle states that "flawed reasons or arguments may not accrue." Although the third principle is not verified in a strict sense, its underlying purpose is. That is, we first allow all arguments to accrue (in a maximal a-structure), and then we let the dialectical analysis (based on the notion of partial defeat) to rule out the flawed parts of the accrual. In the end, no flawed argument will be present in a justified a-structure.

In [Verheij, 1996] the Cumula system is presented. In it the status of arguments is defined using a Dung-like semantics. According to this semantics, an argument is defeated if one of its subarguments is defeated, and if a given argument A is defeated, all its narrowings (arguments accounting for a subset of reasons in A) are also defeated. As analyzed by Prakken in [Prakken, 2005], the condition imposed by Verheij's semantics concerning the status of narrowings of an argument is too strong. That is, if an argument (possibly accruing many individual reasons) is defeated because of subargument defeat, according to Verheij's semantics all the narrowings will become defeated, even though the ones not involving the defeated subargument should not.

Finally, some defeasible logics (e.g., Defeasible Logic [Governatori and Maher, 2000]) incorporate the notion of team defeat, which is in some respect a form of accural.

There exist some interesting features of our approach that we will summarize next. The first two are related to the fact that our formalization of accrual is based on a fully working system such as DeLP. Since DeLP has been applied in several real-world domains, this new capability for modeling accrual can be used to improve those existing applications (e.g., [Ches˜nevar et al., 2006]). The second advantage has to do with explanations for answers. In the literature, an argument is often regarded as an explanation for a certain literal. In [Garc´ıa et al., 2007] a broader notion of explanation was proposed as providing the necessary information to understand the warrant status of a literal, helping to comprehend and analyze answers provided by argumentation systems based on dialectical proof procedures (as is the case of DeLP). This also signifies as a potential feature in our proposal, not exhibited by other frameworks which formalize the status of arguments using Dung's semantics.

There is an advantage of our approach over Prakken's formalization concerning the efficiency of the acceptance analysis of accruals (a-structures). Concretely, in our approach only one accrual is considered for a given conclusion x (the maximal one), whereas in Prakken's formalization the number of accruals constructed for a given conclusion x is exponential in the number of individual reasons for x, and so the computation of Dung's semantics becomes more complex.

Finally, in addition to satisfying all three principles proposed by Prakken, our formalization satisfies an interesting property (Prop. 3) which suggests an additional principle: accrued structures which are ultimately accepted as justified should not involve conflicting arguments.

It must be noted that there are several real-world problems in which accrual of arguments plays a major role (e.g., legal reasoning, social networks, etc.). Part of our current work involves representing those problems in terms of our formalism, analyzing the obtained results. To test the applicability of our proposal we are developing an implementation using the DeLP system 3 as a basis. Also, we are studying different theoretical results emerging from our proposal which could help to speed up the computation of accrued dialectical trees. Research in this direction is currently being pursued.