You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Characterizing strongly admissible sets

Abstract

The concept of strong admissibility plays an important role in dialectical proof procedures for grounded semantics allowing, as it does, concise proofs that an argument belongs to the grounded extension without having necessarily to construct this extension in full. One consequence of this property is that strong admissibility (in contrast to grounded semantics) ceases to be a unique status semantics. In fact it is straightforward to construct examples for which the number of distinct strongly admissible sets is exponential in the number of arguments. We are interested in characterizing properties of collections of strongly admissible sets in the sense that any system describing the strongly admissible sets of an argument framework must satisfy particular criteria. In terms of previous studies, our concern is the signature and with conditions ensuring realizability. The principal result is to demonstrate that a system of sets describes the strongly admissible sets of some framework if and only if that system has the property of being decomposable.

1.Introduction

The formal model of abstract argumentation proposed in the watershed paper of Dung [8] has given rise not only to a coherent and consistent view of argumentation semantics but also to a uniform basis against which issues in algorithmic and computational complexity can be gauged. In addition to the set-theoretic semantics formulated by Dung, a number of alternative forms have been promoted. One of these, strong admissibility is the subject of the present article.

The concept of strong admissibility was first introduced in the work of Baroni and Giacomin [3] and has subsequently been studied by Caminada and Dunne [6,7]. Strong admissibility is especially useful for showing that a particular argument is part of the grounded extension. As the grounded extension is the (unique) biggest strongly admissible set, showing membership of any strongly admissible set is sufficient to prove that the argument is in the grounded extension.

In this paper our aim is to examine the nature of strong admissibility from the perspective of signature and realizability. These concepts for argumentation semantics were introduced and analyzed in detail in Dunne et al. [10,11], one concern of their study being to characterize those subsets of sets of n arguments for which there is some af, H, whose solution sets under a given semantics are exactly the set described. A detailed overview of work on realizability may be found in the survey article of Baumann [4].

This paper is structured as follows. First, in Section 2 we present some formal preliminaries regarding abstract argumentation and strong admissibility. In Section 3 the technical condition underpinning our results is presented and then, in Section 4 we present a necessary condition for a system of sets to be the strongly admissible sets of some af. The characterization is completed in Section 5 wherein the necessary condition presented in Section 4 is shown to be also sufficient. Conclusions and further directions are presented in Section 6.

2.Preliminaries

In the current section, we briefly restate some of the basic concepts in formal argumentation theory, including strong admissibility. For current purposes, we restrict ourselves to finite argumentation frameworks. We note that the focus on finite structures is not imposed in Dung’s original work and some study of infinite frameworks has been carried out, e.g. on realizability by Baumann and Spanring [5], modelling and description of infinite systems in Baroni et al. [2].

Definition 1.

(Dung [8]) An argumentation framework is a pair (X,A) where X is a finite set of entities, called arguments, and A a binary relation on X. For any p,qX we say that p attacks q if p,qA.

Definition 2.

Let (X,A) be an argumentation framework, xX and SX. We define {x}+ as {yXx attacks y}, {x} as {yXy attacks x}, S+ as {{x}+xX}, and S as {{x}xX}. The set S is said to be conflict-free if SS+=. A set S is said to defend x iff {x}S+. The characteristic function F:2X2X is defined as F(S)={xS defends x}.

Definition 3.

Let (X,A) be an argumentation framework. A subset S of X is said to be:

  • an admissible set if S is conflict-free and SF(S);

  • a complete extension if S is conflict-free and S=F(S);

  • a grounded extension if S is the smallest (w.r.t. ⊆) complete extension;

  • a preferred extension if S is a maximal (w.r.t. ⊆) complete extension.

We use the notation cf for the collection of conflict-free sets and, similarly, adm, com, gr and pr respectively to denote the forms above so that, e.g. adm(H) describes those subsets of arguments in H that are admissible, i.e. Sadm(H) if and only if S is admissible.

It is well known (being illustrated in Dung’s original paper [8]) that for any af, H,

