Search

Abstract We tackle the problem of expressing incomplete knowledge in abstract argumentation frameworks originally introduced by Dung [26]. In applications, incomplete argumentation frameworks may arise as intermediate states in an elicitation process, or when merging different beliefs about an argumentation framework's state, or in cases where complete information cannot be obtained. We consider two specific models of incomplete argumentation frameworks, one focusing on attack incompleteness and the other on argument incompleteness, and we also provide a general model of incomplete argumentation framework that subsumes both specific models. In these three models, we study the computational complexity of variants of the verification problem with respect to six common semantics of argumentation frameworks: the conflict-free, admissible, stable, complete, grounded, and preferred semantics. We provide a full complexity map covering all three models and these six semantics. Our main result shows that the complexity of verifying the preferred semantics rises from coNP- to Σ 2 p -completeness when allowing uncertainty about either attacks or arguments, or both. [ABSTRACT FROM AUTHOR]

Over the last decade, several extensions of Dung's Abstract Argumentation Frameworks ( AF s) have been introduced in the literature. Some of these extensions concern the nature of the attack relation, such as the consideration of recursive attacks, whereas others incorporate additional interactions, such as a support relation. Recently, the Attack–Support Argumentation Framework ( ASAF ) was proposed, which accounts for recursive attacks and supports, attacks to supports and supports to attacks, at any level, where the support relation is interpreted as necessity . Currently, to determine the accepted elements of an ASAF (which may be arguments, attacks, and supports) it is required to translate such an ASAF into a Dung's AF . In this work, we provide a formal characterization of acceptability semantics directly on the ASAF , without requiring such a translation. We prove that our characterization is sound since it satisfies different results from Dung's argumentation theory; moreover, we formally show that the approach proposed here for addressing acceptability is equivalent to the preexisting one, in which the ASAF was translated into an AF . Also, we formalize the relationship between the ASAF and other frameworks on which it is inspired: the Argumentation Framework with Recursive Attacks ( AFRA ) and the Argumentation Framework with Necessities ( AFN ). [ABSTRACT FROM AUTHOR]

Different semantics of abstract Argumentation Frameworks (AFs) provide different levels of decisiveness for reasoning about the acceptability of conflicting arguments. The stable semantics is useful for applications requiring a high level of decisiveness, as it assigns to each argument the label “accepted” or the label “rejected”. Unfortunately, stable labellings are not guaranteed to exist, thus raising the question as to which parts of AFs are responsible for the non-existence. In this paper, we address this question by investigating a more general question concerning preferred labellings (which may be less decisive than stable labellings but are always guaranteed to exist), namely why a given preferred labelling may not be stable and thus undecided on some arguments. In particular, (1) we give various characterisations of parts of an AF, based on the given preferred labelling, and (2) we show that these parts are indeed responsible for the undecisiveness if the preferred labelling is not stable. We then use these characterisations to explain the non-existence of stable labellings. We present two types of characterisations, based on labellings that are more (or equally) committed than the given preferred labelling on the one hand, and based on the structure of the given AF on the other, and compare the respective AF parts deemed responsible. To prove that our characterisations indeed yield responsible parts, we use a notion of enforcement of labels through structural revision, by means of which the preferred labelling of the given AF can be turned into a stable labelling of the structurally revised AF. Rather than prescribing how this structural revision is carried out, we focus on the enforcement of labels and leave the engineering of the revision open to fulfil differing requirements of applications and information available to users. [ABSTRACT FROM AUTHOR]

