ω -Groundedness of argumentation and completeness of grounded dialectical proof procedures

Abstract

Dialectical proof procedures in assumption-based argumentation are in general sound but not complete with respect to both the credulous and skeptical semantics (due to non-terminating loops). This raises the question of whether we could describe exactly what such procedures compute.

In a previous paper, we introduce infinite arguments to represent possibly non-terminating computations and present dialectical proof procedures that are both sound and complete with respect to the credulous semantics of assumption-based argumentation with infinite arguments.

In this paper, we study whether and under what conditions dialectical proof procedures are both sound and complete with respect to the grounded semantics of assumption-based argumentation with infinite arguments. We introduce the class of ω-grounded and finitary-defensible argumentation frameworks and show that finitary assumption-based argumentation is ω-grounded and finitary-defensible. We then present dialectical procedures that are sound and complete wrt finitary assumption-based argumentation.

1. .Introduction

Dialectical proof procedures for assumption-based argumentation ([12,13,15,17–19,22,24,32,33]) could be viewed as an integration of the dialectical procedures of abstract argumentation ([8,20,21,26,34,35]) with the process of argument constructions where the latter could get into a non-terminating loop leading to the incompleteness wrt both credulous and skeptical semantics.

A natural question here is: Can we give a precise semantical characterization of what dialectical proof procedures compute?

Representing possibly non-terminating loops as infinite arguments, we present dialectical proof procedures in [31], that are sound and complete wrt credulous semantics. Continuing this line of research, in this paper we present dialectical procedures that are sound and complete with respect to the grounded semantics.

A detailed analysis of the need for infinite arguments in understanding the semantics of dialectical proof procedures is given in [31].

To illustrate how some practical systems of dialectical procedures (like SWI-Prolog ([36])) handle infinite arguments, we analyze the working of SWI-Prolog on two examples taken from [31] below.1 $$\begin{array}{rl}& {\mathcal{F}}_1:r:a\leftarrow not\mathrm{\_}\alpha r^{\prime }:\alpha \leftarrow f(0)r_n:f(n)\leftarrow f(n+1),n⩾0\\ & t:\beta \leftarrow \\ & {\mathcal{F}}_2:r:a\leftarrow not\mathrm{\_}\alpha r^{″}:\alpha \leftarrow not\mathrm{\_}\beta ,f(0)r_n:f(n)\leftarrow f(n+1),n⩾0\\ & t:\beta \leftarrow \end{array}$$

The behaviors of ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ could be explained by the proof trees (viewed arguments) in Fig. 1.

Fig. 1.

Arguments of ${\mathcal{F}}_1$ and ${\mathcal{F}}_2$ .

SWI-prolog does not deliver any answer to the queries $\leftarrow a$ ? and “ $\leftarrow \alpha$ ?” because of infinite recursion in executing α.2

How could we interpret the outputs of SWI-prolog declaratively?

SWI-prolog could not overcome the non-termination of the process to construct an argument supporting α due to the “infinite-loop” represented by infinite argument $C_1$ .

We could interpret this observation as indicating that infinite arguments (representing “infinite-loop”) do not support their conclusions the way finite arguments do.

We could also say that the failure of SWI-prolog to deliver any answer to the query “ $\leftarrow a$ ?” is due to the non-acceptability of argument A. It implies that though infinite argument $C_1$ can not support its conclusion, it could still attack argument A.

SWI-prolog delivers respectively the answers “True”, “False”, “True” to the queries $\leftarrow a$ ?, “ $\leftarrow \alpha$ ?” and “ $\leftarrow \beta$ ?” wrt program ${\mathcal{F}}_2$ .3 The answer to “ $\leftarrow \alpha$ ?” is false because the only argument supporting it is $C_2$ that is based on assumption $not\mathrm{\_}\beta$ that is attacked by argument B. We could hence say that infinite arguments are attacked the same way finite arguments are attacked.

These observations suggest that infinite arguments still attack (or are attacked by) other arguments as finite arguments do though they do not support their own conclusions.

To capture this peculiar character of infinite arguments, [31] views infinite arguments as self-attacking arguments.

In [31], two proof procedures for credulous semantics are presented. In one, proof trees are constructed explicitly. A filtering mechanism to memorizing the attacked assumptions of both proponent and opponent is employed to prevent each player from constructing the same proof trees twice. The other procedure is simply a flattening of the first. The filtering mechanism in these procedures can not be applied for grounded semantics. The following example illustrates this point.

Example 1.

Consider the argumentation framework $\mathcal{F}$ represented by the simple logic program: $$\begin{array}{rl}& r:p\leftarrow not\mathrm{\_}qt:q\leftarrow not\mathrm{\_}p\end{array}$$

To support p, the proof procedures in [31] would correctly deliver argument P (See Fig. 2).

The proponent first constructs argument P to support p. The opponent responds by constructing argument Q to attack P at assumption $not\mathrm{\_}q$ . The filtering mechanism memorizes assumption $not\mathrm{\_}q$ after the opponent attacks it and does not allow the opponent to attack it again. The procedures hence stop and deliver P as an admissible argument supporting p.

As the grounded extension of $\mathcal{F}$ is empty, procedures for grounded extension need to drop this filtering mechanism.

Fig. 2.

Illustration of Example 1.

A consequence of dropping the filtering mechanism in the procedures for credulous semantics in [31] is that an argument could be constructed repeatedly many times at different stages in the computation. To distinguish between these distinct “copies” of the same argument, we consider them together with their histories.

The grounded extension of an argumentation framework $AF=(Ar,att)$ coincides with the least fixed point of the characteristic function $F_{AF}$ . It hence follows that the grounded extension of $AF$ contains the set $F_{AF}^{\omega }(\mathrm{\varnothing })=\cup \{F_{AF}^i(\mathrm{\varnothing })|i\text{is a natural number}\}$ .4

To check whether an argument A is groundedly accepted, a dialectical proof procedure would compute the defenders of A (i.e. arguments attacking those attacking A) and then check whether such defenders could also be defended and so on. In cases where there are infinitely many arguments attacking A, such process may not succeed.

Example 2.

Let $AF=(Ar,att)$ with $Ar=\{B,A_0,A_1,...,A_i,A_{i+1},...\}$ and $att=\{(A_{2k+1},B)|k⩾0\}\cup \{(A_k,A_{k+1})|k⩾0\}$ . (A graphical illustration of this argumentation framework is in Fig. 3).

It is easy to see that for each natural number $⩾1$ : $F_{AF}^i(\mathrm{\varnothing })=\{A_0,A_2,...,A_{2(i-1)}\}$ . Hence $F^{\omega }(\mathrm{\varnothing })=\cup \{F_{AF}^i(\mathrm{\varnothing })|i\text{is a natural number}\}=\{A_0,A_2,...,A_{2i},...\}$ .

The grounded extension of $AF$ is: $F_{AF}(F_{AF}^{\omega }(\mathrm{\varnothing }))=F_{AF}^{\omega }(\mathrm{\varnothing })\cup \{B\}$ .

To check whether B is groundedly accepted, a dialectical procedure would need to compute the infinite set $\{A_{2k+1}|k⩾0\}$ of arguments attacking B and find the infinite set $\{A_{2k}|k⩾0\}$ of defenders of B. In general, no dialectical proof procedures could carry out such task successfully.

Fig. 3.

An argumentation framework that is not ω-grounded.

To address this issue, we introduce the class of ω-grounded argumentation frameworks where the grounded extension is “computed” after at most ω steps, i.e. the grounded extension of $AF$ coincides with $F_{AF}^{\omega }(\mathrm{\varnothing })=\cup \{F_{AF}^i(\mathrm{\varnothing })|i\text{ is a natural number}\}$ . We then present several key results:

We show that an argumentation framework is ω-grounded iff it is finitary defensible (i.e. all minimal defences of non-selfattacking arguments are finite);

We show that finitary assumption-based argumentation frameworks (see Definition 1) with infinite arguments are finitary defensible;

We present two dialectical proof procedures that are both sound and complete wrt finitary assumption-based frameworks with infinite arguments where in the first procedure, proof trees together with their histories are fully and explicitly represented to shed light on the construction process of arguments and counter arguments during a derivation and hence providing key insights into the soundness and completeness of the procedure. We then present another procedure that is simply the result of flattening the first where most of the data structures representing the proof tree structures of the arguments are striped away. Consequently, the second procedure is both sound and complete but with much simpler data structure and hence much more amenable to possible implementation.

The rest of this paper is organized as follows. In Section 2, we recall the basic notions of abstract and assumption-based argumentation as well as the machinery of infinite arguments. Section 3 proposes the concept of ω-groundedness of argumentation framework and show that finitary assumption-based argument systems are ω-grounded. We then present a dialectical proof procedure wrt grounded semantics in Section 4. The soundness and completeness of the grounded proof procedure are discussed in Section 5–6. Further we present the flatten version of the proof procedure in Section 7. We conclude and discuss possible expansions of our works in Section 8.

2. .Preliminaries: Argumentation with infinite arguments

In this section, we recall key basic concepts of abstract argumentation from [16] and [14] and infinite arguments together with some illustrating examples in assumption-based argumentation from [31] and [30].

2.1. .Abstract argumentation

Following [14,16], an argumentation framework is a pair $AF=(Ar,att)$ where $Ar$ is a set of arguments, and $att\subseteq Ar\times Ar$ so that $(X,Y)\in att$ specifies that X attacks Y. A set of arguments S attacks an argument X if some argument in S attacks X. S attacks another set of arguments $S^{\prime }$ if S attacks some argument in $S^{\prime }$ . Moreover we say that S defends X iff S attacks all arguments attacking X. We also say that an argument X is defensible if it is defended by some set of arguments.

A set $S\subseteq Ar$ is said to be

• conflict-free iff S does not attack itself; and

• admissible iff S is conflict-free and S defends each argument in S; and

• a preferred extension if S is maximally (wt set inclusion) admissible;5 and

• a complete extension if S is admissible and contains each argument it defends.

The characteristic function of AF, denoted by $F_{AF}$ , is defined by $$\begin{array}{r}{F}_{AF}:2^{Ar}\to 2^{Ar}\end{array}$$ where $$\begin{array}{r}{F}_{AF}(S)=\{X\in Ar|S\text{defends}X\}\end{array}$$

It is straightforward to see that $F_{AF}$ is monotonic (wrt set inclusion). Since $2^{Ar}$ is a complete partial order (wrt set inclusion),6 $F_{AF}$ has a least fixed point.7

The grounded extension of $AF$ denoted by ${GE}_{AF}$ , is defined as the least fixed point of $F_{AF}$ .8

As the set of complete extensions of $AF$ is a complete semilattice ([16]),9 the grounded extension coincides with the least complete extension of $AF$ .

2.2. .Assumption-based argumentation

Given a logical language $\mathcal{L}$ , a standard assumption-based argumentation (ABA) framework ([6]) is a triple $\mathcal{F}=(\mathcal{R},\mathcal{A},\$\overline{}\$)$ where $\mathcal{R}$ is a set of inference rules of the form $l_0\leftarrow l_1,...l_n$ ( $n⩾0$ and $l_0,...,l_n\in \mathcal{L}$ ), and $\mathcal{A}\subseteq \mathcal{L}$ is a set of assumptions, and $\$\overline{}\$$ is a (total) one-one mapping from $\mathcal{A}$ into $\mathcal{L}\setminus \mathcal{A}$ , where $\overline{x}$ is referred to as the contrary of x, and assumptions in $\mathcal{A}$ do not appear in the heads of rules.

Remark 1.

In non-standard ABA frameworks ([24]), the contrary $\overline{\alpha }$ of an assumption α could be a set. Such non-standard frameworks could be translated into equivalent standard ones by introducing a new atom ${\alpha }^{\prime }$ for each assumption α and i) define ${\alpha }^{\prime }$ as the contrary of α; and ii) for each $\delta \in \overline{\alpha }$ , add a new rule: ${\alpha }^{\prime }\leftarrow \delta$ to $\mathcal{R}$ .

Remark 2.

Logic programming is a well-known instance of standard ABA where the contrary of a negation-as-failure assumption $not\mathrm{\_}p$ is p.

Remark 3.

For each rule r of the form $l_0\leftarrow l_1,...l_n$ , $l_0$ and the set $\{l_1,...,l_n\}$ are referred respectively as the head and the body of r and denoted by $hd(r)$ , $bd(r)$ .

Further the set of assumptions (resp non-assumptions) appearing in the body of r is denoted by $Ass(r)$ (resp. $NAss(r)$ ).

Definition 1 Finitary ABA

An ABA framework $\mathcal{F}=(\mathcal{R},\mathcal{A},\$\overline{}\$)$ is finitary if for each sentence $\delta \in \mathcal{L}$ , the set of rules with head δ is finite.10

Convention 1.

From now on until the end of the paper,

we restrict our consideration to standard finitary ABA. Hence whenever we refer to an ABA framework, we mean a standard finitary one; and

if not otherwise mentioned, we assume an arbitrary but fixed finitary standard assumption-based argumentation framework $\mathcal{F}=(\mathcal{R},\mathcal{A},\$\overline{}\$)$ .

Definition 2 Partial Proof

Given an ABA $\mathcal{F}$ , a partial proof supporting ${\sigma }_0$ (wrt $\mathcal{F}$ ) is a finite sequence of the form $$\begin{array}{r}(root,{\sigma }_0).(r_1,{\sigma }_1)....(r_n,{\sigma }_n)\end{array}$$ where $r_i\in \mathcal{R}$ , $i⩾1$ such that ${\sigma }_{i-1}=hd(r_i)$ and ${\sigma }_i\in bd(r_i)$ . If $bd(r_i)=\mathrm{\varnothing }$ then ${\sigma }_i=true$ .

Example 3.