pr(H)adm(H)cf(H).
Furthermore while com(H)adm(H) (“every complete set is admissible”) the converse does not necessarily hold so that one may have admissible sets that are not complete.

The examples presented above are just a small selection of those approaches that have been studied. We refer the interested reader to the treatment of Baroni, Caminada and Giacomin [1] for a comprehensive overview. The concept of strong admissibility was first introduced by Baroni and Giacomin [3]. For current purposes we will, however, apply the equivalent definition of Caminada [6].

Definition 4.

Let (X,A) be an argumentation framework. A subset S of X is strongly admissible if every xS is defended by some TS{x}, T being also strongly admissible.

It can be shown that each strongly admissible set is an admissible subset of the grounded extension [7].

To illustrate, consider the example in Fig. 1 from Caminada [6].

Fig. 1.

Example af.

Example af.

We have

{,{A},{D},{A,C},{A,D},{A,C,D},{A,C,F},{D,F},{A,C,D,F}}
as the strongly admissible sets. The grounded extension of this framework being {A,C,D,F}. Every strongly admissible set is a subset of {A,C,D,F}. Notice that the sets
{{G},{H},{F},{C,H},{C,H,F}}
are all admissible, however none of these are strongly admissible.

3.Signatures and realizability

An arbitrary semantics, σ, describes a set of subsets of X so that for an af, H,

σ(H)={SX:S satisfies the criteria of σ}.
For example, with σ=cf and H=(X,A), we have
cf(H)={SX:S+S=}.

Definition 5.

The signature of a semantics σ, denoted Σσ is

Σσ={S2X:H with σ(H)=S }.

The counterpart to the concept of signature is that of being realizable.

Definition 6.

Let S2X, that is to say a set of subsets of X. The set S is said to be realizable with respect to a semantics σ if there is an af, H=(Z,A) for which XZ and σ(H)=S.

Notice that in this definition we allow arguments zZ which are not acceptable with respect to the conditions specified by σ: so-called auxiliary arguments. The form whereby such additional arguments are not permitted is dubbed “compact realizability” and has been studied (together with divers other formulations) in Baumann [4].

With regard to these notions of signature and realizability the central question of interest, discussed in Dunne et al. [10,11] is the following:

For an argumentation semantics, σ, describe necessary and sufficient conditions, Π:22X{,}, under which,

  • a. For all afs H, Π(σ(H)) holds. (signature)

  • b. For all S2X that satisfy Π(S), there is an af H for which σ(H)=S. (realizable)

In [11] characterization of such conditions are presented for (among others) σ{adm,com,pr}, i.e. admissible, complete, and preferred semantics.

In the current work we consider the case of strong admissibility denoting the relevant semantics as σ=str.

It turns out that we may identify some requirements for membership in Σstr from a number of properties already known from Baroni and Giacomin [3] and Caminada [6].

We first introduce some further notational ideas.

Definition 7.

As is standard we distinguish N (the set of positive integers {1,2,3,}) and W (the set of non-negative integers {0}N).

Let S be a subset of 2X. The set which we denote [S] is the system S[k] formed by setting S[0]=S and for k>0

S[k]=(P,Q)S[k1]×S[k1]{{PQ}}
until the point S[k]=S[k1] is reached.

We say that S is []-closed if S=[S], i.e. k=1 in the process just described since S=S[0] (by definition) and S[0]=S[1].

As a small example of the process of forming [S] suppose we have

S={{1},{2},{3,4},{3,4,5}},S[0]={{1},{2},{3,4},{3,4,5}},S[1]=S[0]{{1,2},{1,3,4},{1,3,4,5},{2,3,4},{2,3,4,5}},S[2]=S[1]{{1,2,3,4},{1,2,3,4,5}},S[3]=S[2].

A final idea, is that of a decomposition of a system of sets.

Definition 8.

Given a system of sets S2X its r-partial decomposition, denoted Δr(S) is formed as an ordered sequence of subsets of S which we denote (S(0),S(1),,S(r)) with the S(i)S pairwise disjoint, i.e. S(i)S(j)=.

