Abstractly Interpreting Argumentation Frameworks for Sharpening Extensions
Ryuta Arisaka and Jérémie Dauphin

arXiv:1802.01526v1 [cs.AI] 5 Feb 2018

ryutaarisaka@gmail.com, jeremie.dauphin@uni.lu

Abstract
Cycles of attacking arguments pose non-trivial issues in Dung
style argumentation theory, apparent behavioural difference
between odd and even length cycles being a notable one.
While a few methods were proposed for treating them, to in particular - enable selection of acceptable arguments in an
odd-length cycle when Dung semantics could select none, so
far the issues have been observed from a purely argumentgraph-theoretic perspective. Per contra, we consider argument graphs together with a certain lattice like semantic structure over arguments e.g. ontology. As we show, the semanticargumentgraphic hybrid theory allows us to apply abstract interpretation, a widely known methodology in static program
analysis, to formal argumentation. With this, even where no
arguments in a cycle could be selected sensibly, we could say
more about arguments acceptability of an argument framework that contains it. In a certain sense, we can ‘verify’ Dung
extensions with respect to a semantic structure in this hybrid
theory, to consolidate our confidence in their suitability. By
defining the theory, and by making comparisons to existing
approaches, we ultimately discover that whether Dung semantics, or an alternative semantics such as cf2, is adequate
or problematic depends not just on an argument graph but also
on the semantic relation among the arguments in the graph.

Introduction
Consider the following scenario: the members of a board
of directors are gathered in a meeting to decide the future
general strategy of their company.
• a1 : “We should focus on improving our business organization structure, because it determines our economic conduct.” (focusOnOs and OsDeterminesEc, to shorten) is
advanced by one member.
• a2 : “We should focus on improving our market performance, because it determines our business organization
structure.” (focusOnMp and MpDeterminesOs) is then
advanced by another member, as an attack on a1 .
• a3 : “We should focus on improving our economic conduct, because it determines our market performance.”
(focusOnEc and EcDeterminesMp), is then given in response to a2 .
• The first member attacks a3 , however, with a1 , to an inconclusive argumentation.
Copyright c 2018, All rights reserved.

• a5 : “Our firm needs 1 billion dollars revenue this fiscal
year.”, meanwhile, is an argument expressed by another
member.
• a4 : “Let our company just sink into bankruptcy!”
(focusOnLiq), another member impatiently declares in
response, against which, however, all the first three speakers promptly express dissent with their arguments.
A

B

a1
a3

a4

a5

ax

a4

a5

a2
AF1
We can represent this argumentation as AF1 of Figure A.
In Dung’s abstract argumentation theory (Dung 1995), an
admissible set of arguments is such that (1) no argument in
the set is attacking an argument of the same set and (2) each
argument attacking an argument in the set is attacked back
by some argument in the set. Clearly, there is no non-empty
admissible set in AF1 . With labelling (Caminada 2006) (an
argument is in if all its attackers are out, is out if there exists
an attacker that is in, and is undecided, otherwise), every
argument is labelled undecided, and so we gain almost no
information on the acceptability of the arguments.
However, notice that a1 , a2 and a3 are arguments for
the benefit of their company’s growth. So, by aggregating
them into a new argument ax : “We should focus on our
company’s further growth” (focusOnImp), and by thus
deriving the framework as in Figure B, we could obtain
some more useful information on the acceptability of
arguments, namely, that ax is in, a4 is out, and a5 is in.
Hence we have sharpened acceptability statuses of a4 and,
in particular, a5 of AF1 .

Abstract interpretation for cycles
What we saw is effectively abstract interpretation (Cousot
and Cousot 1977), a powerful methodology known in static
program analysis to map concrete space semantics to abstract space semantics and to do inferences in the latter space

to say something about the former space. The abstract semantics is typically coarser than the concrete semantics; in
our example, the detail of what exactly their company should
focus on was abstracted away. In return, we were able to conclude that ax is in and, moreover, that a4 is out. Compared
to existing approaches to deal with cycles e.g. (Baroni, Giacomin, and Guida 2005), which gives in state to a5 by enforcing acceptance of either of a1 , a2 and a3 to reject a4 , this
approach that we propose does not require one to accept any
of the arguments within the cycle, even provisionally, in order to be able to reject a4 , and thus accept a5 . By abstracting
away some or all of the cyclic arguments, we avoid having
to accept any of them while rejecting others.
In general, abstract interpretation is applicable to cycles of any length. There can be more than one way
of interpreting an argumentation framework abstractly,
however, and the key for obtaining a good outcome is
to find properties sufficiently fine for abstraction. For
the attacks among a1 , a2 , a3 and a4 in AF1 , we observe that, specifically: a1 ’s focusOnOs, a3 ’s focusOnEc,
and a2 ’s focusOnMp attacks a4 ’s focusOnLiq; and a1 ’s
focusOnOs a3 ’s focusOnEc and a2 ’s focusOnEc form
a cycle of attacks. For these, the semantic information fine
enough to abstract a1 , a2 , a3 into ax is shown below (only
focusOnX expressions are explicitly stated here). In this
focusOnImp

focusOnOs

focusOnMp

focusOnLiq

focusOnEc