Let’s consider an argumentation framework ${\mathcal{F}}_2$ in the introduction. $$\begin{array}{rl}& {\mathcal{F}}_2:r:a\leftarrow not\mathrm{\_}\alpha r^{″}:\alpha \leftarrow not\mathrm{\_}\beta ,f(0)r_n:f(n)\leftarrow f(n+1),n⩾0\\ & t:\beta \leftarrow \end{array}$$

Some partial proofs supporting a and α are described below and illustrated in Fig. 4. $$\begin{array}{rl}& \psi =(root,a)\\ & {\psi }^{\prime }=(root,a).(r,not\mathrm{\_}\alpha )\\ & p_0=(root,\alpha )\\ & p_1^{{}^{\prime }}=(root,\alpha ).(r^{″},not\mathrm{\_}\beta )\\ & p_1=(root,\alpha ).(r^{″},f(0))\\ & p_2=(root,\alpha ).(r^{″},f(0)).(r_0,f(1))\\ & ...\\ & p_{n+1}=(root,\alpha ).(r^{″},f(0)).(r_0,f(1))...(r_{n-1},f(n))\end{array}$$

Fig. 4.

A graphical representation of partial proofs of Example 3.

Fig. 5.

Some proof trees of ${\mathcal{F}}_2$ .

We next define partial proof trees where we identify the nodes in such trees with the partial proofs representing the unique paths from the root to them.

Definition 3 Partial Proof Trees

A partial proof tree (or just proof tree for simplification) T for a sentence ${\sigma }_0$ wrt $\mathcal{F}$ is a non-empty set of partial proofs supporting ${\sigma }_0$ wrt $\mathcal{F}$ such that for each partial proof $$\begin{array}{r}p\equiv (root,{\sigma }_0).(r_1,{\sigma }_1)....(r_n,{\sigma }_n),n>0\end{array}$$ from T, the following properties hold:

The partial proof $p^{\prime }\equiv (root,{\sigma }_0).(r_1,{\sigma }_1)....(r_{n-1},{\sigma }_{n-1})$ also belongs to T and is referred to as the unique parent of p whereas p is referred to as a child of $p^{\prime }$ ;

Every partial proof of the form $p^{\prime }.(r_n,{\sigma }^{\prime })$ with ${\sigma }^{\prime }\in bd(r_n)$ , also belongs to T and is a child of $p^{\prime }$ ;

$p^{\prime }$ has no other children.

${\sigma }_0$ is often referred to as the conclusion of T, denoted by $Cl(T)$ while the partial proof $(root,{\sigma }_0)$ is referred to as the root of T.

An example of partial proof trees is given in Fig. 5.

Remark 4.

For convenience, we often refer to a partial proof tree without mentioning its conclusion if there is no possibility for misunderstanding.

Notation 1 Nodes in Partial Proof Trees

Abusing the notation for convenience, we often refer to a partial proof $(root,{\sigma }_0).(r_1,{\sigma }_1)....(r_n,{\sigma }_n)$ in a partial proof tree T as a node labeled by ${\sigma }_n$ in T.

Notation 2.

Let T be a partial proof tree and S be a set of partial proof trees,

A node N in T is said to be a leaf of T if N has no children.

A leaf N of T is said to be final if N is labeled by $true$ or by an assumption. N is non-final if it is not final.

The support of T, denoted by $Sp(T)$ , is the set of all sentences labeling the leaves of T and different from $true$ .

The set of all assumptions appearing in T is denoted by $Ass(T)$ .

The set of all assumptions appearing in partial proof trees in S is denoted by $Ass(S)$ .

The set of conclusions of partial proof trees in S is denoted by $Cl(S)$ .

Considering Fig. 5, the partial proof $(root,\alpha ).(r^{″},f(0))$ is a leaf node of $T_{r_0}$ while, $(root,\alpha ).(r^{″},f(0))...(r_{n-1},f(n))$ is a leaf node of $T_{r_n}$ .

Further, the support of $T_{r_0}$ , i.e. $Sp(T_{r_0})$ , is $\{not\mathrm{\_}\beta ,f(0)\}$ and $Ass(T_{r_0})$ is $\{not\mathrm{\_}\beta \}$ .

Definition 4 Arguments

A partial proof tree T is a full proof tree if all leaves of T are final.

An argument for α is a full proof tree for α.

The set of all arguments wrt the ABA framework $\mathcal{F}$ is denoted by ${Ar}_{\mathcal{F}}$ .

Convention 2.

For short, we often simply say, proof trees instead of partial proof trees if there is no possibility of confusion.

When a player in a dialectical computation is attempting to construct an argument, the attempt may not terminate. Declaratively, we model a non-terminating attempt to construct an argument as an attempt to construct an infinite argument.

As infinite arguments do not provide support for their conclusions, they can not be accepted as an admissible argument. We model this intuition as self-attacks of infinite arguments.

Definition 5 Attacks

An argument A attacks an argument B iff one of the following conditions holds:

(1)

The conclusion of A is the contrary of some assumption in the support of B.

(2)

A and B are identical and infinite.

The attack relation between arguments in ${Ar}_{\mathcal{F}}$ is denoted by ${att}_{\mathcal{F}}$ . Define $$\begin{array}{r}{AF}_{\mathcal{F}}=({Ar}_{\mathcal{F}},{att}_{\mathcal{F}})\end{array}$$

Due to the fact that the infinite arguments always attack themselves, the following lemma holds obviously.

Lemma 1.

Let $S\subseteq {Ar}_{\mathcal{F}}$ be admissible wrt ${AF}_{\mathcal{F}}=({Ar}_{\mathcal{F}},{att}_{\mathcal{F}})$ . Then S contains only finite arguments.

Notation 3.

Let T, $T^{\prime }$ be proof trees and N be a non-final leaf node in T labeled by a non-assumption σ.11

$T^{\prime }$ is an immediate expansion of T at N if there is a rule r of the form $\sigma \leftarrow b_1,...,b_m$ such that $T^{\prime }=T\cup \{N.(r,b_1),...,N.(r,b_m)\}$ .

Note that if $m=0$ , $T^{\prime }=T\cup \{N.(r,true)\}$ .12

We write $T^{\prime }=\mathbf{\text{exp}}(\mathbf{\text{T}},\mathbf{\text{N}},\mathbf{\text{r}})$ .

We say $T^{\prime }$ is an immediate expansion of T if $T^{\prime }$ is an immediate expansion of T at some leaf node N of T.

We define $$\begin{array}{r}\mathbf{\text{CE}}(\mathbf{\text{T}},\mathbf{\text{N}})=\{\exp (T,N,r^{\prime })|r^{\prime }\text{is a rule s.t}.hd(r^{\prime })=\sigma \}.\end{array}$$

Considering Fig. 5, $T_{r_1}=\exp (T_{r_0},N,r_0)$ where N is $(root,\alpha ).(r^{″},f(0))$ .

Further the set of all immediate expansion of $T_{r_0}$ at node N, i.e. $CE(T_{r_0},N)$ , is $\{T_{r_1}\}$ .

Notation 4.

Let $T_0$ , $T_1$ be proof trees for ${\sigma }_0$ .

We say T, $T^{\prime }$ are compatible iff $T\cup T^{\prime }$ is also a proof tree.

We say $T_0$ is a prefix of $T_1$ iff $T_0\subseteq T_1$ .13^,14

We say $T_0$ is a proper prefix of $T_1$ if $T_0$ is a prefix of $T_1$ and $T_0\ne T_1$ .

Considering Fig. 5, $T_{r_0}$ is a prefix of $T_{r_1}$ .

Remark 5.

It is worthwhile to note that two proof trees could be compatible without being in a prefix-relationship as illustrated below (see Fig. 6).

Consider an assumption-based framework with three rules: $$\begin{array}{rl}& r_1:a\leftarrow b,c;\\ & r_2:b\leftarrow ;\\ & r_3:c\leftarrow .\end{array}$$

Consider two proof trees: $$\begin{array}{rl}& T_0=\{p_0,p_1,p_2,p_3\},T_1=\{p_0,p_1,p_2,p_4\}\text{where}\\ & p_0=(root,a),p_1=(root,a).(r_1,b),p_2=(root,a).(r_1,c)\text{and}\\ & p_3=(root,a).(r_1,b).(r_2,true),p_4=(root,a).(r_1,c).(r_3,true).\\ & T_0,T_1\text{are compatible but neither is a prefix of the other}.\end{array}$$

Fig. 6.

Two compatible proof trees.

Lemma 2.

Let $T_0$ , $T_1$ be proof trees. The following statements hold:

• (1)

If $T_1$ is an immediate expansion of $T_0$ then $T_0$ is a proper prefix of $T_1$ .

(2)

Suppose $T_0$ is a prefix of $T_1$ . It holds that

• (a)

the roots of $T_0$ , $T_1$ coincide; and

(b)

if N is a node in $T_0$ then the parent and children (if exist) of N in $T_0$ are respectively also the parent and children of N in $T_1$ .

Proof.

Obvious.

Lemma 3.

Let T be an argument, $T_0$ be a proof tree such that $T_0$ is a proper prefix of T. Furthermore, let N be a leaf node in $T_0$ such that $CE(T_0,N)\ne \mathrm{\varnothing }$ . Then there is an unique $T_1\in CE(T_0,N)$ such that $T_1$ is a prefix of T.

$T_1$ is often simply denoted by $\mathbf{e}\mathbf{x}\mathbf{p}({\mathbf{T}}_{\mathbf{0}},\mathbf{N},\mathbf{T})$ .

We also define $\mathbf{e}\mathbf{x}\mathbf{p}({\mathbf{T}}_{\mathbf{0}},\mathbf{T})=\{\exp (T_0,N,T)|Nisanon-finalleafnodeof{T}_0\}$ . 15

Proof.

Lemma 3 in [31] proves the existence of $T_1$ . The uniqueness of $T_1$ should be obvious.

Definition 6.

An increasing sequence of proof trees $T_0\subseteq T_1\subseteq ...T_i\subseteq ...$ is said to be fair if for each $T_i$ , for each non-final leaf node $N\in T_i$ there is a node $M\in T_j$ , $j>i$ , such that N is a proper prefix of M.

Lemma 4.

Let $sq\equiv T_0\subseteq T_1\subseteq ...T_i\subseteq ...$ be an increasing sequence of proof trees. The following statements hold:

• (1)

$T_0\cup T_1\cup ...T_i\cup ...$ is a proof tree.

(2)

If the sequence $sq$ is fair then $T_0\cup T_1\cup ...T_i\cup ...$ is an argument.

Proof.

This is Lemma 4 in [31].

Notation 5.

Let T be a proof tree and $N\equiv (root,{\sigma }_0).(r_1,{\sigma }_1)....(r_i,{\sigma }_i)$ be a node in T.

The height of N in T, denoted by $h(N,T)$ , is defined by $h(N,T)=i$ .16

The minimum of the heights of the non-final leaf nodes in T are denoted by $hi(T)$ , i.e. $hi(T)=min\{h(N,T)|N\text{is a non-final leaf node in}T\}$

3. .ω-Groundedness of argumentation frameworks

We first introduce the notion of ω-grounded argumentation frameworks. We then show that finitary ABA frameworks are ω-grounded.

3.1. .ω-Grounded argumentation frameworks

Let $AF=(Ar,att)$ be an argumentation framework.

Definition 7 ω-Groundedness

An argumentation framework $AF$ is ω-grounded if its grounded extension ${GE}_{AF}$ can be “computed” after at most ω steps, i.e. $$\begin{array}{r}G{E}_{AF}=F_{AF}^{\omega }(\mathrm{\varnothing })=\bigcup _{i=0}^{\mathrm{\infty }}{F}_{AF}^i(\mathrm{\varnothing })\end{array}$$

It should be obvious that the argumentation framework in Fig. 1 is not ω-grounded.

We give now a sufficient condition for ω-groundedness.

Let $\mathcal{D}$ be a set of sets of arguments (i.e $\mathcal{D}\subseteq 2^{Ar}$ ). $\mathcal{D}$ is said to be directed iff for all $S,S^{\prime }\in \mathcal{D}$ , $S\cup S^{\prime }\in \mathcal{D}$ .17

Note that the least upper bound of $\mathcal{D}$ , $lub(\mathcal{D})$ , is $lub(\mathcal{D})=\cup \mathcal{D}$ .

Definition 8 Admissibility Continuity

A function $\mathrm{\Phi }:2^{Ar}\to 2^{Ar}$ is said to be admissibility-continuous (or just ad-continuous for short) if for each directed set of admissible sets $\mathcal{D}$ $$\begin{array}{r}lub\{\mathrm{\Phi }(S)|S\in \mathcal{D}\}=\mathrm{\Phi }(lub(\mathcal{D}))\end{array}$$

Lemma 5.

If the characteristic function $F_{AF}$ is ad-continuous then $AF$ is ω-grounded.

Proof.

Suppose ${\mathcal{F}}_{AF}$ is ad-continuous. Let $\mathcal{D}=\{F_{AF}^i(\mathrm{\varnothing })|i\text{is a natural number}\}$ . $\mathcal{D}$ is obviously directed and $lub(\mathcal{D})=F_{AF}^{\omega }(\mathrm{\varnothing })={\bigcup }_{i=0}^{\mathrm{\infty }}{F}_{AF}^i(\mathrm{\varnothing })$ .

Since $F_{AF}$ is ad-continuous, $F_{AF}^{\omega }(\mathrm{\varnothing })={\bigcup }_{i=0}^{\mathrm{\infty }}{F}_{AF}^i(\mathrm{\varnothing })=lub\{F_{AF}(S)|S\in \mathcal{D}\}=F_{AF}(lub(\mathcal{D}))=F_{AF}(F_{AF}^{\omega }(\mathrm{\varnothing }))$ . Therefore $F_{AF}^{\omega }(\mathrm{\varnothing })$ coincides with the grounded extension of $AF$ .