Δr(S) is formed from S by applying the following process.

If S then Δr(S)=. Otherwise,

Δr(S)=({})if r=0 and S,(Δr1(S);S(r))if r>0.
In this Δr1(S)=(S(0),S(1),,S(r1)) the (r1)-partial decomposition of S. The system of sets in S(r) (r>0) contains all subsets of S of the form
{{{y}T}:yi=0r1US(i)U and T is -minimal in [i=0r1S(i)] with yTS}.
If S or the process used to define S(r) cannot be applied further then S(r)=. Using this convention every system of subsets of 2X has some r-partial decomposition, although for r large enough (r>|X| for example), S(r)=.

Definition 9.

We say that S2X is decomposable if for some rW

S=[i=0rS(i)]
with (S(0),,S(r)) formed using S according to the prescription given. If S is decomposable we denote its full decomposition by Δ(S) without indicating r.

Again, as a small illustration, suppose that

S={,{1},{2},{1,3},{2,4},{1,3,5},{2,4,6},{1,3,5,7},{1,2,3,4,7}}.
We have,
S(0)={}.
To form S(1) we can only use single element sets from S, leading to
S(1)={{1},{2}}.
Notice that {1}S and that [S(0)] is a minimal such set. We further observe that if there are no sets SS for which |S|=1 then S has (at best) a 0-partial decomposition.

Continuing this example, in order to form S(2) we must identify those minimal sets T[S(0)S(1)] together with those single elements, x, for which {x}TS. In the example we find these to be

{1} with 3,{2} with 4
so giving
S(2)={{1,3},{2,4}}.
In forming S(3) the range of sets we may choose from are those T[S(0)S(1)S(2)] and we require single elements, x, with which {x}TS and T is a minimal set. Here we find
{1,3} with 5,{2,4} with 6
giving
S(3)={{1,3,5},{2,4,6}}.

Notice that {1,2,3,4,7}, although in S with {1,2,3,4}[S(0)S(1)S(2)] cannot be included in S(3): the reason being because of the set {1,3,5,7} in S. The element, 5, is first introduced in S(3) so any sets in S containing 5 and some as yet unrecovered item (such as 7) cannot be built until 5 is available. If it were the case that {1,3,5,7}S then we could add {1,2,3,4,7} to S(3) via {1,2,3,4}[S(0)S(1)S(2)].

The final stage of the decomposition of S forms S(4) as

S(4)={{1,2,3,4,7},{1,3,5,7}}.

We stress the distinction between S(k)= and S(0)={}: the former case describes the situation where either no further expansion (or any expansion whatsoever) via the process of Definition 8, is possible. Thus if S then S(k)= for all kW. Similarly, noting the requirement for new members of X to be used when progressing from S(k) to S(k+1), it is easily seen that S(r)= whenever r>|X|.

We further note the requirement that T witnessing {y}TS(k) is minimal with respect to ⊆, e.g. if y is a new element introduced in forming S(k), and {{u,v,w},{u,v},{v,w}}[S(k1)] then S(k) could contain {u,v,y} or {v,w,y} or {{u,v,y},{v,w,y}}: in all three cases, however, S(k) would not contain {u,v,w,y}. Similarly were {u,v,w,y}S(k) then neither {u,v,y} nor {v,w,y} would be.

Two properties of decomposable systems are given in the next lemmata.

Lemma 1.

Let S2X. For all kW, Δk(S) is unique.

Proof.

Let S2X have an r-partial decomposition

Δr(S)=(S(0),S(1),,S(r)).
Suppose, for the sake of contradiction, that (T(0),T(1),,T(r)) is an r-partial decomposition of S differing from Δr(S).

Choose pW to be the least value for which S(p)T(p). Since it is the case that S(p)T(p) we must have some subset SS for which SS(p) but ST(p) (or vice-versa).

By definition SS(p) indicates that, in addition to SS, we have S=U{y}, U[k=0p1S(k)] and no strict subset V of U for which V[k=0p1S(k)] and V{y}S. Furthermore