Figure C: AF and some ontological abstract-concrete relation over its arguments. focusOnImp is more abstract an
argument than focusOnOs, focusOnMp, and focusOnEc.
Neither of the three is more abstract or more concrete than
the other two. focusOnLiq is not a concrete instance of
focusOnImp.
figure, ax (focusOnImp: focus on further growth), sits as
more abstract an argument of a1 , a2 and a3 . While there may
be other alternatives for abstracting them, focusOnImp belongs to a class of good abstractions, as it satisfies the property that the three arguments but not focusOnLiq fall into
it, which gives justification as to why the attack relation in
the initial argumentation framework is expected to preserve
in the abstractly interpreted argumentation framework (from
ax to a4 ). This is what we might describe the condition of
attack-preservation.
Further, the three concrete arguments exhibit a kind of
competition for the objective: their company’s business focus. While “organisation structure”, “market performance”,
and “economic conduct” all vie for it and in that sense they
indeed oppose, neither of them actually contradicts the ob-

jective, which is why abstraction of the three arguments is
possible here.
We will formulate abstract interpretation for argumentation frameworks, the first study of the kind, as far as we are
aware. We will go through technical preliminaries (in Section 2), and develop our formal frameworks and make comparisons to Dung preferred and cf2 semantics (in Section
3), before drawing conclusions. The discovery we ultimately
make is that whether Dung preferred or cf2 semantics is adequate or problematic depends not only on the argumentation
framework’s structure, but also on the semantic relation between its arguments. We will show that our methodology is
one viable way of enhancing accuracy in judgement as to
which set of arguments should be accepted.

Technical preliminaries
Abstract argumentation
Let A be a class of abstract entities. An argumentation
framework according to Dung’s argumentation theory is a
2-tuple (A, R) for A ⊆fin A and R : A × A. Let a with a
subscript refer to a member of A, and let A with or without a
subscript refer to a subset of A. An argument a1 is said to attack another argument a2 if and only if, or iff, (a1 , a2 ) ∈ R.
A subset A1 is said to accept, synonymously to defend, ax
iff, for each ay attacking ax , it is possible to find some
az ∈ A1 such that az attacks ax . A subset A1 is said to
be: conflict-free iff no element of A1 attacks an element of
A1 ; an admissible set iff it is conflict-free and defends all
the elements of A1 ; and a preferred set (extension) iff it is
a set-theoretically maximal admissible set. There are other
classifications to admissibility, and an interested reader will
find details in (Dung 1995). An argument is skeptically accepted iff it is in all preferred sets and credulously accepted
iff it is in at least one preferred set.

Order and Galois connection for abstract
interpretation
Let L1 and L2 (each) be an ordered set, ordered in v1 and
v2 respectively. Let α be an abstraction function that maps
each element of L1 onto an element of L2 , and let γ be a
concretisation function that maps each element of L2 onto
an element of L1 . α(l1 ) for l1 ∈ L1 is said to be an abstraction of l1 in L2 , and γ(l2 ) for l2 ∈ L2 is said to be a concretisation of l2 in L1 . If α(l1 ) v2 l2 implies l1 v1 γ(l2 )
and vice versa for every l1 ∈ L1 and every l2 ∈ L2 , then
the pair of α and γ is said to be a Galois connection. Galois
connection is contractive: α ◦ γ(l2 ) v2 l2 for every l2 ∈ L2 ,
and extensive: l1 v1 γ ◦ α(l1 ) for every l1 ∈ L1 . Also, both
α and γ are monotone with α ◦ γ ◦ α = α and γ ◦ α ◦ γ = γ.
An ordered set L1 , ordered by a partial order v1 , is a complete lattice just when it is closed under join and meet for
every L01 ⊆ L1 . Every finite lattice is a complete lattice.

Argumentation frameworks for abstraction
While, for our purpose, Dung’s theory is not expressive
enough, all we have to do is to detail the components of the
tuple so that we gain access to some internal information of
each argument.

Lattices

L2

...

(L02 , v,

W V
Let
, ) be a finite lattice. Let E be the class of
expressions as abstract entities. We denote each element of
E by e with or without a subscript and a superscript. Those
focusOnMP and others in our earlier example are expressions. Let f : E → L02 be a function that maps an expression onto an element in the lattice. This function is basically a semantic interpretation of E, which could be some
chosen ontology representation with annotations of generalspecific relation among entities. For example, in Introduction, focusOnImp was more general than focusOnMp,
focusOnEc and focusOnOs, which should enforce
focusOnImp mapped onto an upper part in L02 than the
three, i.e. f (focusOnEc), f (focusOnMp), f (focusOnOs)
v f (focusOnImp). In the rest, rather than L02 itself, we will
talk of the sub-complete-lattice L2 of all f (e) for e ∈ E as
well as its top and its bottom.
E form abstract space arguments with the relation as defined in L2 . Concrete space arguments, in comparison, are
just a set of expressions that can possibly be arguments.
VLet
low : L2 → 2L2 be such that: low(l2 ) := {l2 } if l2 = L2
(the bottom element); else low(l2 ) := {x ∈ LS
2 |Tx @
l2 and @y ∈ L2 .x @ y @ l2 }. We let (L1 , ⊆0 , , ) be
another complete lattice where L1 := 2E and ⊆0 satisfies:
• x ⊆0 y if x ⊆ y.
• x ⊆0 y and y ⊆0 x iff: x = {e1 , . . . , en } and
y ={e1 , . . . , ei−1 , e01 , . . . , e0m , ei+1 , . . . , en } with
low(f (ei )) = {e01 , . . . , e0m }.
The lattices shown in Figure D illustrate the second condition. Notice that low(f (focusOnImp)) =
{f (focusOnMp), f (focusOnEc), f (focusOnOs)} in L2 .
{focusOnImp} and {focusOnMp, focusOnEc, focusOnOs}
are equivalent in L1 which is indeed a quotient lattice.
This equivalence reflects the following interpretation of ours
of expressions. Any expression e1 has concrete instances
e2 , . . . , ei if f (e2 ), . . . , f (ei ) are children of f (e1 ) in abstract lattice. If, here, f (e2 ), . . . , f (ei ) are all the children
of f (e1 ), our interpretation is that mentioning f (e1 ) is just
a short-hand of mentioning all f (e2 ), . . . , f (ei ), i.e. both
mean the same thing with respect to the structure of L2 . It
is because of this that we place all equivalent sets of expressions at the same node in L1 .