Definition 9.

A set S of arguments is said to be a minimal defense of an argument A if S defends A and no proper subset of S defends A.

Definition 10 Finitary Defensible

A defensible argument A is finitary-defensible iff all minimal defenses of A are finite.18

An argumentation framework $AF$ is said to be finitary-defensible if all defensible arguments in $AF$ that are not self-attacking19 are finitary defensible.

Theorem 1 Finitary Defensibility implies ad-Continuity

Let $AF$ be a finitary-defensible argumentation framework. Then $F_{AF}$ is ad-continuous and hence $AF$ is ω-grounded.

Proof.

Let $AF$ be a finitary-defensible argumentation framework, $\mathcal{D}$ be a directed set of admissible sets of arguments. We show that $lub\{F_{AF}(S)|S\in \mathcal{D}\}=F_{AF}(lub(\mathcal{D}))$ .

It is obvious that for each $S\in \mathcal{D}$ : $S\subseteq lub(\mathcal{D})$ . Since $F_{AF}$ is monotonic, it holds for each $S\in \mathcal{D}$ : $F_{AF}(S)\subseteq F_{AF}(lub(\mathcal{D}))$ . Therefore $lub\{F_{AF}(S)|S\in \mathcal{D}\}\subseteq F_{AF}(lub(\mathcal{D}))$ .

It remains to show that $lub\{F_{AF}(S)|S\in \mathcal{D}\}\supseteq F_{AF}(lub(\mathcal{D}))$ .

Let $A\in F_{AF}(lub(\mathcal{D}))$ . Hence $lub(\mathcal{D})$ is a defense of A. Since $\mathcal{D}$ is a set of admissible sets of arguments, $lub(\mathcal{D})=\cup \mathcal{D}$ is also admissible. Therefore $F_{AF}(lub(\mathcal{D}))$ is admissible. Thus A is not self-attacking. Since $AF$ is a finitary-defensible, there is a finite minimal defense $\mathcal{M}\subseteq lub(\mathcal{D})$ of A. Hence for each $X\in \mathcal{M}$ there is $S_X\in \mathcal{D}$ such that $X\in S_X$ . Since $\mathcal{M}$ is finite, $S^{\prime }=\cup \{S_X|X\in \mathcal{M}\}\in \mathcal{D}$ . Thus $A\in F_{AF}(S^{\prime })\subseteq lub\{F_{AF}(S)|S\in \mathcal{D}\}$ .

From Lemma 5, it follows immediately that $AF$ is ω-grounded.

3.2. .Finitary ABA frameworks are finitary-defensible and ω-grounded

We present a novel insight into the semantic structure of finitary ABA systems by showing that finitary ABA frameworks are finitary-defensible and hence ω-grounded. We begin with a lemma stating that finite arguments of finitary ABA framework are finitary-defensible.

Lemma 6 Finite Arguments are Finitary Defensible

Let $\mathcal{F}$ be a finitary ABA framework. Then defensible finite arguments in ${AF}_{\mathcal{F}}$ are finitary-defensible.

Proof.

Let B be a defensible finite argument in ${Ar}_{\mathcal{F}}$ .

Let S be a minimal defense of B wrt ${AF}_{\mathcal{F}}=({Ar}_{\mathcal{F}},{att}_{\mathcal{F}})$ . We show that S is finite.

Suppose the contrary that S is infinite. Hence $S=\{D_1,...,D_i,...\}$ . Let $S_i=\{D_1,...,D_i\}$ .

Because S is a minimal defense of B, it follows that the set $\mathcal{A}\subseteq {Ar}_{\mathcal{F}}$ of attacks against B is infinite (if $\mathcal{A}$ is finite, pick for each $X\in \mathcal{A}$ , an argument $D_X\in S$ s.t. $D_X$ attacks X. Hence the set $\{D_X|X\in \mathcal{A}\}\subset S$ is a finite defense of B (wrt ${AF}_{\mathcal{F}}$ ). Contradiction to the fact that S is a infinite minimal defense of B).

Let ${PA}_n$ be the set of balanced proof trees of height n20 that are prefixes of arguments in $\mathcal{A}$ and ${PAN}_n$ are those elements in ${PA}_n$ that are not attacked by S.

Further let ${FA}_n$ be the set of the full arguments of height n in $\mathcal{A}$ .21

Since $\mathcal{F}$ is finitary, both ${PA}_n$ and ${FA}_n$ are finite22 and so are ${PAN}_n$ .

We first show that for each n, ${PAN}_n\ne \mathrm{\varnothing }$ . Suppose the contrary that there is n such that ${PAN}_n=\mathrm{\varnothing }$ , i.e. each partial argument in ${PA}_n$ is attacked by S. Since ${PA}_n$ is finite, there is some i such that $S_i$ attacks each partial argument in ${PA}_n$ . Therefore each full argument of height $>n$ in $\mathcal{A}$ is attacked by $S_i$ .

Since the set ${FA}_0\cup \cdots \cup {FA}_n$ is also finite, there is some j such that $S_j$ attacks each argument in this set. Therefore $S_i\cup S_j$ attacks each (full) argument in $\mathcal{A}$ . Hence $S_i\cup S_j$ is a finite defense of B, contrary to the assumption that S is a infinite minimal defense of B.

We show now that there is an infinite sequence $T_0\subset T_1\subset ...$ such that for each $i⩾0$ : $T_i\in {PAN}_i$ .

It should be clear that each proof tree in ${PAN}_{i+1}$ is obtained by expanding a proof tree in ${PAN}_i$ at all non-final leaf nodes of the later.

Let $\mathcal{T}=(V,E)$ be a tree defined as follows:

• *

The set of vertices of $\mathcal{T}$ is defined by: $V=\{\mathbf{\text{root}}\}\cup {\bigcup }_{i=0}^{\mathrm{\infty }}{PAN}_i$ where $\mathbf{\text{root}}$ is the root of $\mathcal{T}$ .23

*

The set of edges of $\mathcal{T}$ is defined by: $(T,T^{\prime })\in E$ iff

• *

$\mathrm{\exists }i$ s.t. $T\in {PAN}_i$ and $T^{\prime }\in {PAN}_{i+1}$ and $T\subseteq T^{\prime }$ ; or

*

$T=\mathbf{\text{root}}$ and $T^{\prime }\in {PAN}_0$ .

Since ${PAN}_i\ne \mathrm{\varnothing }$ for all i, $\mathcal{T}$ is infinite and because $\mathcal{F}$ is finitary, each child of $\mathcal{T}$ has finitely many children. Thus there is an infinite path in $\mathcal{T}$ . In other words, there is an infinite sequence $T_0\subset T_1\subset ...$ such that for each $i⩾0$ : $T_i\in {PAN}_i$ . Since each $T_i$ is a balanced tree of height i, the sequence $T_0\subset T_1\subset ...$ is obviously fair.

Let $T={\bigcup }_{i=0}^{\mathrm{\infty }}{T}_i$ . T is therefore a full proof tree and hence an argument. T is hence an attack against B and not attacked by S. Contradiction.

Since the set of finite arguments in ${AF}_{\mathcal{F}}$ contains the set of all non-self-attacking arguments, it follows immediately from Theorem 1 and the above Lemma 6: Theorem 2 ω-Groundedness of finitary ABA frameworks

Let $\mathcal{F}$ be a finitary ABA framework. Then the following statements hold:

${AF}_{\mathcal{F}}$ is finitary-defensible;

The characteristic function $F_{{AF}_{\mathcal{F}}}$ is ad-continuous;

${AF}_{\mathcal{F}}$ is ω-grounded.

4. .Grounded dispute derivations

In this section we will present a proof procedure for grounded semantics where proof trees together with their histories are fully and explicitly represented to shed light on the construction process of arguments and counter arguments during a derivation and hence providing key insights into the soundness and completeness of the procedure. Later, in Section 7, we present another procedure that is simply the result of flattening the one presented in this section. Consequently, the second procedure is both sound and complete but with much simpler data structure and hence much more amenable to possible implementation.

The purpose of the dispute derivations is to construct arguments. So it is kind of natural to refer to proof trees representing partly constructed arguments in a dispute derivation as partial arguments. It also makes it more intuitive to talk about attack between partial arguments.

Remark 6 Partial Arguments

Abusing the notation slightly for ease of reference, from now on until the end of the paper, we often refer to proof trees as partial arguments.

To avoid any possibility of misunderstanding, we often refer to arguments as full arguments.

We often say that a partial argument Tattacks a partial argument $T^{\prime }$ if there is an assumption $\alpha \in Ass(T^{\prime })$ such that $Cl\left(T\right)=\overline{\alpha }$ .

We also often refer to a proof tree consisting only of the root and supporting a sentence δ by $[\delta ]$ , i.e. $[\delta ]=\{(root,\delta )\}$ .

In a dispute derivation, an argument could be constructed repeatedly many times at different stages in the computation. To distinguish between these distinct “copies” of the same argument, we consider them together with their histories.

Definition 11 Histories of Partial Arguments

A possible history of a partial argument T is represented by a sequence $(T_0,t_0),...,(T_k,t_k)$ where $T_0,...,T_k$ are partial arguments such that

$T_0=[Cl(T)]$ and $T=T_k$ ; and

$T_i$ , $0<i⩽k$ , is an immediate expansion of $T_{i-1}$ ; and

$t_0<t_1<\cdots <t_k$ are natural numbers representing the stages in the dispute when such expansions happen.

Definition 12 Profiled Partial Arguments

A profiled partial argument (ppa) is a pair $\pi =(T,h)$ where T is a partial argument and $h=(T_0,t_0),...,(T_k,t_k)$ is a history of T.

(1)

We also often refer to T and h by ${\mathbf{\text{T}}}_{\mathit{\pi }}$ and ${\mathbf{\text{h}}}_{\mathit{\pi }}$ respectively;

(2)

$t_0$ is often referred to as the starting time of π denoted by $\mathbf{\text{st}}\mathbf{\text{(}}\mathit{\pi }\mathbf{\text{)}}$ while k is referred to as the length of the history of π denoted by $\mathbf{\text{lh}}\mathbf{\text{(}}\mathit{\pi }\mathbf{\text{)}}$ ;

(3)

An assumption α is often referred to as the target of π denoted by $\mathbf{\text{target}}\mathbf{\text{(}}\mathit{\pi }\mathbf{\text{)}}$ , if $Cl\left(T\right)=\overline{\alpha }$ ;

Example 4.

Considering again the argumentation framework ${\mathcal{F}}_2$ in the introduction $$\begin{array}{rl}& {\mathcal{F}}_2:r:a\leftarrow not\mathrm{\_}\alpha r^{″}:\alpha \leftarrow not\mathrm{\_}\beta ,f(0)r_n:f(n)\leftarrow f(n+1),n⩾0.\\ & t:\beta \leftarrow \end{array}$$

${\pi }_0=(T_0,h_0)$ is an example of a profiled partial argument where $T_0=[a]$ and $h_0=(T_0,0)$ where $h_0$ says that $T_0$ is obtained at stage 0.

Suppose $T_0$ is expanded at stage 1 resulting in a new profiled partial argument ${\pi }_1=(T_1,h_1)$ (see Fig. 7) where $h_1=(T_0,0),(T_1,1)$ . The history $h_1$ says that $T_1$ is obtained by expanding $T_0$ at stage 1 and $T_0$ is obtained a stage 0.

Fig. 7.

Proof trees of Example 4.

A dispute derivation is viewed as a game between a proponent and an opponent where the players take turn to develop their arguments. The goal of the proponent is to construct an argument to support some desired conclusion and other arguments to defend against the attacks from the opponent while the opponent’s goal is to construct arguments to attack proponent’s arguments. At each step, either player could choose to either expand their partly constructed arguments or start a new argument to attack the other’s argument.

Definition 13 Grounded Dispute Derivation

A grounded dispute derivation for a sentence σ is a (possibly infinite) sequence of the form $$\begin{array}{r}⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩...\end{array}$$ where 24

(1)

for each $i⩽n$ , ${PPT}_i$ , ${OPT}_i$ are sets of profiled partial arguments; and

(2)

${PTA}_i$ is a set of assumptions appearing in the proponent partial arguments (up to stage i) that are to be attacked by the opponent; and

(3)

$PP{T}_0$ contains exactly one profiled partial argument consisting of only the root labeled by σ, i.e. ${PPT}_0=\{(T_0,h_0)\}$ where $T_0=[\sigma ]$ and $h_0=([\sigma ],0)$ , and

(4)

${PTA}_0=\mathrm{\varnothing }$ if σ is not an assumption, otherwise ${PTA}_0=\{\sigma \}$ , and

(5)

${OPT}_0=\mathrm{\varnothing }$ .

at stage $i>0$ , one of the dispute parties makes a move transforming the dispute from state $i-1$ to state i as follows:

• (1)

Suppose the proponent makes a move at stage i. The proponent can choose one of the following two options:

• (a)

The proponent expands some profiled partial argument $\pi =(T,h)\in {PPT}_{i-1}$ by:

• *

selecting a non-final leaf node N in T labeled by a non-assumption sentence δ and a rule r with $hd(r)=\delta$ ; and

*

expanding $(T,h)$ at N by r.

The result will be:

• *

  ${PPT}_i=({PPT}_{i-1}\setminus \{\pi \})\cup \{{\pi }^{\prime }\}$ where ${\pi }^{\prime }=(T^{\prime },h^{\prime })$ and $T^{\prime }=\exp (T,N,r)$ and $h^{\prime }=h.(T^{\prime },i)$ ;25

• *

  ${PTA}_i={PTA}_{i-1}\cup Ass(r)$

• *

  ${OPT}_i={OPT}_{i-1}$ .

(b)