yi=0p1WS(i)W.
We have chosen p as the smallest value for which S(p)T(p) and so S(p1)=T(p1). In consequence, [k=0p1S(k)]=[k=0p1T(k)] and, hence, U is a minimal set (wrt ⊆) in [k0p1T(k)] for which {y}US. It is also the case that
yi=0p1WT(i)W.
The inclusion of yU as part of S(p) or T(p) is dependent only on S (since U must be a minimal set for which yUS) and the structure of [k=0p1S(k)] (respectively [k=0p1T(k)]). The underlying set S is the same regardless of how it is decomposed. We have, however, chosen p as the least value at which S(p)T(p). Now we obtain the required contradiction since in order for S(p) to differ from T(p) would require
[i=0p1S(p1)][i=0p1T(p1)]
so contradicting the choice of p.

We conclude that the r-partial decomposition of S is unique. □

Lemma 2.

Let (S(0),,S(r)) be the r-partial decomposition of S and Y be

Y=i=1rTS(i)T={x1,x2,,xt}.
Then Y may be partitioned into disjoint sets (T1,T2,,Tk) each having an associated qi with
1q1<q2<<qk=r
and for all 1p<k
j=1pTj=i=1qpSS(i)S
but
j=1pTji=1qp1SS(i)S;j=1pTji=1qp+1SS(i)S.

Proof.

The partition simply follows the ordering by which individual elements of X are added to S(i) so that,

T1={y:{y}S},T2={y:{y}US,UT1,yT1,and U is a minimal such subset of T1},
and, in general,
Ti = {y:yUS,Uj=1i1Tj,yj=1i1Tj,and U minimal}.

Before presenting our main results it may be helpful to look at two example systems both of which are decomposable.

Consider S defined as

{,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3},{1,4},{1,2,4},{1,3,4},{1,2,3,4},{2,3,5},{1,2,3,5},{1,2,3,4,5}}.
This has a 2-decomposition as
S(0)={},S(1)={{1},{2},{3}},S(2)={{1,4},{2,3,5}}.
Each set in S(2) is formed as the union of a new argument (4 or 5) with a set in [S(1)]. Notice that {1,2,3,4,5}S(2) but is in [S(2)] (via {1,4}{2,3,5}).

We cannot defer adding {2,3,5} to a later level: the definition states that since we are able to include {2,3,5} in S(2) it is required to do so.

The system [S{{1,4,5}}], is also decomposable, however, now the decomposition would be

S(0)={}S(1)={{1},{2},{3}}S(2)={{1,4}}S(3)={{1,4,5},{2,3,5}}
Now we cannot add {2,3,5} to S(2) since we cannot add {1,4,5} at the same time: {1,4}[S(1)] and {1,5}[S(1)] and since 1 occurs as an element of sets in S(1) a decomposition including {1,4,5} would need {1,4}[S(1)].

It is also the case that both systems of sets are in Σstr as can easily be seen by inspecting Fig. 2.

Fig. 2.

Realization of str(H) for example system.

Realization of str(H) for example system.

The implied partitions from Lemma 2 being

({1,2,3};{4,5})first case,({1,2,3};{4};{5})second case.
On the other hand, a system such as
{,{1},{1,2},{1,3,4},{1,2,3,4}}
is not decomposable (this system, however, is []-closed) since there is no way of including {1,3,4} in a decomposition.

Applying the process described in Definition 8 would yield

S(0)={},S(1)={{1}},S(2)={{1,2}}
and no further expansion is possible.

Were the set {1,3} to be added the resulting system would be decomposable. Applying the process described in Definition 8 would then yield

S(0)={},S(1)={{1}},S(2)={{1,2},{1,3}},S(3)={{1,3,4}}.

4.Strongly admissible systems are decomposable

With the concept of decomposability we obtain Theorem 1. We note that the partition structure and its properties in relationship to the characteristic function are used (although not explicity phrased as such) in the algorithm of Caminada and Dunne [7] by which verification of a set as strongly admissible is shown to be decidable in polynomial time.

Theorem 1.

