Markus Ulbricht

AIJ Journal 2026 Journal Article

Defining defense and defeat in abstract argumentation from scratch – A generalizing approach

• Lydia Blümel
• Markus Ulbricht

AIJ Journal 2026 Journal Article

Redefining ABA + Semantics via Abstract Set-To-Set Attacks

• Yannis Dimopoulos
• Wolfgang Dvořák
• Anna Rapberger
• Matthias König
• Markus Ulbricht
• Stefan Woltran

KR Conference 2024 Conference Paper

Capturing Non-flat Assumption-based Argumentation with Bipolar SETAFs

• Matti Berthold
• Anna Rapberger
• Markus Ulbricht

While the flat fragment of assumption-based argumentation (ABA) is widely studied in the literature, the general, non-flat case has mostly been neglected so far. Until recently, there was no possible way to instantiate non-flat ABA in terms of an abstract argumentation framework. While this gap has been closed for complete-based ABA semantics, capturing admissible-based semantics cannot yet be achieved by looking at the relation between the instantiated arguments only; it requires augmenting arguments with their premises, hence being a semi-abstract instantiaiton. In this paper, we provide a compact and fully abstract instantiation by making use of both collective attack and support relations. Then, inspired by fundamental properties of abstract formalisms, we identify flaws of native ABA semantics in the non-flat case and provide refinements thereof, utilizing our novel instatiation.

IJCAI Conference 2024 Conference Paper

Formal Argumentation in Symbolic AI

• Markus Ulbricht

In the area of symbolic AI, researchers strive to develop techniques to teach machines (commonsense) reasoning. Human reasoning is often argumentative in its nature, and consequently, computational models of argumentation constitute a vibrant research area in symbolic AI. In this paper I describe my most significant contributions to the field spanning from general non-monotonic logics to formal argumentation.

KR Conference 2024 Conference Paper

From Acceptance to Rejection in Abstract Argumentation

• Anne-Marie Heine
• Markus Ulbricht

Dynamic reasoning environments are among the key aspects in formal argumentation research. Presumably the best understood problem is the so-called enforcement problem which asks, generally speaking, whether a given argumentation framework can be modified in a way that a certain desired outcome is ensured. However, enforcement research primarily focuses on the acceptance of arguments or sets thereof. This paper aims to explore the dual problem and investigates means to reject certain unreasonable viewpoints. To achieve this, we use labelling semantics on abstract argumentation frameworks (AFs), since they provide a clearly defined notion of rejection. We consider different kinds of updates for our given AF and provide results on existence as well as minimality of syntactic and semantic changes. For the latter, we define the new concept of consensus preservation, formalizing the intuition that formerly acceptable opinions should remain acceptable in the adapted framework. Lastly we discuss how these two notions of minimizing change interact.

IJCAI Conference 2024 Conference Paper

Instantiations and Computational Aspects of Non-Flat Assumption-based Argumentation

• Tuomo Lehtonen
• Anna Rapberger
• Francesca Toni
• Markus Ulbricht
• Johannes P. Wallner

Most existing computational tools for assumption-based argumentation (ABA) focus on so-called flat frameworks, disregarding the more general case. In this paper, we study an instantiation-based approach for reasoning in possibly non-flat ABA. We make use of a semantics-preserving translation between ABA and bipolar argumentation frameworks (BAFs). By utilizing compilability theory, we establish that the constructed BAFs will in general be of exponential size. To keep the number of arguments and computational cost low, we present three ways of identifying redundant arguments. Moreover, we identify fragments of ABA which admit a poly-sized instantiation. We propose two algorithmic approaches for reasoning in non-flat ABA; the first utilizes the BAF instantiation while the second works directly without constructing arguments. An empirical evaluation shows that the former outperforms the latter on many instances, reflecting the lower complexity of BAF reasoning. This result is in contrast to flat ABA, where direct approaches dominate instantiation-based solvers.

IJCAI Conference 2024 Conference Paper