Abstract dialectical frameworks have been proposed as a generalization of the abstract argumentation frameworks. The semantics of abstract dialectical frameworks is defined by identifying different classes of models. In this paper, we show that the semantics of abstract dialectical frameworks could naturally be defined based on simple notions of arguments and attacks like in abstract argumentation. This insight allows us to adapt directly the semantical concepts in abstract argumentation to abstract dialectical frameworks that not only capture the standard semantics of abstract dialectical frameworks, but also suggest other new semantics based on the idea of "rejection as assumption" (raa) (similar to the concept of "negation as assumption" in assumption-based argumentation and logic programming) like the well-founded semantics or the raa-preferential semantics. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of the dynamic enforcement of a constraint in an argumentation system. The system consists in (1) an argumentation framework, made up, notably, of a set of arguments and of an attack relation, (2) an evaluation semantics, and (3) the evaluation result, computed from (1) and (2). An agent may want another agent to consider a new attack, or to have a given argument accepted, or even to relax the definition of the semantics. A constraint on any of the three components is thus defined, and it has to be enforced in the system. The enforcement may result in changes on components of the system. The paper surveys existing approaches for the dynamic enforcement of a constraint and its consequences, and reveals challenging enforcement cases that remain to be investigated. [ABSTRACT FROM AUTHOR]

Several efficient SAT-based methods for computing the preferred extensions in (abstract) argumentation frameworks (AF) are proposed lately. However, only complete SAT solvers have been exploited so far. It is a natural question that how the appealing stochastic local search (SLS) approach could advance the performance. In this paper, we developed two SLS algorithms for computing the preferred extensions in AF, and a complete one which combines the strength of the better one with complete SAT solvers. Our first SLS algorithm Ite-CCAEP works by calling an SLS SAT solver Swcca in an iterative manner with adaptive heuristics. Our second SLS algorithm Inc-CCAEP realized an incremental version of Swcca, specially designed for computing the preferred extensions in AF. Though Ite-CCAEP and Inc-CCAEP do not guarantee completeness, they notably outperform a state-of-the-art solver consistently on most benchmarks with non-empty preferred extensions. Experimental results also show that Inc-CCAEP is more efficient than Ite-CCAEP, which inspired the design of a novel complete algorithm called CCASATEP that uses Inc-CCAEP as an efficient preprocessor. Further experiments show that CCASATEP is competitive to the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In many knowledge representation formalisms, a constructive semantics is defined based on sequential applications of rules or of a semantic operator. These constructions often share the property that rule applications must be delayed until it is safe to do so: until it is known that the condition that triggers the rule will continue to hold. This intuition occurs for instance in the well-founded semantics of logic programs and in autoepistemic logic. In this paper, we formally define the safety criterion algebraically. We study properties of so-called safe inductions and apply our theory to logic programming and autoepistemic logic. For the latter, we show that safe inductions manage to capture the intended meaning of a class of theories on which all classical constructive semantics fail. [ABSTRACT FROM AUTHOR]

Dung’s abstract argumentation provides us with a general framework to deal with argumentation, non-monotonic reasoning and logic programming. For the extension-based semantics, one of the basic principles is I-maximality which is in particular related with the notion of skeptical justification. Another one is directionality which can be employed for the study of dynamics of argumentation. In this paper, we introduce two new extension-based semantics into Dung’s abstract argumentation, called grounded-like semantics and initial semantics which satisfy the I-maximality and directionality principles. The initial semantics has many good properties and can be expected to play a central role in studying other extension-based semantics, such as admissible, complete and preferred semantics. [ABSTRACT FROM AUTHOR]

The question whether increased interaction among scientists is beneficial or harmful for their efficiency in acquiring knowledge has in recent years been tackled by means of agent-based models (ABMs) (e.g. Zollman 2007, 2010; Grim 2009; Grim et al. 2013). Nevertheless, the relevance of some of these results for actual scientific practice has been questioned in view of specific parameter choices used in the simulations (Rosenstock et al. 2016). In this paper we present a novel ABM that aims at tackling the same question, while representing scientific interaction in terms of argumentative exchange. In this way we examine the robustness of previously obtained results under different modeling choices. [ABSTRACT FROM AUTHOR]

We test different solvers dedicated to the solution of classical problems in Abstract Argumentation, as enumeration/existence of extensions, and sceptical/credulous acceptance of arguments. We handle a subset of the solvers tested in ICCMA15, and a superset of graphs used in the same competition. The goal is to provide considerations that can help future comparisons and competitions as ICCMA15. We offer a detailed report of this comparison from the point of view of different graphs, solvers, problems and timeouts. We show that the characteristics of graphs impact on the performance of solvers and on their final ranking. In addition, we extract other general considerations, e.g. reducing the computation timeout does not change the same ranking. [ABSTRACT FROM AUTHOR]