Argumentation frameworks
We call an expression with an ID - which we just take from
A - an argument-let, so the class of all argument-lets is
Ab : A × E. Each argument-let shall be denoted by ab with
a subscript.
We update Dung’s (A, R) into (Ab , Rb ) for Ab ⊆fin Ab ,
and Rb : Ab × Ab . To readers interested in knowing
compatibility with Dung’s argumentation frameworks,
Dung’s argument corresponds to a set of all argument-lets
in Ab that share the same ID. For example, we may have
Ab = {(a1 , e1 ), (a1 , e2 ), (a1 , e3 ), (a2 , e1 ), (a2 , e4 )},
in
which case Ab maps into A = {a1 , a2 } if projected into
Dung’s argumentation framework. For compatibility of
attack relation, too, Dung’s (a1 , a2 ) ∈ R, i.e. a1 attacks
a2 , (assuming that both a1 and a2 are in A) corresponds to

...

f(focusOnImp)
f(focusOnMp) f(focusOnEc)

...

f(focusOnOs)

f(focusOnLiq)

... ...

L1

...
...

...

{focusOnMp, focusOnEc, focusOnOs}, {focusOnImp}
{focusOnMp, {focusOnMp,
focusOnEc} focusOnOs}
{focusOnMp}

{focusOnEc,
focusOnOs}

{focusOnOs}
{focusOnEc}
...

{focusOnLiq}

...

Figure D: Illustration of a concrete lattice and an abstract lattice.
((a1 , e1 ), (a2 , e2 )) ∈ Rb for some e1 and some e2 (assuming both (a1 , e1 ) and (a2 , e2 ) are in Ab ). For convenience
hereafter, by argument a with or without a subscript, we
refer to a set of argument-lets in Ab that share the ID a. We
do not consider any more structured arguments than a finite
subset of Ab in this work; further structuring, while of interest, is not the main focus, which is left to a future work. All
notations around extensions: conflict-freeness, acceptance
and defence, admissible and preferred sets, are carried over
here for arguments (note, not for argument-lets).

Abstraction and concretisation
Now, let α : L1 → L2 be the abstraction function, and let
γ : L2 →WL1 be the concretisation function. We require:
α(l1 ) = eu ∈l1 f (eu ); and γ(l2 ) = {x ∈ E | f (x) ∈
low(l2 )}. Intuition is as we described earlier in 3.1. Note
γ(l2 ) is an empty set when low(l2 ) does not contain any
f (e) for e ∈ E. We say that ex is the best abstraction
of {e1 , . . . , en } iff f (ex ) = α({e1 , . . . , en }), but more
generally we say that ex is an abstraction of e1 , . . . , en
iff α({e1 , . . . , en }) v f (ex ). We say that {e1 , . . . , en } is
the most general concretisation of ex iff {e1 , . . . , en } =
γ(f (ex )). More generally, we say that {e1 , . . . , en } is a concretisation of ex iff {e1 , . . . , en } ⊆0 γ(f (ex )).
Proposition 1 (Galois connection) For every l1 ∈ L1 and
every l2 ∈ L2 , we have α(l1 ) v l2 iff l1 ⊆0 γ(l2 ).
W
Proof If: Suppose l2 @ α(l1 ), i.e. l2 @ eu ∈l1 f (eu ) by
definition of α. @ is a standard abbreviation. Then we have
γ(l2 ) ⊂0 l1 , contradiction. Suppose l2 and α(l1 ) are not
comparable in v, then clearly l1 6⊆0 γ(l2 ), contradiction.
Only if: Suppose γ(l2 ) ⊂0 l1 , then there exists at least one
e in l1 which is not in any set equivalent to γ(l2 ) under ⊆0 .
Then by definition of α, we have l2 @ α(l1 ), contradiction.

Example 1 In Figure D, low(f (focusOnImp))
=
{focusOnMp, focusOnEc, focusOnOs}. We see that,
for instance, {focusOnMp, focusOnEc} is mapped to
f (focusOnImp) by α as α({focusOnMp, focusOnEc}) =
f (focusOnMp) ∨ f (focusOnEc). focusOnImp is hence