Justifying Argument Acceptance with Collective Attacks: Discussions and Disputes

• Giovanni Buraglio
• Wolfgang Dvorak
• Matthias König
• Markus Ulbricht

In formal argumentation one aims for intuitive and concise justifications for the acceptance of arguments. Discussion games and dispute trees are established methods to obtain such a justification. However, so far these techniques are based on instantiating the knowledge base into graph-based Dung style abstract argumentation frameworks (AFs). These instantiations are known to produce frameworks with a large number of arguments and thus also yield long discussion games and large dispute trees. To obtain more concise justifications for argument acceptance, we propose to instantiate the knowledge base as an argumentation framework with collective attacks (SETAF). Remarkably, this approach yields smaller frameworks compared to traditional AF instantiation, while exhibiting increased expressive power. We then introduce discussion games and dispute trees tailored to SETAFs, show that they correspond to credulous acceptance w. r. t. the well-known preferred semantics, analyze and tune them w. r. t. the size, and compare the two notions. Finally, we illustrate how our findings apply to assumption-based argumentation.

AAAI Conference 2024 Conference Paper

Non-flat ABA Is an Instance of Bipolar Argumentation

• Markus Ulbricht
• Nico Potyka
• Anna Rapberger
• Francesca Toni

Assumption-based Argumentation (ABA) is a well-known structured argumentation formalism, whereby arguments and attacks between them are drawn from rules, defeasible assumptions and their contraries. A common restriction imposed on ABA frameworks (ABAFs) is that they are flat, i.e. each of the defeasible assumptions can only be assumed, but not derived. While it is known that flat ABAFs can be translated into abstract argumentation frameworks (AFs) as proposed by Dung, no translation exists from general, possibly non-flat ABAFs into any kind of abstract argumentation formalism. In this paper, we close this gap and show that bipolar AFs (BAFs) can instantiate general ABAFs. To this end we develop suitable, novel BAF semantics which borrow from the notion of deductive support. We investigate basic properties of our BAFs, including computational complexity, and prove the desired relation to ABAFs under several semantics.

IJCAI Conference 2024 Conference Paper

Preferred Reasoning in ABA by Cycle-Breaking

• Kiet Nguyen Anh
• Markus Ulbricht

We develop a fixed-parameter tractable (FPT) algorithm for skeptical preferred reasoning in assumption-based argumentation (ABA). To this end we make use of so-called backdoors, i. e. sets of assumptions that need to be evaluated s. t. the remaining ABA framework (ABAF) belongs to a computational beneficial sub-class. In order to identify such target classes, we employ a suitable notion of a dependency graph of an ABAF. We show that these graphs can be constructed in polynomial time and that one can efficiently check sufficient properties ensuring that reasoning in the underlying ABAF is tractable. After establishing the theoretical foundations, we test our implementation against the ASPforABA solver which convincingly won the ABA track of the ICCMA'23 competition. As it turns out, our algorithm outperforms ASPforABA on instances with small backdoor sizes.

JAIR Journal 2024 Journal Article

Principles and their Computational Consequences for Argumentation Frameworks with Collective Attacks

• Wolfgang Dvořák
• Matthias König
• Markus Ulbricht
• Stefan Woltran

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.

AAAI Conference 2024 Conference Paper

Redefining ABA+ Semantics via Abstract Set-to-Set Attacks

• Yannis Dimopoulos
• Wolfgang Dvorak
• Matthias König
• Anna Rapberger
• Markus Ulbricht
• Stefan Woltran

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.

KR Conference 2024 Conference Paper

Repairing Assumption-Based Argumentation Frameworks

• Anna Rapberger
• Markus Ulbricht

The field of formal argumentation is driven by situations where conflicting information need to be balanced out argumentatively. However, if the given knowledge base does not induce any reasonable viewpoint, these methods are stretched to their limits. In this paper, we address this issue in the context of assumption-based argumentation (ABA). More specifically, we study repairing notions for knowledge bases where no assumption can be accepted. We develop genuine repairing techniques for ABA, based on the modification of the building blocks of ABA frameworks, i. e. , rules and assumptions. Thereby, we start from basic operators towards more and more fine-grained approaches. We compare their behavior to each other and demonstrate their compliance with suitable repairing desiderata.