Let X be a finite set of n arguments and S2X.

If SΣstr then S is decomposable.

Proof.

Consider any SΣstr and let H=(X,A) be any af witnessing the realizability of S, i.e. for which str(H)=S.

To begin consider the following partition of

{xX:Sstr(H) with xS}.
This partition is formed as (P0;P1;;Pt) with Pi=FHi and
FHi=if i=0,FH(FHi1)FHi1if i>0.
Here FH(U) is the characteristic function of conflict-free sets U with respect to H=(X,A) so that
FH(U)={xX:y{x}zyUs.t.zy,yA}.
Notice that this is a partition of {xX:Sstr(H) with xS} and, furthermore the grounded extension, GE(H) satisfies,
GE(H)=i=0tPi.
This partition will form the basis for constructing the decomposition of S as
(S(0),S(1),,S(t)).
Fix S(0)={} and S(1)={{x}:xP1}. Every {x}S(1) satisfies xFH1=FH() so not only is {x}S, i.e. str(H) but also every subset of P1 (such corresponding to some union of a subset of S(1)) is in S.

Now suppose we continue this construction relative to elements (S(k1), k2) already built (via the template specified in Definition 8) and the system S. Consider which sets would be included in S(k). We have SS(k) whenever S=yU and

yi=0k1TS(i)T
and U is a ⊆-minimal set in [i=0k1S(i)] for which yUS.

We now argue that for all k, the proposition, Q(k) holds, where

Q(k){(SS and Si=0kPi)S[i=0kS(i)]}.
This will establish the Theorem: SΣstrS is decomposable.

To see this is the case, notice that Q(k) treats S=str(H) as a sequence of sets built by adding single arguments, y, (according to the partition (P0;P1;;Pr) described earlier) to (minimal) strongly admissible sets, S, that defend y, i.e. have yFH(S). Noting the closure of str(H) under set union, so that Sstr(H) and Tstr(H) leads to STstr(H), applying the closure operation [] to S(i) ensures that all S[S(i)] are also in str(H).

We have already shown that Q(1) and Q(0) hold.

Suppose, as an inductive hypothesis, we have demonstrated Q(k) for all 0kr1 for some rt (t being the number of classes in the partition of {xX:Sstr(H) with xS} from Lemma 2).

Consider Pr. By definition, Pr contains FH(FHr1)FHr1 and (from the construction) no argument yPr occurs in

i=0r1TS(i)T.
From the fact that yFH(FHr1)FHr1 we can find some strongly admissible subset, U, using only arguments in i=0r1Pi which defends y. To see this just work back from k=r1 constructing Wr1 (the subset of Pr1 that defends y which, since yFH(FHr1)FHr1, is well-defined); then Wr2 as the subset of Pr2 that collectively defends Wr1 and, in general, Wj as the subset of Pj that defends Wj+1. The set
j=0r1Wi
is in str(H) (thence also in S). Furthermore every set, U, for which U is formed as the union of sets
{Vi:ViPi with ViFH(Vi1)Vi1 (and 1ir1)}
is in str(H) and thus in
[i=0r1S(i)]
from the inductive assumption Q(r1). The argument y is such that yUS and we have just seen that this can be rewritten as
yi=0r1ViViPi.
Now, since we can find some set, U with yUS and Ui=0r1Pi we can certainly find a minimal such set. Furthermore such minimal sets can be divided by exactly the same process, i.e. expressed as the union of sets
{Zi:ZiPi with ZiFH(Zi1)Zi11ir1}.
We deduce that for every yPr we can identify minimal subsets U1,,Ur for which yUiS and S(r) including yUi. Hence every set formed in
[i=0rS(i)]
is in str(H).

We have shown,

