Assumption-based argumentation (ABA) is a powerful defeasible reasoning formalism which is based on the interplay of assumptions, their contraries, and inference rules. ABA with preferences ( ABA + ) generalizes the basic model by allowing a qualitative comparison of assumptions. The integration of preferences however comes with a cost. In ABA + , the evaluation under two central and well-established semantics—grounded and complete semantics—is not guaranteed to yield an outcome. Moreover, while ABA frameworks without preferences allow for a graph-based representation in Dung-style frameworks, an according instantiation for general ABA + frameworks has not been established so far. In this work, we tackle both issues: First, we develop a novel abstract argumentation formalism based on set-to-set attacks. We show that our so-called Hyper Argumentation Frameworks (HYPAFs) capture the attack relation between assumptions in ABA + . Second, we exploit this correspondence between ABA + and HYPAFs to obtain relaxed variants of complete and grounded semantics for HYPAFs that yield an extension for all frameworks by design, while still faithfully generalizing the established semantics of Dung-style Argumentation Frameworks. Finally, we discuss basic properties and provide a thorough complexity analysis for both the abstract HYPAFs as well as ABA + .

Assumption-based argumentation (ABA) is a powerful defeasible reasoning formalism which is based on the interplay of assumptions, their contraries, and inference rules. ABA with preferences (ABA+) generalizes the basic model by allowing qualitative comparison between assumptions. The integration of preferences however comes with a cost. In ABA+, the evaluation under two central and well-established semantics---grounded and complete semantics---is not guaranteed to yield an outcome. Moreover, while ABA frameworks without preferences allow for a graph-based representation in Dung-style frameworks, an according instantiation for general ABA+ frameworks has not been established so far. In this work, we tackle both issues: First, we develop a novel abstract argumentation formalism based on set-to-set attacks. We show that our so-called Hyper Argumentation Frameworks (HYPAFs) capture ABA+. Second, we propose relaxed variants of complete and grounded semantics for HYPAFs that yield an extension for all frameworks by design, while still faithfully generalizing the established semantics of Dung-style Argumentation Frameworks. We exploit the newly established correspondence between ABA+ and HYPAFs to obtain variants for grounded and complete ABA+ semantics that are guaranteed to yield an outcome. Finally, we discuss basic properties and provide a complexity analysis. Along the way, we settle the computational complexity of several ABA+ semantics.

Already in Dung’s seminal paper introducing Abstract Argumentation Frameworks (AFs), several connections to seemingly unrelated reasoning formalisms have been illustrated. In this work, we continue this trend and establish a connection between abstract argumentation frameworks and boolean networks (BNs). BNs, in a nutshell, mimic simple binary-valued systems, where for each point in time, the value of each bit (component) depends only on the other components’ values of the previous point in time of the network. This formalism is widely used to formally analyze biological processes, where from simple rules complex behavior emerges. We show that stable extensions of an arbitrary AF correspond to single state attractors of its canonically corresponding BN, the complete extensions correspond to a distinctive 2-state attractor, and the admissible sets correspond to the seeds of the BN. We thereby lay the groundwork for a fruitful exchange of ideas between the two research areas.

Is an argument acceptable if all potential counter-arguments are unacceptable themselves? In standard models of argumentation, the answer to this question is counter-intuitively not necessarily yes. However, based on the notion of weak admissibility, a family of semantics has been established where these unreasonable attacks do not successfully counter otherwise strong arguments. While in the abstract setting weak admissibility is well-understood, a similar issue arises in the context of structured argumentation formalisms like assumption based argumentation (ABA). It is well known that under standard argumentation semantics, ABA frameworks can be reduced to abstract argumentation frameworks (AFs), however, it turns out that in the case of weak admissibility this approach surprisingly fails. We instead propose to utilize a recently published instantiation technique utilizing collective attacks (SETAFs). We first define weak admissibility for SETAFs and study basic properties; afterwards, we push our proposal to the structured setting. We show that via our approach the characteristic properties of weak admissibility carry over to ABA, and thus establish a basis for further studies of these common scenarios also in ABA and related structured argumentation formalisms.