KR Conference 2024 Conference Paper

Weak Admissibility for ABA via Abstract Set-Attacks

• Lydia Blümel
• Matthias König
• Markus Ulbricht

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.

KR Conference 2023 Conference Paper

Argumentation Frameworks Induced by Assumption-based Argumentation: Relating Size and Complexity

• Tuomo Lehtonen
• Anna Rapberger
• Markus Ulbricht
• Johannes P. Wallner

A key ingredient of computational argumentation in AI is the generation of arguments in favor of or against claims under scrutiny. In this paper we look at the complexity of argument construction and reasoning in the prominent structured formalism of assumption-based argumentation (ABA). We point out that reasoning in ABA by means of constructing an abstract argumentation framework (AF) gives rise to two main sources of complexity: (i) constructing the AF and (ii) reasoning within the constructed graph. Since both steps are intractable in general, it is no surprise that the best performing state-of-the-art ABA reasoners skip the instantiation procedure entirely and perform tasks directly on the input knowledge base. Driven by this observation, we identify and study atomic and symmetric ABA, two ABA fragments that preserve the expressive power of general ABA, and that can be utilized to have milder complexity in the first or second step. We show that using atomic ABA allows for an instantiation procedure for general ABA leading to polynomially-bounded AFs and that symmetric ABA can be used to create AFs that have mild complexity to reason on. By an experimental evaluation, we show that using the former approach with modern AF solvers can be competitive with state-of-the-art ABA solvers, improving on previous AF instantiation approaches that are hindered by intractable argument construction.

JAIR Journal 2023 Journal Article

Equivalence in Argumentation Frameworks with a Claim-centric View: Classical Results with Novel Ingredients

• Ringo Baumann
• Anna Rapberger
• Markus Ulbricht

A common feature of non-monotonic logics is that the classical notion of equivalence does not preserve the intended meaning in light of additional information. Consequently, the term strong equivalence was coined in the literature and thoroughly investigated. In the present paper, the knowledge representation formalism under consideration is claimaugmented argumentation frameworks (CAFs) which provide a formal basis to analyze conclusion-oriented problems in argumentation by adapting a claim-focused perspective. CAFs extend Dung AFs by associating a claim to each argument representing its conclusion. In this paper, we investigate both ordinary and strong equivalence in CAFs. Thereby, we take the fact into account that one might either be interested in the actual arguments or their claims only. The former point of view naturally yields an extension of strong equivalence for AFs to the claim-based setting while the latter gives rise to a novel equivalence notion which is genuine for CAFs. We tailor, examine and compare these notions and obtain a comprehensive study of this matter for CAFs. We conclude by investigating the computational complexity of naturally arising decision problems.

KR Conference 2023 Conference Paper

Forgetting Aspects in Assumption-Based Argumentation

• Matti Berthold
• Anna Rapberger
• Markus Ulbricht

We address the issue of forgetting in assumption-based argumentation (ABA). Forgetting is driven by the goal to remove certain elements from a knowledge base, while preserving the structure of its models as well as possible. We introduce several forgetting operators tailored to accomplish the removal of different pieces of the ABA knowledge base—assumptions, contraries, and atoms—formalizing a diverse selection of perspectives on this issue. We examine the quality of our operators by studying their compliance with suitable desiderata we propose. Thereby, we investigate the impact of the operators on the syntax of the given ABA knowledge base, its semantics, but also the instantiated argumentation framework; thus bridging recent forgetting studies on non-monotonic formalisms including argumentation theory.

JAIR Journal 2023 Journal Article

On Dynamics in Structured Argumentation Formalisms

• Anna Rapberger
• Markus Ulbricht