Abstract solvers are a quite recent method to uniformly describe algorithms in a rigorous formal way via graphs. Compared to traditional methods like pseudo-code descriptions, abstract solvers have several advantages. In particular, they provide a uniform formal representation that allows for precise comparisons of different algorithms. Recently, this new methodology has proven successful in declarative paradigms such as Propositional Satisfiability and Answer Set Programming. In this paper, we apply this machinery to Dung’s abstract argumentation frameworks. We first provide descriptions of several advanced algorithms for the preferred semantics in terms of abstract solvers. We also show how it is possible to obtain new abstract solutions by “combining” concepts of existing algorithms by means of combining abstract solvers. Then, we implemented a new solving procedure based on our findings in CEGARTIX, and call it CEGARTIX+. We finally show that CEGARTIX+ is competitive and complementary in its performance to CEGARTIX on benchmarks of the first and second argumentation competition. [ABSTRACT FROM AUTHOR]

Understanding the expressiveness of a formalism is undoubtedly an important part of understanding its possibilities and limitations. Translations between different formalisms have proven to be valuable tools for understanding this very expressiveness. In this work, we complement recent investigations of the intertranslatability of argumentation semantics for Dung's abstract argumentation frameworks. As our focus is on the expressiveness of argumentation semantics, we are not only interested in efficiently computable translations but also consider translations that might not (always) be efficiently computable. This allows us to provide translations between certain semantics, where under established complexity assumptions no efficiently computable translation exists. However, for some semantics we give strong translational impossibility results stating that even with arbitrary computational power we cannot in all situations translate one to the other. Finally, this allows us to draw a hierarchy for the expressiveness of argumentation semantics. [ABSTRACT FROM AUTHOR]

The simulation of mathematical reasoning has been a driving force throughout the history of Artificial Intelligence research. However, despite significant successes in computer mathematics, computers are not widely used by mathematicians apart from their quotidian applications. An oft-cited reason for this is that current computational systems cannot do mathematics in the way that humans do. We draw on two areas in which Automated Theorem Proving (ATP) is currently unlike human mathematics: firstly in a focus on soundness, rather than understandability of proof, and secondly in social aspects. Employing techniques and tools from argumentation to build a framework for mixed-initiative collaboration, we develop three complementary arcs. In the first arc – our theoretical model – we interpret the informal logic of mathematical discovery proposed by Lakatos, a philosopher of mathematics, through the lens of dialogue game theory and in particular as a dialogue game ranging over structures of argumentation. In our second arc – our abstraction level – we develop structured arguments, from which we induce abstract argumentation systems and compute the argumentation semantics to provide labelings of the acceptability status of each argument. The output from this stage corresponds to a final, or currently accepted proof artefact, which can be viewed alongside its historical development. Finally, in the third arc – our computational model – we show how each of these formal steps is available in implementation. In an appendix, we demonstrate our approach with a formal, implemented example of real-world mathematical collaboration. We conclude the paper with reflections on our mixed-initiative collaborative approach. [ABSTRACT FROM AUTHOR]

Dung's argumentation frameworks are adopted in a variety of applications, from argument-mining, to intelligence analysis and legal reasoning. Despite this broad spectrum of already existing applications, the mostly adopted solver-in virtue of its simplicity-is far from being comparable to the current state-of-the-art solvers. On the other hand, most of the current state-of-the-art solvers are far too complicated to be deployed in real-world settings. In this paper we provide and extensive description of jArgSemSAT, a Java re-implementation of ArgSemSAT. ArgSemSAT represents the best single solver for argumentation semantics with the highest level of computational complexity. We show that jArgSemSAT can be easily integrated in existing argumentation systems (1) as an off-the-shelf, standalone, library; (2) as a Tweety compatible library; and (3) as a fast and robust web service freely available on the Web. Our large experimental analysis shows that despite being written in Java, jArgSemSAT would have scored in most of the cases among the three bests solvers for the two semantics with highest computational complexity 'Stable and Preferred' in the last competition on computational models of argumentation. [ABSTRACT FROM AUTHOR]