(the best) abstraction of {focusOnMp, focusOnEc}. Meanwhile, γ(f (focusOnImp)) = {focusOnMp, focusOnEc,
focusOnOs} = X. Since (α, γ) is a Galois connection,
α(X) = f (focusOnImp) again.
Let E ⊆ E with or without a subscript denote a set of expressions. Each argument-let comes with a singleton set of
expression, so an argument comes with a set of expressions.
When we write Eax , we mean to refer to all expressions associated with ax . For abstraction, we say that an argument
ax is:
abstraction-covering for a set of arguments a1 , . . . , an iff,
if ex ∈ Eax is an abstraction
S of E ⊆ {Ea1 , . . . , Ean },
then it is an abstraction of 1≤i≤n Ea0 i where Ea0 i is a
non-empty subset of Eai .
abstraction-disjoint for a set of arguments a1 , . . . , an iff,
for each ai , 1 ≤ i ≤ n, if ek ∈ Eax is an abstraction of
eu ∈ Eai , then ej ∈ Eax , j 6= k, is not eu ’s abstraction.
abstraction-sound for a set of arguments a1 , . . . , an iff, for
each ai , 1 ≤ i ≤ n, there is no e ∈ Eai that is not abstracted by any e ∈ Eax .
abstraction-complete for a set of arguments a1 , . . . , an
iff, for each e ∈ ax , e is an abstraction of E ⊆
S
1≤m≤n Eam .
Abstraction-covering

[A]

ax

a1

e’1

e1

e2

e’3

e4

e3

Abstraction-disjoint

[B]

ax

a1

e’2

ax

e’1

e1

e’2

e2

e’1

e1

ax

e4

a2 a1

e’2

e2

e’3

e4

e3

a2

Abstraction-complete

[D]

e’3

e3

a2 a1

e’1

e1

e’2

e2

Proposition 4 (Existence) There exists at least one abstraction for every set of arguments.
Proof L2 is a complete lattice.

e’3

e3

As for motivation of the four conditions, our goal for abstraction of a given set A of arguments dictates that, in
whatever manner we may abstract, eventually we abstract
from all expressions of all the arguments in A. Hence
we have abstraction-soundness. However, consider an extreme case where each e0i abstracts from a single argument
a1 . Then, certainly, such abstraction weakens each member of A, but there is no guarantee that the weakening is
a weakening of A, because abstraction of {e1 , . . . , en } is
necessarily abstraction of each of e1 , . . . , en , but abstraction of e1 is not necessarily that of {e1 , . . . , en }. Not abstracting from each and every a1 ∈ A is problematic for
this reason. Abstraction-covering-ness is therefore desired.
Abstraction-disjointness discourages redundancy in abstraction. Abstraction-completeness ensures relevance of abstraction to a given set of arguments to be abstracted. In the
rest, whenever we state au is an abstraction of {a1 , . . . , an },
au will be assumed to be abstraction-covering, abstractiondisjoint, abstraction-sound and abstraction-complete for
them. We say that the abstraction is the best abstraction iff
it is the best abstraction of all expressions associated with
{a1 , . . . , an }.
Proposition 3 If ax is the best abstraction of a set A of arguments, then every abstraction of A is an abstraction of ax .

Abstraction-sound

[C]

{ax is abstraction-covering, ax is abstraction-sound,
ax is abstraction-disjoint, ax is abstraction-complete}.
Then ω materially implies β iff ω = β.

e4

a2

Figure E: Illustration for abstraction-covering-ness [A],
abstraction-disjointness [B], abstraction-soundness [C] and
abstraction-completeness [D].
Figure E illustrates these 4 conditions. ax comes with
{e01 , e02 , e03 }, a1 with {e1 , e2 }, and a2 with {e3 , e4 }. In [A],
ax is abstraction-covering for {a1 , a2 } because e01 ∈ Eax
abstracts from a non-empty subset of both Ea1 and Ea2 . If
e01 should abstract only from a non-empty subset of Ea1 but
not of Ea2 , abstraction-covering-ness would not be satisfied.
In [B], ax satisfies abstraction-disjointness because any expression is abstracted at most by one expression in Eax . If,
here, e01 should abstract both from e1 and e2 , this condition
would fail to hold. In [C], ax satisfies abstraction-soundness
because all expressions in Ea1 ∪ Ea2 are abstracted. If there
should be even one expression in Ea1 ∪ Ea2 that is not abstracted, this condition would fail to hold. In [D], ax satisfies abstraction-completeness because each expression in
Eax abstracts expressions in Ea1 ∪ Ea2 . If there should be
even one expression in Eax that does not abstract any expressions in Ea1 ∪ Ea2 , this condition would fail to hold.
Proposition 2 (Independence)
Let
ω, β
be
one
of
the
propositions