S[i=0rS(i)]SS.
To complete the proof we need
Sstr(H)S[i=0rS(i)].
We have already demonstrated the inductive base: SP1 (the only case, other than S= for which Sstr(H) and S[S(0)S(1)]). Hence assume, as inductive hypothesis, it has been shown for all 0kr1 (rt) that
(Sstr(H) and Si=0r1Pi)S[i=0r1S(i)].
We extend this to argue that
(Sstr(H) and Si=0rPi)S[i=0rS(i)].
Let Sstr(H) with Si=0rPi. If SPr= then no further argument is required (the case has been dealt with under our Inductive assumptions). Thus consider
SPr={y1,y2,,ym}.
We know that – by the definition of strongly admissible – there is some subset, U of S{y1,,ym} such that Ustr(H) and, furthermore yiFH(U) for each i. Notice that from the construction of Pr it cannot be the case that yi is needed to defend attacks upon yj. We know that Ustr(H) and Ui=0r1Pi. Therefore, from the inductive hypothesis
U[i=0r1S(i)].
For the construction of S(r) we have sets U1,U2,,Um for which
yiUiS
with Ui a ⊆ smallest set in i=1r1Pi with Uistr(H). We now have,
{U1,U2,,Um}[i=0r1S(i)](I.H.)
and yiUiS(r) (from the minimality of Ui). Hence
i=1m(yiUi)[i=0rS(i)]
and
i=1mUiU[i=0r1S(i)].
Hence,
Ui=1m(yiUi)=U{y1,,ym}[i=0rS(i)].
Completing the argument that if SΣstr then S is decomposable. □

If we look at the case from Fig. 1, we had str(H) as,

{,{A},{D},{A,C},{A,D},{A,C,D},{A,C,F},{D,F},{A,C,D,F}}.
Since this is (self-evidently) a set of sets formed by the strongly admissible sets of an af, the result of Theorem 1 asserts that this system is decomposable. Such a decomposition is given by
S(0)={},S(1)={{A},{D}},S(2)={{A,C}}},S(3)={{A,C,F},{D,F}}
with which every Sstr(H) is formed by taking the union of (sometimes more than 2) appropriate sets from (S(0),S(1),S(2),S(3)), e.g. {A,C,D} is {A,C}{D} the former in S(2), the latter in S(1). We further note that we cannot include {D,F} in S(2) despite {D}S(1): the reason being the need to include all minimal sets with F at the same time, however {A,C,F} is one such set and C first appears in S(2) delaying {A,C,F} to S(3).

5.Decomposable systems are strongly admissible

We now complete the characterization of strong admissibility, the first part of which was demonstrated in Theorem 1 by showing that any system of sets S which is decomposable is in Σstr, i.e. there is an af, H, for which str(H)=S. We need some additional preliminaries.

Given yX and H define FH1(y) to be the subset of 2X{y} for which SFH1(y) if {y}S is conflict-free, yFH(S)S and for all strict subsets T of S yFH(T)T.

The concept FH1(y) was introduced in Dunne [9] where it is dubbed the “inverse characteristic function” of y with respect to H.1

Lemma 3.

Let T2X{y} all of whose members are incomparable, i.e. if (P,Q)T×T then PQ and QP. Let Z=TTT. There is an af H=(X,A) in which {y}ZX and T=FH1(y).

Proof.

Given T as described in the Lemma statement consider the (monotone) Boolean function fT over the propositional variables Z=(z1,z2,,zn) defined via

fT(z1,,zn)TT(ziTzi).
It is clearly the case that fT[S]= if and only if ST for some TT. The specification of fT is given in implicant form, i.e. as a disjunction of product terms. It is, however, well known that any Boolean function has an equivalent specification in implicate form, i.e as a conjunction of clauses. It follows that we can translate T to another system of subsets over Z,
P={P1,P2,,Pm}
with the sets in P being incomparable and
fT(z1,,zn)k=1m(ziPkzi).
Build the af H=(X,A) with X=Z{y}{p1,p2,,pm} m being the number of clause sets in P. Add attacks pk,y for each 1km and an attack zi,pj whenever ziPjP. If UTT then U+={p1,p2,,pm} since the implicant (disjunction of product terms using T) and implicate (conjunction of clauses using P) describe exactly the same propositional function. In order for fT[S]= to hold some TT must describe a subset of S, or (equivalently), S must include at least one zi from every clause PkP. From the latter interpretation we see that each attack on y is defended by T+, i.e. tFH(T)T and no strict subset of T suffices to defend y. □