We propose a new paradigm for reasoning over abstract argumentation frameworks where the " who said what " relation, associating each argument with the set of agents who claimed it, is taken into account, along with possible information on the trustworthiness of the agents. Specifically, we extend the traditional reasoning based on the classical verification and acceptance problems and introduce a reasoning paradigm investigating how the "robustness" of a set of arguments S (in terms of being an extension or not) or of an argument a (in terms of being accepted or not) can change if what has been claimed by some agents is ignored (as if these agents were removed from the dispute modeled by the argumentation framework). In this regard, we address the problems of searching the "minimum extent" of the removal of agents that makes a set S an extension or an argument a accepted. Compared with the case where only the " yes/no " answer of the traditional verification and acceptance problems are available, the knowledge of such a minimum provides the analyst with further insights allowing them to better judge the robustness of S and a. We consider the above minimization problems in two variants, where the agents are associated with a measure of their trustworthiness or not and provide a thorough characterization of their complexities. [ABSTRACT FROM AUTHOR]

Abstract argumentation frameworks ( af s) are one of the most studied formalisms in AI and are formally simple tools to model arguments and their conflicts. The evaluation of an af yields extensions (with respect to a semantics) representing alternative acceptable sets of arguments. For many of the available semantics two effects can be observed: there exist arguments in the given af that do not appear in any extension (rejected arguments); there exist pairs of arguments that do not occur jointly in any extension, albeit there is no explicit conflict between them in the given af (implicit conflicts). In this paper, we investigate the question whether these situations are only a side-effect of particular af s, or whether rejected arguments and implicit conflicts contribute to the expressiveness of the actual semantics. We do so by introducing two subclasses of af s, namely compact and analytic frameworks. The former class contains af s that do not contain rejected arguments with respect to a semantics at hand; af s from the latter class are free of implicit conflicts for a given semantics. Frameworks that are contained in both classes would be natural candidates towards normal forms for af s since they minimize the number of arguments on the one hand, and on the other hand maximize the information on conflicts, a fact that might help argumentation systems to evaluate af s more efficiently. Our main results show that under stable, preferred, semi-stable, and stage semantics neither of the classes is able to capture the full expressive power of these semantics; we thus also refute a recent conjecture by Baumann et al. on implicit conflicts. Moreover, we give a detailed complexity analysis for the problem of deciding whether an af is compact, resp. analytic. Finally, we also study the signature of these subclasses for the mentioned semantics and shed light on the question under which circumstances an arbitrary framework can be transformed into an equivalent compact, resp. analytic, af . [ABSTRACT FROM AUTHOR]

Human and artificial reasoning has to deal with uncertain environments. Ideally, probabilistic information is available. However, sometimes probabilistic information may not be precise or it is missing entirely. In such cases we reason with higher-order uncertainty. Formal argumentation is one of the leading formal methods to model defeasible reasoning in artificial intelligence, in particular in the tradition of Dung's abstract argumentation. Also from the perspective of cognition, reasoning has been considered as argumentative and social in nature, for instance by Mercier and Sperber. In this paper we use formal argumentation to provide a framework for reasoning with higher-order uncertainty. Our approach builds strongly on Haenni's system of probabilistic argumentation, but enhances it in several ways. First, we integrate it with deductive argumentation, both in terms of the representation of arguments and attacks, and in terms of utilizing abstract argumentation semantics for selecting some out of a set of possibly conflicting arguments. We show how our system can be adjusted to perform well under the so-called rationality postulates of formal argumentation. Second, we provide several notions of argument strength which are studied both meta-theoretically and empirically. In this way the paper contributes a formal model of reasoning with higher-order uncertainty with possible applications in artificial intelligence and human cognition., Competing Interests: The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest., (Copyright © 2023 Straßer and Michajlova.)