However, some abstraction, including the top element
of L2 if it is in {f (e) ∈ L2 | e ∈ E}, can be so general
that all arguments are abstracted by it. In the first example
in Introduction, “Argumentation is taking place.” could
be such an argument, in which one may not be normally
interested for reasoning about argumentation: the whole
point of argumentation theory is for us to be able to judge
which set(s) of arguments may be acceptable when the
others are unacceptable, so we should not trivialise a given
argumentation by a big summary argument.
Conditions for conservative abstraction Hence, a few
conditions ought to be defined in order to ensure conservative abstraction. Assume an argumentation framework
(Ab , Rb ). We assume that those elements of L2 that are so
abstract that they could abstract all argument-lets in Ab into
a single argument-let are forming a non-empty upper set M
of L2 : M (⊆ L2 ) is an upper set iff, if x ∈ M and x v y,
then y ∈ M . Intuition is that once we find some f (e) in L2
that is so general, then any f (e1 ) such that f (e) v f (e1 ) is
also. For example, if f (focusOnImp) in L2 is so general,
then f (“Argumentation is taking place.”) is also so general.
Let us say that there is a path from an argument a1 to
an argument a2 iff either a1 attacks a2 , or else there is a
path from a1 to some argument a3 which attacks a2 . Let us
say that a set A1 of arguments is strongly connected component in (Ab , Rb ) iff (1) there is a path from any a1 ∈ A1

to any a2 ∈ A1 and (2) there exists no A1 ⊂ Ax ⊂ Ab
such that Ax satisfies (1). For an argumentation framework
(Ab , Rb ), we define that abstraction ax of a set A1 of arguments is: valid iff there exists a strongly connected component As ⊆ Ab such that: (1) A1 ⊆ As ; and (2) there exists
no A1 ⊂ A2 ⊂ As such that ax is an abstraction of A2 (abstraction is over as many members of a strongly connected
component as possible); non-trivial iff α(Eax ) 6∈ M (abstraction cannot be too general); and compatible iff: there
exist no argument-lets (a1 , e1 ), (a2 , e2 ) ∈ A that satisfy
both (1) ((a1 , e1 ), (a2 , e2 )) ∈ Rb and (2) f (e1 ) and f (e2 )
are comparable in v (abstraction cannot be over arguments
that contain an attack from more abstract an argument on
more concrete an argument or vice versa).
What compatibility expresses is: a pair of arguments a1
and a2 with an attack between them is not suited for abstraction if a1 (or a2 ) is more, if not equally, abstract than
a2 (or a1 ). For justification, suppose firstly that a2 is a1 .
Then it is a self-attack. Let us suppose that abstraction of
a1 and a2 is feasible, then we can get rid of all self-attacks
by means of abstraction. But that would render all such selfattacks not playing any role in argumentation, which cannot
be the case (Baumann et al. 2017). In a more general setting
where a2 is not a1 , if it is a1 that attacks a2 , given that a2 is
more concrete an argument of a1 , the attack is again a type
of self-attack. Still, it is not safe to compile away the attack
by taking abstraction of a1 and a2 , because the abstraction
is more, if not equally, abstract than a1 which a2 was attacking. The second condition of validity is motivated in a way
by compatibility.1 Let us consider the example in Introduction again (a part of it is re-listed in Figure F on the left).
There are three arguments in the cycle, and α(Ea1 ), α(Ea2 )

a1
a2

a3
AF

a4

a3

a4

ay

Figure F: Left: an argumentation framework before abstraction. Right: an argumentation framework after a compatible
but invalid abstraction.
and α(Ea3 ) are not comparable in v (Cf. Figure D). The
least upper bound of any two among the three, by the way,
is the same element in L2 . Hence, by taking abstraction of
only two among them, say a1 and a2 , we obtain an abstract
space argumentation framework as in the right figure of Figure F. As the attacks between ay and a3 are both of abstractconcrete and of concrete-abstract, the compatibility condition prevents any further abstraction on this argumentation
framework. This, however, is amiss, because such abstractconcrete (concrete-abstract) relation among the participants
1

We, however, have a more recent result on abstraction of selfattacks. An interested reader can contact either of the authors for
detail.

of the cycle were not present (they were not comparable in
v) in the original argumentation framework. The validity
condition precludes this anomaly.
Proposition 5 (Independence) Let ω, β be one of the
propositions: {ax is valid, ax is non-trivial, ax is
compatible}. ω materially implies β iff ω = β.
These are conditions that apply for abstraction of a given set
of arguments alone. In an argumentation framework, however, we also consider attacks between a set of arguments
and the arguments that are not in the set. We say that abstraction ax of a set A1 of arguments is attack-preserving
iff, for each ab ∈ Ab \A1 and each ab1 ∈ A1 , if at least either
(ab , ab1 ) ∈ Rb or (ab1 , ab ) ∈ Rb , then α(Eax ) and α(Eab1 )
are not comparable in v (abstraction of ax and external attackers/attackees shall not be in abstract-concrete (concreteabstract) relation). For intuition behind this condition, let us
consider Figure G. For simplicity, let us assume that Eai ,
L2
a1
a3

f(e6)
f(e5)

a4

f(e3)

f(e2)

f(e1)

f(e4)

a2