We note that the relationship between “sets of arguments providing a defence against attacks on y” and the well-known formalisms from propositional logic of cnf and dnf has already been often exploited in formal argumentation. A similar use to that of Lemma 3 is found in Dunne et al. [11].

It is shown in [9, Thm. 4] that this construction is optimal. Given some incomparable system of subsets, S, with P the set of clauses in the unique minimal cnf equivalent to fS(Z), any af in which: for all SS, S{y} is conflict-free and S+{y} must be such that |{y}||P|.

In particular, the realization of an af, H=(X,A) in which FH1(y)=T for some incomparable system of subsets T drawn from Z may use exponentially many auxiliary arguments. This is not only in cases for which |T|2|Z|, e.g. when |Z|=2n and T comprises all subsets of size n from Z. Perhaps less obviously, one might have (again with |Z|=2n) |T|=n but, with the construction used, 2n auxiliary arguments in X. For example if

T={{zi,zn+i}:1in}.
The implicant form of fT(z1,,z2n) used in the proof of Lemma 3 is
i=1nzizn+i.
The implicate form giving rise to the system of sets P has 2n clauses leading to |X|=1+n+2n.

The principal importance of Lemma 3, is as a vehicle by which to establish Theorem 2.

Theorem 2.

If S2X is decomposable then SΣstr.

Proof.

Given S2X which is decomposable let

(S(0),S(1),,S(r))
be the decomposition of S and (P0;P1;;Pt) the partition of i=1rSS(i)S described in Lemma 2 (recalling that P0={}). We use an inductive construction to build, Hk satisfying
str(Hk)=[i=0kS(i)].
The inductive bases (k=0 and k=1) are easily dealt with. In the former case, since S(0)={}, we can use any H0 for which every xX is attacked by at least one other argument. In the case of k=1, H1 comprises the arguments in P1 only with A1=.

Now let us assume, inductively that we have built Ht for all tk1. We wish to form Hk. From the properties of the partition and formulation of the decomposition of S we know that each set in S(k) has the form yU where yi=1k1Pi and U is a subset minimal set in [i=0k1S(i)] for which yUS. For each yPk define

G(y)={{U}:yUS(k)}.
We wish to develop Hk1 to Hk in such a way that G(y)str(Hk). These subsets, G(y) must be such that
G(y)=FHk1(y).
We can now apply the outcome of Lemma 3. Identify each of the arguments contributing to sets in G(y) (all such arguments being in Hk1) and then use the result of Lemma 3 to add the required defences of y as minimal sets in str(Hk).

This suffices to complete the inductive proof. □

Returning to the system presented in Fig. 1, we saw that this corresponds to the system of sets

{,{A},{D},{A,C},{A,D},{A,C,D},{A,C,F},{D,F},{A,C,D,F}}
which has decomposition
S(0)={},S(1)={{A},{D}},S(2)={{A,C}}},S(3)={{A,C,F},{D,F}}.
In forming the af with str(H)=[S(0)S(1)] we require only the two arguments {A,D} and A=. To add S(2) we have a new argument (C) which requires A as a defender. Thus we can add {C} and an argument x together with attacks A,x and x,C. Finally we must account for the cases in S(3) which introduce F which can be defended by either D alone or by {A,C}. We can extend the framework constructed so far adding arguments {y,F} with y,FA. Now, however, we need both C,yA and D,yA. The first will ensure {A,C,F}str(H) and the second that {D,F}str(H).

Combining Theorem 1 and Theorem 2 gives

Corollary 1.

Let S2X.

SΣstrS is decomposable.

6.Conclusions & extensions

