The concept of strong admissibility plays an important role in dialectical proof procedures for grounded semantics allowing, as it does, concise proofs that an argument belongs to the grounded extension without having necessarily to construct this extension in full. One consequence of this property is that strong admissibility (in contrast to grounded semantics) ceases to be a unique status semantics. In fact it is straightforward to construct examples for which the number of distinct strongly admissible sets is exponential in the number of arguments. We are interested in characterizing properties of collections of strongly admissible sets in the sense that any system describing the strongly admissible sets of an argument framework must satisfy particular criteria. In terms of previous studies, our concern is the signature and with conditions ensuring realizability. The principal result is to demonstrate that a system of sets describes the strongly admissible sets of some framework if and only if that system has the property of being decomposable.
The formal model of abstract argumentation proposed in the watershed paper of Dung  has given rise not only to a coherent and consistent view of argumentation semantics but also to a uniform basis against which issues in algorithmic and computational complexity can be gauged. In addition to the set-theoretic semantics formulated by Dung, a number of alternative forms have been promoted. One of these, strong admissibility is the subject of the present article.
The concept of strong admissibility was first introduced in the work of Baroni and Giacomin  and has subsequently been studied by Caminada and Dunne [6,7]. Strong admissibility is especially useful for showing that a particular argument is part of the grounded extension. As the grounded extension is the (unique) biggest strongly admissible set, showing membership of any strongly admissible set is sufficient to prove that the argument is in the grounded extension.
In this paper our aim is to examine the nature of strong admissibility from the perspective of signature and realizability. These concepts for argumentation semantics were introduced and analyzed in detail in Dunne et al. [10,11], one concern of their study being to characterize those subsets of sets of n arguments for which there is some af, , whose solution sets under a given semantics are exactly the set described. A detailed overview of work on realizability may be found in the survey article of Baumann .
This paper is structured as follows. First, in Section 2 we present some formal preliminaries regarding abstract argumentation and strong admissibility. In Section 3 the technical condition underpinning our results is presented and then, in Section 4 we present a necessary condition for a system of sets to be the strongly admissible sets of some af. The characterization is completed in Section 5 wherein the necessary condition presented in Section 4 is shown to be also sufficient. Conclusions and further directions are presented in Section 6.
In the current section, we briefly restate some of the basic concepts in formal argumentation theory, including strong admissibility. For current purposes, we restrict ourselves to finite argumentation frameworks. We note that the focus on finite structures is not imposed in Dung’s original work and some study of infinite frameworks has been carried out, e.g. on realizability by Baumann and Spanring , modelling and description of infinite systems in Baroni et al. .
(Dung ) An argumentation framework is a pair where is a finite set of entities, called arguments, and a binary relation on . For any we say that p attacks q if .
Let be an argumentation framework, and . We define as , as , as , and as . The set S is said to be conflict-free if . A set S is said to defend x iff . The characteristic function is defined as .
Let be an argumentation framework. A subset S of is said to be:
an admissible set if S is conflict-free and ;
a complete extension if S is conflict-free and ;
a grounded extension if S is the smallest (w.r.t. ⊆) complete extension;
a preferred extension if S is a maximal (w.r.t. ⊆) complete extension.
It is well known (being illustrated in Dung’s original paper ) that for any af, ,
The examples presented above are just a small selection of those approaches that have been studied. We refer the interested reader to the treatment of Baroni, Caminada and Giacomin  for a comprehensive overview. The concept of strong admissibility was first introduced by Baroni and Giacomin . For current purposes we will, however, apply the equivalent definition of Caminada .
Let be an argumentation framework. A subset S of is strongly admissible if every is defended by some , T being also strongly admissible.
It can be shown that each strongly admissible set is an admissible subset of the grounded extension .
3.Signatures and realizability
An arbitrary semantics, σ, describes a set of subsets of so that for an af, ,
The signature of a semantics σ, denoted is
The counterpart to the concept of signature is that of being realizable.
Let , that is to say a set of subsets of . The set is said to be realizable with respect to a semantics σ if there is an af, for which and .
Notice that in this definition we allow arguments which are not acceptable with respect to the conditions specified by σ: so-called auxiliary arguments. The form whereby such additional arguments are not permitted is dubbed “compact realizability” and has been studied (together with divers other formulations) in Baumann .
For an argumentation semantics, σ, describe necessary and sufficient conditions, , under which,
a. For all afs , holds. (signature)
b. For all that satisfy , there is an af for which . (realizable)
In the current work we consider the case of strong admissibility denoting the relevant semantics as .
We first introduce some further notational ideas.
As is standard we distinguish (the set of positive integers ) and (the set of non-negative integers ).
Let be a subset of . The set which we denote is the system formed by setting and for
We say that is -closed if , i.e. in the process just described since (by definition) and .
As a small example of the process of forming suppose we have
A final idea, is that of a decomposition of a system of sets.
Given a system of sets its r-partial decomposition, denoted is formed as an ordered sequence of subsets of which we denote with the pairwise disjoint, i.e. .
is formed from by applying the following process.
If then . Otherwise,
We say that is decomposable if for some
Again, as a small illustration, suppose that
Continuing this example, in order to form we must identify those minimal sets together with those single elements, x, for which . In the example we find these to be
Notice that , although in with cannot be included in : the reason being because of the set in . The element, 5, is first introduced in so any sets in containing 5 and some as yet unrecovered item (such as 7) cannot be built until 5 is available. If it were the case that then we could add to via .
The final stage of the decomposition of forms as
We stress the distinction between and : the former case describes the situation where either no further expansion (or any expansion whatsoever) via the process of Definition 8, is possible. Thus if then for all . Similarly, noting the requirement for new members of to be used when progressing from to , it is easily seen that whenever .
We further note the requirement that T witnessing is minimal with respect to ⊆, e.g. if y is a new element introduced in forming , and then could contain or or : in all three cases, however, would not contain . Similarly were then neither nor would be.
Two properties of decomposable systems are given in the next lemmata.
Let . For all , is unique.
Let have an r-partial decomposition
Choose to be the least value for which . Since it is the case that we must have some subset for which but (or vice-versa).
By definition indicates that, in addition to , we have , and no strict subset V of U for which and . Furthermore
We conclude that the r-partial decomposition of is unique. □
Let be the r-partial decomposition of and be
The partition simply follows the ordering by which individual elements of are added to so that,
Before presenting our main results it may be helpful to look at two example systems both of which are decomposable.
Consider defined as
We cannot defer adding to a later level: the definition states that since we are able to include in it is required to do so.
The system , is also decomposable, however, now the decomposition would be
It is also the case that both systems of sets are in as can easily be seen by inspecting Fig. 2.
The implied partitions from Lemma 2 being
Applying the process described in Definition 8 would yield
Were the set to be added the resulting system would be decomposable. Applying the process described in Definition 8 would then yield
4.Strongly admissible systems are decomposable
With the concept of decomposability we obtain Theorem 1. We note that the partition structure and its properties in relationship to the characteristic function are used (although not explicity phrased as such) in the algorithm of Caminada and Dunne  by which verification of a set as strongly admissible is shown to be decidable in polynomial time.
Let be a finite set of n arguments and .
If then is decomposable.
Consider any and let be any af witnessing the realizability of , i.e. for which .
To begin consider the following partition of
Now suppose we continue this construction relative to elements (, ) already built (via the template specified in Definition 8) and the system . Consider which sets would be included in . We have whenever and
We now argue that for all k, the proposition, holds, where
To see this is the case, notice that treats as a sequence of sets built by adding single arguments, y, (according to the partition described earlier) to (minimal) strongly admissible sets, S, that defend y, i.e. have . Noting the closure of under set union, so that and leads to , applying the closure operation to ensures that all are also in .
We have already shown that and hold.
Suppose, as an inductive hypothesis, we have demonstrated for all for some (t being the number of classes in the partition of from Lemma 2).
Consider . By definition, contains and (from the construction) no argument occurs in
We have shown,
If we look at the case from Fig. 1, we had as,
5.Decomposable systems are strongly admissible
We now complete the characterization of strong admissibility, the first part of which was demonstrated in Theorem 1 by showing that any system of sets which is decomposable is in , i.e. there is an af, , for which . We need some additional preliminaries.
Given and define to be the subset of for which if is conflict-free, and for all strict subsets T of S .
Let all of whose members are incomparable, i.e. if then and . Let . There is an af in which and .
Given as described in the Lemma statement consider the (monotone) Boolean function over the propositional variables defined via
We note that the relationship between “sets of arguments providing a defence against attacks on y” and the well-known formalisms from propositional logic of cnf and dnf has already been often exploited in formal argumentation. A similar use to that of Lemma 3 is found in Dunne et al. .
It is shown in [9, Thm. 4] that this construction is optimal. Given some incomparable system of subsets, , with the set of clauses in the unique minimal cnf equivalent to , any af in which: for all , is conflict-free and must be such that .
In particular, the realization of an af, in which for some incomparable system of subsets drawn from may use exponentially many auxiliary arguments. This is not only in cases for which , e.g. when and comprises all subsets of size n from . Perhaps less obviously, one might have (again with ) but, with the construction used, auxiliary arguments in . For example if
If is decomposable then .
Given which is decomposable let
Now let us assume, inductively that we have built for all . We wish to form . From the properties of the partition and formulation of the decomposition of we know that each set in has the form where and U is a subset minimal set in for which . For each define
This suffices to complete the inductive proof. □
Returning to the system presented in Fig. 1, we saw that this corresponds to the system of sets
6.Conclusions & extensions
Our principal aim in this paper has been to present a characterization of strong admissibility, as first presented in Baroni and Giacomin , in terms of the notions of signature and realizability from Dunne et al. [10,11]. Our main result, summarized as Corollary 1, being that a collection of subsets of describes the strongly admissible sets of some af if and only if that collection possesses the property of being decomposable. The notion of decomposability raises a number of combinatorial and complexity-theoretic questions, some of which we briefly discuss here. One specific aspect of interest concerns the contrast between a framework having exponentially many sets in but with the possibility of describing these through a much more concise description of its decomposition. As a very simple example, the af, in which has exactly strongly admissible sets (every subset of ). These, however, are succinctly described via the 1-decomposition, . On the other hand there are cases in which the number of distinct sets in must be exponential in : a simple example of such behaviour being the incomparable system formed by all subsets of containing exactly members. Hence one direction for further work would concern exploring the relationship between and its decomposition. One complexity-theoretic question concerns the following: given S it is known that verifying can be carried out efficiently from the results of Caminada and Dunne . If we ask instead whether for some k, it is unclear whether this continues to be tractable: intractability is suggested by complexity-theoretic study of “minimal labellings” on the other hand there may be some variation of the algorithm from  that could be applied.
Finally we have some questions of interest regarding signatures of analogues of strong admissibility in variant afs. One such being the collective attacks model introduced in Neilsen and Parsons  and studied with respect to realizability for the canonical Dung semantics in Dvorak et al. . We leave these and similar questions for further work.
The author would like to thank Martin Caminada for useful discussions regarding the strong admissibility semantics.
P. Baroni, M. Caminada and M. Giacomin, Abstract argumentation frameworks and their semantics, in: Handbook of Formal Argumentation, Vol. 1, 2018, pp. 157–234.
P. Baroni, F. Cerutti, P.E. Dunne and M. Giacomin, Automata for infinite argumentation structures, Artificial Intelligence 203 (2013), 104–150. doi:10.1016/j.artint.2013.05.002.
P. Baroni and M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171(10–15) (2007), 675–700. doi:10.1016/j.artint.2007.04.004.
R. Baumann, On the nature of argumentation semantics: Existence and uniqueness, expressibility, and replaceability, Journal of Applied Logics 4(8) (2017), 2779–2886.
R. Baumann and C. Spanring, A study of unrestricted abstract argumentation frameworks, in: IJCAI, Vol. 17, 2017, pp. 807–813. doi:10.24963/ijcai.2017/112.
M.W.A. Caminada, Strong admissibility revisited, in: Computational Models of Argument; Proceedings of COMMA 2014, S. Parsons, N. Oren, C. Reed and F. Cerutti, eds, IOS Press, 2014, pp. 197–208.
M.W.A. Caminada and P.E. Dunne, Strong admissibility revised: Theory and applications, Argument & Computation (2019), in print.
P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial Intelligence 77 (1995), 321–357. doi:10.1016/0004-3702(94)00041-X.
P.E. Dunne, The inverse characteristic function in argumentation frameworks: Properties and complexity (submitted), 2020, www.csc.liv.ac.uk/~ped/combined.pdf.
P.E. Dunne, W. Dvořák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, in: 14th International Conference on the Principles of Knowledge Representation and Reasoning, 2014.
P.E. Dunne, W. Dvořák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, Artificial Intelligence 228 (2015), 153–178. doi:10.1016/j.artint.2015.07.006.
W. Dvořák, J. Fandinno and S. Woltran, On the expressive power of collective attacks, Argument & Computation 10(2) (2019), 191–230. doi:10.3233/AAC-190457.
S.H. Nielsen and S. Parsons, A generalization of Dung’s abstract framework for argumentation: Arguing with sets of attacking arguments, in: International Workshop on Argumentation in Multi-Agent Systems, Springer, 2006, pp. 54–73.