KR Conference 2014 Conference Paper
- Paul E. Dunne
- Wolfgang Dvořák
- Thomas Linsbichler
- Stefan Woltran
and gives the collection of all possible sets of extensions an AF can possess under semantics σ. We shall focus on several important semantics namely naive, preferred, semistable, stage, stable, and complete semantics (Dung 1995; Verheij 1996; Caminada, Carnielli, and Dunne 2012) and aim at finding simple criteria to decide whether a set S is contained in Σσ. For instance, we will show that each S ∈ Σpref satisfies the condition that for each pair of distinct sets A and B from S there is at least one a ∈ A and b ∈ B such that a, b do not occur together in any set in S. Thus, for instance, S = {{a, b}, {c, d}, {a, c}, {b, d}} is part of the signature Σpref while neither S ∪ {{a, d}} nor S ∪ {{b, c}} are. This fact can be exploited in a search procedure for enumerating preferred extensions: assume for a given AF F, the three extensions from S have already been calculated as preferred extensions of F. The procedure can now restrict the search space to find further extensions of F (if they exist) to sets with at least one argument different from a, b, c, and d. The problem we study here is also essential in many other aspects. First, our results are important for constructing AFs. Indeed, knowing whether a set S is contained in Σσ is a necessary condition which should be checked before actually looking for an AF F which realizes S under σ, i. e. σ(F) = S. This is of high importance when dynamic aspects of argumentation are considered (Falappa et al. 2011). As an example, suppose a framework F possesses as its σ-extensions a set S and one asks for an adaptation of the framework F such that its σ-extensions are given by S ∪ {E}, i. e. one extension is to be added. The addition of E to S may, for instance, be desired by some agent on the grounds that E contains some subset of arguments which it wishes to be collectively accepted by other agents: no extension in S, however, provides support for the subset of interest to be considered justifiable. Furthermore the agent wishing to add E is reluctant to jeopardize the chance of this happening if the modified AF is such that some existing element of S ceases to be an extension: such an outcome being likely to prejudice other agents against agreeing to changes which admit E. Before considering the adapted framework’s structure, it is obviously crucial to know whether an appropriate framework exists at all, i. e. whether S ∪ {E} ∈ Σσ. In a recent paper on revision of AF s (Coste-Marquis et al. 2013), the authors circumvent this issue by allowing revision to result in a set of AFs such that The study of extension-based semantics within the seminal abstract argumentation model of Dung has largely focused on definitional, algorithmic and complexity issues. In contrast, matters relating to comparisons of representational limits, in particular, the extent to which given collections of extensions are expressible within the formalism, have been under-developed. As such, little is known concerning conditions under which a candidate set of subsets of arguments are “realistic” in the sense that they correspond to the extensions of some argumentation framework AF for a semantics of interest. In this paper we present a formal basis for examining extension-based semantics in terms of the sets of extensions that these may express within a single AF. We provide a number of characterization theorems which guarantee the existence of AFs whose set of extensions satisfy specific conditions and derive preliminary complexity results for decision problems that require such characterizations.