Vol-3197/paper9
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3197/paper9 |
| wikidataid | Q117341796→Q117341796 |
| title | Argumentation Frameworks Induced by Assumption-Based Argumentation: Relating Size and Complexity |
| pdfUrl | https://ceur-ws.org/Vol-3197/paper9.pdf |
| dblpUrl | https://dblp.org/rec/conf/nmr/Rapberger0W22 |
| volume | Vol-3197→Vol-3197 |
| session | → |
Argumentation Frameworks Induced by Assumption-Based Argumentation: Relating Size and Complexity
Argumentation Frameworks Induced by
Assumption-Based Argumentation: Relating Size and
Complexity
Anna Rapberger1 , Markus Ulbricht2 and Johannes P. Wallner3
1
TU Wien, Institute of Logic and Computation
2
Leipzig University, Department of Computer Science
3
Graz University of Technology, Institute of Software Technology
Abstract
A key ingredient of computational argumentation in AI is the generation of arguments in favor or against claims under scrutiny.
In this paper we look at the complexity of the argument generation procedure in the prominent structured formalism of
assumption-based argumentation (ABA). We show several results connecting expressivity of ABA fragments and number
of constructed arguments. First, for several NP-hard fragments of ABA, the number of generated arguments is not bounded
polynomially. Even under equivalent rewritings of the given ABA framework there are situations where one cannot avoid an
exponential blow-up. We establish a weaker notion of equivalence under which this blow-up can be avoided. As a general tool
for analyzing ABA frameworks and resulting arguments and their conflicts, we extend results regarding dependency graphs of
ABA frameworks, from which one can infer structural properties on the induced attacks among arguments.
1. Introduction assess the instantiated AF. Thus, many typical research
questions can be answered out of the box after converting
Computational models of argumentation are a central ap- the knowledge base. Moreover, since AFs are directed
proach within non-monotonic reasoning [1] with a variety graphs, they are accessible and user-friendly; much infor-
of applications [2] in, e.g., legal or medical reasoning. mation encoded in the knowledge base is made explicit
Key to many approaches to computational argumentation and clear within the graphical framework.
are formalisms in what is called structured argumenta- Let us consider the following situation. Suppose we
tion which specify formal argumentative workflows, with plan to model the behavior of the propositional CNF-
assumption-based argumentation (ABA) [3], ASPIC+ [4], formula 𝜑 = (𝑥1 ∨ ¬𝑥2 ) ∧ (¬𝑥1 ∨ 𝑥2 ) via an ABA
defeasible logic programming (DeLP) [5], and deduc- knowledge base (see Section 2 for a formal introduction
tive argumentation [6] among the prominent approaches to ABA). For this, we identify 𝜑 with the set {𝐶1 , 𝐶2 }
in the field. Reasoning within these formalisms is of- of clauses 𝐶1 = {𝑥1 , ¬𝑥2 } and 𝐶2 = {¬𝑥1 , 𝑥2 }. A
tentimes carried out by instantiating argument structures natural representation would make use of assumptions
and conflicts among these arguments from (rule-based) corresponding to the four occurring literals, i.e. 𝒜 =
knowledge bases in a principled manner. The resulting {𝑥1 , 𝑥2 , 𝑥′1 , 𝑥′2 }. Then, rules model satisfaction of the
arguments and (directed) conflicts are referred to as ar- given clauses; we construct
gumentation frameworks (AFs) [7]. Argumentation se-
𝑟 1 = 𝐶 1 ← 𝑥1 . 𝑟3 = 𝐶2 ← 𝑥′1 .
mantics define argumentative acceptability on an AF s.t.
conclusions can be drawn for the original knowledge base. 𝑟2 = 𝐶1 ← 𝑥′2 . 𝑟4 = 𝐶2 ← 𝑥2 .
In the present paper, we will focus on ABA [8] which with the intuitive meaning that e.g. 𝐶1 can be derived if 𝑟1
is well studied and has applications in, e.g., decision mak- or 𝑟2 is applicable which in turn is the case if the assump-
ing [9, 10, 11]. Argumentative reasoning can be carried tion 𝑥1 or the assumption ¬𝑥2 is set to true, respectively.
out by instantiating arguments as derivations in the given Lastly, the rule “𝑟5 = 𝜑 ← 𝐶1 , 𝐶2 .” models that 𝜑 can
rule base and attacks between arguments based on con- be derived if both 𝐶1 and 𝐶2 can. When constructing
traries among the derivations. the argumentation framework corresponding to this ABA
Constructing an AF corresponding to a given knowl- knowledge base, we would make the conditions under
edge base has several advantages. From a technical point which 𝜑 can be derived (i.e. what satisfying assignments
of view, there is an abundance of research concerned with to the formula exist) visible; indeed, among others, the
AFs (see [1] for an overview) which can be applied to following arguments would be obtained:
𝜑 𝜑 𝜑 𝜑
NMR 2022: 20th InternationalWorkshop on Non-Monotonic Reason-
ing, August 07–09, 2022, Haifa, Israel 𝐴1 : 𝑐1 𝑐2 𝐴3 : 𝑐1 𝑐2 𝐴2 : 𝑐1 𝑐2 𝐴4 : 𝑐1 𝑐2
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org) 𝑥1 𝑥′1 𝑥′2 𝑥′1 𝑥1 𝑥2 𝑥′2 𝑥2
92
�We can now directly read off that e.g. {𝑥1 , 𝑥2 } (see 𝐴3 ) on ABA via using AFs, both the size of the resulting
constitutes a satisfying assignment to 𝜑 since both 𝐶1 and AF and complexity of the resulting AF can pose barri-
𝐶2 (and thus 𝜑) can be derived. We can also see that ers to (automated) argumentative reasoning. On the one
{𝑥1 , 𝑥′1 } would in principle infer 𝜑 as well, but this set hand size and complexity of AFs are direct challenges
of literals does not correspond to a well-defined (partial) for solvers [15, 16]. On the other hand, a large number
assignment; we can not set 𝑥1 to true and false simultane- of arguments in an AF can be a barrier to methods sup-
ously. We thus see that constructing the arguments helps porting argumentative explanations on the AF, due to the
visualizing the information encoded in the knowledge sheer number of arguments. Therefore, investigating for-
base and makes certain relations explicit. Indeed, sim- mal foundations which provide guidance how to encode
ply inspecting all arguments deriving 𝜑 suffices to decide information, depending on the intended behavior of the
whether there is a satisfying assignment to our formula. induced AF, is a worthwhile endeavor.
However, since checking satisfiability of a given CNF- The main contributions of the paper can be summarized
formula is the prototypical NP-complete problem, we as follows.
expect that this procedure must come with computational
cost elsewhere. Indeed, many structured argumentation • We first deal with the case of infinite instantiated
formalisms (including ABA) suffer from the drawback AFs and show that one can restrict attention to
that the knowledge base gives rise to exponentially many finite cores.
(or even an infinite amount of) arguments [12, 13, 14]. So, • We relate bounds on the given ABA instance to (i)
in a nutshell, the instantiated AF makes information within size bounds and computability of the constructed
the knowledge base explicit, but requires many arguments AF and (ii) complexity of reasoning.
to do so. This gives rise to the following question: • We show that each ABA framework can be rewrit-
ten in a way that reasoning in the induced AF is
Is the argumentation framework induced tractable, while credulous acceptance of a target
by an ABA knowledge base large in size, conclusion is preserved.
but reasoning is easy?
• We present, for a fairly large class of ABA frame-
Although this idea is appealing in principle, the answer works, a general transformation procedure to ob-
turns out to be negative in general: Even if we reduce our tain a translated ABA framework which is equiva-
attention to the class of AFs induced by ABA knowledge lent under projection and has a polynomial-sized
bases, reasoning is still intractable in general. Nonethe- AF. We present an impossibility result suggesting
less, we expect an underlying trade-off between size and that the notion of equivalence cannot be strength-
complexity which is worth to be investigated. As a high ened to full equivalence.
level observation we expect an ideal ABA knowledge base • We extend the notion of dependency graphs on
to ABA frameworks (see, e.g., Craven and Toni,
2016) to a general tool for investigating ABA
• induce a large AF, but with reasoning being simple, frameworks able to check structural properties
or inducing milder complexity, such as acyclic or
• a concise AF, in which reasoning is potentially odd-cycle free AFs.
hard.
If the former is the case, then the instantiation proce- 2. Assumption-based
dure can help displaying relationships encoded within the
knowledge base, as it was the case for our CNF formula Argumentation
𝜑 from above. If on the other hand the latter case occurs,
We recall preliminaries for assumption-based argumen-
then the constructed AF is efficient and easy to capture
tation (ABA) [8, 3] and argumentation frameworks
visibly. In this paper, we will investigate this trade-off
(AFs) [7].
and examine the relationship between size and complexity
The first ingredient of ABA is that of a deductive system
of the induced AF. Most notably, we will show that each
(ℒ, ℛ), with ℒ a formal language and ℛ a set of inference
ABA framework can be transferred in a way that either
rules over ℒ. In this work we assume that ℒ is a set of
reasoning becomes easy (Theorem 32) or the AF is of
atoms. A rule 𝑟 ∈ ℛ is of the form 𝑠 ← 𝑎1 , . . . , 𝑎𝑛
polynomial size (Proposition 28), but reaching both goals
with 𝑎𝑖 ∈ ℒ. A shorthand for the head of a rule 𝑟 is
simultaneously is not possible in general (Theorem 32).
defined by ℎ𝑒𝑎𝑑(𝑟) = {𝑠}, and for the (possibly empty)
In doing so, our goal is also contributing to a general
body via 𝑏𝑜𝑑𝑦(𝑟) = {𝑎1 , . . . , 𝑎𝑛 }. An ABA framework
formal understanding under which conditions a knowl-
contains a deductive system and specifies which atoms
edge base induces large AFs and which techniques might
are assumptions and what are contraries of assumptions.
help avoiding this blow-up. For carrying out reasoning
93
�Definition 1. An ABA framework is a tuple 𝐷 = 𝐴 does not attack itself. Set 𝐴 defends assumption set
(ℒ, ℛ, 𝒜, ), where (ℒ, ℛ) is a deductive system, 𝒜 ⊆ ℒ 𝐵 ⊆ 𝒜 in 𝐷 iff for all 𝐶 ⊆ 𝒜 that attack 𝐵 it holds that
a non-empty set of assumptions, and a function map- 𝐴 attacks 𝐶.
ping assumptions 𝑎 ∈ 𝒜 to atoms 𝑠 ∈ ℒ (the contrary
function). In this paper, we focus on the central semantical con-
cept of admissibility.
In this work, we focus on ABA frameworks which are
/ 𝒜 Definition 4. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame-
(i) flat, i.e., for each rule 𝑟 ∈ ℛ it holds that ℎ𝑒𝑎𝑑(𝑟) ∈
(no assumptions can be derived), (ii) ℒ, ℛ, and 𝑏𝑜𝑑𝑦(𝑟) work. A set of assumptions 𝐴 ⊆ 𝒜 is admissible iff 𝐴 is
for each 𝑟 ∈ 𝑅 is finite, and (iii) each rule in ℛ is stated conflict-free and 𝐴 defends itself.
explicitly (given as input). We move on to tree-based arguments.
Semantics of ABA frameworks can be defined on sub-
sets of the assumptions or via translation to arguments Definition 5. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame-
and attacks. Below, we recall both notions. work, and (𝐴 ⊢ 𝑠) and (𝐵 ⊢ 𝑡) two tree-based argu-
Arguments in an ABA framework 𝐷 = (ℒ, ℛ, 𝒜, ) ments based on 𝐷. Tree-based argument (𝐴 ⊢ 𝑠) attacks
are based on proof trees (derivations). Due to our focus on (𝐵 ⊢ 𝑡) if there is an assumption 𝑏 ∈ 𝐵 s.t. 𝑏 = 𝑠.
computational aspects, we will in later sections consider
a different representation of arguments, hence we refer Collecting all tree-based arguments and attacks based
to arguments based directly on proof trees as “tree-based on an ABA results in an argumentation framework corre-
arguments”. Formally, a tree-based argument, denoted by sponding to the given ABA.
𝐴 ⊢ℛ 𝑠, with 𝐴 ⊆ 𝒜 and 𝑠 ∈ ℒ based on 𝐷 is defined Definition 6. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame-
as a finite labeled rooted tree s.t. the root is labeled with work. The pair (A, R) is called the argumentation frame-
𝑠, each leaf is labeled by an assumption 𝑎 ∈ 𝒜 or a work (AF) corresponding to 𝐷 if A is the set of all tree-
dedicated symbol ⊤ ∈ / ℒ s.t. the set of all labels of leaves based arguments based on 𝐷, and R is the set of all
is 𝐴, and each internal node is labeled with ℎ𝑒𝑎𝑑(𝑟) of a attacks based on 𝐷.
rule 𝑟 ∈ ℛ s.t. the set of labels of children of this node
is equal to 𝑏𝑜𝑑𝑦(𝑟) or ⊤ if the body is empty. Moreover, Below we recall the analogous notions of conflict-
if 𝑎 ∈ 𝒜, then {𝑎} ⊢ℛ 𝑎 is also a tree-based argument freeness, defense and admissibility in AFs.
(special case without using any derivation rules). In brief,
a tree-based argument represents a derivation using rules Definition 7. Let 𝐷 be an ABA framework, 𝐹 = (A, R)
in ℛ to derive 𝑠 starting from assumptions in 𝒜. We say the corresponding AF, and 𝐻 ⊆ A a set of tree-based
that 𝑠 is the claim of the tree-based argument. We remark arguments of 𝐹 . The set 𝐻 is conflict-free (in 𝐹 ) if there
that there can be multiple tree-based arguments with the are no arguments (𝐴 ⊢ 𝑠), (𝐵 ⊢ 𝑡) ∈ 𝐻 s.t. (𝐴 ⊢
same set of assumptions and claim. 𝑠) attacks (𝐵 ⊢ 𝑡). A conflict-free set 𝐻 defends an
Given an ABA framework 𝐷 = (ℒ, ℛ, 𝒜, ), deriv- argument (𝐴 ⊢ 𝑠) (in 𝐹 ) if for each argument (𝐵 ⊢ 𝑡) ∈
ability for a set of assumptions 𝐴 ⊆ 𝒜 is defined via A that attacks (𝐴 ⊢ 𝑠) it holds that there is an argument
Th 𝐷 (𝐴) = {𝑠 | there is a tree-based argument 𝐴′ ⊢ℛ (𝐶 ⊢ 𝑢) ∈ 𝐻 s.t. (𝐶 ⊢ 𝑢) attacks (𝐵 ⊢ 𝑡). Moreover, 𝐻
𝑠, 𝐴′ ⊆ 𝐴}. That is, Th 𝐷 (𝐴) contains all atoms that is admissible (in 𝐹 ) if it is conflict-free and defends itself.
can be derived (via tree-based arguments) using assump- Claims of tree-based arguments are collected via
tions in 𝐴. We omit subscripts 𝐷 and ℛ if clear from the cl (𝐻) = {𝑠 | (𝐴 ⊢ 𝑠) ∈ 𝐻} for a set of tree-
context. based arguments 𝐻, and assumptions via asms(𝐻) =
We now recall conflicts, admissible sets, and subse- ⋃︀
(𝐴⊢𝑠)∈𝐻 𝐴.
quently the corresponding definitions on tree-based argu- To clearly distinguish semantics, we say that 𝐴 ⊆ 𝒜
ments. is an admissible assumption set (or an adm-assumption
Definition 2. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame- set) and that a set of tree-based arguments 𝐸 is an admis-
work, and 𝐴, 𝐵 ⊆ 𝒜 be two sets of assumptions. Assump- sible extension (or adm-extension for short). We refer
tion set 𝐴 attacks assumption set 𝐵 in 𝐷 if 𝑏 ∈ Th(𝐴) to all adm-assumption sets of 𝐷 via adm(𝐷), and to
for some 𝑏 ∈ 𝐵. all adm-extensions of an AF 𝐹 by adm(𝐹 ). There is a
direct correspondence between semantics via assumption
In words, an assumption set 𝐴 attacks assumption set sets and sets of tree-based arguments (see, e.g., Čyras
𝐵 if it is possible to derive from 𝐴 the contrary of some et al., 2018).
assumption in 𝐵.
Proposition 8. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame-
Definition 3. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame- work and 𝐹 = (A, R) the corresponding AF.
work. An assumption set 𝐴 ⊆ 𝒜 is conflict-free in 𝐷 iff
94
� • If 𝐸 ∈ adm(𝐷) then {(𝐴 ⊢ 𝑠) | 𝐴 ⊆ and 𝑏 = 𝑥. There are infinitely (countably) many tree-
𝐸, (𝐴 ⊢ 𝑠) is a tree-based argument in 𝐷} ∈ based arguments based on 𝐷 (via chaining rules arbitrary
adm(𝐹 ), and many times), and argument {𝑎} ⊢ 𝑎 is attacked by all
• if 𝐻 ∈ adm(𝐹 ) then asms(𝐻) ∈ adm(𝐷). tree-based arguments concluding 𝑦 (of which there are
infinitely many).
An important reasoning task on ABA and AFs is cred-
ulous reasoning under admissibility. An atom 𝑠 is cred- This leads to the simple observation stated next. That
ulously accepted under admissibility in an ABA 𝐷 iff there are countably many tree-based arguments can be
there is an adm-assumption-set 𝐸 s.t. 𝑠 ∈ Th(𝐸). For a seen since one can write (for a given ABA) each argument
given AF (A, R) and 𝛼 ∈ A, it holds that 𝛼 is credulously as a string over a restricted alphabet.
accepted under admissibility in 𝐹 iff there is an adm- Observation 11. Given an ABA framework, the corre-
extension 𝐻 containing 𝛼. We remark that credulous sponding AF can be (countably) infinite and non-finitary.
acceptance of tree-based arguments in a given AF can be
directly generalized to ask for acceptance of claims 𝑠 of Nevertheless, as one can see intuitively in the example,
tree-based arguments, i.e., asking whether there is some AFs corresponding to an ABA framework can be “cut
adm-extension containing some tree-based argument 𝛼 down” to a finite core by removing “duplicates” of ar-
with claim 𝑠. guments. This observation is sometimes assumed to be
Complexity results for reasoning in ABA and AFs were folklore in the research community and stated for other
established (see, e.g., Dvořák and Dunne, 2018, for an forms of structured argumentation [12].
overview) when the corresponding structure is given (in Let us formalize how to obtain such a duplicate-free
particular for AFs the full AF is given as input). For both core. Tree-based arguments in an ABA framework are
assumption sets and extensions, credulous acceptance un- defined as proof trees, with each argument (𝐴 ⊢ 𝑠) based
der admissibility is NP -complete. on a set of assumptions and a claim. While rules are driv-
ing derivability, they are not important when evaluating
Example 9. We formalize the introductory example. The arguments: conflicts between arguments are solely spec-
ABA framework 𝐷 = (ℒ, ℛ, 𝒜, ) is given by ified via assumptions 𝐴 and claim 𝑠. A natural way to
represent arguments is thus by using only 𝐴 and 𝑠. From
ℒ = {𝑐1 , 𝑐2 , 𝜑} ∪ 𝒜,
now on, we mean by arguments pairs (𝐴, 𝑠) but insist that
𝒜 = {𝑥1 , 𝑥′1 , 𝑥2 , 𝑥′2 } with 𝑥𝑖 = 𝑥′𝑖 , 𝑥′𝑖 = 𝑥𝑖 , there is a corresponding proof tree (𝐴 ⊢ 𝑠) in the given
ABA framework. We call the resulting set of arguments
moreover, the rules ℛ of the given ABA are the core of an ABA.
𝑐 1 ← 𝑥1 ; 𝑐1 ← 𝑥′2 ; 𝑐2 ← 𝑥′1 ; Definition 12. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be
𝑐2 ← 𝑥2 ; 𝜑 ← 𝑐1 , 𝑐2 . an ABA framework. Let A = {(𝐴, 𝑠) |
there is a tree-based argument (𝐴 ⊢ 𝑠) in 𝐷}. An
It holds that each 𝐴 ⊆ 𝒜 is admissible whenever argument (𝐴, 𝑠) attacks an argument (𝐵, 𝑡) (in 𝐷) if
{𝑥𝑖 , 𝑥′𝑖 } ̸⊆ 𝐴 for 𝑖 ∈ {1, 2} (no “complementary lit- ∃𝑏 ∈ 𝐵 s.t. 𝑏 = 𝑠, with R being the set of all such attacks.
erals”). Moreover, the literal 𝜑 is credulously accepted The AF 𝐹 = (A, R) is called the core of 𝐷.
under admissibility, since, e.g. {𝑥1 , 𝑥2 } is admissible and Claims and assumptions of a set of arguments 𝐻 ⊆
𝜑 ∈ Th({𝑥1 , 𝑥2 }). A are defined similarly as for tree-based arguments:
⋃︀(𝐻) = {𝑠 | (𝐴, 𝑠) ∈ 𝐻} and asms(𝐻) =
cl
3. Infinite AFs, Cores, and (𝐴,𝑠)∈𝐻 𝐴. Given an ABA 𝐷 its corresponding AF 𝐹
and core 𝐹 ′ , in addition to the core being finite it follows
Representation directly that
In general it can be the case that an AF 𝐹 corresponding • for each tree-based argument (𝐴 ⊢ 𝑠) there is an
to a given ABA 𝐷 is not finite. We first recall some basic argument (𝐴, 𝑠) and vice versa, and thus
properties of such (possibly) infinite corresponding AFs. • 𝐹 has an admissible set of tree-based arguments
We say that an AF 𝐹 = (A, R) is infinite if A is infinite. 𝐻 with cl (𝐻) = 𝑆 and asms(𝐻) = 𝐴 iff 𝐹 ′ has
An AF 𝐹 is finitary [7] if it holds that each argument an admissible set of arguments 𝐻 ′ , cl (𝐻 ′ ) = 𝑆
𝛼 ∈ A is attacked by a finite number of arguments (but and asms(𝐻 ′ ) = 𝐴.
the overall number of arguments may still be infinite).
If one is not interested in the actual derivation of a claim,
Example 10. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame- representing an argument as a pair (𝐴, 𝑠) narrows down
work with 𝒜 = {𝑎, 𝑏}, ℒ = {𝑥, 𝑦} ∪ 𝒜, four rules the argument to the information required in order to con-
(𝑥 ← 𝑎), (𝑥 ← 𝑥), (𝑦 ← 𝑦), and (𝑦 ← 𝑏), and 𝑎 = 𝑦 struct the corresponding AF (the core) and perform the
95
�standard reasoning tasks. To some extent surprising per- 4.1. Bounds and Complexity of
haps, we can find a complexity-theoretic result supporting Reasoning
the intuition that the core is a more efficient representa-
tion: while deciding whether a proof tree constitutes a First, we consider bounds on (i) the depth of chaining
tree-based argument for a given ABA is immediate, it is rules and (ii) the size of bodies of rules. We show that
NP -hard to decide whether a pair (𝐴, 𝑠) occurs in the restricting derivation-depth or rule-size does not yield
core. milder complexity regarding credulous reasoning under
admissibility.
Proposition 13. It is NP-hard to decide whether there is Formally, an ABA 𝐷 is bounded by 𝑘-derivation-depth
a proof tree from a given set of assumptions to a given if each proof tree of 𝐷 has height at most 𝑘 (i.e., the
claim. longest path from assumptions to claim is at most 𝑘). A
rule of the form 𝑠 ← 𝑏1 , . . . , 𝑏𝑛 is bounded by 𝑘 if 𝑛 ≤ 𝑘;
Proof. Let 𝜑 = 𝑐1 ∧· · ·∧𝑐𝑚 be a Boolean formula in con-
an ABA 𝐷 is rule-size bounded by 𝑘 if each rule in 𝐷 is
junctive normal form over vocabulary 𝑋 = {𝑥1 , . . . , 𝑥𝑛 }
bounded by 𝑘.
with 𝐶 = {𝑐1 , . . . , 𝑐𝑚 } the set of clauses. We construct
In order to show that bounding derivation-depth is in-
an ABA framework 𝐷 with 𝒜 = 𝐶, atoms 𝐶 together
tractable, we reduce the Boolean Satisfiability Problem
with literals over 𝑋 and {𝑑𝑥1 , . . . , 𝑑𝑥𝑛 }, and the follow-
via the following reduction:
ing rules (note that “¬𝑥” is a symbol in ABA and has no
meaning attached to the negation sign): Reduction 14. Let 𝜑 = 𝑐1 ∧ · · · ∧ 𝑐𝑚 be a Boolean for-
mula in conjunctive normal form (CNF) over clauses 𝐶 =
𝑥 ← {𝑐 ∈ 𝐶|𝑥 ∈ 𝑐}, and
{𝑐1 , . . . , 𝑐𝑚 } and Boolean variables 𝑋 = {𝑥1 , . . . , 𝑥𝑛 }.
¬𝑥 ← {𝑐 ∈ 𝐶|¬𝑥 ∈ 𝑐} for each 𝑥 ∈ 𝑋 Define 𝑋 ′ = {𝑥′ | 𝑥 ∈ 𝑋}. Construct 𝐷 = (ℒ, ℛ, 𝒜, )
𝑑𝑥 ← 𝑥 and 𝑑𝑥 ← ¬𝑥 for each 𝑥 ∈ 𝑋 by
𝑓 ← 𝑑 𝑥1 , . . . , 𝑑 𝑥𝑛 • ℒ = 𝑋 ∪ 𝑋 ′ ∪ 𝐶 ∪ {𝜑},
Contraries are assigned to literals not appearing in any • 𝒜 = 𝑋 ∪ 𝑋 ′,
rules (for the task of argument construction, contraries are • 𝑥 = 𝑥′ and 𝑥′ = 𝑥 for each 𝑥 ∈ 𝑋, and
not relevant). It can be shown that (𝐶, 𝑓 ) is an argument • let the set of rules be composed of 𝜑 ←
of the resulting ABA framework iff 𝜑 is satisfiable. 𝑐1 , . . . , 𝑐𝑚 , and 𝑐𝑖 ← 𝑧 with 𝑧 = 𝑥 and 𝑥 ∈ 𝑐𝑖
or 𝑧 = 𝑥′ and ¬𝑥 ∈ 𝑐𝑖 .
We want to emphasize that this result does not imply
that it is harder to compute the core compared to a corre- The resulting ABA framework is bounded by 2-
sponding AF, since one can directly extract the core from derivation-depth as each proof tree has height at most
the corresponding AF. Rather, Proposition 13 formalizes 2. We observe that the presented reduction formalizes our
that skipping computation of the proof trees in order to introductory example:
construct the core is a hard task in general.
From now on, we restrict our attention to cores, and Example 15. Given the CNF-formula 𝜑 = (𝑥1 ∨ ¬𝑥2 ) ∧
assume that, for a given ABA, we operate exclusively on (¬𝑥1 ∨𝑥2 ) from the introduction. Following Reduction 14,
a core, unless explicitly mentioned otherwise. we obtain an ABA framework 𝐷 = (ℒ, ℛ, 𝒜, ) which
contains the assumptions 𝒜 = {𝑥1 , 𝑥2 , 𝑥′1 , 𝑥′2 } and the
rules 𝜙 ← 𝑐1 , 𝑐2 and
4. Bounds on Assumption-based • 𝑐1 ← 𝑥1 , 𝑐1 ← 𝑥′2 (since 𝑥1 , ¬𝑥2 ∈ 𝑐1 ) as well
Frameworks as
• 𝑐2 ← 𝑥′1 , 𝑐2 ← 𝑥2 (since 𝑥′1 , 𝑥2 ∈ 𝑐2 )
In this section we study the impact of bounding certain
parts of the input ABA on the complexity of reasoning Moreover, the ABA framework assigns symmetric con-
and size of cores (and corresponding AFs in cases). We traries, i.e., 𝑥𝑖 = 𝑥′𝑖 and 𝑥′𝑖 = 𝑥𝑖 for 𝑖 ∈ {1, 2}. The
consider bounds on derivation-depth and bodies of rules. resulting framework indeed coincides with the introduc-
When investigating size of cores, we make use of the tory example (cf. Example 9).
following definition. Given an ABA 𝐷 the size of 𝐷 (|𝐷|)
is the length of a (direct) string representation of 𝐷. Let It can be shown that the special atom 𝜑 is credulously
𝒟 be a set of ABA frameworks. We say that the cores of accepted under admissible semantics in the ABA frame-
𝒟 are polynomially bounded if there is a polynomial 𝑝 s.t. work iff the formula 𝜑 is satisfiable.
𝑝(|𝐷|) ≥ |A| for all 𝐷 ∈ 𝒟 with 𝐹 = (A, R) the core of Observe that tree-based arguments in the correspond-
𝐷. We will see below that the cores of the set of all ABA ing AF in Reduction 14 have derivation-depth of at most
frameworks are not polynomially bounded. 2. We obtain that credulous reasoning is NP -complete
96
� 𝜑 𝜑 𝜑 𝜑 Proposition 18. Credulous reasoning under admissibility
𝑐1 𝑐2 𝑐1 𝑐2 𝑐1 𝑐2 𝑐1 𝑐2 is decidable in polynomial time in cores of symmetric
ABAs.
𝑥1 𝑥′1 𝑥′2 𝑥′1 𝑥1 𝑥2 𝑥′2 𝑥2
4.2. Size of the Constructed AF
𝑥1 𝑥′1 𝑥2 𝑥′2
From identifying arguments as pairs of assumption sets
𝑐2 𝑐1 𝑐1 𝑐2 and claims we directly obtain that the number of argu-
𝑥′1 𝑥1 𝑥 ′
𝑥2 ments in cores is bounded by 2|𝒜| · |ℒ ∖ 𝒜| + |𝒜| for
2
each ABA framework 𝐷 = (ℒ, ℛ, 𝒜, ). We establish a
Figure 1: AF instantiation of the ABA framework from bound on the number of tree-based arguments that consid-
Example 15 for the formula 𝜑 = (𝑥1 ∨ ¬𝑥2 ) ∧ (¬𝑥1 ∨ 𝑥2 ) ers derivation-depth and rule-size and show that bound-
(cf. Reduction 14). ing both derivation-depth and rule-size yields ABAs with
polynomially bounded cores.
The number of tree-based arguments that can be con-
even when restricting ABA frameworks to be bounded by structed from a given ABA framework 𝐷 depends on the
𝑘-derivation-depth for some constant 𝑘 ≥ 2. Moreover, number of rules, derivation-depth, rule-size, and number
in general Reduction 14 yields cores which are not poly- of rules with same heads, as follows.
nomially bounded by the given ABA framework: for a
Theorem 19. For each 𝑚-derivation-depth and 𝑘-rule-
formula 𝜙 with 𝑚 clauses and 𝑘 variables per clause, we
𝑚 size bounded ABA framework 𝐷 = (ℒ, ℛ, 𝒜, ) with
construct up to 𝑘 many arguments with conclusion 𝜙.
|{𝑟 ∈ ℛ | ℎ𝑒𝑎𝑑(𝑟) = 𝑠}| ≤ 𝑙 for all 𝑠 ∈ ℒ, there are at
Figure 1 depicts the core (equivalent to the corresponding
most∑︀𝑙𝑝 · |ℒ ∖ 𝒜| + |𝒜| many tree-based arguments with
AF) of the constructed ABA framework from Example 15. 𝑚−1 𝑖
𝑝 = 𝑖=0 𝑘 .
Here, we have 22 many arguments with conclusion 𝜙.
A slight adaption of the reduction shows that credu- Proof. To prove the statement, we show that the number
lous reasoning under admissibility remains NP -complete, of all possible trees constructible from 𝐷 is bounded by
when bounding instead the body-size of the rules by 2. 𝑛 · 𝑙𝑝 with 𝑝 = 𝑚−1 𝑘𝑖 and 𝑛 = |ℒ ∖ 𝒜|. Here, we
∑︀
𝑖=0
Theorem 16. Credulous reasoning under admissibility do not require that the leaves of the trees are labelled as
remains NP-hard even if restricted to derivation-depth assumptions. Observe that the set of all tree-based argu-
bounded or rule-size bounded ABA frameworks. ments is a subset of the number of all trees constructible
from 𝐷.
A closer inspection of the ABAs constructed from Re- For each literal 𝑠 ∈ ℒ ∖ 𝒜 which appears as head of
duction 14 points to another class of ABA frameworks a rule in 𝐷, there are at most 𝑙 · 𝑥𝑘 many trees where
with notable properties. In this reduction, we construct 𝑥 is the maximum number of trees with head 𝑐 for a
ABA frameworks with a symmetric contrary function, i.e., literal 𝑐 ∈ 𝑏𝑜𝑑𝑦(𝑟) for some rule 𝑟 with ℎ𝑒𝑎𝑑(𝑠). Indeed,
𝑎 = 𝑏 iff 𝑏 = 𝑎 for all 𝑎, 𝑏 ∈ 𝒜. We call these ABA there are at most 𝑙 rules with head 𝑠, all bounded by 𝑘. We
frameworks symmetric. First, observe that credulous rea- express this correspondence via the function 𝑓 (𝑥) = 𝑙·𝑥𝑘 .
soning in this framework is NP -hard (following directly The total number of trees with root 𝑠 constructible from
from Theorem 16). 𝐷 after 𝑚 steps is thus given by 𝑓 𝑚 (1). We show that
∑︀𝑚−1 𝑖
𝑓 𝑚 (1) = 𝑙 𝑖=0 𝑘 via induction over 𝑚.
Corollary 17. Credulous reasoning under admissibility
For 𝑚 = 1, we have 𝑓 (1) = 𝑙.
is NP -hard for symmetric ABA frameworks.
Now assume the statement holds true for rule depth
On the other hand, we observe that the computational 𝑚 − 1.
hardness in symmetric ABAs stems entirely from the con-
struction of arguments: indeed, constructing the cores 𝑓 𝑚 (1) = 𝑙 · (𝑓 𝑚−1 (1))𝑘
∑︀𝑚−2 𝑖
results in AFs with |𝒜|/2 many even cycles of length 2 (a = 𝑙 · (𝑙 𝑖=0 𝑘 )𝑘
cycle for every assumption and its negation) satisfying ∑︀𝑚−2 𝑖
that all arguments with claim 𝑠 ∈/ 𝒜 have only incoming = 𝑙 · 𝑙𝑘( 𝑖=0 𝑘 )
attacks. For an example we refer to Figure 1. Credulous ∑︀𝑚−1 𝑖
reasoning under admissibility in such AFs is decidable = 𝑙 𝑖=0 𝑘 .
in time polynomial in the number of arguments, since it
We thus obtain that the number of all possible trees
suffices to check if there exists an argument having the
constructible from 𝐷 is bounded by 𝑙𝑝 · 𝑛 with 𝑝 =
queried claim that is not attacked by both arguments in a ∑︀𝑚−1 𝑖
𝑖=0 𝑘 .
2-cycle.
97
� Intuitively, exponentiality of the number of tree-based new argument. Therefore, after at most |A| + 1 iterations
arguments stems from 𝑝, and thus from derivation-depth we are done. Each iteration visits |ℛ| rules. Consider one
and rule-size. Moreover, it is clear that the result extends particular rule 𝑟. For each body literal, we need to search
to the number of arguments in the cores of derivation- through at most |A| arguments. Since |𝑏𝑜𝑑𝑦(𝑟)| ≤ 𝑘,
depth and rule-size bounded ABA frameworks. Bounding this is in 𝒪(|A|𝑘 ). In order to decide whether or not the
both parameters thus yields polynomially bounded cores. induced argument 𝐴 ⊢ ℎ𝑒𝑎𝑑(𝑟) needs to be added, we
again search through the at most |A| already constructed
Corollary 20. The cores of the set of ABA frameworks arguments and compare. In summary, we visit rules at
which are both derivation-depth and rule-size bounded by most (|A| + 1) · |ℛ| times and thereby, we can perform
some constant 𝑘 are polynomially bounded. the necessary computations in time in 1𝒪(|A|𝑘+1 ).
Bounding derivation-depth or rule-size individually,
The preceding result together with Corollary 20 yields
however, does not yield cores that are polynomially
a procedure to obtain a polynomially bounded core in
bounded.
polynomial time for rule-size bounded and derivation-
Proposition 21. The cores of ABA frameworks which depth bounded ABA frameworks.
are derivation-depth bounded by some constant 𝑘 are not
Corollary 23. The cores of the set of rule-size and
polynomially bounded. Likewise, the cores of rule-size
derivation-depth bounded ABA frameworks can be com-
bounded ABA frameworks are not polynomially bounded.
puted in polynomial time in size of the given ABA frame-
work.
4.3. Computation of the Core
We remark that it is currently not known whether the
As the reader might have noticed, having polynomially condition of rule-size boundedness in Theorem 22 can
bounded cores does not (directly) imply the existence of be dropped; we conjecture that the condition is required.
a polynomial-time algorithm that can actually obtain the In any case, Theorem 22 also yields the result that enu-
core in question. We show that for ABA frameworks merating arguments in the core of a rule-size bounded
which are rule-size bounded an algorithm can be ob- ABA framework has incremental polynomial time com-
tained that enumerates arguments in polynomial-time re- plexity [19], i.e., one can in polynomial time w.r.t. the
garding size of input and number of arguments. This given ABA and partially enumerated arguments find a
can be achieved by a direct algorithm: for each rule fresh argument or conclude that all arguments were enu-
𝑟 with 𝑏𝑜𝑑𝑦(𝑟) = {𝑠1 , . . . , 𝑠𝑛 } and already computed merated.
(tree-based) arguments {𝛼1 , . . . , 𝛼𝑚 } loop through each
𝑛-sized subset 𝑋 of {𝛼1 , . . . , 𝛼𝑚 } and check whether
cl (𝑋) = 𝑏𝑜𝑑𝑦(𝑟). If so, attach it to a potential new argu- 5. Transformations and
ment concluding ℎ𝑒𝑎𝑑(𝑟). If this argument is fresh, add Complexity Trade-offs
it to the output. If 𝑛 ≤ 𝑘 for a constant 𝑘, this search is
bounded polynomially by the given ABA and size of core. We saw that ABA frameworks may yield a core not poly-
Theorem 22. The cores of ABA frameworks whose rule- nomially bounded, but with polynomial-time reasoning
size is bounded by a constant can be constructed in poly- (under the credulous view and admissibility), e.g., when
nomial time w.r.t. the size of the given ABA and core. looking at Reduction 14. In this section we look at possi-
bility results and an impossibility result of transforming
Proof. Consider the following brute-force procedure. a given ABA to another ABA framework whose core is
polynomially bounded or allows for polynomial-time rea-
• loop through each rule 𝑟 ∈ ℛ as long as new soning.
arguments are added.
– given 𝑏𝑜𝑑𝑦(𝑟) = {𝑎1 , . . . , 𝑎𝑡 }, for each 5.1. Tractable Reasoning in Core
subset 𝑥1 , . . . , 𝑥𝑡 of the already con-
structed arguments s.t. cl (𝑥𝑖 ) = 𝑎𝑖 Recall that one of our main goals was to formalize the
idea that one could construct ABA frameworks in a way
* if the corresponding argument 𝐴 ⊢
ℎ𝑒𝑎𝑑(𝑟) is not yet constructed, add it that the induced AF might be large, but yields tractable
to the list; reasoning in return. As we already mentioned, the ABA
framework constructed in the motivating example corre-
* otherwise break;
sponds to applying Reduction 14. Our intuition is that the
By definition, this algorithm constructs the correct argu- ABA frameworks constructed according to this reduction
ments in 𝐹 . The outer loop over each rule can be left indeed yield AFs with tractable reasoning (though in the
once there was one iteration which did not induce any potential exponential size of the AF). This intuition can
98
�be confirmed as follows: First, observe hat Reduction 14 The transformation is defined as follows. Intuitively, for
yields symmetric ABA frameworks (by definition). Thus each conclusion 𝑠 derivable from a given ABA framework
by Proposition 18 stating that reasoning in symmetric AFs 𝐷, we introduce fresh assumptions 𝑠𝑑 (’𝑠 is derivable’)
is indeed tractable, we obtain the desired outcome. and 𝑠𝑛𝑑 (’𝑠 is not derivable’) that simulate derivations.
However, this only states that a certain class of ABA The resulting ABA framework 𝐷′ contains only rules
frameworks possesses this property. We would like to go with assumptions in the body, each of which gives rise
one step further and transform an arbitrary given ABA to exactly one tree-based argument. Since no rule in 𝐷′
framework s.t. the corresponding AF behaves this way. It contains non-assumptions, each proof tree is of height 1.
turns out that this can be achieved indeed, at least if we
Definition 26. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be a non-circular
restrict our attention to some target conclusion, say 𝑥 ∈ ℒ.
ABA framework such that each 𝑠 ∈ ℒ is in Th 𝐷 (𝒜). We
The underlying idea is surprisingly simple: Suppose we
define 𝐷′ = (ℒ′ , ℛ′ , 𝒜′ , ′ ) as the AF-sensitive ABA
want to transform the ABA framework 𝐷. Since the SAT
framework of 𝐷 as follows. For each 𝑠 ∈ ℒ ∖ 𝒜
problem is NP-complete, we can in polynomial time con-
struct a formula 𝜑 which is satisfiable iff 𝑥 is credulously • let 𝑠𝑑 and 𝑠𝑛𝑑 be two fresh assumptions, with
accepted in 𝐷. Now, our Reduction 14 translates 𝜑 into • 𝑠𝑑 = 𝑠𝑛𝑑 and 𝑠𝑛𝑑 = 𝑠 in ′ .
an ABA framework with the behavior we wish to obtain.
All these steps can be performed in polynomial time. ThisLet 𝒜′ = 𝒜 ∪ {𝑠𝑑 , 𝑠𝑛𝑑 | 𝑠 ∈ ℒ ∖ 𝒜} and ℒ′ = ℒ ∪ 𝒜′ .
yields the following main theorem. Contraries in 𝐷′ are defined as for 𝐷, except for the
new assumptions as above. For each rule 𝑟 ∈ ℛ, let 𝑟′
Theorem 24. For each ABA framework 𝐷 = being 𝑟 except that if 𝑏𝑜𝑑𝑦(𝑟) contains a non-assumption
(ℒ, ℛ, 𝒜, ) and 𝑥 ∈ ℒ one can construct an ABA frame- 𝑠, replace 𝑠 by 𝑠𝑑 . Finally, set ℛ′ = {𝑟′ | 𝑟 ∈ ℛ}.
work 𝐷′ in polynomial time s.t.
Let us consider an example.
• under admissibility, 𝑥 is credulously accepted in
𝐷 iff 𝑥 is credulously accepted in 𝐷′ , Example 27. Consider an ABA framework 𝐷 =
(ℒ, ℛ, 𝒜, ) with assumptions 𝒜 = {𝑎, 𝑏}, rules ℛ:
• reasoning in the corresponding AF 𝐹 is tractable
in the size of 𝐹 . 𝑟1 : 𝑝 ← 𝑞; 𝑟2 : 𝑞 ← 𝑎; 𝑟3 : 𝑠 ← 𝑏;
We want to mention however that this procedure as and contraries 𝑎 = 𝑟 and 𝑏 = 𝑝. In 𝐷, both {𝑎} and {𝑏}
given above is rather theoretical. We believe that finding are admissible as they symmetrically attack each other.
a constructive proof for this result is an exciting future Following Definition 26, we obtain the corresponding
work direction. ABA 𝐷′ = (ℒ′ , ℛ′ , 𝒜′ , ′ ) with assumptions 𝑎, 𝑏, and
additional assumptions 𝑝𝑑 , 𝑝𝑛𝑑 , 𝑞𝑑 , 𝑞𝑛𝑑 , 𝑠𝑑 , 𝑠𝑛𝑑 ; and
5.2. Obtaining a Polynomial Core rules ℛ′ :
Now we turn our attention to the opposite direction: We 𝑟1′ : 𝑝 ← 𝑞𝑑 ; 𝑟2′ : 𝑞 ← 𝑎; 𝑟3′ : 𝑠 ← 𝑏.
present a general polynomial-time procedure which under
mild conditions transforms a given ABA framework 𝐷 s.t. The assumption 𝑞𝑑 is defended by each assumption set
(i) the translated framework is equivalent under projection that derives 𝑞 (since 𝑞𝑑 is attacked by 𝑞𝑛𝑑 which is in
to 𝐷 and (ii) the core of the translated ABA framework turn attacked by all assumption sets that derive 𝑞). Conse-
is polynomially bounded. That is, this time we do not try quently, {𝑞𝑑 , 𝑎} is admissible since it derives 𝑞 and 𝑝 and
to obtain an AF with tractable reasoning, but we wish to thus defeats the attackers 𝑏 and 𝑞𝑛𝑑 . Likewise, {𝑏, 𝑞𝑛𝑑 }
prevent the exponential blow-up which might be caused is admissible in 𝐷′ as it defends itself against the attack
from the instantiation procedure. from 𝑞𝑑 and 𝑎.
We take the definition of circular tree-based arguments As we have seen in the above example, restricting the
(proof trees) from Craven and Toni (2016). outcome to the initial set of assumptions yields the original
extensions. This is not a coincidence, as we show next:
Definition 25. A tree-based argument is circular if there
admissible assumption sets and derivations are preserved
is a path from a leaf to the root which contains two dis-
when projecting to 𝒜 of the original ABA framework.
tinct vertices with the same label. An ABA framework is
circular if there is a circular tree-based argument for this Proposition 28. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be a non-circular
framework. ABA framework such that each 𝑠 ∈ ℒ is in Th 𝐷 (𝒜) and
𝐷′ the AF-sensitive ABA framework of 𝐷. It holds that
We remark that ABA frameworks obtained from Re-
duction 14 are non-circular and all atoms are derivable • if 𝐸 ∈ adm(𝐷), then there is an 𝐸 ′ ∈ adm(𝐷′ )
(independently of whether the underlying formula is satis- with 𝐸 = 𝐸 ′ ∩𝒜 and Th ℛ (𝐸) = Th ℛ′ (𝐸 ′ )∩ℒ,
fiable). and
99
� 𝜑 • if 𝐸 ∈ adm(𝐷), then there is an 𝐸 ′ ∈ adm(𝐷′ )
(𝑐1 )𝑑 (𝑐2 )𝑑 with 𝐸 = 𝐸 ′ ∩𝒜 and Th ℛ (𝐸) = Th ℛ′ (𝐸 ′ )∩ℒ,
• if 𝐸 ′ ∈ adm(𝐷′ ), then 𝐸 ′ ∩ 𝒜 ∈ adm(𝐷) and
Th ℛ (𝐸) ⊇ Th ℛ′ (𝐸 ′ ) ∩ ℒ, and
(𝑐1 )𝑑 (𝑐1 )𝑛𝑑 (𝑐2 )𝑛𝑑 (𝑐2 )𝑑
• the size of the AF corresponding to 𝐷′ is bounded
by 𝑝(|𝐷′ |).
𝑐2 𝑐1 𝑐1 𝑐2
5.3. Trade-Off: Size and Complexity
𝑥′1 𝑥1 𝑥′2 𝑥2
In Section 5.1 the central idea was to start off with Reduc-
𝑥1 𝑥′1 𝑥2 𝑥′2 tion 14 modeling a CNF-formula. We could try to do the
same here and then apply Theorem 31 in order to avoid
Figure 2: Constructed ABA framework from Example 15 the exponential blow-up in size of the AF. However, if we
when applying the construction from Definition 26. could proceed like this with one-to-one correspondence
of the semantics, we would end up solving an NP-hard
problem in polynomial time. Therefore, the condition of
• if 𝐸 ∈ adm(𝐷 ), then 𝐸 = 𝐸 ∩ 𝒜 ∈ adm(𝐷) equivalence under projection in Theorem 31 seems neces-
′ ′ ′
and Th ℛ (𝐸) ⊇ Th ℛ′ (𝐸 ′ ) ∩ ℒ. sary. We present an impossibility result stating that one
cannot transform a given ABA framework to an equiva-
We note that Th ℛ (𝐸) and Th ℛ′ (𝐸 ′ )∩ℒ are not equal lent one with polynomially bounded cores and bounded
but in subset-relation in the second bullet since deriva- rule-size, at least under standard complexity-theoretic as-
tions are potentially cut off in the construction of an AF- sumptions.
sensitive ABA framework. Consider the ABA frameworks
𝐷 and 𝐷′ in Example 27. In 𝐷, the assumption 𝑎 derives Theorem 32. Assuming 𝑃 ̸= NP , there is no constant 𝑘
𝑝 and 𝑞 while in 𝐷′ , the assumption 𝑎 derives only 𝑞. Thus and polynomial-time algorithm which translates a given
Th ℛ ({𝑎}) = {𝑎, 𝑝, 𝑞} ⊇ {𝑎, 𝑞} = Th ℛ′ ({𝑎})(∩ℒ). ABA framework 𝐷 to another ABA framework 𝐷′ s.t.
From the construction of AF-sensitive frameworks, it
• adm(𝐷) = adm(𝐷′ ),
follows that the cores are polynomially bounded. Indeed,
• Th ℛ (𝐸) = Th ℛ′ (𝐸) for 𝐸 ∈ adm(𝐷),
since each assumption as well as each rule corresponds
to precisely one tree-based argument, we obtain that the • 𝐷′ has rule-size bounded by 𝑘, and
′ ′
corresponding AF has at most |𝒜 |+|ℛ | many arguments • the cores of the set of ABA frameworks 𝒟′ trans-
in the core. lated by the algorithm are bounded polynomially.
Proposition 29. Let 𝒟 be the set of all non-circular ABA Proof. Suppose that such an algorithm 𝑇 exists. Let
frameworks with all atoms derivable, and 𝒟′ the set of 𝜑 = 𝑐1 ∧ · · · ∧ 𝑐𝑚 be a Boolean formula in CNF over
AF-sensitive ABA frameworks from 𝒟. It holds that the clauses 𝐶 = {𝑐1 , . . . , 𝑐𝑚 } and Boolean variables 𝑋 =
cores of 𝒟′ are polynomially bounded. {𝑥1 , . . . , 𝑥𝑛 }. Let 𝐷 be the ABA framework obtained
from Reduction 14, and let 𝐷′ = 𝑇 (𝐷) be the outcome
Example 30. Let us consider again our ABA framework of the algorithm. Note that 𝐷′ can be constructed in time
from Example 15. Applying the above construction, we polynomial w.r.t. size of 𝜑. By Reduction 14 and second
obtain an ABA 𝐷′ with additional assumptions (𝑐1 )𝑑 , item, it holds that 𝜑 is satisfiable iff there is an admissible
(𝑐1 )𝑛𝑑 , (𝑐2 )𝑑 , (𝑐2 )𝑛𝑑 ; moreover, we replace rule 𝜙 ← assumption set 𝐴 with 𝜑 ∈ Th ℛ′ (𝐴).
𝑐1 , 𝑐2 with the rule 𝜙 ← (𝑐1 )𝑑 , (𝑐2 )𝑑 . The resulting AF Each admissible assumption-set 𝐵 in 𝐷 satisfies 𝐵 ⊆
is given in Figure 2. 𝑋 ∪ {𝑥′ | 𝑥 ∈ 𝑋}, moreover, 𝐵 does not contain both
𝑥 and 𝑥′ for any 𝑥 ∈ 𝑋 Also note that each conflict-free
We can now gather our results to infer our desired theo- assumption-set is admissible since Reduction 14 yields a
rem. Due to Proposition 29 the AF-sensitive ABA frame- symmetric ABA framework.
work induces an AF with polynomial size and Proposi- By the first item, 𝐷′ has the same admissible assump-
tion 28 ensures that applying this constructions preserves tion sets as 𝐷′ . It holds that there is an argument (𝐵, 𝜑) in
admissible reasoning under projection. Combining these 𝐷′ and 𝐵 does not contain both 𝑥 and 𝑥′ for any 𝑥 ∈ 𝑋
insights yields the following central result. iff 𝜑 is credulously accepted under admissible semantics
in 𝐷′ iff 𝜑 is credulously accepted under admissible se-
Theorem 31. There is some polynomial 𝑝 such that each
mantics in 𝐷 iff 𝜑 is satisfiable. Thus, if one finds an
non-circular ABA framework 𝐷 = (ℒ, ℛ, 𝒜, ) with
argument (𝐵, 𝜑) for 𝐷′ without “complementary literals”
ℒ ⊆ Th 𝐷 (𝒜) can be transformed in polynomial time
(i.e., without any 𝑥 ∈ 𝑋 s.t. both 𝑥 and 𝑥′ are in 𝐵) we
into an ABA framework 𝐷′ where
100
�conclude that 𝜑 is satisfiable, and if 𝜑 is unsatisfiable no Proof. Suppose there is a cycle in 𝐹 . Then there is also a
such argument in 𝐷′ exists. cycle 𝑥1 , . . . , 𝑥𝑛 in 𝐹 where cl (𝑥𝑖 ) ̸= cl (𝑥𝑗 ) for 𝑖 ̸= 𝑗
By Theorem 22 and due to the third item, one can enu- which can be seen as follows. If cl (𝑥𝑖 ) = cl (𝑥𝑗 ), then
merate all arguments of 𝐷′ in polynomial time. Overall, (supposing 𝑖 < 𝑗) there is an attack from 𝑥𝑖 to 𝑥𝑗+1
we can search the space of all arguments in 𝐷′ in time and we can simply remove the sub-sequence consisting
polynomial to size of 𝜑, implying that we can decide of 𝑥𝑖+1 , . . . 𝑥𝑗 . This procedure can be iterated until we
satisfiability of 𝜑 in polynomial time, a contradiction to obtain the sub-sequence with the two required properties.
𝑃 ̸= NP . We now prove the two statements. i) By iteratively
applying Lemma 35 we find a cycle in G𝐷 . ii) By utilizing
cl (𝑥𝑖 ) ̸= cl (𝑥𝑗 ) for 𝑖 ̸= 𝑗, Lemma 35 even guarantees
6. Dependency Graphs on ABA that the length is preserved which yields an odd cycle in
G𝐷 if 𝑥1 , . . . , 𝑥𝑛 is odd.
We look at dependencies induced by the rules of a given
ABA framework, inspired by dependency graphs in logic The above proposition does not hold for even cycles.
programming, and related but different to the dependency
As a counter-example consider the even-cycle free de-
graph notion existing for ABA [17]. pendency graph of Example 34. In contrast, the core 𝐹
Definition 33. The dependency graph G𝐷 = (𝑉, 𝐸, 𝑙) possesses an even cycle. Vice versa, given a cycle in the
for a given ABA 𝐷 = (ℒ, ℛ, 𝒜, ) is an edge-labelled dependency graph, we can construct a cycle of the same
graph with length in 𝐹 .
• 𝑉 = ℒ is the set of vertices, Proposition 37. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame-
• edge 𝑒 = (𝑠, 𝑡) ∈ 𝐸 iff i) there is some rule work such that each 𝑠 ∈ ℒ is in Th(𝒜), 𝐹 be the core
𝑟 ∈ ℛ with 𝑠 ∈ 𝑏𝑜𝑑𝑦(𝑟) and ℎ𝑒𝑎𝑑(𝑟) = {𝑡}, in and G𝐷 the dependency graph. If 𝑝1 , . . . , 𝑝𝑛 is a cycle
this case 𝑙(𝑒) = +; or ii) 𝑡 ∈ 𝒜 and 𝑡 = 𝑠, in this in G𝐷 , then there is a cycle of the same length in 𝐹 .
case, 𝑙(𝑒) = −.
Proof. For 2 ≤ 𝑖 ≤ 𝑛 let 𝑝𝑖 be an assumption. By con-
In brief, vertices represent atoms, and positive edges struction of G𝐷 , 𝑝𝑖−1 = 𝑝𝑖 . Since 𝐷 is trim, there is
connect body elements and heads of rules, while negative an argument 𝑥1 with conclusion cl (𝑥1 ) = 𝑝𝑖−1 . Now
edges correspond to contraries. let 𝑗 be minimal s.t. 𝑖 < 𝑗 and 𝑝𝑗 is an assumption.
Again since 𝐷 is trim, there is also an argument 𝑥2 with
Example 34. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame-
cl (𝑥2 ) = 𝑝𝑗−1 = 𝑝𝑗 . Observe that 𝑥2 is attacked by
work with 𝒜 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}, distinct contraries 𝑥 = 𝑥
¯
arguments with conclusion 𝑝𝑖−1 . Thus, we have an at-
for each 𝑥 ∈ 𝒜 and the following rules:
tack from 𝑥1 to , 𝑥2 in 𝐹 . In G𝐷 , the length of the path
¯←𝑎
𝑑 ¯𝑏 ← 𝑎 ¯𝑐 ← 𝑏 𝑝𝑖−1 , . . . 𝑝𝑗−1 equals one since by choice of 𝑗 we have
{𝑝𝑖−1 , . . . 𝑝𝑗−1 }∩𝒜 = {𝑝𝑖 }. If we continue analogously
¯←𝑐
𝑎 ¯𝑒 ← 𝑑 ¯←𝑒
𝑎
we find a cycle in 𝐹 having the same length as our cycle
Then the dependency graph G𝐷 is given as follows. 𝑝1 , . . . , 𝑝 𝑛 .
− + + − The dependency graph can be utilized to obtain approx-
𝑑 ¯
𝑑 𝑎 ¯𝑏 𝑏 imations for several bounds we considered throughout this
+ − + paper.
¯𝑒 𝑒 𝑎
¯ 𝑐 ¯𝑐
− + + − Proposition 38. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA frame-
work and G𝐷 = (𝑉, 𝐸, 𝑙) the dependency graph. i) For
A path (cycle) in G𝐷 is defined as usual; the length of the rule size 𝑘 of 𝐷 we have 𝑘 ≤ max𝑒∈𝑉 |{𝑒′ ∈ 𝑉 |
a path (cycle) is the number of edges labeled “−”. The (𝑒′ , 𝑒) ∈ 𝐸}|. ii) If G𝐷 is acyclic, then the derivation-
relation between paths in G𝐷 and the core 𝐹 of 𝐷 is very depth of 𝐷 is bounded by the size of the longest path
close as formalized in the following lemma. (counting “+” labels) in G𝐷 .
Lemma 35. Let 𝐷 be an ABA framework with core 𝐹 = Finally, we get a tighter approximation for the size of
(A, R) and dependency graph G𝐷 . If (𝛼, 𝛽) ∈ R, then the core than our previously established term 2|𝒜| ·|ℒ∖𝒜|.
there is a path of length one from cl (𝛼) to cl (𝛽) in G𝐷 .
Proposition 39. Let 𝐷 = (ℒ, ℛ, 𝒜, ) be an ABA
The observation can be extended to the following result. framework, 𝐹 = (A, R) be the core and G𝐷 the de-
Proposition 36. Let 𝐷 be an ABA framework with core pendency graph. For each 𝑠 ∈ ℒ let 𝑝(𝑠) = {𝑎 ∈
𝐹 and dependency graph G𝐷 . i) If G𝐷 is acyclic, then so 𝒜 ∑︀ | 𝑎 has|𝑝(𝑠)|
a path in G𝐷 to 𝑠}. Then |A| ≤ |𝒜| +
is 𝐹 . ii) If G𝐷 is odd-cycle free, then so is 𝐹 . 𝑠∈ℒ∖𝐴 2 .
101
�7. Discussion Acknowledgments
The computation of a corresponding AF, and different We thank the anonymous reviewers of this paper for their
forms of representing arguments together with optimiza- helpful comments. This research was funded in whole, or
tions for structured argumentation have been consid- in part, by the Austrian Science Fund (FWF) W1255-N23,
ered before, e.g., for ABA [17, 20, 13], and for other by the Vienna Science and Technology Fund (WWTF)
forms of structured argumentation [12, 21]. Moreover, through project ICT19-065, and by the German Federal
complexity of ABA was investigated in several direc- Ministry of Education and Research (BMBF, 01/S18026A-
tions [22, 23, 24, 25], potentially exponential AFs arising F) by funding the competence center for Big Data and AI
from structured argumentation and their issues was dis- “ScaDS.AI” Dresden/Leipzig.
cussed, e.g., by Strass et al. (2019), and infinite arguments
for ABA were investigated [27]. In contrast to these works,
we relate features of the given ABA instance to the size
References
of the resulting arguments and complexity of reasoning. [1] P. Baroni, D. Gabbay, M. Giacomin, L. van der
We focused on arguments as pair structures (assumptions Torre (Eds.), Handbook of Formal Argumentation,
and claim). College Publications, 2018.
Considering variants for representing arguments is an [2] K. Atkinson, P. Baroni, M. Giacomin, A. Hunter,
appealing avenue for future work, but it seems that differ- H. Prakken, C. Reed, G. R. Simari, M. Thimm,
ent representations arrive at other computational barriers. S. Villata, Towards artificial argumentation, AI
For instance, Lehtonen et al. (2017) showed #P-hardness Magazine 38 (2017) 25–36.
under subtractive reductions for counting the number of [3] A. Bondarenko, P. M. Dung, R. A. Kowalski, F. Toni,
argument structures for a representation incorporating a An abstract, argumentation-theoretic approach to
form of minimality on the assumption sets. When requir- default reasoning, Artif. Intell. 93 (1997) 63–101.
ing a core to contain only arguments with subset-minimal [4] S. Modgil, H. Prakken, A general account of argu-
assumption sets one can show hardness for argument con- mentation with preferences, Artif. Intell. 195 (2013)
struction, e.g., it is NP -hard to decide whether there is a 361–397.
subset-minimal argument not yet constructed. [5] A. J. García, G. R. Simari, Defeasible logic pro-
Our results on trade-offs regarding size and complex- gramming: An argumentative approach, Theory
ity of reasoning suggest that it might be worthwhile to Pract. Log. Program. 4 (2004) 95–138.
pre-process ABA frameworks in a suitable way before [6] P. Besnard, A. Hunter, Elements of Argumentation,
utilizing AF solvers; also, one may model problems in MIT Press, 2008.
ABA such that the corresponding AF is either small in [7] P. M. Dung, On the acceptability of arguments and
size or the reasoning in the AF is tractable, depending on its fundamental role in nonmonotonic reasoning,
the intention. logic programming and n-person games, Artif. Intell.
The most interesting future work directions we identify 77 (1995) 321–358.
are as follows. First, the results which make use of the [8] K. Čyras, X. Fan, C. Schulz, F. Toni, Assumption-
actual semantics are only phrased for admissible sets yet. based argumentation: Disputes, explanations, pref-
In particular generalizing Theorem 31 to the other clas- erences, in: P. Baroni, D. Gabbay, M. Giacomin,
sical Dung semantics would contribute to our research. L. van der Torre (Eds.), Handbook of Formal Argu-
Moreover, Theorem 24 is not constructive and one needs mentation, College Publications, 2018, pp. 365–408.
to fix a given atom in advance. Finding an analogous [9] R. Craven, F. Toni, C. Cadar, A. Hadad,
construction which preserves the semantics, similar in M. Williams, Efficient argumentation for medical
spirit to Theorem 31, would be a great generalization. Fur- decision-making, in: Proc. KR, AAAI Press, 2012,
thermore, it would be interesting to investigate to which pp. 598–602.
extent a pre-processing as suggested by Theorem 31 can [10] K. Čyras, T. Oliveira, A. Karamlou, F. Toni,
help boosting the performance of ABA solvers. As a final Assumption-based argumentation with preferences
remark we want to mention that many other structured for- and goals for patient-centric reasoning with inter-
malisms are similar in their spirit, i.e. induce a potentially acting clinical guidelines, Argument Comput. 12
infinite AF which makes information encoded within the (2021) 149–189.
knowledge base explicit. One could therefore examine [11] X. Fan, F. Toni, A. Mocanu, M. Williams, Dialog-
whether our results translate to other formalisms as well. ical two-agent decision making with assumption-
based argumentation, in: Proc. AAMAS, IFAA-
MAS/ACM, 2014, pp. 533–540.
[12] L. Amgoud, P. Besnard, S. Vesic, Equivalence in
102
� logic-based argumentation, J. Appl. Non Class. Log- interface, Int. J. Approx. Reason. 112 (2019) 55–84.
ics 24 (2014) 181–208. [27] P. M. Thang, P. M. Dung, J. Pooksook, Infinite argu-
[13] T. Lehtonen, J. P. Wallner, M. Järvisalo, From struc- ments and semantics of dialectical proof procedures,
tured to abstract argumentation: Assumption-based Argument Comput. (2021). In-press.
acceptance via AF reasoning, in: Proc. ECSQARU,
volume 10369 of LNCS, Springer, 2017, pp. 57–68.
[14] B. Yun, N. Oren, M. Croitoru, Efficient con-
struction of structured argumentation systems, in:
Proc. COMMA, volume 326 of FAIA, IOS Press,
2020, pp. 411–418.
[15] M. Thimm, S. Villata, The first international com-
petition on computational models of argumentation:
Results and analysis, Artif. Intell. 252 (2017) 267–
294.
[16] S. A. Gaggl, T. Linsbichler, M. Maratea, S. Woltran,
Design and results of the second international com-
petition on computational models of argumentation,
Artif. Intell. 279 (2020).
[17] R. Craven, F. Toni, Argument graphs and
assumption-based argumentation, Artif. Intell. 233
(2016) 1–59.
[18] W. Dvořák, P. E. Dunne, Computational problems
in formal argumentation and their complexity, in:
P. Baroni, D. Gabbay, M. Giacomin, L. van der
Torre (Eds.), Handbook of Formal Argumentation,
College Publications, 2018.
[19] D. S. Johnson, C. H. Papadimitriou, M. Yannakakis,
On generating all maximal independent sets, Inf.
Process. Lett. 27 (1988) 119–123.
[20] Z. Bao, K. Čyras, F. Toni, ABAplus: Attack reversal
in abstract and structured argumentation with pref-
erences, in: Proc. PRIMA, volume 10621 of LNCS,
Springer, 2017, pp. 420–437.
[21] B. Yun, S. Vesic, M. Croitoru, Toward a more effi-
cient generation of structured argumentation graphs,
in: Proc. COMMA, volume 305 of FAIA, IOS Press,
2018, pp. 205–212.
[22] Y. Dimopoulos, B. Nebel, F. Toni, On the computa-
tional complexity of assumption-based argumenta-
tion for default reasoning, Artif. Intell. 141 (2002)
57–78.
[23] K. Čyras, Q. Heinrich, F. Toni, Computational com-
plexity of flat and generic assumption-based argu-
mentation, with and without probabilities, Artif.
Intell. 293 (2021) 103449.
[24] T. Lehtonen, J. P. Wallner, M. Järvisalo, Declarative
algorithms and complexity results for assumption-
based argumentation, J. Artif. Intell. Res. 71 (2021)
265–318.
[25] A. Karamlou, K. Čyras, F. Toni, Complexity re-
sults and algorithms for bipolar argumentation, in:
Proc. AAMAS, IFAAMAS, 2019, pp. 1713–1721.
[26] H. Strass, A. Wyner, M. Diller, EMIL: Extract-
ing meaning from inconsistent language: Towards
argumentation using a controlled natural language
103
