=Paper=
{{Paper
|id=None
|storemode=property
|title=Doing Argumentation using Theories in Graph Normal Form
|pdfUrl=https://ceur-ws.org/Vol-954/paper2.pdf
|volume=Vol-954
}}
==Doing Argumentation using Theories in Graph Normal Form==
https://ceur-ws.org/Vol-954/paper2.pdf
Doing Argumentation using Theories in Graph
Normal Form
Sjur Dyrkolbotn
Department of Informatics
University of Bergen, Norway
sjur.dyrkolbotn@ii.uib.no
Abstract. We explore some links between abstract argumentation, logic
and kernels in digraphs. Viewing argumentation frameworks as proposi-
tional theories in graph normal form, we observe that the stable seman-
tics for argumentation can be given equivalently in terms of satisfaction
and logical consequence in classical logic. We go on to show that the
complete semantics can be formulated using Lukasiewicz three-valued
logic.
1 Introduction
Abstract argumentation in the style of Dung [11], has gained much popularity in the
AI-community, see [3] for an overview. Dung introduced argumentation frameworks,
networks of abstract arguments that are not assumed to have any particular internal
structure. All that arguments can do is attack one another, and extension based se-
mantics for argumentation identify sets of arguments that are in some sense successful.
Given a set A of arguments, some requirements are intuitively natural to stipulate. If,
for instance, a, b ∈ A and one of a and b attacks the other, then it seems problem-
atic to accept A as successful - A effectively undermines itself. There are several other
more or less natural constraints one might consider, some of which cannot be mutually
satisfied, and this has given rise to several different semantics for argumentation frame-
works, each able to capture some, but not all, intuitive requirements, see e.g. [2] for an
overview and comparison of various approaches. In this paper we introduce argumenta-
tion theories, a representation of argumentation frameworks as propositional theories
in graph normal form, a novel normal form for theories in propositional logic [4], closely
connected to directed graphs.
In section 2 we give the necessary definitions from argumentation theory and we
observe that stable sets in argumentation frameworks, satisfying assignments to their
representations as theories, and kernels in the directed graphs obtained by reversing
their attacks, are all one and the same. In section 3 we work with the representation
of frameworks as theories, showing that the definition of a complete extension can be
given equivalently in terms of satisfaction in Lukasiewicz three-valued logic L3.
2 Preliminaries
An argumentation framework, framework for short, is a finite digraph, F = hA, Ri, with
A a set of vertices, called arguments, and R ⊆ A × A a set of directed edges, called
R.K. Rendsvig and S. Katrenko (Eds.): ESSLLI 2012 Student Session Proceedings, CEUR Work-
shop Proceedings vol.: see http://ceur-ws.org/, 2012, pp. 13–22.
14 Sjur Dyrkolbotn
the attack relation. For ha, a′ i ∈ R we say that the argument a attacks the argument
a′ . We use the notation R+ (x) = {y | hx, yi ∈ R} Sand R− (y) = {x | hx, yi ∈ R}. This
notation extends point-wise to sets, e.g. R (X) = x∈X R− (x). We use the convention
−
that R+ (∅) = R− (∅) = ∅.
The most well-known semantics for argumentation, first introduced in [11] and [6]
(semi-stable semantics), are given in the following definition.
Definition 21 Given any argumentation framework F = hA, Ri and a subset A ⊆ A,
we define D(A) = {x ∈ A | R− (x) ⊆ R+ (A)}, the set of vertices defended by A. We
say that
– A is conflict-free if R+ (A) ⊆ A \ A, i.e. if there are no two arguments in A that
attack each other.
– A is admissible if it is conflict free and A ⊆ D(A). The set of all admissible sets
in F is denoted a(F).
– A is complete if it is conflict free and A = D(A). The set of all complete sets in F
is denoted c(F).
– A is the grounded set if it is complete and there is no complete set B ⊆ A such
that B ⊂ A, it is denoted g(F).
– A is preferred if it is admissible and not strictly contained in any admissible set.
The set of all preferred sets in F is denoted p(F).
– A is stable if R+ (A) = A \ A. The set of all stable sets in F is denoted s(F)
– A is semi-stable if it is admissible and there is no admissible set B such that
A ∪ R+ (A) ⊂ B ∪ R+ (B). The set of all semi-stable sets in F is denoted by ss(F).
For any S ∈ {a, c, g, p, s, ss}, one also says that A ∈ S(F) is an extension (of the type
prescribed by S). Given a framework F and an argument a ∈ A, we say that a is credu-
lously accepted with respect to some S ∈ {a, c, g, p, s, ss} just in case there is some set
A ∈ S(F) such that a ∈ A. If a ∈ A for every A ∈ S(F), we say that A is skeptically ac-
cepted with respect to S. If an argument is neither credulously nor skeptically accepted
with respect to a semantics, it is rejected.1 Intuitively, if an argument is credulously
accepted, then it is involved in some line of argument that is successful; it is potentially
useful, and should be considered further. If an argument is skeptically accepted, it is
involved in all successful lines of arguments; it is beyond reproach, and arguing against
it should be considered useless.
Notice that it follows from Definition 21 that the empty set is admissible and that
all stable sets are semi-stable, all semi-stable sets are preferred, all preferred sets are
complete and all complete sets are admissible. Also, it is not hard to see that the
grounded extension is contained in every complete set of arguments. In Figure 1, we
give two argumentation frameworks, F and F′ , that serve as examples. In the framework
F, every argument is attacked by some argument, and from this it follows that we have
g(F) = ∅, i.e., the grounded extension is the empty set. The non-empty conflict-free
sets are the singletons {a}, {b} and {c}, but we observe that a does not defend himself
against the attack he receives from c (since there is no attack (a, c)), and that c does
not defend himself against the attack he receives from b. So the only possible non-
empty admissible set is {b}. It is indeed admissible; b is attacked only by a and he
defends himself, attacking a in return. In fact, since b also attacks c, the set {b} is
the unique stable set of this framework. It follows that s(F) = p(F) = ss(F) = {{b}}
1
Arguments that are credulously but not skeptically accepted are typically called
defensible
Doing Argumentation using Theories in Graph Normal Form 15
F: F′ :
w
a_ 7b :jo bo a @ hO d iO d
w #
c c 6d /e /f v 7g
Q
Fig. 1. Two argumentation frameworks
and a(F) = c(F) = {∅, {b}}. For a more subtle example, consider F′ . The first thing to
notice here is that we have an unattacked argument a, so the grounded extension is
non-empty. In fact, the framework is such that all semantics from Definition 21 behave
differently. It might look a bit unruly, but there are many self-attacking arguments that
can be ruled out immediately (since they are not in any conflict-free sets), and it is
easy to verify that the extensions of F′ under the different semantics are the following:
g(F′ ) = {a}, s(F′ ) = ∅, ss(F′ ) = {{a, d, g}}
a(F′ ) = {∅, {a}, {a, c}, {a, c, e}, {d}, {a, d}, {a, d, g}, {d, g}}
p(F′ ) = {{a, d, g}, {a, c, e}}, c(F′ ) = {{a}, {a, d, g}, {a, c, e}, {a, d}}
Notice that s(F′ ) = ∅ - no stable set exists in the framework. That stable sets
are not guaranteed to exist is a major objection against what is otherwise a fairly
conclusive notion of success - an internally consistent set of arguments that defeats
all others. Other semantics for argumentation can - to quite some extent - be seen
as attempts at arriving at a reasonable notion of success that is weak enough so that
interesting extensions always exists, while still strong enough so that it is adequate
for applications and have interesting theoretical properties. As we will see later, this is
intimately related to the problem of inconsistency handling in logic, with stable sets
not existing in a framework precisely when the corresponding propositional theory is
not classically consistent.
Argumentation has close links to established concepts in both graph theory and
logic. We start by briefly accounting for the link with what is known as kernels in
the theory of directed graphs. Given a directed graph (digraph) D = hD, N i with
N ⊆ D × D, a set K ⊆ D is a kernel in D if
N − (K) = D \ K
Kernels were introduced by Von Neumann and Morgenstern in [18] in the context of
cooperative games, but have since attracted quite a bit of interest from graph-theorists,
see [5] for a recent overview. The connection to argumentation should be apparent. If
←
−
we let D denote the digraph obtained by reversing all edges in D, then it is not hard
←
−
to see that a kernel in D is a stable set in D and vice versa. In kernel theory, one also
considers local kernels [17], which are sets L ⊆ D such that
N + (L) ⊆ N − (L) ⊆ D \ L
←
−
It is easy to verify that a local kernel in D is an admissible set in D and vice versa.
These two observations seem valuable to argumentation, since in graph theory, several
interesting results and techniques have been found, especially concerning the question
16 Sjur Dyrkolbotn
of finding structural conditions that ensure the existence of kernels, see e.g. [9, 10,
15]. Still, as far as we are aware, the connection to argumentation has never been
systematically explored.2
In this paper, we will describe some connections between argumentation and logic,
and we will not explore the link with kernels any further. What is important for us,
is that digraphs inspire a normal form for propositional theories where an assignment
is satisfying iff it gives rise to a kernel in the corresponding digraph, see [4, 19] for
two recent papers that explore this link. We remark that the observation we make
here is in some sense implicit already in the original paper by Dung [11], who connects
argumentation to logic programming. Still, the direct representation of argumentation
frameworks as propositional theories is more straightforward and also seems useful,
as suggested by the results we obtain in Section 3, and the fact that they can be
established so easily. V
A propositional formula, φ, is said to be in graph normal form iff φ = x ↔ y∈X ¬y
for propositional letters {x} ∪ X. In [4] it is shown that this is indeed a normal form for
propositional logic, every propositional theory has an equisatisfiable one containing only
formulas of this form.3 The correspondence with digraphs is detailed in [4, 19]. Instead
of reversing edges in order to connect it to argumentation, we give our own formulation
that can be applied directly. Given a framework F, we define the argumentation theory
TF as follows: ^
TF = {x ↔ ¬y | x ∈ A} (1)
y∈R− (x)
For instance, the argumentation theory for the framework F depicted in Figure 1,
consists of the following equivalences:
a ↔ ¬b ∧ ¬c, b ↔ ¬a, c ↔ ¬b
We observe that the only satisfying assignment in classical logic is δ : A → {0, 1}
such that δ(a) = δ(c) = 0 and δ(b) = 1, corresponding to the fact that the only
successful line of argument under stable semantics is the set containing the argument
b, defeating a and c.
Argumentation theories are written using graph normal form, and we can also
move in the opposite direction. The construction seems to be of independent interest,
so we will present it here. It provides, in particular, a simple way in which results
and techniques from argumentation can be applied to logic. Solving SAT, for instance,
becomes the search for a stable set, while the other semantics for argumentation could
provide new and useful ways in which to extract information from inconsistent theories.
ForVa positive natural number
V n, let [n] = {1, . . . , n}. Then, for any theory, T =
{x1 ↔ x∈X1 ¬x, . . . , xn ↔ x∈Xn ¬x}, we define an argumentation framework FT =
hFT , RT i as follows
S
AT = i∈[n] ({xi } ∪ Xi ∪ {x̄ | x ∈ Xi ∧ ∀i ∈ [n] : x 6= xi })
S (2)
RT = ( i∈[n] {(x, xi ) | x ∈ Xi }) ∪ {(x, x̄), (x̄, x) | x ∈ AT }
2
The connection has been noted, for instance in [8], where the authors remark that
some of their results concerning symmetric argumentation frameworks (all attacks are
mutual) follow from basic results in kernel theory.
3
Equisatisfiable means that for every satisfying assignment to one there is a satis-
fying assignment to the other, i.e., the assignments are not necessarily the same (the
addition of new propositional letters must be permitted)
Doing Argumentation using Theories in Graph Normal Form 17
We introduce a fresh argument x̄ for every propositional letter x that does not occur
to the left of any equivalence. The reason is that we do not want to force acceptance
of x when viewed as an argument. Rather, x should be open for both acceptance and
rejection, depending on the rest of the theory. This is achieved by adding the symmetric
attack {(x, x̄), (x̄, x)}.
Let I = {x̄ | x ∈ A} denote all the arguments from FT that do not correspond
to propositional letters used in T. Given a function α : X → Y , let α|Z denote its
restriction to domain Z ⊆ X. Also, given δ : X → {0, 1}, we let δ̄ denote the boolean
evaluation of formulas induced by δ according to classical logic.
Given a stable set E ⊆ FT , consider δE : A → {0, 1} defined by δE (x) = 1 iff
x ∈ E (meaning that δE (x) = 0 for all x ∈ AT \ E). It is not hard to show that
δE |AT \I is a satisfying assignment for T in classical logic, i.e., that δ̄E (φ) = 1 for all
φ ∈ T . Similarly, if we are given a satisfying assignment δ : AT \ I → {0, 1}, we obtain
the stable set Eδ = {x ∈ AT | δ(x) = 1} ∪ {x̄ ∈ I | δ(x) = 0}.
The constructions given in this section are completely analogous to the ones given
in [4] in order to establish equivalence between theories in graph normal form and
kernels in digraphs. Therefore, we will simply summarize, without a formal proof, one
obvious consequence for argumentation. We let |= denote the satisfaction relation in
classical propositional logic, and we let ⊥ denote contradiction in classical logic.
Theorem 24 Given an argumentation framework F, and an argument a ∈ A
(1) F admits a stable extension iff TF 6|= ⊥ (i.e. iff TF is satisfiable)
(2) a ∈ A is credulously accepted with respect to stable semantics iff {a} ∪ TF 6|= ⊥
(3) a ∈ A is skeptically accepted with respect to stable semantics iff TF |= a
When we succeed in giving semantics for argumentation in terms of logical con-
sequence and consistency, we no longer need to consider just atomic arguments and
statements about them specified in some informal or semi-formal way. Rather, one can
now use logic, and form a propositional formula which can then be evaluated against
the theory corresponding to the framework. For instance, given a framework F with
a ∈ A, we have that a is not credulously accepted with respect to stable semantics iff
TF is a model of ¬a, i.e., iff we have TF |= ¬a. For another example, consider how
one may write simply a → b to indicate that every successful line of argument which
involves accepting a must also involve accepting b. More generally, when we succeed
in providing a formulation in terms of a known logic, we can use reasoning systems
developed for this logic both to address standard notions from argumentation such
as credulous and skeptical acceptance, and also to check how arbitrary propositional
formulas fare with respect to an argumentation theory; formulas that can now be seen
as statements about interaction among arguments in the underlying argumentation
framework. Conversely, we may use techniques developed in argumentation theory to
analyze logical theories in graph normal form - something that might prove partic-
ularly useful for algorithmic problems, since the digraph structure of argumentation
frameworks should prove particularly useful in this regard. We remark that interesting
results have already been obtained which exploits digraph-properties for tackling al-
gorithmic problems concerning the semantic properties of argumentation frameworks,
see e.g., [12, 13].
It seems, in light of this, that the search for nice logical accounts of argumentation
is a highly worthwhile direction of research. In fact, it has recently been taken up by
logicians coming at argumentation from a more theoretical, less application-oriented,
18 Sjur Dyrkolbotn
angle, see e.g., [7, 16]. Conceptually, we differ from these approaches in that we rely on
the link with known concepts in digraph theory and the representation of frameworks
as propositional theories, rather than on the use of modal logic.
3 Argumentation and Lukasiewicz logic L3
In this section we will characterize the complete extensions logically. This necessitates
a move away from classical logic. In Caminada and Gabbay [7], a characterization is
provided using modal logic and a complicated modal version of Equation 1. In this
section we show that complete extensions can be characterized much more simply
using Lukasiewicz three valued logic L3. This observation is also made in [14], but
there it is formalized only with respect to local kernels and a new logic for reasoning
about paradoxes. The details and consequences are not worked out in the context of
argumentation.
Here, we directly link L3 to argumentation by showing that any satisfying assign-
ment to TF gives rise to a complete extension in F and vice versa. The argument we
give proceeds by showing that an assignment is satisfying iff it is what is known in
argumentation theory as a complete Caminada labeling. While not technically chal-
lenging, this result seems nice, since it implies that skeptical and credulous acceptance
of arguments with respect to the complete semantics reduces to logical consequence and
satisfiability in L3. We remark, in particular, that Lukasiewicz three-valued logic ad-
mits a nice proof theory, see e.g., [1]. We also remark that since the grounded extension
is complete and also contained in every complete extension, characterizing skeptical ac-
ceptance with respect to complete semantics amounts to completely characterizing the
grounded extension.
Given a propositional language over connectives {¬, ∧, →} and propositional al-
phabet A, the semantics of logic L3 is defined as follows.
Definition 31 Given an assignment δ : A → {0, 1/2, 1} its extension, δ̄, is defined
inductively on complexity of formulas.
– δ̄(a) = δ(a) for all a ∈ A
– δ̄(¬φ) = 1 − δ̄(φ)
– δ̄(φ → ψ) = min{1, (1 − ᾱ(φ)) + ᾱ(φ)}
– δ̄(φ ∧ ψ) = min{ᾱ(φ), ᾱ(ψ)}
The consequence relation of Lukasiewicz logic is |=L ⊆ 2L × L, defined such that
Φ |=L φ iff for all δ : A → {0, 1/2, 1}, we have that δ̄(φ) = 1 whenever δ̄(ψ) = 1 for all
ψ ∈ Φ,
Notice that φ → ψ obtains semantic value 1 (”true”) under some assignment just
in case ψ does not receive a lower semantic value than φ. Defining φ ↔ ψ = (φ →
ψ) ∧ (ψ → φ) as usual, one also notices that φ ↔ ψ obtains the value 1 just in case φ
and ψ obtain the same semantic value.
Next we define the complete Caminada labellings, not using the original definition,
but the equivalence stated and proven in [7, Proposition 1, p. 6-7]
Definition 32 A function δ : A → {0, 1/2, 1} is a complete Caminada labeling iff for
all x ∈ A we have:
– If δ(x) = 1 then for all y ∈ R− (x) : δ(y) = 0
Doing Argumentation using Theories in Graph Normal Form 19
– If δ(x) = 0 then there is y ∈ R− (x) : δ(y) = 1
– If δ(x) = 1/2 then there is y ∈ R− (x) such that δ(y) = 1/2 and there is no
z ∈ R− (x) such that δ(z) = 1
In [7, Theorem 2], the authors prove that if δ : A → {0, 1/2, 1} is a complete
Caminada labeling then δ 1 = {x ∈ A | δ(x) = 1} is a complete extension for F. They
also show that if E ⊆ A is a complete extension, then there is a corresponding complete
Caminada labeling δE : A → {0, 1/2, 1}, defined as follows:
– δE (x) = 1 for all x ∈ E
– δE (x) = 0 for all x ∈ R+ (E)
– δE (x) = 1/2 for all x ∈ A \ (E ∪ R+ (E))
In the following, we prove that a complete Caminada labeling can be equivalently
defined as a satisfying assignment for TF in the logic L3. This shows that the results
from [7] have direct logical content, and that we do not need to introduce modal logic
to characterize complete extensions logically.
Theorem 33 Given an argumentation framework F, we have that δ : A → {0, 1/2, 1}
is a complete Caminada labeling iff δ̄(φ) = 1 for all φ ∈ TF.
Proof. ⇒) Assume that δ : A → V {0, 1/2, 1} is a complete Caminada labeling and
consider an arbitrary φ = x ↔ y∈R− (x) ¬y ∈ TF. We need to show that δ̄(x ↔
V
y∈R− (x) ¬y) = 1. There are three cases:
– δ(x) = 1. Since δ is a complete Caminada labeling we have, for all y ∈ R− (x),
that δ̄(¬y) = 1 for all y ∈ R− (x). Since all conjuncts are true,
δ(y) = 0. It follows V
we conclude that δ̄( y∈R− (x) ¬y) = 1 = δ(x) = δ̄(x). So δ̄(φ) = 1 as desired.
– δ(x) = 0. Since δ is a complete Caminada labeling it follows that V there is some
y ∈ R− (x) such that δ(y) = 1. Then δ̄(¬y) = 0, so it follows that δ̄( y∈R− (x) ¬y) =
0 = δ(x) = δ̄(x). So δ̄(φ) = 1 as desired.
– δ(x) = 1/2. Since δ is a complete Caminada labeling, there is some y ∈ R− (x)
such that δ(y) = 1/2. It also follows that there is no z ∈ R− (x) such that
−
V = 1. From this we conclude that 1/2 = min{δ̄(y) | y ∈ R (x)} which means
δ(z)
δ̄( y∈R− (x) ¬y) = 1/2 = δ(x) = δ̄(x). So δ̄(φ) = 1 as desired.
⇐) Assume that δ : A → {0, 1/2, 1} is a satisfying
V assignment for TF, i.e. that δ̄(φ) = 1
for all φ ∈ TF. Consider arbitrary φ = x ↔ y∈R− (x) ¬y ∈ TF. Again there are three
cases:
V
– δ(x) = 1. Since δ̄(φ) = 1, we have δ̄( y∈R− (x) ¬y) = 1. It follows that δ̄(¬y) = 1
and therefore δ(y) = 0 for all y ∈ R− (x). So the criterion of Definition 32 is met
in this case. V
– δ(x) = 0. Since δ̄(φ) = 1, we have δ̄( y∈R− (x) ¬y) = 0. It follows that δ̄(¬y) = 0,
and therefore δ(y) = 1 for some y ∈ R− (x).VSo the criterion of Definition 32 is met.
– δ(x) = 1/2. Since δ̄(φ) = 1, we have δ̄( y∈R− (x) ¬y) = 1/2. This means that
1/2 = min{δ̄(¬y) | y ∈ R− (x)}. So there must be some y ∈ R− (x) such that
δ̄(¬y) = 1/2, which means δ(y) = 1/2. Also, it follows that there is no z ∈ R− (x)
such that δ̄(¬z) = 0. So there is no z ∈ R− (x) such that δ(z) = 1, meaning that
the criterion of Definition 32 is met in this case as well.
20 Sjur Dyrkolbotn
✷
We conclude by stating the following corollary, which sums up the immediate conse-
quences for argumentation. We let ⊥ denote contradiction in L3.
Corollary 34 Given an argumentation framework F. An argument a ∈ A is skeptically
accepted with respect to complete semantics iff TF |=L a and credulously accepted iff
TF ∪ {a} 6|=L ⊥.
Proof. For the first claim, remember that a ∈ A is said to be skeptically accepted
with respect to complete semantics iff for all complete extensions E ⊆ A we have a ∈ E
iff δ(a) = 1 for all complete Caminada labellings δ : A → {0, 1/2, 1}. By Theorem 33
this is the same as saying that δ(a) = 1 for all δ such that δ̄(φ) = 1 for all φ ∈ TF. By
Definition 31, this is the same as TF |=L a. The second claim follows similarly. ✷
As already noted, the logical approach means that we can form complex statements
to express various claims about arguments and their interaction in the framework. For
the case of complete semantics, we may write, for instance, a ↔ ¬a to indicate that
the argument a can be neither defeated nor accepted. It is not hard to see that this
formula is true in a model TF iff neither a nor any of its attackers is credulously
accepted with respect to the complete semantics. So it does capture the intended
meaning, and we believe that the formula is a beautiful representation of an argument
having malfunctioned, becoming instead a paradox: an argument such that accepting
it is logically equivalent with defeating it!
Using a logical language to talk about argumentation provides clarity, but also
sheds light on subtleties that we might not otherwise come to fully appreciate. As
an example, consider again the framework F′ from Figure 1. With some thought, we
see that in order for both h and i to be defeated, it is necessary to use d to defeat
h (since using e will defeat g - the only attacker of i except i itself). But if we try
the formula (¬h ∧ ¬i) → d and check if it follows logically from TF′ in L3, we find
that it does not. The explanation for this is that implication in L3 treats an argument
that is neither accepted nor defeated as closer to truth than an argument that is
defeated. Since there is a complete set ({a,c,e}) such that d is defeated while i is neither
accepted nor defeated, it follows from this that a countermodel to the implication can
be found. Still, it is possible to express a claim that correctly describes the state of
affairs that obtains. In fact, after some thought, it is seen that the claim we stated
informally - that you must accept d to defeat both h and i - while true, actually serves
to misrepresent the situation at hand. For what we actually have is something stronger,
namely that in order for h and i to obtain any of the two classical values (true/false
or, if you like, defeated/accepted), we have to accept d. This we can express by the
implication (¬(h ↔ ¬h) ∧ ¬(i ↔ ¬i)) → d, and now we observe that this implication
does indeed follow logically from TF′ . Also, we obtain the further logical consequence
(¬(h ↔ ¬h) ∧ ¬(i ↔ ¬i)) → (¬h ∧ ¬i) which is also stronger than the original intuition
that we had. Thus, what seemed at first sight a shortcoming of the logical approach
really suggested a more precise analysis of the situation, one that we might not as
easily have arrived at without a logical formulation.
Doing Argumentation using Theories in Graph Normal Form 21
4 Conclusion
In this paper we have observed how argumentation frameworks can be viewed as propo-
sitional theories in graph normal form. We have shown that this makes it possible to
capture the stable and complete semantics using classical and three-valued Lukasiewicz
logic respectively. Moreover, we have argued that argumentation theories provide a
nice way in which to talk about argumentation in a logical language. It is much more
straightforward than the modal approach from [7], and exploring it further seems worth-
while. For a possible first step in future work, we remark that both the preferred and
semi-stable sets seem to involve notions of maximal consistency that it should be pos-
sible, and interesting, to express in terms of logic.
References
1. Arnon Avron. Natural 3Valued Logics - Characterization and Proof Theory. Jour-
nal of Symbolic Logic, 56:276–294, 1991.
2. Pietro Baroni and Massimiliano Giacomin. On principle-based evaluation of
extension-based argumentation semantics. Artificial Intelligence, 171(10–15):675–
700, 2007.
3. T.J.M. Bench-Capon and Paul E. Dunne. Argumentation in artificial intelligence.
Artificial Intelligence, 171(10–15):619–641, 2007.
4. Marc Bezem, Clemens Grabmayer, and Michal Walicki. Expressive power of di-
graph solvability. Annals of Pure and Applied Logic, 2011. [to appear].
5. Endre Boros and Vladimir Gurvich. Perfect graphs, kernels and cooperative games.
Discrete Mathematics, 306:2336–2354, 2006.
6. Martin Caminada. Semi-stable semantics. In Proceedings of the 2006 conference on
Computational Models of Argument: Proceedings of COMMA 2006, pages 121–130.
IOS Press, 2006.
7. Martin W. A. Caminada and Dov M. Gabbay. A logical account of formal argu-
mentation. Studia Logica, 93(2-3):109–145, 2009.
8. Sylvie Coste-marquis, Caroline Devred, and Pierre Marquis. Symmetric argumen-
tation frameworks. In Proc. 8th European Conf. on Symbolic and Quantitative
Approaches to Reasoning With Uncertainty (ECSQARU), volume 3571 of LNAI,
pages 317–328. Springer-Verlag, 2005.
9. Pierre Duchet. Graphes noyau-parfaits, II. Annals of Discrete Mathematics, 9:93–
101, 1980.
10. Pierre Duchet and Henry Meyniel. Une généralisation du théorème de Richard-
son sur l’existence de noyaux dans les graphes orientés. Discrete Mathematics,
43(1):21–27, 1983.
11. Phan Minh Dung. On the acceptability of arguments and its fundamental role
in nonmonotonic reasoning, logic programming and n-person games. Artificial
Intelligence, 77:321–357, 1995.
12. Paul E. Dunne. Computational properties of argument systems satisfying graph-
theoretic constraints. Artif. Intell., 171(10-15):701–729, 2007.
13. Wolfgang Dvorák, Reinhard Pichler, and Stefan Woltran. Towards fixed-parameter
tractable algorithms for abstract argumentation. Artif. Intell., 186:1–37, 2012.
14. Sjur Dyrkolbotn and Michal Walicki. Propositional discourse logic. (submitted),
2011. www.ii.uib.no/ michal/graph-paradox.pdf.
15. Hortensia Galeana-Sánchez and Victor Neumann-Lara. On kernels and semikernels
of digraphs. Discrete Mathematics, 48(1):67–76, 1984.
22 Sjur Dyrkolbotn
16. Davide Grossi. On the logic of argumentation theory. In Proceedings of the 9th
International Conference on Autonomous Agents and Multiagent Systems: volume
1 - Volume 1, AAMAS ’10, pages 409–416, Richland, SC, 2010. International Foun-
dation for Autonomous Agents and Multiagent Systems.
17. Victor Neumann-Lara. Seminúcleos de una digráfica. Technical report, Anales del
Instituto de Matemáticas II, Universidad Nacional Autónoma México, 1971.
18. John von Neumann and Oscar Morgenstern. Theory of Games and Economic
Behavior. Princeton University Press, 1944 (1947).
19. Michal Walicki and Sjur Dyrkolbotn. Finding kernels or solving SAT. Journal of
Discrete Algorithms, 10:146–164, 2012.