Figure G: Left: an argumentation framework with 4 arguments. Eai is assumed to be a singleton {ei }. Right: abstract
lattice L2 . α(ai ) is assumed to be f (ei ).
1 ≤ i ≤ 4, is a singleton {ei }. The abstract lattice L2 is
shown in Figure G. See to it that the attack of a1 on a4
is not of absolute-concrete (concrete-absolute). Now, with
(the best) abstraction of a1 , a2 and a3 , we obtain a5 with
Ea5 = {e5 }. While, in general, there is no continuity between some argument a1 attacking some argument a4 and
some abstraction ax of a1 attacking a4 , an exception is taken
when there exists some pivotal point in L2 that strongly distinguishes α(Eax ) and α(Ea4 ) = f (e4 ) (which, by the definition of abstraction, means a1 and a4 are equally distinguished), ax to one group, and a4 to another distinct group.
In such a case, as the attack of a1 on a4 can be viewed as
the attack of the group that a1 belongs to on the group that
a4 belongs to, and as a1 and ax belong to the same group,
abstraction of a1 into ax does not modify the attack. This
strong distinction holds just when α(Eax ) and α(Ea4 ) are
not comparable in v. This justifies retention of the attack by
a5 on a4 (the pivot is f (e6 )) in the abstract space argumentation framework.
We say that abstraction ax of a set A1 of arguments is conservative iff it is valid, non-trivial, compatible, and attackpreserving.
Theorem 1 For a given (Ab , Rb ), if an abstraction ax of
A1 ⊆ Ab is conservative, then each abstraction ay of A1
such that ax is an abstraction of ay is conservative.
Proof Suffice it to check the four conditions one by one. 

Computation of abstract space argumentation
frameworks from a concrete space argumentation
framework
Algorithm 1 Computation of the set of abstract space argumentation frameworks for a given concrete space argumentation framework
Require: X is an argumentation framework, X.addSet(Y ) adds
the elements of Y into X, but is assumed to discard duplicates.
1: function D ERIVE A BS(X)
2:
Σ ← an empty set.
3:
. abs.space.arg.framwrks to be added to Σ
4:
Σ.addSet(X)
. Initially only X is in Σ
5:
Γ ← all distinct sets of arguments in X that are strongly
connected.
6:
for all A in Γ do
7:
Σ1 ← Σ
. Copy Σ
8:
Σ ← an empty set.
. Reset
9:
Π ← the set of all maximal subsets of A that satisfy
conservative abstraction.
10:
while Σ1 is not empty do
11:
while Π is not empty do
12:
X1 ← the 1st element of Σ1
13:
A1 ← the 1st element of Π
14:
ax ← the best abstraction of A1
15:
Replace A1 in X1 with ax , while preserving
attacks.
16:
Σ.addSet(X1 )
17:
Remove the 1st element of Π
18:
end while
19:
Remove the 1st element of Σ1
20:
end while
21:
end for
22:
return Σ
23: end function

All abstract space argumentation frameworks with conservative and best abstraction can be computed for a given argumentation framework, E, f , L2 and M ⊆ L2 with Algorithm
1 which, informally, just keeps replacing, where possible at
all, a part of, or an entire, cycle with an abstract argument
for all possibilities. Concerning Line 9, for a set of arguments A1 in a given argumentation framework, we say that
A2 ⊆ A1 is a maximal subset of A1 that satisfies conservative abstraction iff (1) the best abstraction of A2 is conservative and (2) there exists no A3 that satisfy both (2A):
A2 ⊂ A3 ⊂ A1 and (2B): the best abstraction of A3 is conservative.
Proposition 6 (Complexity) Algorithm 1 runs at worst in
exponential time.
Proof. Strongly connected components are known to be
computable in linear time (Line 5). Line 9 is computable at
worst in exponential time. With n argument-lets (with possibly less than n arguments), we can over-estimate that the
for loop executes at most n times, the 1st while loop at most
(n Cdn/2e )n times, and the 2nd while loop at most n Cdn/2e
times.


Preferred sets in concrete and abstract spaces
We now subject preferred sets in concrete space to those
in abstract space for more clues on arguments acceptability in concrete space. Let us denote Algorithm 1 by gα ,
and a function with [inputs = a set of argumentation frameworks] and [output = a set of all preferred sets for each
given argumentation framework] by gp (the procedure can
be found in the literature). Further, let gγ be a projection
function with [inputs = a set of sets of sets of arguments
(i.e. all preferred sets for each argumentation framework)]
and [outputs = a set of sets of sets of arguments], with
the following description. Let σ be a function with [inputs = a set of sets of arguments × arguments] and [outputs = a set of sets of arguments] such that σ(X, A) =
(Ab ,Rb )

{{A1 } | ∃A2 ∈ X.A1 = A2 ∩ A}. Then gγ
(Z) =
{{X1 } | ∃X ∈ Z.X1 = σ(X, Ab )}. For example, if Ab =
(Ab ,Rb )

{a1 , a2 }, then gγ
({{{a1 , a3 }}, {{a4 }, {a2 , a5 }}}) is
{{{a1 }}, {{a2 }}}. Figure H illustrates on one hand
Abstract preferred sets

AFa

gp

Abstraction

Concretisation

g↵

AFc

Pa

g(Ab, Rb)

Concrete preferred sets

gp

Pc