The proponent attacks an opponent’s profiled partial argument $\pi =(T,h)\in {OPT}_{i-1}$ at an assumption $\alpha \in Ass(T)$ resulting in:

${PPT}_i={PPT}_{i-1}\cup \{(T^{\prime },h^{\prime })\}$ where $T^{\prime }=[\overline{\alpha }]$ and $h^{\prime }=([\overline{\alpha }],i)$ ; and

${PTA}_i={PTA}_{i-1}$

${OPT}_i={OPT}_{i-1}\setminus \{\pi \}$

(2)

Suppose the opponent makes a move at stage i. The opponent can choose one of the following two options:

• (a)

The opponent expands an opponent profiled partial argument $\pi =(T,h)\in {OPT}_{i-1}$ at a non-final leaf node $N\in T$ labeled by a non-assumption sentence δ resulting in:

${PPT}_i={PPT}_{i-1}$

${PTA}_i={PTA}_{i-1}$

${OPT}_i=({OPT}_{i-1}\setminus \{\pi \})\cup \{{\pi }^{\prime }|{\pi }^{\prime }=(T^{\prime },h^{\prime }),T^{\prime }\in CE(T,N),h^{\prime }=h.(T^{\prime },i)\}$ 26

(b)

The opponent attacks an assumption $\alpha \in {PTA}_i$ resulting in:

${PPT}_i={PPT}_{i-1}$

${PTA}_i={PTA}_{i-1}\setminus \{\alpha \}$

${OPT}_i={OPT}_{i-1}\cup \{\pi \}$ where $\pi =(T,h)$ and $T=[\overline{\alpha }]$ and $h=([\overline{\alpha }],i)$

Remark 7.

When opponent carries out step (2.a), it is possible that $CE(T,N)=\mathrm{\varnothing }$ . We often refer to this case as a failed expansion of opponent profiled partial argument π.

Note that if the assumption-based framework is not finitary, the set ${OPT}_i$ in step (2a) could be infinite, and hence not implementable.

A dispute derivation is successful (for the proponent) if i) the proponent manages to construct in full her arguments to support her stated conclusion and to defend against the attacks from the opponent and ii) the opponent runs out of attacks against the proponent.

Definition 14 Successful Grounded Dispute Derivation

A grounded dispute derivation $$\begin{array}{r}⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩\end{array}$$ is successful (for the proponent) if ${PTA}_n={OPT}_n=\mathrm{\varnothing }$ and for each $(T,h)\in {PPT}_n$ , T is a full argument.

Table 1

A successful grounded dispute derivation of ${\mathcal{F}}_2$ .

Stage	Move	$PPT$	$PTA$	$OPT$
0		${\pi }_0=(T_0,h_0)$ $h_0=(T_0,0)$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$
1	$1a$	${\pi }_1=(T_1,h_1)$ $h_1=(T_0,0),(T_1,1)$	$not\mathrm{\_}\alpha$	$\mathrm{\varnothing }$
2	$2b$	${\pi }_1=(T_1,h_1)$ , $h_1=(T_0,0),(T_1,1)$	$\mathrm{\varnothing }$	${\pi }_0^{{}^{\prime }}=(T_0^{{}^{\prime }},h_0^{{}^{\prime }})$ $h_0^{{}^{\prime }}=(T_0^{{}^{\prime }},2)$
3	$2a$	${\pi }_1=(T_1,h_1)$ , $h_1=(T_0,0),(T_1,1)$	$\mathrm{\varnothing }$	${\pi }_1^{{}^{\prime }}=(T_1^{{}^{\prime }},h_1^{{}^{\prime }})$ $h_1^{{}^{\prime }}=(T_0^{{}^{\prime }},2),(T_1^{{}^{\prime }},3)$
4	$1b$	${\pi }_1=(T_1,h_1)$ , $h_1=(T_0,0),(T_1,1)$ ${\pi }_0^{{}^{″}}=(T_0^{{}^{″}},h_0^{{}^{″}})$ , $h_0^{{}^{″}}=(T_0^{{}^{″}},4)$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$
5	$1a$	${\pi }_1=(T_1,h_1)$ , $h_1=(T_0,0),(T_1,1)$ ${\pi }_1^{{}^{″}}=(T_1^{{}^{″}},h_1^{{}^{″}})$ , $h_1^{{}^{″}}=(T_0^{{}^{″}},4),(T_1^{{}^{″}},5)$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$

Example 5.

A successful grounded dispute derivation $$\begin{array}{r}⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_5,{PTA}_5,{OPT}_5⟩\end{array}$$ for sentence a (wrt the argumentation framework ${\mathcal{F}}_2$ in the introduction) is illustrated in Table 1 and explained in details below. For convenience we recall ${\mathcal{F}}_2$ below. $$\begin{array}{rl}& {\mathcal{F}}_2:r:a\leftarrow not\mathrm{\_}\alpha r^{″}:\alpha \leftarrow not\mathrm{\_}\beta ,f(0)r_n:f(n)\leftarrow f(n+1),n⩾0\\ & t:\beta \leftarrow \end{array}$$

At stage 0, we have ${PPT}_0=\{{\pi }_0\}$ , ${PTA}_0={OPT}_0=\mathrm{\varnothing }$ where ${\pi }_0=(T_0,h_0)$ and $T_0=[a]$ and $h_0=(T_0,0)$ .

At stage 1, the proponent makes a move to expand the ppa ${\pi }_0$ by applying step (1a) using rule r.

Hence ${PPT}_1=({PPT}_0\setminus \{{\pi }_0\})\cup \{{\pi }_1\}=\{{\pi }_1\}$ where ${\pi }_1=(T_1,h_1)$ , $T_1=\exp (T_0,root,r)$ and $h_1=(T_0,0),(T_1,1)$ ( $T_1$ is illustrated in Fig. 8).

Since rule r has the assumption $not\mathrm{\_}\alpha$ (i.e. $Ass(r)=\{not\mathrm{\_}\alpha \}$ ), we have ${PTA}_1={PTA}_0\cup Ass(r)={PTA}_0\cup \{not\mathrm{\_}\alpha \}=\{not\mathrm{\_}\alpha \}$ .

${OPT}_1={OPT}_0=\mathrm{\varnothing }$ .

Next, at stage 2, the opponent attacks the assumption $not\mathrm{\_}\alpha \in {PTA}_1$ by applying step (2b). Hence ${OPT}_2={OPT}_1\cup \{{\pi }_0^{{}^{\prime }}\}=\{{\pi }_0^{{}^{\prime }}\}$ where ${\pi }_0^{{}^{\prime }}=(T_0^{{}^{\prime }},h_0^{{}^{\prime }})$ with $T_0^{{}^{\prime }}=[\alpha ]$ and $h_0^{{}^{\prime }}=(T_0^{{}^{\prime }},2)$ stating that $T_0^{{}^{\prime }}$ is created at stage 2 (See Fig. 8).

${PPT}_2={PPT}_1=\{{\pi }_1\}$ .

${PTA}_2={PTA}_1\setminus \{not\mathrm{\_}\alpha \}=\mathrm{\varnothing }$ .

At stage 3, the opponent applies step (2a) to expand $T_0^{{}^{\prime }}$ to $T_1^{{}^{\prime }}$ . Since rule $r^{″}$ is the only one with head α, it follows $CE(T_0^{{}^{\prime }},root)=\{T_1^{{}^{\prime }}\}$ with $T_1^{{}^{\prime }}=\exp (T_0^{{}^{\prime }},root,r^{″})$ (See Fig. 8). Therefore

${OPT}_3=({OPT}_2\setminus \{{\pi }_0^{{}^{\prime }}\})\cup \{{\pi }_1^{{}^{\prime }}\}=\{{\pi }_1^{{}^{\prime }}\}$ where ${\pi }_1^{{}^{\prime }}=(T_1^{{}^{\prime }},h_1^{{}^{\prime }})$ and $h_1^{{}^{\prime }}=(T_0^{{}^{\prime }},2),(T_1^{{}^{\prime }},3)$ .

${PPT}_3={PPT}_2=\{{\pi }_1\}$

${PTA}_3={PTA}_2=\mathrm{\varnothing }$

At stage 4, the proponent attacks opponent’s ppa ${\pi }_1^{{}^{\prime }}$ at assumption $not\mathrm{\_}\beta \in T_1^{{}^{\prime }}$ by applying step (1b).

Therefore ${PPT}_4={PPT}_3\cup \{{\pi }_0^{{}^{″}}\}=\{{\pi }_1,{\pi }_0^{{}^{″}}\}$ where ${\pi }_0^{{}^{″}}=(T_0^{{}^{″}},h_0^{{}^{″}})$ and $T_0^{{}^{″}}=[\beta ]$ and $h_0^{{}^{″}}=(T_0^{{}^{″}},4)$ (See Fig. 8).

${PTA}_4={PTA}_3=\mathrm{\varnothing }$

${OPT}_4={OPT}_3\setminus \{{\pi }_1^{{}^{\prime }}\}=\mathrm{\varnothing }$ .

Finally at stage 5, the proponent applies step (1a), using rule t, to expand $T_0^{{}^{″}}$ to argument $T_1^{{}^{″}}=\exp (T_0^{{}^{″}},root,t)$ (See Fig. 8). Therefore

${PPT}_5=({PPT}_4\setminus \{{\pi }_0^{{}^{″}}\})\cup \{{\pi }_1^{{}^{″}}\}=\{{\pi }_1,{\pi }_1^{{}^{″}}\}$ where ${\pi }_1^{{}^{″}}=(T_1^{{}^{″}},h_1^{{}^{″}})$ with $h_1^{{}^{″}}=(T_0^{{}^{″}},4),(T_1^{{}^{″}},5)$ .

${PTA}_5={PTA}_4\cup Ass(t)=\mathrm{\varnothing }$

${OPT}_5={OPT}_4=\mathrm{\varnothing }$

As there is no any other assumption in $PT{A}_5$ and $OP{T}_5$ is empty and all ppa in $PP{T}_5$ are full, the derivation is successful.

Fig. 8.

Proof trees for Example 5.

Example 6.

Consider the following argumentation framework $$\begin{array}{r}{\mathcal{F}}_3:r:p\leftarrow not\mathrm{\_}a\end{array}$$

Table 2

A successful grounded dispute derivation of ${\mathcal{F}}_3$ .

Stage	Move	$PPT$	$PTA$	$OPT$
0		${\pi }_0=(T_0,h_0)$ $h_0=(T_0,0)$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$
1	$1a$	${\pi }_1=(T_1,h_1)$ $h_1=(T_0,0),(T_1,1)$	$not\mathrm{\_}a$	$\mathrm{\varnothing }$
2	$2b$	${\pi }_1=(T_1,h_1)$ $h_1=(T_0,0),(T_1,1)$	$\mathrm{\varnothing }$	${\pi }_0^{{}^{\prime }}=(T_0^{{}^{\prime }},h_0^{{}^{\prime }})$ $h_0^{{}^{\prime }}=(T_0^{{}^{\prime }},2)$
3	$2a$	${\pi }_1=(T_1,h_1)$ $h_1=(T_0,0),(T_1,1)$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$

Fig. 9.

Proof trees of the dispute derivation for sentence “p”.

A successful dispute derivation for sentence “p” $$\begin{array}{r}⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_3,{PTA}_3,{OPT}_3⟩\end{array}$$ is illustrated in Table 2 and is explained in details below.

At stage 0, we have ${PPT}_0=\{{\pi }_0\}$ , ${PTA}_0={OPT}_0=\mathrm{\varnothing }$ where ${\pi }_0=(T_0,h_0)$ and $T_0=[p]$ and $h_0=(T_0,0)$ (see Fig. 9).

• At stage 1, the proponent makes a move to expand the ppa ${\pi }_0$ by applying step (1a) using rule r.

  Hence ${PPT}_1=({PPT}_0\setminus \{{\pi }_0\})\cup \{{\pi }_1\}=\{{\pi }_1\}$ where ${\pi }_1=(T_1,h_1)$ , $T_1=\exp (T_0,root,r)$ (see Fig. 9) and $h_1=(T_0,0),(T_1,1)$ .

  Since rule r has the assumption $not\mathrm{\_}a$ (i.e. $Ass(r)=\{not\mathrm{\_}a\}$ ), we have ${PTA}_1={PTA}_0\cup Ass(r)={PTA}_0\cup \{not\mathrm{\_}a\}=\{not\mathrm{\_}a\}$ .

  ${OPT}_1={OPT}_0=\mathrm{\varnothing }$ .

• Next, at stage 2, the opponent attacks the assumption $not\mathrm{\_}a\in {PTA}_1$ by applying step (2b). Hence ${OPT}_2={OPT}_1\cup \{{\pi }_0^{{}^{\prime }}\}=\{{\pi }_0^{{}^{\prime }}\}$ where ${\pi }_0^{{}^{\prime }}=(T_0^{{}^{\prime }},h_0^{{}^{\prime }})$ with $T_0^{{}^{\prime }}=[a]$ and $h_0^{{}^{\prime }}=(T_0^{{}^{\prime }},2)$ stating that $T_0^{{}^{\prime }}$ is created at stage 2 (see Fig. 9).

  ${PPT}_2={PPT}_1=\{{\pi }_1\}$ .

  ${PTA}_2={PTA}_1\setminus \{not\mathrm{\_}a\}=\mathrm{\varnothing }$ .

• At stage 3, the opponent applies step (2a) to expand $T_0^{{}^{\prime }}$ . Since there is no rule with head a, it follows $CE(T_0^{{}^{\prime }},root)=\mathrm{\varnothing }$ . Therefore

  ${OPT}_3=({OPT}_2\setminus \{{\pi }_0^{{}^{\prime }}\})\cup \mathrm{\varnothing }=\mathrm{\varnothing }$ .

  ${PPT}_3={PPT}_2=\{{\pi }_1\}$

  ${PTA}_3={PTA}_2=\mathrm{\varnothing }$

