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.

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.

Syntax splitting, first introduced by Parikh in 1999, is a natural and desirable property of KR systems. Syntax splitting combines two aspects: it requires that the outcome of a certain epistemic operation should only depend on relevant parts of the underlying knowledge base, where relevance is given a syntactic interpretation (relevance). It also requires that strengthening antecedents by irrelevant information should have no influence on the obtained conclusions (independence). In the context of belief revision the study of syntax splitting already proved useful and led to numerous new insights. In this paper we analyse syntax splitting in a different setting, namely nonmonotonic reasoning based on conditional knowledge bases. More precisely, we analyse inductive inference operators which, like system P, system Z, or the more recent c-inference, generate an inference relation from a conditional knowledge base. We axiomatize the two aforementioned aspects of syntax splitting, relevance and independence, as properties of such inductive inference operators. Our main results show that system P and system Z, whilst satisfying relevance, fail to satisfy independence. C-inference, in contrast, turns out to satisfy both relevance and independence and thus fully complies with syntax splitting.

Abstract Powerful formalisms for abstract argumentation have been proposed, among them abstract dialectical frameworks (ADFs) that allow for a succinct and flexible specification of the relationship between arguments and the GRAPPA framework which allows argumentation scenarios to be represented as arbitrary edge-labeled graphs. The complexity of ADFs and GRAPPA is located beyond NP and ranges up to the third level of the polynomial hierarchy. The combined complexity of Answer Set Programming (ASP) exactly matches this complexity when programs are restricted to predicates of bounded arity. In this paper, we exploit this coincidence and present novel efficient translations from ADFs and GRAPPA to ASP. More specifically, we provide reductions for the five main ADF semantics of admissible, complete, preferred, grounded, and stable interpretations, and exemplify how these reductions need to be adapted for GRAPPA for the admissible, complete, and preferred semantics.

This paper continues the rather recent line of research on the dynamics of non-monotonic formalisms. In particular, we consider semantic changes in Dung’s abstract argumentation formalism. One of the most studied problems in this context is the so-called enforcing problem which is concerned with manipulating argumentation frameworks (AFs) such that a certain desired set of arguments becomes an extension. Here we study the inverse problem, namely the extension removal problem: is it possible – and if so how – to modify a given argumentation framework in such a way that certain undesired extensions are no longer generated? Analogously to the well known AGM paradigm we develop an axiomatic approach to the removal problem, i.e. a certain set of axioms will determine suitable manipulations. Although contraction (that is, the elimination of a particular belief) is conceptually quite different from extension removal, there are surprisingly deep connections between the two: it turns out that postulates for removal can be directly obtained as reformulations of the AGM contraction postulates. We prove a series of formal results including conditional and unconditional existence and semantical uniqueness of removal operators as well as various impossibility results – and show possible ways out.

Abstract Dialectical Frameworks (ADFs) generalize Dung's argumentation frameworks allowing various relationships among arguments to be expressed in a systematic way. We further generalize ADFs so as to accommodate arbitrary acceptance degrees for the arguments. This makes ADFs applicable in domains where both the initial status of arguments and their relationship are only insufficiently specified by Boolean functions. We define all standard ADF semantics for the weighted case, including grounded, preferred and stable semantics. We illustrate our approach using acceptance degrees from the unit interval and show how other valuation structures can be integrated. In each case it is sufficient to specify how the generalized acceptance conditions are represented by formulas, and to specify the information ordering underlying the characteristic ADF operator. We also present complexity results for problems related to weighted ADFs.

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 kb-inconsistent subsets of a knowledge base kb---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.

Notions of equivalence that are stronger than standard equivalence in the sense that they also take potential modifications of the available information into account have received considerable interest in non-monotonic reasoning. In this article, we focus on equivalence notions in argumentation. More specifically, we establish a number of new results about the relationships among various equivalence notions for Dung argumentation frameworks that are located between strong equivalence (Oikarinen and Woltran, 2011, Art. Intell, 175, 1985–2009) and standard equivalence. We provide the complete picture for this variety of equivalence relations (which we call the equivalence zoo) for stable, preferred, admissible and complete semantics.

Powerful formalisms for abstract argumentation have been proposed. Their complexity is often located beyond NP and ranges up to the third level of the polynomial hierarchy. The combined complexity of Answer-Set Programming (ASP) exactly matches this complexity when programs are restricted to predicates of bounded arity. In this paper, we exploit this coincidence and present novel efficient translations from abstract dialectical frameworks (ADFs) and GRAPPA to ASP.We also empirically compare our approach to other systems for ADF reasoning and report promising results.

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.