Figure H: Relating abstract and concrete preferred extensions. It is assumed that AFc = (Ab , Rb ).
gp ({AFc }) for an argumentation framework AFc in concrete space, which gives us all preferred sets of AFc ,
(Ab ,Rb )
◦ gp ◦ gα ({AFc }), which
and on the other hand gγ
also gives us a set of all preferred sets in concrete space
but through abstraction. The abstract transformations proceed by transforming the given concrete space argumentation framework into a set of abstract space argumentation
frameworks (gα ({AFc })), deriving preferred sets for them
(gp ◦ gα ({AFc })), and projecting them to concrete space
(Ab ,Rb )

preferred sets (gγ
◦ gp ◦ gα ({AFc })) so that comparisons to the preferred sets obtained directly within concrete space can be done. In particular, we can learn: (1) an
argument deemed credulously/skeptically acceptable within
concrete space is positively approved by abstract space preferred sets, thus we gain more confidence in the set members being acceptable; (2) arguments not deemed acceptable
within concrete space, i.e. those that are not in any preferred set, are negatively approved also by abstract space
preferred sets, thus we gain more confidence in those arguments not acceptable. But also: (3) arguments deemed credulously/skeptically acceptable within concrete space may be
questioned when their acceptability is not inferred from any
abstract space preferred set; and, on the other hand, (4) ar-

guments deemed not acceptable within concrete space may
be credulously/skeptically implied by abstract space preferred set(s). To summarise formally, given an argumentation framework AF : (Ab , Rb ), we say that an argument
that is deemed credulously/skeptically acceptable in concrete space is:
(Ab ,Rb )

+approved iff, for some/every element X of gγ
◦ gp ◦
gα ({AFc }), it belongs to some/every element A of X.
(Ab ,Rb )

questioned iff, for every element X of gγ
◦ gp ◦
gα ({AFc }), it belongs to no element A of X.
And we say that an argument that is deemed not acceptable
in concrete space is:
(Ab ,Rb )

-approved iff, for every element X of gγ
◦ gp ◦
gα ({AFc }), it belongs to no element A of X.
credulously/skeptically implied iff, for some/every ele(Ab ,Rb )
ment X of gγ
◦ gp ◦ gα ({AFc }), it belongs to
some/all member(s) A of X.

Comparisons to Dung preferred semantics and cf2
semantics, and observations
We conclude this section with comparisons to Dung preferred semantics and cf2 semantics (Baroni, Giacomin, and
Guida 2005). Let us first consider AF1 in Figure A and the
lattices as shown in Figure D. Let us denote gγAF ◦ gp ◦ gα by
GAF , then we have: ∅ for gp (AF1 ) (i.e. Dung preferred set);
{{a1 , a5 }, {a2 , a5 }, {a3 , a5 }} for cf2(AF1 ); while {a5 } for
GAF1 (AF1 ) (as we have already shown the only one abstract space argumentation framework, in Figure B, we omit
the derivation process). By comparisons between gp (AF1 )
and GAF1 (AF1 ), we observe that all a1 , a2 , a3 , a4 are approved, while a5 is implied. Hence in this case, with respect to the semantic structure of L2 , we might say that
Dung preferred set behaves more conservative than necessary. On the other hand, by comparisons between cf2(AF1 )
and GAF1 (AF1 ), we observe that cf2(AF1 ) accepts either
of the arguments in the odd cycle, which is more liberal
than necessary with respect to L2 - since no arguments in
AF1 could break the preference pre-order focusOnOs <
focusOnMp < focusOnEc < focusOnOs of the three
arguments. Therefore, for AF1 , Dung semantics seems to
give false-negative to a5 acceptability, while cf2 seems to
give false-positives to either of a1 , a2 , a3 acceptability. If
those acceptability semantics aim to answer “Which arguments should be (credulously) accepted?”, false-negatives
only signal omission, but false-positives signal unintuitive
results and are less desirable.
Let us, however, consider another argumentation framework AF3 in Figure I borrowed from (Baroni, Giacomin,
and Guida 2005). Consider:
a1 The downpour has been relentless since the morning.
a2 It was burning hot today.
a3 All our employees ran a pleasant full marathon today.
a4 Nobody stayed indoor.
a5 Many enjoyed TV shows at home.

a1

AF3
a2

L2

f(HWA)

(a part)

a4

a5

f(NoId)

a3
...

a3

ay

a4

f(MWA)

f(Id)

f(HW)

f(Fm)

f(TV)

f(Dp) f(Bn)

a5