As there is no any other assumption in $PT{A}_3$ and $OP{T}_3$ is empty and all ppa in $PP{T}_3$ are full, the derivation is successful.

5. .Soundness of grounded dispute derivation

We first introduce some new notations.

Notation 6.

We say a ppa ${\pi }^{\prime }$ is a continuation of another ppa π iff $h_{\pi }$ is a prefix of $h_{{\pi }^{\prime }}$ (and hence $T_{\pi }\subseteq T_{{\pi }^{\prime }}$ and $st(\pi )=st({\pi }^{\prime })$ ).

${\pi }^{\prime }$ is an immediate expansion of π if $h_{\pi }=(T_0,t_0),...,(T_k,t_k)$ and $h_{{\pi }^{\prime }}=h_{\pi }.(T_{k+1},t_{k+1})$ .27

A ppa π is said to be full iff $T_{\pi }$ is an argument.

We say two ppas π, ${\pi }^{\prime }$ are compatible if $st(\pi )=st({\pi }^{\prime })$ and $T_{\pi }$ , $T_{{\pi }^{\prime }}$ are compatible.

We often refer to a ppa appearing in some ${PPT}_i$ (resp. ${OPT}_i$ ) in a grounded dispute derivation as a proponent ppa (resp opponent ppa).

The following lemma expresses the intuition that when the proponent has partially constructed an argument, she is expected to finish it. And she should not construct two distinct arguments for the same purpose at the same time, i.e. at any stage there should be no distinct continuations of the same proponent ppa at some previous stage.

Lemma 7.

Let $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a grounded dispute derivation.

• (1)

Let π be some proponent ppa appearing in $dd$ . The following statements hold:

• (a)

For each $i:st(\pi )⩽i⩽n$ , there is an unique continuation of π in ${PPT}_i$ .

(b)

Let ${\pi }_i$ , ${\pi }_{i+1}$ ( $st(\pi )⩽i<n$ ) be continuations of π in ${PPT}_i$ , ${PPT}_{i+1}$ respectively. Then ${\pi }_{i+1}$ is either an immediate expansion of ${\pi }_i$ or identical to ${\pi }_i$ .

(2)

Let π, ${\pi }^{\prime }$ be two proponent ppas in $dd$ such that $st(\pi )=st({\pi }^{\prime })$ . Then one is a continuation of the other.

Consequently, if π, ${\pi }^{\prime }$ are full then they are identical.

Proof.

See proof of Lemma 7 in Appendix A.3.

The following lemma states intuitively that at any stage in a derivation, it is not possible for the opponent to construct the same argument in different ways.

Lemma 8.

Let $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a grounded dispute derivation. It holds that for each $0⩽i⩽n$ , for all $\pi ,{\pi }^{\prime }\in {OPT}_i$ , if π, ${\pi }^{\prime }$ are compatible then π, ${\pi }^{\prime }$ are identical.

Proof.

See proof of Lemma 8 in Appendix A.3.

Remark 8.

An opponent ppa π in a dispute derivation $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ is said to be discontinued at step i iff $\pi \in {OPT}_{i-1}$ and there is no continuation of π afterwards, i.e. $\mathrm{\forall }j⩾i$ there is no continuation of π in ${OPT}_j$ .

It is obvious that in a successful grounded dispute derivation, every opponent ppa is discontinued at some stage. The following lemma sheds light on the structure of the evolution of opponent ppas in a grounded dispute derivation.

Lemma 9.

Let $dd$ be a dispute derivation $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ .

Further let A be an argument such that $Cl\left(A\right)=\overline{\alpha }$ for some assumption α and $\pi =([\overline{\alpha }],([\overline{\alpha }],i))\in {OPT}_i$ for some $0⩽i⩽n$ .

Then there is an unique sequence ${cont}_{dd}(\pi )={\pi }_0,...,{\pi }_k$ ( $i⩽i+k⩽n$ ) such that

• (1)

${\pi }_0=\pi$ ; and

(2)

for each $i<j⩽k$ , ${\pi }_j\in {OPT}_{i+j}$ and ${\pi }_j$ is a continuation of ${\pi }_{j-1}$ and $T_{{\pi }_j}\subseteq A$ ; and

(3)

if $i+k<n$ then ${\pi }_k$ is discontinued at $i+k+1$ and there is no ppa at any ${OPT}_{i+k+1},...,{OPT}_n$ that is compatible with ${\pi }_k$ .

Proof.

See proof of Lemma 9 in Appendix A.3.

The following lemma states that each argument attacking a proponent argument in a successful dispute derivation is counter-attacked by some proponent argument.

Lemma 10.

Let $dd$ be a successful grounded dispute derivation that terminates at $⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ and $\pi =(T,h)\in {PPT}_n$ and $T^{\prime }$ be an argument attacking argument T. Then there is a opponent ppa ${\pi }^{\prime }$ such that $st(\pi )<st({\pi }^{\prime })$ and $T_{{\pi }^{\prime }}\subseteq T^{\prime }$ and ${\pi }^{\prime }$ is discontinued at some step between $st({\pi }^{\prime })$ and n.

Proof.

See proof of Lemma 10 in Appendix A.3.

The following theorem shows that in a successful dispute derivation, each proponent argument whose construction started at some stage i is defended by the proponent arguments constructed after stage i.

Theorem 3.

Let $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a successful grounded dispute derivation and $\pi =(T,h)\in {PPT}_n$ . Further let ${\mathcal{T}}_{\pi }=\{T_{{\pi }^{\prime }}|{\pi }^{\prime }\in {PPT}_{n}andst({\pi }^{\prime })>st(\pi )\}$ . It holds: $$\begin{array}{r}T\in F_{{AF}_{\mathcal{F}}}({\mathcal{T}}_{\pi })\end{array}$$

Proof.

Let $T^{\prime }\in {Ar}_{\mathcal{F}}$ such that $T^{\prime }$ attacks T. From Lemma 10 there is opponent ppa ${\pi }^{\prime }$ (discontinued at stage i) such that $st(\pi )<st({\pi }^{\prime })$ and $T_{{\pi }^{\prime }}\subseteq T^{\prime }$ .

There are two cases:

• (1)

Case 1 The opponent makes a move at stage i. Because ${\pi }^{\prime }$ is discontinued at step i, the opponent expands ${\pi }^{\prime }$ at stage i. Because $T_{{\pi }^{\prime }}\subseteq T^{\prime }$ , it follows from Lemma 3 that ${\pi }^{\prime }$ has a continuation at stage i. Contradiction to the fact that ${\pi }^{\prime }$ is discontinued at stage i. Hence this case is not possible.

(2)

Case 2 The proponent makes a move at stage i. Since ${\pi }^{\prime }$ is discontinued at stage i, it follows that the proponent attacks ${\pi }^{\prime }$ at some assumption α at this stage. Since $T_{{\pi }^{\prime }}\subseteq T^{\prime }$ , it follows that α appears in $T^{\prime }$ .

Hence a new proponent ppa ${\pi }_1=(T_1,h_1)$ is created in ${PPT}_i$ where $T_1=[\overline{\alpha }]$ and $h_1=(T_1,i)$ .

Since $dd$ is successful, there is ${\pi }_2\in {PPT}_n$ that is a continuation of ${\pi }_1$ . Hence $T_{{\pi }_2}$ attacks $T^{\prime }$ .

Since $st({\pi }_2)=st({\pi }_1)=i>st({\pi }^{\prime })>st(\pi )$ , it follows that $T_{{\pi }_2}\in {\mathcal{T}}_{\pi }$ . Thus ${\mathcal{T}}_{\pi }$ defends T against $T^{\prime }$ .

Since $T^{\prime }$ is arbitrary selected, it follows that ${\mathcal{T}}_{\pi }$ defends T against all attacks against T.

We have proved that $T\in F_{{AF}_{\mathcal{F}}}({\mathcal{T}}_{\pi })$ .

An immediate consequence of Theorem 3 is the soundness of the grounded dispute procedure as stated in the following theorem. Theorem 4 Soundness Theorem

Let $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a successful grounded dispute derivation. It holds $$\begin{array}{r}\{T_{\pi }|\pi \in {PPT}_n\}\subseteq {GE}_{{AF}_{\mathcal{F}}}\end{array}$$

Proof.

Let $m=|{PPT}_n|$ . Let ${\pi }_m,...,{\pi }_1$ be an increasing (according to the starting times) listing of ppas in ${PPT}_n$ , i.e. for $m⩾i>1$ , $st({\pi }_m)=0$ and $st({\pi }_i)<st({\pi }_{i-1})$ .

Let $T_i=T_{{\pi }_i}$ . We first prove by induction on i, $T_i\in F_{{AF}_{\mathcal{F}}}^i(\mathrm{\varnothing })$ .

Basic Step $i=1$ .

From Theorem 3, it follows immediately that $T_1\in F_{{AF}_{\mathcal{F}}}(\mathrm{\varnothing })$ (because ${\mathcal{T}}_{{\pi }_1}=\mathrm{\varnothing }$ ).

Inductive Step Suppose for all j ( $i>j⩾1$ ), $T_j\in F_{{AF}_{\mathcal{F}}}^j(\mathrm{\varnothing })$ .

We prove that $T_i\in F_{{AF}_{\mathcal{F}}}^i(\mathrm{\varnothing })$ .

From $F_{{AF}_{\mathcal{F}}}(\mathrm{\varnothing })\subseteq F_{{AF}_{\mathcal{F}}}^2(\mathrm{\varnothing })\subseteq \cdots \subseteq F_{{AF}_{\mathcal{F}}}^{i-1}(\mathrm{\varnothing })$ and for each j ( $i>j⩾1$ ), $T_j\in F_{{AF}_{\mathcal{F}}}^j(\mathrm{\varnothing })$ , it follows that ${\mathcal{T}}_{{\pi }_i}=\{T_{i-1},...,T_1\}\subseteq F_{{AF}_{\mathcal{F}}}(\mathrm{\varnothing })\cup F_{{AF}_{\mathcal{F}}}^2(\mathrm{\varnothing })\cup \cdots \cup F_{{AF}_{\mathcal{F}}}^{i-1}(\mathrm{\varnothing })\subseteq F_{{AF}_{\mathcal{F}}}^{i-1}(\mathrm{\varnothing })$ .

Thus from Theorem 3, $T_i\in F_{AF}({\mathcal{T}}_{{\pi }_i})\subseteq F_{AF}(F_{{AF}_{\mathcal{F}}}^{i-1}(\mathrm{\varnothing }))=F_{{AF}_{\mathcal{F}}}^i(\mathrm{\varnothing })$ .

Therefore $\{T_{\pi }|\pi \in {PPT}_n\}=\{T_m,...,T_0\}\subseteq F_{{AF}_{\mathcal{F}}}^m(\mathrm{\varnothing })\subseteq {GE}_{{AF}_{\mathcal{F}}}$ .

6. .Completeness of grounded proof procedure

It should be clear that for each sentence $\sigma \in Cl({GE}_{{AF}_{\mathcal{F}}})$ , there are always some arguments in ${GE}_{{AF}_{\mathcal{F}}}$ supporting σ. The completeness of the grounded proof procedure means that at least one of such arguments could be derived in a successful grounded dispute derivation.

In other words, completeness of grounded procedure is not about verifying whether a sentence is supported by an argument in the grounded extension. It is rather about showing that for each sentence in the grounded extension, an argument supporting it could be derived by a grounded derivation.

The proof is constructive by first constructing (according to the definition of strongly grounded dd) for each sentence $\sigma \in Cl({GE}_{{AF}_{\mathcal{F}}})$ , a special kind of grounded dispute derivation, and then show that each of such special grounded derivation is always successful.

For each argument $A\in {GE}_{{AF}_{\mathcal{F}}}$ and sentence $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ , define $$\begin{array}{r}rank(A)=min\{i|A\in F_{{AF}_{\mathcal{F}}}^i(\mathrm{\varnothing })\}\text{and}\\ rank(\delta )=min\{i|\delta \in Cl(F_{{AF}_{\mathcal{F}}}^i(\mathrm{\varnothing }))\}\end{array}$$

Remark 9.

• (1)

Since ${AF}_{\mathcal{F}}$ is ω-grounded (because $\mathcal{F}$ is finitary (see Convention 1)), both $rank(A)$ and $rank(\delta )$ are natural numbers.

(2)

It is not difficult to see that for each $A\in {GE}_{{AF}_{\mathcal{F}}}$ , $rank(Cl(A))⩽rank(A)$ .

(3)

For each $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ , an argument $A\in {GE}_{{AF}_{\mathcal{F}}}$ with $Cl(A)=\delta$ and $rank(\delta )=rank(A)$ , is often referred to as a ground support of δ.

It is obvious that each sentence $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ has a ground support.

(4)

A mapping λ assigning to each sentence in $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ a ground support $\lambda (\delta )\in {GE}_{{AF}_{\mathcal{F}}}$ of δ is often referred to as a ground map of $\mathcal{F}$ .28

Lemma 11.

Let $A\in {GE}_{{AF}_{\mathcal{F}}}$ and $\alpha \in Ass(A)$ . Further let B be an argument attacking α. The following statements hold:

• (1)

$\alpha \in Cl({GE}_{{AF}_{\mathcal{F}}})$ and $rank(\alpha )⩽rank(A)$ ; and

(2)

There is an assumption $\beta \in Ass(B)$ such that $\overline{\beta }\in Cl\left({GE}_{{AF}_{\mathcal{F}}}\right)$ and $rank(\overline{\beta })<rank\left(\alpha \right)$ .

Proof.