This paper is a contribution to the research on dynamics in assumption-based argumentation (ABA). We investigate situations where a given knowledge base undergoes certain changes. We show that two frequently investigated problems, namely enforcement of a given target atom and deciding strong equivalence of two given ABA frameworks, are intractable in general. Notably, these problems are both tractable for abstract argumentation frameworks (AFs) which admit a close correspondence to ABA by constructing semanticspreserving instances. Inspired by this observation, we search for tractable fragments for ABA frameworks by means of the instantiated AFs. We argue that the usual instantiation procedure is not suitable for the investigation of dynamic scenarios since too much information is lost when constructing the abstract framework. We thus consider an extension of AFs, called cvAFs, equipping arguments with conclusions and vulnerabilities in order to better anticipate their role after the underlying knowledge base is extended. We investigate enforcement and strong equivalence for cvAFs and present syntactic conditions to decide them. We show that the correspondence between cvAFs and ABA frameworks is close enough to capture dynamics in ABA. This yields the desired tractable fragment. We furthermore discuss consequences for the corresponding problems for logic programs.

KR Conference 2022 Conference Paper

Defining Defense and Defeat in Abstract Argumentation From Scratch -- A Generalizing Approach

• Lydia Blümel
• Markus Ulbricht

We propose a general framework to investigate semantics of Dung-style argumentation frameworks (AFs) by means of a generic defeat notion formalized by refute operators. After establishing the technical foundations, we propose natural generic versions of Dung's classical semantics. We demonstrate how classical as well as recent proposals can be captured by our approach when utilizing suitable notions of refutal. We perform an investigation of basic properties which semantics inherit from the underlying refute operator. In particular, we show under which conditions a counterpart to Dung's fundamental lemma can be inferred and how it ensures the existence of the generalized version of complete extensions. We contribute to a principle-based study of AF semantics by discussing properties tailored to compare different refute operators. Finally, we report computational complexity results for basic reasoning tasks which hold in our general framework.

AAAI Conference 2022 Conference Paper

Equivalence in Argumentation Frameworks with a Claim-Centric View – Classical Results with Novel Ingredients

• Ringo Baumann
• Anna Rapberger
• Markus Ulbricht

A common feature of non-monotonic logics is that the classical notion of equivalence does not preserve the intended meaning in light of additional information. Consequently, the term strong equivalence was coined in the literature and thoroughly investigated. In the present paper, the knowledge representation formalism under consideration is claimaugmented argumentation frameworks (CAFs) which provide a formal basis to analyze conclusion-oriented problems in argumentation by adapting a claim-focused perspective. CAFs extend Dung AFs by associating a claim to each argument representing its conclusion. In this paper, we investigate both ordinary and strong equivalence in CAFs. Thereby, we take the fact into account that one might either be interested in the actual arguments or their claims only. The former point of view naturally yields an extension of strong equivalence for AFs to the claim-based setting while the latter gives rise to a novel equivalence notion which is genuine for CAFs. We tailor, examine and compare these notions and obtain a comprehensive study of this matter for CAFs. We conclude by investigating the computational complexity of naturally arising decision problems.

KR Conference 2022 Conference Paper

On Dynamics in Structured Argumentation Formalisms

• Anna Rapberger
• Markus Ulbricht

In this paper we contribute to the investigation of dynamics in assumption-based argumentation (ABA) and investigate situations where a given knowledge base undergoes certain changes. We show that two frequently investigated problems, namely enforcement of a given target atom and deciding strong equivalence of two given ABA frameworks, are intractable in general. Interestingly, these problems are both tractable for abstract argumentation frameworks (AFs) which admit a close correspondence to ABA by constructing semantics-preserving instances. Inspired by this observation, we search for tractable fragments for ABA frameworks by means of the instantiated AFs. We argue that the usual instantiation procedure is not suitable for the investigation of dynamic scenarios since too much information is lost when constructing the AF. We thus consider an extension of AFs, called cvAFs, equipping arguments with conclusions and vulnerabilities in order to better anticipate their role after the underlying knowledge base is extended. We investigate enforcement and strong equivalence for cvAFs and present syntactic conditions to decide them. We show that the correspondence between cvAFs and ABA frameworks is close enough to capture ABA also in dynamic scenarios. This yields the desired tractable ABA fragment. We furthermore discuss consequences for the corresponding problems for logic programs.