Our principal aim in this paper has been to present a characterization of strong admissibility, as first presented in Baroni and Giacomin [3], in terms of the notions of signature and realizability from Dunne et al. [10,11]. Our main result, summarized as Corollary 1, being that a collection of subsets of X describes the strongly admissible sets of some af if and only if that collection possesses the property of being decomposable. The notion of decomposability raises a number of combinatorial and complexity-theoretic questions, some of which we briefly discuss here. One specific aspect of interest concerns the contrast between a framework having exponentially many sets in str(H) but with the possibility of describing these through a much more concise description of its decomposition. As a very simple example, the af, (X,A) in which A= has exactly 2|X| strongly admissible sets (every subset of X). These, however, are succinctly described via the 1-decomposition, ({};{{x1},{x2},,{xn}}). On the other hand there are cases in which the number of distinct sets in S(2) must be exponential in |X|: a simple example of such behaviour being the incomparable system formed by all subsets of X containing exactly |X|/2 members. Hence one direction for further work would concern exploring the relationship between |str(H)| and its decomposition. One complexity-theoretic question concerns the following: given S it is known that verifying Sstr(H) can be carried out efficiently from the results of Caminada and Dunne [7]. If we ask instead whether for some k, SS(k) it is unclear whether this continues to be tractable: intractability is suggested by complexity-theoretic study of “minimal labellings” on the other hand there may be some variation of the algorithm from [7] that could be applied.

Finally we have some questions of interest regarding signatures of analogues of strong admissibility in variant afs. One such being the collective attacks model introduced in Neilsen and Parsons [13] and studied with respect to realizability for the canonical Dung semantics in Dvorak et al. [12]. We leave these and similar questions for further work.

Notes

1 The actual case considered in the present paper is denoted ϜH,cf1(y) in [9] in order to distinguish ⊆-minimal sets. In [9] properties of FH,cf1(y) are studied, this concept covering all subsets, S, for which {y}S is conflict-free and yFH(S). It is, of course, clear that ϜH,cf1(y)FH,cf1(y).

Acknowledgements

The author would like to thank Martin Caminada for useful discussions regarding the strong admissibility semantics.

References

[1] 

P. Baroni, M. Caminada and M. Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, Vol. 1, 2018, pp. 157–234.

[2] 

P. Baroni, F. Cerutti, P.E. Dunne and M. Giacomin, Automata for infinite argumentation structures, Artificial Intelligence 203 (2013), 104–150. doi:10.1016/j.artint.2013.05.002.

[3] 

P. Baroni and M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171(10–15) (2007), 675–700. doi:10.1016/j.artint.2007.04.004.

[4] 

R. Baumann, On the nature of argumentation semantics: Existence and uniqueness, expressibility, and replaceability, Journal of Applied Logics 4(8) (2017), 2779–2886.

[5] 

R. Baumann and C. Spanring, A study of unrestricted abstract argumentation frameworks, in: IJCAI, Vol. 17, 2017, pp. 807–813. doi:10.24963/ijcai.2017/112.

[6] 

M.W.A. Caminada, Strong admissibility revisited, in: Computational Models of Argument; Proceedings of COMMA 2014, S. Parsons, N. Oren, C. Reed and F. Cerutti, eds, IOS Press, 2014, pp. 197–208.

[7] 

M.W.A. Caminada and P.E. Dunne, Strong admissibility revised: Theory and applications, Argument & Computation (2019), in print.

[8] 

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

[9] 

P.E. Dunne, The inverse characteristic function in argumentation frameworks: Properties and complexity (submitted), 2020, www.csc.liv.ac.uk/~ped/combined.pdf.

[10] 

P.E. Dunne, W. Dvořák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, in: 14th International Conference on the Principles of Knowledge Representation and Reasoning, 2014.

[11] 

P.E. Dunne, W. Dvořák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artificial Intelligence 228 (2015), 153–178. doi:10.1016/j.artint.2015.07.006.

[12] 

W. Dvořák, J. Fandinno and S. Woltran, On the expressive power of collective attacks, Argument & Computation 10(2) (2019), 191–230. doi:10.3233/AAC-190457.

[13] 

S.H. Nielsen and S. Parsons, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking arguments, in: International Workshop on Argumentation in Multi-Agent Systems, Springer, 2006, pp. 54–73.