Figure I: Top left: an argumentation framework AF3 .
Bottom-left: AF3 ’s abstraction. Right: an abstract lattice L2 .
We assume the abstract lattice
W as shown in Figure I for
AF3 . We assume M =
L2 , and any nodes below
f (Fm), f (TV), f (Dp), f (Bn) not explicitly shown there
are still assumed to be there. W, A, M, H, Id, Fm, Dp,
Br each abbreviates Weather, Activity, Mild, Hard, Indoor, Full-marathon, Downpour and Burning. The lattice
expresses in particular that a downpour and the burning
sun relate under the hard weather, and the hard weather
and indoor activities such as watching TV shows relate
under hard weather activity (that is, an activity to do
under a hard weather condition), but that hard weather
and mild weather activities do not go together. Also, indoor and no-indoor oppose. Here we have: {{a5 }} for
gp (AF3 ); {{a1 , a4 }, {a1 , a5 }, {a2 , a5 }, {a3 , a4 }, {a3 , a5 }}
for cf2(AF3 ). Meanwhile, for GAF3 (AF3 ), {a1 , a2 } is first
of all the set of a maximal subset of {a1 , a2 , a3 }. It is attackpreserving: α({DP, Br}) = f (HW), which is not comparable with f (NoId) or f (Fm), valid because f (HW) does not
abstract Fm, non-trivial, and compatible. Hence the argumentation framework shown under AF3 in Figure I is the
abstract space argumentation framework with respect to L2 .
Consequently, GAF3 (AF3 ) = {{a3 , a4 }, {a3 , a5 }, {a5 }}.
Therefore, in this example, GAF3 (AF3 ), too, credulously
accepts an argument in the odd-cycle as cf2(AF3 ) does. Notice, however, that we still obtain the Dung conservative preferred set {a5 } which obtains from {ay , a5 }.
It is safe to observe that the traditional Dung, or cf2,
which is more appropriate depends not just on an argument
graph but also the semantic relation among the arguments
in the graph; and that combination of abstract argumentation and abstract interpretation is one viable methodology to
address this problem around cycles in argumentation frameworks.

Related work
As far as we are aware, this is the first study that incorporates abstract interpretation into abstract argumentation theory. Odd-sized cycles have been a popular topic of research
in the literature for some time, as they tend to prevent the
acceptability of all subsequent arguments with respect to directionality. Noting the difference between preferred and the
grounded semantics, Baroni et al. (Baroni, Giacomin, and
Guida 2005) proposed to accept maximal conflict-free subsets of a cycle for gaining more acceptable arguments off
an odd-length cycle, which led to cf1/cf2 semantics. They

are regarded as improvements on more traditional naive semantics (Bondarenko et al. 1997). They also weaken Dung
defence around strongly connected components of an argumentation framework into SCC-recursiveness.
The stage2 semantics that took inspiration from cf2 is
another approach with a similar SCC-recursive aspect, but
which is based on the stage semantics (Verheij 1996) rather
than the naive semantics, the incentive being to maximise
range (the range of a set of arguments is itself plus all arguments it attacks).
The fundamental motivation behind those semantics was
to treat an odd-length cycle in a similar manner to an evenlength cycle. As we showed, however, specialisation of
Dung semantics without regard to semantic relation among
arguments in a given argumentation framework seems not
fully generalisable. To an extent, that any such systematic
resolution of acceptability of cyclic arguments based only on
a Dung argumentation graph is tricky relates to the fact that
attacking arguments in a cycle can be contrarily (Horn 2001)
but not necessarily contradictorily opposing. As the study in
(Baroni, Giacomin, and Liao 2015) shows and as is known
in linguistics, dealing with contrary relations is difficult in
Fregean logic. However, with abstract interpretation, we can
take advantage of semantic information of arguments in partitioning those attacking arguments in a cycle into mutually
incompatible subsets, by which uniform treatment of cycles
come into reach.

Conclusion
We introduced abstract interpretation into argumentation
frameworks. Our formulation shows it is also a powerful methodology in AI reasoning. We believe that more
and more attention will be directed towards semanticargumentgraph hybrid studies within argumentation community, and we hope that our work will provide one fruitful
research direction.

Acknowledgement
We thank Leon van der Torre and Ken Satoh for discussion
on related topics which greatly influeced this work of ours.

References
[Baroni, Giacomin, and Guida 2005] Baroni, P.; Giacomin,
M.; and Guida, G. 2005. SCC-recursiveness: a general
schema for argumentation semantics. Artificial Intelligence
168:162–210.
[Baroni, Giacomin, and Liao 2015] Baroni, P.; Giacomin,
M.; and Liao, B. 2015. Dealing with Generic Contrariness
in Structured Argumentation. In IJCAI, 2727–2733.
[Baumann et al. 2017] Baumann, R.; Dvorák, W.; Linsbichler, T.; and Woltran, S. 2017. A General Notion of Equivalence for Abstract Argumentation. In IJCAI, 800–806.
[Bondarenko et al. 1997] Bondarenko, A.; Dung, P. M.;
Kowalski, R. A.; and Toni, F.
1997.
An abstract,
argumentation-theoretic approach to default reasoning. Artificial intelligence 93(1-2):63–101.

[Caminada 2006] Caminada, M. 2006. On the Issue of Reinstatement in Argumentation. In JELIA, 111–123.
[Cousot and Cousot 1977] Cousot, P., and Cousot, R. 1977.
Abstract interpretation: a unified lattice model for static
analysis of programs by construction or approximation of
fixpoints. In POPL, 238–252.
[Dung 1995] Dung, P. M. 1995. On the Acceptability of Arguments and Its Fundamental Role in Nonmonotonic Reasoning, Logic Programming, and n-Person Games. Artificial
Intelligence 77(2):321–357.
[Horn 2001] Horn, L. R. 2001. A Natural History of Negation. The University Chicago Press., 2nd edition.
[Verheij 1996] Verheij, B. 1996. Two approaches to dialectical argumentation: admissible sets and argumentation
stages. Proc. NAIC 96:357–368.