JAIR Journal 2022 Journal Article

Recursion in Abstract Argumentation is Hard --- On the Complexity of Semantics Based on Weak Admissibility

• Wolfgang Dvořák
• Markus Ulbricht
• Stefan Woltran

We study the computational complexity of abstract argumentation semantics based on weak admissibility, a recently introduced concept to deal with arguments of self-defeating nature. Our results reveal that semantics based on weak admissibility are of much higher complexity (under typical assumptions) compared to all argumentation semantics which have been analysed in terms of complexity so far. In fact, we show PSPACE-completeness of all non-trivial standard decision problems for weak-admissible based semantics. We then investigate potential tractable fragments and show that restricting the frameworks under consideration to certain graph-classes significantly reduces the complexity. We also show that weak-admissibility based extensions can be computed by dividing the given graph into its strongly connected components (SCCs). This technique ensures that the bottleneck when computing extensions is the size of the largest SCC instead of the size of the graph itself and therefore contributes to the search for fixed-parameter tractable implementations for reasoning with weak admissibility.

KR Conference 2022 Conference Paper

Rediscovering Argumentation Principles Utilizing Collective Attacks

• Wolfgang Dvořák
• Matthias König
• Markus Ulbricht
• Stefan Woltran

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 analysing 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 give a novel parameterized tractability result for verifying preferred extensions.

AIJ Journal 2022 Journal Article

Shedding new light on the foundations of abstract argumentation: Modularization and weak admissibility

• Ringo Baumann
• Gerhard Brewka
• Markus Ulbricht

KR Conference 2021 Conference Paper

Choices and their Consequences - Explaining Acceptable Sets in Abstract Argumentation Frameworks

• Ringo Baumann
• Markus Ulbricht

We develop a notion of explanations for acceptance of arguments in an abstract argumentation framework. To this end we show that extensions returned by Dung's standard semantics can be decomposed into i) non-deterministic choices made on even cycles of the given argumentation graph and then ii) deterministic iteration of the so-called characteristic function. Naturally, the choice made in i) can be viewed as an explanation for the corresponding extension and thus the arguments it contains. We proceed to propose desirable criteria a reasonable notion of an explanation should satisfy. We present an exhaustive study of the newly introduced notion w. r. t. these criteria. Finally some interesting decision problems arise from our analysis and we examine their computational complexity, obtaining some surprising tractability results.

IJCAI Conference 2021 Conference Paper

Comparing Weak Admissibility Semantics to their Dung-style Counterparts (Extended Abstract)

• Ringo Baumann
• Gerhard Brewka
• Markus Ulbricht

Semantics based on weak admissibility were recently introduced to overcome a problem with self-defeating arguments that has not been solved for more than 25 years. The recursive definition of weak admissibility mainly relies on the notion of a reduct regarding a set E which only contains arguments which are neither in E, nor attacked by E. At first glance the reduct seems to be tailored for the weaker versions of Dung-style semantics only. In this paper we show that standard Dung semantics can be naturally reformulated using the reduct revealing that this concept is already implicit. We further identify a new abstract principle for semantics, so-called modularization describing how to obtain further extensions given an initial one. Its importance for the study of abstract argumentation semantics is shown by its ability to alternatively characterize classical and non-classical semantics.

IJCAI Conference 2021 Conference Paper

On Cycles, Attackers and Supporters --- A Contribution to The Investigation of Dynamics in Abstract Argumentation

• Ringo Baumann
• Markus Ulbricht