AGM theory is the most influential formal account of belief revision. Nevertheless, there are some issues with the original proposal. In particular, Parikh has pointed out that completely irrelevant information may be affected in AGM revision. To remedy this, he proposed an additional axiom (P) aiming to capture (ir)relevance by a notion of syntax splitting. In this paper we generalize syntax splitting from logical sentences to epistemic states, a step which is necessary to cover iterated revision. The generalization is based on the notion of marginalization of epistemic states. Furthermore, we study epistemic syntax splitting in the context of ordinal conditional functions. Our approach substantially generalizes the semantical treatment of (P) in terms of faithful preorders recently presented by Peppas and colleagues.

In this paper we introduce a new approach for revising and merging consistent Horn formulae under minimal model semantics. Our approach is translation-based in the following sense: we generate a propositional encoding capturing both the syntax of the original Horn formulae (the clauses which appear or not in them) and their semantics (their minimal models). We can then use any classical revision or merging operator to perform belief change on the encoding. The resulting propositional theory is then translated back into a Horn formula. We identify some specific operators which guarantee a particular kind of minimal change. A unique feature of our approach is that it allows us to control whether minimality of change primarily relates to the syntax or to the minimal model semantics of the Horn formula. We give an axiomatic characterization of minimal change on the minimal model for this new setting, and we show that some specific translation-based revision and merging operators satisfy our postulates.

In this paper we describe asprin, a general, flexible, and extensible framework for handling preferences among the stable models of a logic program. We show how complex preference relations can be specified through user-defined preference types and their arguments. We describe how preference specifications are handled internally by so-called preference programs, which are used for dominance testing. We also give algorithms for computing one, or all, optimal stable models of a logic program. Notably, our algorithms depend on the complexity of the dominance tests and make use of multi-shot answer set solving technology.

We show in this paper how managed multi-context systems (mMCS) can be turned into a reactive formalism suitable for continuous reasoning in dynamic environments. We extend mMCS with (abstract) sensors and define the notion of a run of the extended systems. We then show how typical problems arising in online reasoning can be addressed: handling potentially inconsistent sensor input, modeling intelligent forms of forgetting, and controlling the reasoning effort spent by contexts. We also investigate the complexity of some important related decision problems.

Graphical models are widely used in argumentation to visualize relationships among propositions or arguments. The intuitive meaning of the links in the graphs is typically expressed using labels of various kinds. In this paper we introduce a general semantical framework for assigning a precise meaning to labelled argument graphs which makes them suitable for automatic evaluation. Our approach rests on the notion of explicit acceptance conditions, as first studied in Abstract Dialectical Frameworks (ADFs). The acceptance conditions used here are functions from multisets of labels to truth values. We define various Dung style semantics for argument graphs. We also introduce a pattern language for specifying acceptance functions. Moreover, we show how argument graphs can be compiled to ADFs, thus providing an automatic evaluation tool via existing ADF implementations. Finally, we also discuss complexity issues.

One criticism often advanced against abstract argumentation frameworks (AFs), is that these consider only one form of interaction between atomic arguments: specifically that an argument attacks another. Attempts to broaden the class of relationships include bipolar frameworks, where arguments support others, and abstract dialectical frameworks (ADFs). The latter, allow of an argument, x, to be predicated on a given propositional function, Cx, dependent on the corresponding acceptance of its parents, i.e. those y for which 〈y, x〉 occurs. Although offering a richly expressive formalism subsuming both standard and bipolar AFs, an issue that arises with ADFs is whether this expressiveness is achieved in a manner that would be infeasible within standard AFs. Can the semantics used in ADFs be mapped to some AF semantics? How many arguments are needed in an AF to simulate an ADF? We show that (in a formally defined sense) any ADF can be simulated by an AF of similar size and that this translation can be realised by a polynomial time algorithm.

We study methods to specify preferences among subsets of a set (auniverse). The methods we focus on are of two types. The first one assumes the universe comes with a preference relation on its elements and attempts to lift that relation to subsets of the universe. That approach has limited expressivity but results in orderings that capture interesting general preference principles. The second method consists of developing formalisms allowing the user to specify "atomic" improvements, and generating from them preferences on the powerset of the universe. We show that the particular formalism we propose is expressive enough to capture the lifted preference relations of the first approach, and generalizes propositional CP-nets. We discuss the importance of domain-independent methods for specifying preferences on sets for knowledge representation formalisms, selecting the formalism of argumentation frameworks as an illustrative example.