Since $A\in {GE}_{{AF}_{\mathcal{F}}}$ , it follows from Theorem 2 that $A\in F_{{AF}_{\mathcal{F}}}^k(\mathrm{\varnothing })$ where $k=rank(A)$ and k is a natural number. Hence, every attack against A is attacked by some argument in $F_{{AF}_{\mathcal{F}}}^{k-1}(\mathrm{\varnothing })$ . Thus every attack against α is attacked by some argument in $F_{{AF}_{\mathcal{F}}}^{k-1}(\mathrm{\varnothing })$ implying that $\alpha \in Cl(F_{{AF}_{\mathcal{F}}}^k(\mathrm{\varnothing }))$ . Hence $rank(\alpha )⩽k=rank(A)$ .

Let $rank(\alpha )=m$ . Hence $\alpha \in Cl(F_{{AF}_{\mathcal{F}}}^m(\mathrm{\varnothing }))$ . From Theorem 2, m is a natural number. Thus every attack against α is attacked by some argument in $F_{{AF}_{\mathcal{F}}}^{m-1}(\mathrm{\varnothing })$ . It follows that B is attacked by some argument $C\in F_{{AF}_{\mathcal{F}}}^{m-1}(\mathrm{\varnothing })$ at some assumption $\beta \in Ass(B)$ . Thus $Cl\left(C\right)=\overline{\beta }$ and $rank(\overline{\beta })⩽rank\left(C\right)⩽m-1<m=rank\left(\alpha \right)⩽rank\left(A\right)$ .

We introduce the concept of strongly grounded dispute derivation below where the proponent arguments are grounded according to some ground map λ. This concept is inspired by the idea of the H-constrainted dispute derivations for admissibility semantics in [31].

The construction of strongly grounded dispute derivations mimics such derivations in abstract argumentation when arguments are assumed to be given and a key basic step is like: “pick some argument…”.

This step is elaborated in the strongly grounded dispute derivation by the proponents and opponents as follows:

• Once the proponent has started to build up an argument, she will continue until getting the full argument constructed without being bothered to attack the other’s arguments. The opponent is not allowed to disrupt her even if he could attack her still partly constructed argument at some stage.

• On the contrary, the opponent’s construction of his arguments will be disrupted by attacks from the proponent whenever she could launch such attacks. But the opponent is not allowed to interrupt the constructions of his own arguments to launch an attack against a proponent argument even if such attack is possible.

Definition 15 Strongly Grounded Dispute Derivation

A strongly grounded dispute derivation for a sentence δ wrt a ground map λ is a grounded dispute derivation for δ (as defined in Definition 13) such that the following extra constraints are satisfied:

The proponent executes step (1.a) (to expand proponent ppa $\pi =(T,h)$ ) with an extra condition that $\exp (T,N,r)\subseteq \lambda (Cl(T))$ ;

The proponent executes step (1.b) (to attack an opponent ppa $\pi =(T,h)\in {OPT}_i$ at an assumption $\alpha \in Ass(T)$ ) with two extra conditions:

*

$\overline{\alpha }\in Cl\left({GE}_{{AF}_{\mathcal{F}}}\right)$ and $rank\left(\overline{\alpha }\right)<rank\left(target\left(\pi \right)\right)$ ; and

*

step (1.a) is not possible;

The opponent executes step (2.a) (to expand an opponent ppa $\pi =(T,h)\in {OPT}_i$ ) with two extra conditions:

• *

$h(N,T)=hi(T)$ ;29

*

It is not possible for the proponent to perform any of steps (1.a) or (1.b).

The opponent executes step (2.b) (to attack a proponent assumption $\alpha \in {PTA}_i$ ) with two extra conditions:

• *

It is not possible for the proponent to perform any of steps (1.a) or (1.b);

*

It is not possible for the opponent to perform step (2.a).

Remark 10.

We often simply refer to a strongly grounded dispute derivation without explicitly mentioning the associated ground map if there is no possibilities for misunderstanding.

Definition 16.

A strongly grounded dispute derivation $⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ is said to be terminated if neither the proponent nor the opponent could make a move at stage n.

Theorem 5 Completeness Theorem

Let $\mathcal{F}$ be a finitary ABA framework and $\sigma \in Cl({GE}_{{AF}_{\mathcal{F}}})$ . Then there is a successful strongly grounded dispute derivation for σ $⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ such that $\sigma \in Cl(T_{\pi })$ for some $\pi \in {PPT}_n$ .

Proof.

See Section 6.1.

The proof of the completeness theorem follows directly from two insights:

• i)

each terminated strongly grounded dispute derivation for $\sigma \in Cl({GE}_{{AF}_{\mathcal{F}}})$ is successful; and

ii)

there is no infinite strongly grounded dispute derivation.

We first show below that each terminated strongly grounded dispute derivation for $\sigma \in Cl({GE}_{{AF}_{\mathcal{F}}})$ is successful.

Theorem 6.

Let $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a terminated strongly grounded dispute derivation for $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ wrt a ground map λ. Then $sdd$ is successful.

Proof.

Let $\pi \in {PPT}_n$ and $h_{\pi }=(T_0,i_0)...(T_m,i_m)$ with $T_0=[\delta ]$ . From the design of the proof procedure in definitions 13, 15, it holds: $T_0\subset T_1\subset \cdots \subset T_m\subseteq \lambda (\delta )$ . Since $sdd$ is terminated, it is not possible to expand $T_m$ further into $\lambda (\delta )$ . Hence $\lambda (\delta )=T_m=T_{\pi }$ . Hence $T_{\pi }$ is a full argument.

Since the opponent can not carry out step (2.b) (attack proponent assumptions in ${PTA}_n$ ), even though all other steps are not possible, it follows that ${PTA}_n=\mathrm{\varnothing }$ .

Since the opponent can not carry out step (2.a) (expand opponent partial arguments) even though none of steps (1.a, 1.b, 2.b) can be executed, it follows that for each $\pi \in {OPT}_n$ : $T_{\pi }$ is a full argument and there is $p\in {PPT}_n$ s.t. $T_{\pi }$ attacks $T_p$ . Since $T_p=\lambda (Cl(T_p))$ , $T_p\in {GE}_{{AF}_{\mathcal{F}}}$ .

From Lemma 11, it follows there is an assumption $\alpha \in Ass(T_{\pi })$ such that $\overline{\alpha }\in Cl\left({GE}_{{AF}_{\mathcal{F}}}\right)$ and $rank\left(\overline{\alpha }\right)<rank\left(target\left(\pi \right)\right)$ . Thus it is possible for the proponent to execute step (1b) at stage n. Contradiction. Therefore π does not exist. Hence ${OPT}_n=\mathrm{\varnothing }$ .

We have proved that $sdd$ is successful.

To show the completeness theorem, it remains for us to show that there is no infinite strongly grounded dispute derivation.

Lemma 12.

Let $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a strongly grounded dispute derivation wrt a ground map λ. The following statements hold:

• (1)

Each ${PPT}_i$ contains at most one not-full ppa;

(2)

Let $\pi \in {PPT}_i$ , $0⩽i⩽n$ . Then it holds that π is not full iff there is an unique immediate expansion of π in ${PPT}_{i+1}$ ;

(3)

Let $\pi =(T,h)\in {PPT}_i$ , $0⩽i⩽n$ . Then h is of the form $$\begin{array}{r}h=(T_0,i_0),(T_1,i_0+1),...,(T_k,i_0+k)\end{array}$$ such that

• $i_0+k⩽i$ ; and

• $T_j\subseteq \lambda (Cl(T)))$ for $k⩾j⩾1$ ; and

• if π is not full then $i_0+k=i$ .

(4)

Let $\pi \in {PPT}_i$ ( $0⩽i⩽n$ ) such that the proponent does not make a move to expand π at some stage k with $i⩾k>st(\pi )$ . Then π is full.

Proof.

• (1)

By induction on i. The statement holds obviously for $i=0$ .

Suppose the statement holds for i. We show that it also holds for $i+1$ . If the opponent makes a move at stage $i+1$ then ${PPT}_{i+1}={PPT}_i$ . The statement holds obviously.

If the proponent executes step (1b) at stage $i+1$ meaning that step (1a) is not possible at this stage. Hence all ppas in ${PPT}_i$ are full. The statement holds obviously.

Suppose the proponent executes step (1a) at stage $i+1$ (to expand a ppa $\pi \in {PPT}_i$ into a new ppa ${\pi }^{\prime }\in {PPT}_{i+1}$ ). Hence π is the only non-full ppa in ${PPT}_i$ . Therefore, if ${\pi }^{\prime }$ is full, there is no non-full ppa in ${PPT}_{i+1}$ . If ${\pi }^{\prime }$ is not full, ${\pi }^{\prime }$ is the only non-full ppa in ${PPT}_{i+1}$ . The statement holds.

(2)

Suppose π is not full. It follows immediately from the definition of sdd that the proponent will execute step (1a) at stage $i+1$ to expand π into ${\pi }^{\prime }\in {PPT}_{i+1}$ . The uniqueness of ${\pi }^{\prime }$ follows from Lemma 7.

Suppose ${\pi }^{\prime }\in {PPT}_{i+1}$ is the unique immediate expansion of π. Hence π is no-full obviously.

(3)

By induction on i with $i⩾i_0$ . The statement holds obviously for $i=i_0$ . Suppose the statement holds for $i⩾i_0$ . We show that it also holds for $i+1$ .

Let $\pi \in {PPT}_{i+1}$ . There are two cases:

Case 1 $\pi \in {PPT}_i$ . From statements (1,2) and Lemma 7, it follows that π is full. The statement follows directly from the induction hypothesis.

Case 2 $\pi \notin {PPT}_i$ . Hence the proponent executes step (1a) at stage $i+1$ to expand some $p\in {PPT}_i$ into π with $h_p=(T_0,i_0),(T_1,i_0+1),...,(T_k,i_0+k)$ and $T_p=T_k$ . Hence p is not full. From the induction hypothesis, we have $i_0+k=i$ . Therefore $h_{\pi }=h_p.(T_{\pi },i+1)$ and $T_{\pi }\subseteq Cl(T_{\pi })$ . Hence the statement holds.

(4)

Suppose π is not full. From statement (3), $h_{\pi }=(T_0,i_0),(T_1,i_0+1),...,(T_k,i_0+k)$ with $i_0+k=i$ where $i_0=st(\pi )$ . It follows that the proponent makes the move (1a) at every stage $j:i⩾j>0$ . Contradiction. We have proved that π is full.

Lemma 13.

Let $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a strongly grounded dispute derivation for $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ wrt a ground map λ.

It holds that for all i: ${PTA}_i\subseteq Cl({GE}_{{AF}_{\mathcal{F}}})$ .

Proof.

Let $\alpha \in {PTA}_i$ , $0⩽i⩽n$ . We show by induction on i that $\alpha \in Cl({GE}_{{AF}_{\mathcal{F}}})$ .

Base Step: “ $i=0$ ”. If δ is not an assumption then ${PTA}_0=\mathrm{\varnothing }$ . The lemma holds vacuously. Suppose δ is an assumption. The lemma holds since it is assumed that $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ .

Inductive Step: Suppose the lemma holds for $i-1$ . We show that it also holds for i.

The lemma follows directly from the inductive hypothesis if at step i, the opponent makes a move or the proponent attacks an opponent ppa.

Suppose now that the proponent expands some ppa π at step i. If $\alpha \in {PTA}_{i-1}$ , the lemma follows from the inductive hypothesis.