Abstract argumentation as defined by Dung in his seminal 1995 paper is by now a major research area in knowledge representation and reasoning. Dynamics of abstract argumentation frameworks (AFs) as well as syntactical consequences of semantical facts of them are the central issues of this paper. The first main part is engaged with the systematical study of the influence of attackers and supporters regarding the acceptability status of whole sets and/or single arguments. In particular, we investigate the impact of addition or removal of arguments, a line of research that has been around for more than a decade. Apart from entirely new results, we revisit, generalize and sum up similar results from the literature. To gain a comprehensive formal and intuitive understanding of the behavior of AFs we put special effort in comparing different kind of semantics. We concentrate on classical admissibility-based semantics and also give pointers to semantics based on naivity and weak admissibility, a recently introduced mediating approach. In the second main part we show how to infer syntactical information from semantical one. For instance, it is well-known that if a finite AF possesses no stable extension, then it has to contain an odd-cycle. In this paper, we even present a characterization of this issue. Moreover, we show that the change of the number of extensions if adding or removing an argument allows to conclude the existence of certain even or odd cycles in the considered AF without having further information.

KR Conference 2021 Short Paper

On the Maximal Number of Complete Extensions in Abstract Argumentation Frameworks

• Markus Ulbricht

Abstract argumentation frameworks are by now a major research area in knowledge representation and reasoning. Various aspects of AFs have been extensively studied over the last 25 years. Contributing to understanding the expressive power of AFs, researchers found lower and upper bounds for the maximal number of extensions, that is, acceptable points of view, in AFs. One of the classical and most important concepts in AFs are so-called complete extensions. Surprisingly, the exact bound for the maximal number of complete extensions in an AF has not yet been formally established, although there is a reasonable conjecture tracing back at least to 2015. Recently the notion of modularization was introduced and it was shown that this concept plays a key role for the understanding of relations between semantics as well as intrinsic properties. In this paper, we will use this property to give a formal proof of the conjecture regarding complete semantics.

AAAI Conference 2021 Conference Paper

Recursion in Abstract Argumentation is Hard — On the Complexity of Semantics Based on Weak Admissibility

• Wolfgang Dvořák
• Markus Ulbricht
• Stefan Woltran

We study the computational complexity of abstract argumentation semantics based on weak admissibility, a recently introduced concept to deal with arguments of self-defeating nature. Our results reveal that semantics based on weak admissibility are of much higher complexity (under typical assumptions) compared to all argumentation semantics which have been analysed in terms of complexity so far. In fact, we show PSPACE-completeness of all non-trivial standard decision problems for weak-admissible based semantics. We then investigate potential tractable fragments and show that restricting the frameworks under consideration to certain graphclasses significantly reduces the complexity. As a strategy for implementation we also provide a polynomial-time reduction to DATALOG with stratified negation.

AAAI Conference 2021 Conference Paper

Strong Explanations in Abstract Argumentation

• Markus Ulbricht
• Johannes P. Wallner

Abstract argumentation constitutes both a major research strand and a key approach that provides the core reasoning engine for a multitude of formalisms in computational argumentation in AI. Reasoning in abstract argumentation is carried out by viewing arguments and their relationships as abstract entities, with argumentation frameworks (AFs) being the most commonly used abstract formalism. Argumentation semantics then drive the reasoning by specifying formal criteria on which sets of arguments, called extensions, can be deemed as jointly acceptable. Such extensions provide a basic way of explaining argumentative acceptance. Inspired by recent research, we present a more general class of explanations: in this paper we propose and study so-called strong explanations for explaining argumentative acceptance in AFs. A strong explanation is a set of arguments such that a target set of arguments is acceptable in each subframework containing the explaining set. We formally show that strong explanations form a larger class than extensions, in particular giving the possibility of having smaller explanations. Moreover, assuming basic properties, we show that any explanation strategy, broadly construed, is a strong explanation. We show that the increase in variety of strong explanations comes with a computational trade-off: we provide an in-depth analysis of the associated complexity, showing a jump in the polynomial hierarchy compared to extensions.

KR Conference 2020 Conference Paper

Comparing Weak Admissibility Semantics to their Dung-style Counterparts -- Reduct, Modularization, and Strong Equivalence in Abstract Argumentation