This paper addresses the problem of revising a Dung-style argumentation framework by adding finitely many new arguments which may interact with old ones. We study the behavior of the extensions of the augmented argumentation frameworks, taking also into account possible changes of the underlying semantics (which may be interpreted as corresponding changes of proof standards). We show both possibility and impossibility results related to the problem of enforcing a desired set of arguments. Furthermore, we prove some monotonicity results for a special class of expansions with respect to the cardinality of the set of extensions and the justification state.

Carneades is a rather general framework for argumentation. Unlike many other approaches, Carneades captures a number of aspects, like proof burdens, proof standards etc., which are of central importance, in particular in legal argumentation.

Logic programs with ordered disjunction (LPODs) contain a new connective which allows representing alternative, ranked options for problem solutions in the heads of rules: A×B intuitively means that if possible A, but if A is not possible, then at least B. The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. We show how LPODs can be implemented using answer set solvers for normal programs. The implementation is based on a generator, which produces candidate answer sets and a tester which checks whether a given candidate is maximally preferred and produces a better candidate if it is not. We also discuss the complexity of reasoning tasks based on LPODs and possible applications.

1Computer Science Institute, University of Leipzig 2Institute of Information and Computing Sciences, Utrecht University 3Institute of Information and Computing Sciences, Utrecht University

We present a formal model of argumentation based on situation calculus which captures both the logical and the procedural aspects of argumentation processes. The logic is used to determine what is accepted by each agent participating in the discussion and by the group as a whole, on the basis of the speech acts performed during argumentation. Argumentation protocols, also called rules of order, describe declaratively which speech acts are legal in a particular state of the argumentation. We first discuss argumentation with fixed rules of order. Our model tolerates protocol violations but makes it possible to object to illegal actions. In realistic settings the rules of order themselves can at any time become the topic of the debate. We show how meta‐level argumentation of this kind can be modelled in what we call dynamic argument systems. To illustrate the notions introduced in the paper we present a reconstruction of Rescher's theory of formal disputation and a dynamic argument system with three levels which we use to discuss a murder case.

Default logic is one of the most popular approaches to model defeasible reasoning. Nevertheless, there are a number of problems with Reiter's original semantics that have led to the investigation of alternative approaches. In particular, Baral/Subrahmanian and Przymusinska/Przymusinski have investigated generalizations of well-founded semantics for normal logic programs to default logic. These generalizations have a number of interesting properties. Unfortunately, it turns out that in many realistic situations they are unable to draw any defeasible conclusions at all - which can hardly be viewed as satisfactory. We show how this difficulty can be solved by varying the fixed point operator underlying the semantics. We define a range of different semantics. All of them are correct wrt. safe conclusions under Reiter semantics, i.e. those conclusions with the same proof in all extensions. For the strongest semantics we have also completeness in the case of coherent default theories, i.e. default theories with at least one extension. The logics differ in the effort spent for determining potential conclusions. It turns out that they are at least as complex as original default logic. We show that our approach also leads to new semantics for normal and extended logic programs. Moreover, we define prioritized versions of the logics.

The paper describes an extension of well-founded semantics for logic programs with two types of negation. In this extension information about preferences between rules can be expressed in the logical language and derived dynamically. This is achieved by using a reserved predicate symbol and a naming technique. Conflicts among rules are resolved whenever possible on the basis of derived preference information. The well-founded conclusions of prioritized logic programs can be computed in polynomial time. A legal reasoning example illustrates the usefulness of the approach.

The paper begins with a critique of the Ginsberg/Smith approach to reasoning about action which is based on the notion of maximal consistent subsets of world descriptions. There are some deep difficulties with this approach due to a misconception of what is possible and what is not. Incomplete information about the actual state of the world may lead to counterintuitive conclusions about what is true after an action is performed. These problems were first discussed by Winslett, who presents an alternative formalization based on possible models. Her formalization solves problems with incomplete descriptions of the world. However, related problems caused by using disjunctive postconditions to model ambiguous actions remain unsolved. Moreover, Winslett does not take the effects of causality into account when determining the closeness of worlds. We present a novel formalization of actions that avoids these problems.