Suppose now $\alpha \in {PTA}_i\setminus {PTA}_{i-1}$ . Therefore $\alpha \in Ass(\lambda (Cl(T_{\pi }))$ . Since $\lambda (Cl(T_{\pi }))\in {GE}_{{AF}_{\mathcal{F}}}$ , it follows $\alpha \in Cl({GE}_{{AF}_{\mathcal{F}}})$ .

Lemma 14.

Let $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a strongly grounded dispute derivation for $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ wrt a ground map λ.

For each $0⩽i⩽n$ , for all $\pi ,{\pi }^{\prime }\in {OPT}_i$ , it holds that $st(\pi )=st({\pi }^{\prime })$ .

Proof.

Suppose there are π, ${\pi }^{\prime }$ s.t. $st(\pi )\ne st({\pi }^{\prime })$ ; Without loss of generality, we assume that $st(\pi )<st({\pi }^{\prime })$ . We first show that π is full.

Suppose π is not full. That means that at stage $st({\pi }^{\prime })$ , the opponent attacks a proponent assumption (step 2.b) even though the opponent could have perform step (2a) (expanding a prefix of π). Hence $sdd$ is not a strongly grounded dispute derivation. Contradiction.

We have proved that π is full.

Since step (2a) has higher priority than step (2b) in the definition of sdd, it follows that $st(\pi )+lh(\pi )<st({\pi }^{\prime })$ .

Since π is full, $T_{\pi }$ is an argument. Let α be an assumption such that $Cl\left(T_{\pi }\right)=\overline{\alpha }$ . From Lemma 13, it follows $\alpha \in Cl({GE}_{{AF}_{\mathcal{F}}})$ . From Lemma 11, there is $\beta \in Ass(T_{\pi })$ such that $rank(\overline{\beta })<rank\left(\alpha \right)$ and $\overline{\beta }\in Cl\left({GE}_{{AF}_{\mathcal{F}}}\right)$ . It is thus possible for the proponent to execute step (1b) before $st({\pi }^{\prime })$ to attack β. Hence $\pi \notin {OPT}_i$ . Contradiction.

Therefore the assumption that $st(\pi )\ne st({\pi }^{\prime })$ is wrong.

Definition 17.

Let π be an opponent ppa and ${\pi }^{\prime }$ , ${\pi }^{″}$ be proponent ppas in a strongly grounded dispute derivation $sdd$ .

• (1)

We say π hits ${\pi }^{\prime }$ at an assumption ${\alpha }^{\prime }\in Ass(T_{{\pi }^{\prime }})$ if

${\pi }^{\prime }$ is full and $\overline{{\alpha }^{\prime }}=Cl\left(T_{\pi }\right)$ ; and

$st({\pi }^{\prime })<st(\pi )$ ; and

there is no opponent ppa p in $sdd$ such that $\overline{{\alpha }^{\prime }}=Cl\left(T_p\right)$ and $st({\pi }^{\prime })<st(p)<st(\pi )$ .

We say π hits ${\pi }^{\prime }$ if π hits ${\pi }^{\prime }$ at some assumption.

(2)

We say ${\pi }^{\prime }$ hits π (at an assumption $\alpha \in Ass(T_{\pi })$ ) if the proponent attacks π at assumption α at stage $st({\pi }^{\prime })$ .

(3)

We say ${\pi }^{″}$ supports ${\pi }^{\prime }$ if there is an opponent ppa p such that p hits ${\pi }^{\prime }$ and ${\pi }^{″}$ hits p.

It is not difficult to see that the following lemma holds.

Lemma 15.

Let π be an opponent ppa and ${\pi }^{\prime }$ be proponent ppa in a strongly grounded dispute derivation $sdd$ .

• (1)

for each assumption $\alpha \in T_{\pi }$ , there is at most one proponent ppa hitting π at α.

(2)

for each assumption ${\alpha }^{\prime }\in T_{{\pi }^{\prime }}$ , there is at most one opponent ppa hitting ${\pi }^{\prime }$ at ${\alpha }^{\prime }$ .

(3)

if ${\pi }^{\prime }$ hits π then π is discontinued at stage $st({\pi }^{\prime })$ ; 30

Lemma 16.

Let π, ${\pi }^{\prime }$ be two proponent ppas in a strongly grounded dispute derivation $sdd$ for $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ such that ${\pi }^{\prime }$ supports π. It holds $rank(Cl(T_{\pi }))>rank(Cl(T_{\pi }^{{}^{\prime }}))$ .

Proof.

Let p be an opponent ppa such that p hits π and ${\pi }^{\prime }$ hits p.

From Lemma 11, it follows $rank(Cl(T_{\pi }))⩾rank(target(p))$ . From the selection criteria for step (1b) in sdd, it follows $rank(target(p))>rank(Cl(T_{{\pi }^{\prime }}))$ .

Hence $rank(Cl(T_{\pi }))>rank(Cl(T_{{\pi }^{\prime }}))$ .

Theorem 7.

Let $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩,...$ be an infinite strongly grounded dispute derivation for $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ wrt ground map λ.

Then for each k, the set ${OPT}^k=\{\pi \in {\bigcup }_{i=0}^{\mathrm{\infty }}{OPT}_i|st(\pi )=k\}$ is finite.

Proof.

Suppose the contrary that there is k, such that ${OPT}^k$ is infinite. From Definition 13 (of grounded dispute derivation), it follows that the opponent attacks a proponent assumption α at stage k. From Lemma 14, it follows ${OPT}_k=\{{\pi }_0\}$ where ${\pi }_0=(T_0,h_0)$ with $T_0=[\overline{\alpha }]$ and $h_0=([\overline{\alpha }],k)$ .

It follows that ${OPT}^k$ has the structure of a tree ${\mathcal{T}}_k$ as follows:

The root of ${\mathcal{T}}_k$ is ${\pi }_0$ . A ppa ${\pi }^{\prime }\in {OPT}^k$ is a child of $\pi \in {OPT}^k$ iff ${\pi }^{\prime }$ is an immediate expansion of π.

Because $\mathcal{F}$ is finitary, each ppa has only finitely many immediate expansions. Hence each node in ${\mathcal{T}}_k$ has finitely many children. Since ${\mathcal{T}}_k$ is infinite (because ${OPT}^k$ is infinite), there is an infinite path labeled by ${\pi }_0,{\pi }_1,...$  , in ${\mathcal{T}}_k$ such that ${\pi }_{i+1}$ is an immediate expansion of ${\pi }_i$ .

We show that $T={\bigcup }_{i=0}^{\mathrm{\infty }}{T}_{{\pi }_i}$ is a full argument. Suppose T is not a full argument. Then there is a non-final leaf node N in T. Therefore there is m such that for each $j⩾m$ , N is a non-final leaf node in $T_{{\pi }_j}$ .

For each $j⩾m$ , let $N_j$ be the non-final leaf node in $T_{{\pi }_j}$ selected for expansion to $T_{{\pi }_{j+1}}$ . It follows from the extra condition for step (2a) in Definition 15 of sdd, that $h(N_j,T)=h(N_j,T_{{\pi }_j})⩽h(N,T_{{\pi }_j})=h(N,T)$ . The set of $N_{j}s$ is therefore finite implying that the sequence ${\pi }_0,{\pi }_1,...$ is finite. Contradiction.

We have proved that T is a full argument.

It is clear that T attacks α. Since $\alpha \in Cl({GE}_{{AF}_{\mathcal{F}}})$ (Lemma 13), T is attacked by some $X\in {GE}_{{AF}_{\mathcal{F}}}$ such that $rank(X)<rank(\alpha )$ . It follows there is $\beta \in Ass(T)$ such that $\overline{\beta }=Cl\left(X\right)$ . Hence $rank(\overline{\beta })<rank\left(X\right)<rank\left(\alpha \right)$ .

Let $j=min\{i|\beta \in Ass(T_{{\pi }_i})\}$ . From Definition 15 of sdd, it is possible for the proponent to execute step (1b) at stage j or some later stage $>j$ .31 As step (1b) has higher priority than step (2a), the infinite path ${\pi }_0,{\pi }_1,...$  , in ${\mathcal{T}}_k$ does not exist. Contradiction

Hence tree ${\mathcal{T}}_k$ is finite. Contradiction. Hence we have proved that ${OPT}^k$ is finite.

Lemma 17.

Let $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩,...$ be an infinite strongly grounded dispute derivation for $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ wrt ground map λ.

Let $\pi \in \cup \{{PPT}_i|i⩾0\}$ and π be a full ppa. Then the set of proponent ppas in sdd supporting π is finite.

Proof.

It is obvious that for each assumption $\alpha \in T_{\pi }$ there is at most one opponent ppa hitting π at α. Let P be the set of opponent ppas in sdd that hit π. Since $Ass(T_{\pi })$ is finite, it follows directly from Lemma 15 that P is finite. Hence it also follows directly from Lemma 15 that there are only finite number of proponent ppas hitting the ppas in P. Therefore the lemma holds.

Theorem 8.

Let $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩,...$ be an infinite strongly grounded dispute derivation wrt ground map λ.

The set of proponent profiled full arguments in $sdd$ is finite.

Proof.

We first prove two relevant properties.

Property 1.

• (1)

Each opponent ppa in sdd hits some proponent ppa in sdd;

(2)

Each proponent ppa in sdd that does not start at stage 0 hits some opponent ppa in sdd.

(3)

Each full proponent ppa in sdd that does not start at stage 0 supports some other full proponent ppa in sdd.

Proof of Property 1. Proof of Property 1.

Statement 2 holds obviously. Statement 3 follows directly from statements 1,2. We prove statement 1. Let π be an opponent ppa in sdd and $i=st(\pi )$ and $\alpha \in {PTA}_{i-1}$ such that $\overline{\alpha }=Cl\left(T_{\pi }\right)$ .

Let ${\pi }^{\prime }$ be a proponent full ppa in sdd satisfying the following condition:

$\alpha \in Ass(T_{{\pi }^{\prime }})$ ;

$st({\pi }^{\prime })=max\{st(q)|\alpha \in Ass(T_q)\text{~and~}q\in {PPT}_{i-1}\}$

We show that π hits ${\pi }^{\prime }$ . Suppose π does not hit ${\pi }^{\prime }$ . Hence there is opponent ppa p such that $st({\pi }^{\prime })<st(p)<st(\pi )$ s.t. $\overline{\alpha }=Cl\left(T_p\right)$ . Let $j=st(p)$ . It follows $j<i$ and $\alpha \notin {PTA}_j$ . Since $\alpha \in {PTA}_{i-1}$ , it follows that there is proponent full ppa q such that $st({\pi }^{\prime })<j<st(q)<i$ and $\alpha \in T_q$ . Because $st(q)<i$ , it follows $q\in {PPT}_{i-1}$ . Contradiction to the construction of ${\pi }^{\prime }$ .

Let ${\pi }_0$ be the unique proponent profiled full argument such that $st({\pi }_0)=0$ (the existence and uniqueness of ${\pi }_0$ follows from Lemma 12).

A support path in $sdd$ is a sequence of profiled full arguments ${\pi }_0,...,{\pi }_n$ ( $n⩾0$ ) in ${\bigcup }_{i=0}^{\mathrm{\infty }}{PPT}_i$ such that ${\pi }_{i+1}$ supports ${\pi }_i$ ( $0⩽i<n$ ).

Property 2.

Each full proponent ppa π in sdd appears as the last element of a support path.

The proof is by induction on $st(\pi )$ . The property holds obviously for $st(\pi )=0$ . Suppose that the property holds for all full proponent ppas that start before π. Therefore π supports some full proponent ppa ${\pi }^{\prime }$ (from above Property 1). Hence $st({\pi }^{\prime })<st(\pi )$ . From the induction hypothesis, it follows that ${\pi }^{\prime }$ is the last element of some support path $sq$ . Hence $sq.\pi$ is a support path.

The set of all support paths in $sdd$ forms a tree $\mathcal{T}$ where the root is ${\pi }_0$ and the nodes in $\mathcal{T}$ are support paths and a support path ${\pi }_0,...,{\pi }_n,{\pi }_{n+1}$ is a child of ${\pi }_0,...,{\pi }_n$ .

Suppose the set of proponent profiled full argument in $sdd$ is infinite. Therefore $\mathcal{T}$ is infinite.

From Lemma 17, each node in $\mathcal{T}$ has only finitely many children. Hence there is an infinite support path in $\mathcal{T}$ . Contrary to Lemma 16.

Hence the set of proponent profiled full arguments in $sdd$ is finite.

6.1. .Proof of completeness theorem

We only need to show that there exists no infinite $sdd$ for δ wrt λ.

Assume that there exists an infinite strongly grounded dispute derivation for $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ wrt ground map λ $$\begin{array}{r}sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_i,{PTA}_i,{OPT}_i⟩,...\end{array}$$

From Theorem 8, it follows that there is n such that ${PPT}_n$ contains all proponent profiled full arguments in $sdd$ . Therefore the opponent makes a move at all stages $m>n$ in $sdd$ .

Let $K_0$ be the set of starting times before n of opponent ppas in $sdd$ while $K_1$ be the set of starting times of all opponent ppas in $sdd$ , i.e. $$\begin{array}{rl}{K}_0& =\left\{j|\mathrm{\exists }\pi \in \bigcup _{i=0}^{\mathrm{\infty }}OP{T}_i\mathrm{s}.\mathrm{t}.j=st(\pi )<n\right\},\mathrm{and}\\ K_1& =\left\{j|\mathrm{\exists }\pi \in \bigcup _{i=0}^{\mathrm{\infty }}OP{T}_i\mathrm{s}.\mathrm{t}.j=st(\pi )\right\}.\end{array}$$

From the Definition 15 (of strongly grounded dispute derivation), it follows that $|K_1|⩽|K_0|+|{PTA}_n|$ .

From ${\bigcup }_{i=0}^{\mathrm{\infty }}{OPT}_i=\bigcup _{k\in K_1}{OPT}^k$ , it follows immediately from Theorem 7 that ${\bigcup }_{i=0}^{\mathrm{\infty }}{OPT}_i$ is finite. Hence $sdd$ is finite. Contradiction.

We have proved that there is no infinite $sdd$ .

The completeness theorem follows directly from Theorem 6.

7. .Flatten dispute derivation

We have presented the grounded dispute derivations that are both sound and complete wrt finitary assumption-based frameworks where proof trees together with their histories are fully and explicitly represented to shed light on the construction process of arguments and counter arguments during a derivation and hence providing key structural insights into the soundness and completeness of the procedure.

In this section, we present another procedure that is simply the result of flattening the first where instead of the whole proof trees, only their supports are recorded. Consequently, the second procedure is both sound and complete but with much simpler date structure and hence much more amenable to possible implementation. The disadvantage of the flatten version (like Prolog for logic programming) is that it does not give the reasons how a returned answer is supported and defended.

In this section we propose the flatten grounded dispute derivations which focus on the supports of proof trees instead of the whole trees like other proposals including [17–19,24].

The representation of flatten grounded dispute derivations is based on multisets. To keep the paper self-contained, we recall in Appendix A.1 a brief but formal introduction of multisets from [31].32

Definition 18 Flatten Grounded Dispute Derivation

A flatten grounded dispute derivation for a sentence δ is a sequence of the form $$\begin{array}{r}⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_n,{OS}_n⟩\end{array}$$ where

for each i, ${PS}_i$ is a multiset of sentences while ${OS}_i$ is a multisets of multisets of sentences; and

${PS}_0=\{\delta \}$ , and ${OS}_0=\mathrm{\varnothing }$ , and

at stage i ( $i>0$ ), one of the dispute parties makes a move satisfying the following properties:

(1)

Suppose the proponent makes a move at stage i. The proponent has two options:

• (a)

The proponent selects a non-assumption $\sigma \in {PS}_{i-1}$ , a rule r with $hd(r)=\sigma$ and,

${PS}_i=({PS}_{i-1}\setminus \{\sigma \})\oplus bd(r)$

${OS}_i={OS}_{i-1}$ .

(b)

The proponent selects $S\in {OS}_{i-1}$ and an assumption $\alpha \in S$ and,

${PS}_i={PS}_{i-1}\oplus \left\{\overline{\alpha }\right\}$

${OS}_i={OS}_{i-1}\setminus \{S\}$

(2)

Suppose the opponent makes a move at stage i. The opponent has two options:

• (a)

The opponent selects $S\in {OS}_{i-1}$ and a non-assumption $\sigma \in S$ and proceeds as follows:

${PS}_i={PS}_{i-1}$

${OS}_i=({OS}_{i-1}\setminus \{S\})\oplus \{(S\setminus \{\sigma \})\oplus bd(r)|hd(r)=\sigma \}$ .

(b)

The opponent selects an assumption $\alpha \in {PS}_{i-1}$ and,

${PS}_i={PS}_{i-1}-\{\alpha \}$

${OS}_i={OS}_{i-1}\oplus \{\{\overline{\alpha }\}\}$ .

Definition 19.

A flatten grounded dispute derivation $⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_n,{OS}_n⟩$ is successful if ${PS}_n={OS}_n=\mathrm{\varnothing }$ .

Table 3

A successful flatten grounded dispute derivation.

Stage	Move	$PS$	$OS$
0		$\{a\}$	$\mathrm{\varnothing }$
1	$1a$	$\{not\mathrm{\_}\alpha \}$	$\mathrm{\varnothing }$
2	$2b$	$\mathrm{\varnothing }$	$\{\{\alpha \}\}$
3	$2a$	$\mathrm{\varnothing }$	$\{\{not\mathrm{\_}\beta ,f(0)\}\}$
4	$1b$	$\{\beta \}$	$\mathrm{\varnothing }$
5	$1a$	$\mathrm{\varnothing }$	$\mathrm{\varnothing }$

Example 7.

A successful flatten grounded dispute derivation $⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_5,{OS}_5⟩$ for sentence a (wrt the argumentation framework ${\mathcal{F}}_2$ in the introduction) is illustrated in Table 3 and explained in details below. For convenience we recall ${\mathcal{F}}_2$ below. $$\begin{array}{rl}& {\mathcal{F}}_2:r:a\leftarrow not\mathrm{\_}\alpha r^{″}:\alpha \leftarrow not\mathrm{\_}\beta ,f(0)r_n:f(n)\leftarrow f(n+1),n⩾0\\ & t:\beta \leftarrow \end{array}$$

At stage 0, we have ${PS}_0=\{a\}$ and ${OS}_0=\mathrm{\varnothing }$ .

At stage 1, the proponent makes a move to expand the non-assumption a by applying step (1a) using rule r.

Hence ${PS}_1=({PS}_0\setminus \{a\})\oplus bd(r)=\{not\mathrm{\_}\alpha \}$ where $bd(r)=\{not\mathrm{\_}\alpha \}$ .

${OS}_1={OS}_0=\mathrm{\varnothing }$ .

Next, at stage 2, the opponent attacks the assumption $not\mathrm{\_}\alpha \in {PS}_1$ by applying step (2b). Hence ${OS}_2={OS}_1\oplus \{\{\alpha \}\}=\{\{\alpha \}\}$ .

${PS}_2={PS}_1-\{not\mathrm{\_}\alpha \}=\mathrm{\varnothing }$ .

At stage 3, the opponent applies step (2a), selecting $S=\{\alpha \}$ from $O{S}_2$ and expanding α. Since rule $r^{″}$ is the only one with head α, it follows

${OS}_3=({OS}_2\setminus \{S\})\oplus \{(S\setminus \{\alpha \})\oplus bd(r^{″})\}=\{\{not\mathrm{\_}\beta ,f(0)\}\}$ .

${PS}_3={PS}_2=\mathrm{\varnothing }$

At stage 4, the proponent applies step (1b) by selecting $S=\{not\mathrm{\_}\beta ,f(0)\}\in {OS}_3$ and assumption $not\mathrm{\_}\beta \in S$ for attack. Therefore

${PS}_4={PS}_3\oplus \{\beta \}=\{\beta \}$ .

${OS}_4={OS}_3\setminus \{S\}=\mathrm{\varnothing }$ .

Finally at stage 5, the proponent applies step (1a), using rule t, to expand β. Therefore

${PS}_5=({PS}_4\setminus \{\beta \})\oplus bd(r)=\mathrm{\varnothing }$ (since $bd(r)=\mathrm{\varnothing }$ ).

${OS}_5={OS}_4=\mathrm{\varnothing }$

As both PS and OS are empty, the derivation is successful.

Definition 20.

• (1)

Let $dd$ be a grounded dispute derivation of length n for a sentence δ (as defined in Definition 13).

Define a sequence of multisets of assumptions $$\begin{array}{r}\mathcal{M}(dd)={MPTA}_0,...,{MPTA}_n\end{array}$$ by:

• ${MPTA}_0={PTA}_0$ .

• Suppose ${MPTA}_{i-1}$ is defined. Then

• *

  ${MPTA}_i={MPTA}_{i-1}\oplus Ass(r)$ if the move at stage i is (1a);

• *

  ${MPTA}_i={MPTA}_{i-1}-\{\alpha \}$ if the move at stage i is (2b);

(2)

For any proof tree T, $NSpm(T)$ and $Spm(T)$ denote respectively the multiset of the non-assumptions and the multiset of sentences labeling the leaf nodes of T and different to $true$ .

$NSpm(T)$ and $Spm(T)$ are often referred to as the multiset non-assumption support or multiset support of T, respectively.

For a set S of ppas, define $$\begin{array}{r}NSpm(S)=\oplus \{NSpm(T_{\pi })|\pi \in S\};\end{array}$$

Lemma 18.

Let $dd$ be a grounded dispute derivation of length n for a sentence δ and $\mathcal{M}(dd)={MPTA}_0,...,{MPTA}_n$ . It holds that for all $0⩽i⩽n$ , ${MPTA}_i$ and ${PTA}_i$ are set-equivalent.

Proof.

We prove by induction that for each i, ${MPTA}_i$ and ${PTA}_i$ are set-equivalent.

It is obvious that ${PTA}_0={MPTA}_0$ .

Let $i>0$ . Suppose for each $j<i$ , ${PTA}_j$ and ${MPTA}_j$ are set-equivalent. We show ${PTA}_i$ and ${MPTA}_i$ are set-equivalent. There are four cases according to four possible moves of the players at stage i.

The move at stage i is (1a). Hence ${PTA}_i={PTA}_{i-1}\cup Ass(r)$ and ${MPTA}_i={MPTA}_{i-1}\oplus Ass(r)$ . From the induction hypothesis, ${PTA}_{i-1}$ and ${MPTA}_{i-1}$ are set-equivalent, it follows obviously that ${PTA}_i$ and ${MPTA}_i$ are set-equivalent.

The move at stage i is (1b) or (2a). From the induction hypothesis, ${PTA}_{i-1}$ and ${MPTA}_{i-1}$ are set-equivalent and ${MPTA}_i={MPTA}_{i-1}$ and ${PTA}_i={PTA}_{i-1}$ , it follows obviously that ${PTA}_i$ and ${MPTA}_i$ are set-equivalent.

The move at stage i is (2b). Hence ${PTA}_i={PTA}_{i-1}\setminus \{\alpha \}$ and ${MPTA}_i={MPTA}_{i-1}-\{\alpha \}$ . From the induction hypothesis, ${PTA}_{i-1}$ and ${MPTA}_{i-1}$ are set-equivalent, it follows obviously that ${PTA}_i$ and ${MPTA}_i$ are set-equivalent.

The following lemmas show that each grounded dispute derivation could be translated into an equivalent flatten one and vice versa.

Lemma 19.

Let $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ be a grounded dispute derivation for δ.

Further let $\mathcal{M}(dd)={MPTA}_0,...,{MPTA}_n$ .

Then the sequence $⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_n,{OS}_n⟩$ where for each $0⩽i⩽n$ ,

${PS}_i=NSpm({PPT}_i)\oplus {MPTA}_i$ ; and

${OS}_i=\{Spm(T_{\pi })|\pi \in {OPT}_i\}$ ;

is a flatten grounded dispute derivation for δ.

Proof.

See Appendix A.4

Lemma 20.

Let $fdd=⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_n,{OS}_n⟩$ be a flatten grounded dispute derivation for δ.

There is a grounded dispute derivation $dd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ for δ such that for all $0⩽i⩽n$ , the following properties hold:

${PS}_i=NSpm({PPT}_i)\oplus {MPTA}_i$ ; and

${OS}_i=\{Spm(T_p)|p\in {OPT}_i\}$ ;

where $\mathcal{M}(dd)={MPTA}_0,...,{MPTA}_n$ .

Proof.

See Appendix A.5.

Theorem 9 Soundness Theorem for Flatten Grounded Dispute Derivation

Let $dd=⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_n,{OS}_n⟩$ be a successful flatten grounded dispute derivation for δ. Then $\delta \in Cl({GE}_{{AF}_{\mathcal{F}}})$ .

Proof.

From Lemma 20, there exists a grounded dispute derivation ${dd}^{\prime }=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ for δ such that ${PS}_i=NSpm({PPT}_i)\oplus {MPTA}_i$ ; and ${OS}_i=\{Spm(T_p)|p\in {OPT}_i\}$ ;

Since ${PS}_n=\mathrm{\varnothing }$ , the sets $NSpm({PPT}_n)$ are empty. Therefore all ppas in ${PPT}_n$ are full.

As ${OS}_n=\{Spm(T_p)|p\in {OPT}_n\}$ and ${OS}_n=\mathrm{\varnothing }$ , it follows ${OPT}_n=\mathrm{\varnothing }$ .

Because ${PS}_n=\mathrm{\varnothing }$ and ${PS}_n=NSpm({PPT}_n)\oplus {MPTA}_n$ , ${MPTA}_n$ is empty.

Since ${PTA}_n$ and ${MPTA}_n$ are set-equivalent (see Lemma 18) and ${MPTA}_n$ is empty, ${PTA}_n$ is empty.

Therefore ${dd}^{\prime }$ is a successful grounded dispute derivation. The theorem follows from Theorem 4.

Theorem 10 Completeness Theorem for Flatten Grounded Dispute Derivation

Let $\mathcal{F}$ be a finitary ABA framework and $\sigma \in Cl({GE}_{\mathcal{F}})$ . Then there is a successful flatten dispute derivation $⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_n,{OS}_n⟩$ for σ.

Proof.

From the completeness Theorem 5, there is a successful grounded dispute derivation $sdd=⟨{PPT}_0,{PTA}_0,{OPT}_0⟩,...,⟨{PPT}_n,{PTA}_n,{OPT}_n⟩$ for σ.

It holds that ${OPT}_n=\mathrm{\varnothing }$ and all ppas in ${PPT}_n$ are full.

Let ${sdd}^{\prime }=⟨{PS}_0,{OS}_0⟩,...,⟨{PS}_n,{OS}_n⟩$ be the flatten dispute derivation for σ as defined in Lemma 19.

Since ${PTA}_n=\mathrm{\varnothing }$ , ${MPTA}_n=\mathrm{\varnothing }$ (see Lemma 18).

Since all ppas in ${PPT}_n$ are full, $NSpm({PPT}_n)=\mathrm{\varnothing }$ . It hence follows ${PS}_n=NSpm({PPT}_n)\oplus {MPTA}_n=\mathrm{\varnothing }$ .

Since ${OPT}_n=\mathrm{\varnothing }$ , ${OS}_n=\{Spm(T_p)|p\in {OPT}_n\}=\mathrm{\varnothing }$ , ${sdd}^{\prime }$ is successful.

8. .Discussion

We study the soundness and completeness of dialectical proof procedures for assumption-based argumentation with respect to the skeptical semantics. We have presented two proof procedures. In one, proof trees together with their histories are fully and explicitly represented. The other procedure is simply the result of flattening the first. We show the soundness and completeness of both proof procedures wrt grounded semantics of assumption-based argumentation frameworks where possibly non-terminating computation is represented by infinite arguments.

Assumption-based argumentation is an instance of abstract argumentation. Another well-known instance of abstract argumentation is the ASPIC+ system [27,28]. It would be interesting to see how to apply our proof procedures to ASPIC+.

In many applications, a sentence is (universally) accepted if it is accepted in every preferred extensions (or stable extensions) [2]. It would be interesting to see how our proof systems in this paper as well as in [31] could be extended for the universal acceptance.

Attacks may have different strength [16]. [7] proposed a dialectical proof procedure for abstract argumentation frameworks with attacks having different strength. It would be interesting to see how to integrate the ideas of [7]’s into our proof system for assumption-based argumentation with attacks of different strength.

Dialectical proof procedures are not the only approach to proof theory of logical argumentation. [1] proposes dynamic proof systems for logical argumentation. It would be intriguing to see the relationship between these rather distinct approaches.

Grounded semantics of an assumption-based argumentation could be viewed as a form of nonmonotonic inductive definition of the ABA framework [10]. In that sense, our proof system can be viewed as an example of a dialectical proof procedure for a nonmonotonic inductive definition. It may be worth exploring further whether dialectical proof systems could be developed for other nonmonotonic inductive definition systems as defined in [10].

There are recently several interesting works on the semantics of infinite argumentation frameworks [3,4]. It is worth noting that the inclusion of infinite arguments into the argumentation frameworks of assumption-based argumentation does not transform it into infinite argumentation frameworks as illustrated in the introduction. This leads to an interesting question of how to extend the results in [3,4] to frameworks with “two kinds of infinity”: infinite number of arguments and arguments of infinite size.

Dialectical procedures could be viewed as a form of dialogue games where for both players the sets of rules as well as assumptions are given and fixed at the beginning. A more general form of dialogue games is proposed in [23] where rules and assumptions are introduced during the dialogue. While the soundness of such games has been studied in [23], their completeness is not. The completeness results in this paper, especially the completeness of the flatten procedure could shed light on the completeness of such dialogue games.