• Ringo Baumann
• Gerhard Brewka
• Markus Ulbricht

Semantics based on weak admissibility were recently introduced to overcome a problem with self-defeating arguments that has not been solved for more than 25 years. The recursive definition of weak admissibility mainly relies on the notion of a reduct regarding a set E which only contains arguments which are neither in E, nor attacked by E. At first glance the reduct seems to be tailored for the weaker versions of Dung-style semantics only. In this paper we show that standard Dung semantics can be naturally reformulated using the reduct revealing that this concept is already implicit. We further identify a new abstract principle for semantics, so-called modularization describing how to obtain further extensions given an initial one. Its importance for the study of abstract argumentation semantics is shown by its ability to alternatively characterize classical and non-classical semantics. Moreover, we tackle the notion of strong equivalence via characterizing kernels and give a complete classification of the weak versions regarding well-known properties and postulates known from the literature.

AIJ Journal 2020 Journal Article

Handling and measuring inconsistency in non-monotonic logics

• Markus Ulbricht
• Matthias Thimm
• Gerhard Brewka

AAAI Conference 2020 Conference Paper

Revisiting the Foundations of Abstract Argumentation – Semantics Based on Weak Admissibility and Weak Defense

• Ringo Baumann
• Gerhard Brewka
• Markus Ulbricht

In his seminal 1995 paper, Dung paved the way for abstract argumentation, a by now major research area in knowledge representation. He pointed out that there is a problematic issue with self-defeating arguments underlying all traditional semantics. A self-defeat occurs if an argument attacks itself either directly or indirectly via an odd attack loop, unless the loop is broken up by some argument attacking the loop from outside. Motivated by the fact that such arguments represent self-contradictory or paradoxical arguments, he asked for reasonable semantics which overcome the problem that such arguments may indeed invalidate any argument they attack. This paper tackles this problem from scratch. More precisely, instead of continuing to use previous concepts defined by Dung we provide new foundations for abstract argumentation, so-called weak admissibility and weak defense. After showing that these key concepts are compatible as in the classical case we introduce new versions of the classical Dung-style semantics including complete, preferred and grounded semantics. We provide a rigorous study of these new concepts including interrelationships as well as the relations to their Dung-style counterparts. The newly introduced semantics overcome the issue with self-defeating arguments, and they are semantically insensitive to syntactic deletions of self-attacking arguments, a special case of self-defeat.

JAIR Journal 2019 Journal Article

If Nothing Is Accepted -- Repairing Argumentation Frameworks

• Markus Ulbricht
• Ringo Baumann

Conflicting information in an agent's knowledge base may lead to a semantical defect, that is, a situation where it is impossible to draw any plausible conclusion. Finding out the reasons for the observed inconsistency (so-called diagnoses) and/or restoring consistency in a certain minimal way (so-called repairs) are frequently occurring issues in knowledge representation and reasoning. In this article we provide a series of first results for these problems in the context of abstract argumentation theory regarding the two most important reasoning modes, namely credulous as well as sceptical acceptance. Our analysis includes the following problems regarding minimal repairs/diagnoses: existence, verification, computation of one and enumeration of all solutions. The latter problem is tackled with a version of the so-called hitting set duality first introduced by Raymond Reiter in 1987. It turns out that grounded semantics plays an outstanding role not only in terms of complexity, but also as a useful tool to reduce the search space for diagnoses regarding other semantics.

AIJ Journal 2019 Journal Article

Strong inconsistency

• Gerhard Brewka
• Matthias Thimm
• Markus Ulbricht

KR Conference 2018 Conference Paper

If Nothing is Accepted – Repairing Argumentation Frameworks

• Ringo Baumann
• Markus Ulbricht