Argumentation frameworks (AFs) are a key formalism in AI research. Their semantics have been investigated in terms of principles, which define characteristic properties in order to deliver guidance for analyzing established and developing new semantics. Because of the simple structure of AFs, many desired properties hold almost trivially, at the same time hiding interesting concepts behind syntactic notions. We extend the principle-based approach to argumentation frameworks with collective attacks (SETAFs) and provide a comprehensive overview of common principles for their semantics. Our analysis shows that investigating principles based on decomposing the given SETAF (e.g. directionality or SCC-recursiveness) poses additional challenges in comparison to usual AFs. We introduce the notion of the reduct as well as the modularization principle for SETAFs which will prove beneficial for this kind of investigation. We then demonstrate how our findings can be utilized for incremental computation of extensions and show how we can use graph properties of the frameworks to speed up these algorithms.

Qualitative Choice Logic (QCL) extends classical propositional formulas by a connective called ordered disjunction that is used to express preferences. We translate QCL theories to Argumentation Frameworks with Collective Attacks (SETAFs), and show that the preferred models of the original theory directly correspond to the semi-stable extensions of the target framework. This further allows us to decide the problem of preferred model entailment for QCL via SETAFs.

Argumentation frameworks (AFs) are a core formalism in the field of formal argumentation. As most standard computational tasks regarding AFs are hard for the first or second level of the Polynomial Hierarchy, a variety of algorithmic approaches to achieve manageable runtimes have been considered in the past. Among them, the backdoor-approach and the treewidth-approach turned out to yield fixed-parameter tractable fragments. However, many applications yield high parameter values for these methods, often rendering them infeasible in practice. We introduce the backdoor-treewidth approach for abstract argumentation, combining the best of both worlds with a guaranteed parameter value that does not exceed the minimum of the backdoor- and treewidth-parameter. In particular, we formally define backdoor-treewidth and establish fixed-parameter tractability for standard reasoning tasks of abstract argumentation. Moreover, we provide systems to find and exploit backdoors of small width, and conduct systematic experiments evaluating the new parameter.

Many structured argumentation approaches proceed by constructing a Dung-style argumentation framework (AF) corresponding to a given knowledge base. While a main strength of AFs is their simplicity, instantiating a knowledge base oftentimes requires exponentially many arguments or additional functions in order to establish the connection. In this paper we make use of more expressive argumentation formalisms. We provide several novel translations by utilizing claim-augmented AFs (CAFs) and AFs with collective attacks (SETAFs). We use these frameworks to translate assumption-based argumentation (ABA) frameworks as well as logic programs (LPs) into the realm of graph-based argumentation.

Abstract Argumentation is a key formalism to resolve conflicts in incomplete or inconsistent knowledge bases. Argumentation Frameworks (AFs) and extended versions thereof turned out to be a fruitful approach to reason in a flexible and intuitive setting. The addition of collective attacks, we refer to this class of frameworks as SETAFs, enriches the expressiveness and allows for compacter instantiations from knowledge bases, while maintaining the computational complexity of standard argumentation frameworks. This means, however, that standard reasoning tasks are intractable and worst-case runtimes for known standard algorithms can be exponential. In order to still obtain manageable runtimes, we exploit graph properties of these frameworks. In this paper, we initiate a parameterized complexity analysis of SETAFs in terms of the popular graph parameter treewidth. While treewidth is well studied in the context of AFs with their graph structure, it cannot be directly applied to the (directed) hypergraphs representing SETAFs. We thus introduce two generalizations of treewidth based on different graphs that can be associated with SETAFs, i.e., the primal graph and the incidence graph. We show that while some of these notions allow for parameterized tractability results, reasoning remains intractable for other notions, even if we fix the parameter to a small constant.

Argumentation frameworks are a core formalism in the field of formal argumentation, with several semantics being proposed in the literature. Among them, preferred semantics is one of the most popular but comes with relatively high complexity. In fact, deciding whether an argument is skeptically accepted, i.e. contained in each preferred extension, is Pi^P_2-complete. In this work we study the complexity of this problem w.r.t. the length of the cycles in the considered AF. Our results show which bounds are necessary to decrease the complexity to coNP and P, respectively. We also consider argumentation frameworks with collective attacks and achieve Pi^P_2-hardness already for cycles of length 4.