probabilistic conditional logic (Potyka and Thimm 2014) to mention a few. Conflicting information in an agent’s knowledge base may lead to a semantical defect, that is, a situation where it is impossible to draw any plausible conclusion. Finding out the reasons for the observed inconsistency (so-called diagnosis) and/or restoring consistency in a certain minimal way (socalled repairs) are frequently occurring issues in knowledge representation and reasoning. In this paper we provide a series of first results for these problems in the context of abstract argumentation theory regarding the two most important reasoning modes, namely credulous as well as sceptical acceptance. Our analysis includes the following problems regarding minimal repairs/diagnosis: existence, verification, computation of one and enumeration of all solutions. The latter problem is tackled with a version of the so-called hitting set duality first introduced by Raymond Reiter in 1987. It turns out that grounded semantics plays an outstanding role not only in terms of complexity, but also as a useful tool to reduce the search space for diagnosis regarding other semantics. 1 In this paper we focus on the non-monotonic theory of abstract argumentation (Dung 1995). More precisely, we consider an abstract argumentation framework (AF) as an agent’s knowledge base and the associated extensions correspond to her beliefs (cf. (Coste-Marquis et al. 2014; Nouioua and Würbel 2014; Diller et al. 2018) for similar approaches). In brief, Dung-style AFs consist of arguments and attacks which are treated as primitives, i. e., the internal structure of arguments is not considered. The major focus is on resolving conflicts. To this end a variety of semantics have been defined, each of them specifying acceptable sets of arguments, so-called extensions, in a particular way. The starting point of our study is a semantical defect of an agent’s AF which prevents her from drawing any plausible conclusion in the sense that nothing is accepted. Our aim is to obtain an agent which is able to act. Therefore we want to know what are minimal diagnoses of the given knowledge base, i. e., which parts are causing the semantical defect. The knowledge about these diagnoses may make it easier to decide what to do next. For instance, a certain minimal diagnosis may consist of arguments which are somehow out of date in comparison to the others. Consequently, one may tend to discard these arguments. This is why our repair approach focusses on removal of certain arguments. In general, it is easily conceivable that one may create a certain internal hierarchy over the stored arguments encoding the willingness to drop them. For instance, let us assume that dropping either the argument A1 or the argument A2 represent minimal repairs. Let us further assume that A1 represents ”Do not drive over the lawn, because this would destroy the lawn. ” and A2 stands for “Drive over the lawn, whenever you may save lifes with this action. ” In this situation it might be reasonable to drop A1.

AAAI Conference 2018 Conference Paper

Measuring Strong Inconsistency

• Markus Ulbricht
• Matthias Thimm
• Gerhard Brewka

We address the issue of quantitatively assessing the severity of inconsistencies in nonmonotonic frameworks. While measuring inconsistency in classical logics has been investigated for some time now, taking the nonmonotonicity into account poses new challenges. In order to tackle them, we focus on the structure of minimal strongly K-inconsistent subsets of a knowledge base K—a generalization of minimal inconsistency to arbitrary, possibly nonmonotonic, frameworks. We propose measures based on this notion and investigate their behavior in a nonmonotonic setting by revisiting existing rationality postulates, analyzing the compliance of the proposed measures with these postulates, and by investigating their computational complexity.

IJCAI Conference 2017 Conference Paper

Strong Inconsistency in Nonmonotonic Reasoning

• Gerhard Brewka
• Matthias Thimm
• Markus Ulbricht

Minimal inconsistent subsets of knowledge bases play an important role in classical logics, most notably for repair and inconsistency measurement. It turns out that for nonmonotonic reasoning a stronger notion is needed. In this paper we develop such a notion, called strong inconsistency. We show that—in an arbitrary logic, monotonic or not—minimal strongly inconsistent subsets play the same role as minimal inconsistent subsets in classical reasoning. In particular, we show that the well-known classical duality between hitting sets of minimal inconsistent subsets and maximal consistent subsets generalizes to arbitrary logics if the strong notion of inconsistency is used. We investigate the complexity of various related reasoning problems and present a generic algorithm for computing minimal strongly inconsistent subsets of a knowledge base. We also demonstrate the potential of our new notion for applications, focusing on repair and inconsistency measurement.