Learning argumentation frameworks from labelings

Abstract

We consider the problem of learning argumentation frameworks from a given set of labelings such that every input is a σ-labeling of these argumentation frameworks. Our new algorithm takes labelings and computes attack constraints for each argument that represent the restrictions on argumentation frameworks that are consistent with the input labelings. Having constraints on the level of arguments allows for a very effective parallelization of all computations. An important element of this approach is maintaining a representation of all argumentation frameworks that satisfy the input labelings instead of simply finding any suitable argumentation framework. This is especially important, for example, if we receive additional labelings at a later time and want to refine our result without having to start all over again. The developed algorithm is compared to previous works and an evaluation of its performance has been conducted.

1. Introduction

An abstract argumentation framework due to Dung [15] is defined as a graph, where the nodes are arguments and the edges represent attacks between these arguments. An attack from an argument A to another argument B means that, if we consider the argument A to be acceptable, then we have to reject B, since A contradicts B. The goal of this approach is to model human argumentation in a formal manner and to use this model for reasoning. Abstract argumentation frameworks are interpreted using the notion of an (argumentation) semantics. A semantics characterizes acceptable sets of arguments (called extensions), which are supposed to model a valid outcome of the argumentation represented by an argumentation framework. In particular, they usually require that extensions are conflict-free, i.e., that there is no conflict between arguments of the extension, and that it defends itself, i.e., it counterattacks all its attackers (the latter property is called admissibility). While Dung proposed several different semantics in his seminal paper, like complete, grounded, preferred, and stable semantics, there have since been many proposals for new semantics [4], all with different goals in mind.

Extension-based semantics focus on the accepted arguments only, so, any extension with respect to some semantics only consists of the arguments that are considered acceptable. That means we also get the implicit knowledge that all other arguments are not accepted. However, we do not know for what reason these arguments are not accepted. They could be directly attacked by some acceptable argument, meaning the extension actively contradicts them. In contrast to that they could also be not accepted because they are part of some conflict, unrelated to the acceptable arguments, which means these arguments could potentially also be compatible with the acceptable arguments. This additional information can be encoded in labelings [17]. In a labeling each argument of the argumentation framework receives a label, if it is considered acceptable the argument is labeled $\mathsf{in}$ , if the argument is attacked by some acceptable argument it gets the label $\mathsf{out}$ and otherwise it receives the label $\mathsf{undec}$ .

In Inductive Logic Programming [21] we derive from a given set of examples and background knowledge a hypothesized logic program that entails these examples. In a similar manner, algorithms for Bayesian Network Learning [13,18] are concerned with inducing a bayesian network from given data. Overall, both of these approaches are concerned with generalizing from observations or examples to a program or network which entails this knowledge and therefore also allows for inferring new knowledge in line with the input knowledge.

This approach is also interesting for the field of argumentation. In general, argumentation semantics allows us to perform inference with an abstract argumentation framework, by determining semantical information (extensions or labelings) from given syntactical information (in the form of an argumentation framework). In this work, we are, as already hinted at above, interested in the reverse direction, i.e., the process of learning a syntactic structure from semantical information. So, given a set of labelings we wish to infer a suitable attack relation that explains this input. That means, we want to find an argumentation framework that has at least those labelings.

This is interesting, if we look for example at the area of argument mining [20] which is concerned with extracting arguments and their relations from text. There, extracting the relations between arguments is especially hard [18]. This is one area where inductive learning approaches are useful, since they can aid us in constructing the attack relation for a set of arguments. Additionally, learning the attack relation for a set of arguments can also be helpful in terms of explainability [1,12] since this allows us to construct better argumentative explanations based on the underlying argumentation framework itself, see e.g., [16,27]. It will also allow us to better understand how the labelings originated and how we could challenge them, as the following example will highlight.

Assume a situation where we are able to meet up with a person A that has an anti-vax stance. We are able to discuss with them about the topic of the COVID-19 vaccine and our goal is to understand their personal reasoning process. Doing so may allow us to find better counterarguments in future discussions on the topic and it will also aid us in identifying false conclusions that A might have made, so that we can potentially clear them up. The internal reasoning process of A is represented as an argumentation framework, which is hidden to us. During the discussion, we may ask A for his opinion on different statements on the topic. From A’s answers we can then infer a labeling, which essentially assigns to each argument their stance, i.e., either they agree ( $\mathsf{in}$ ), disagree ( $\mathsf{out}$ ) or their stance is unclear/unknown ( $\mathsf{undec}$ ). Given such a labeling, our goal is to reconstruct the hidden argumentation framework of A.

For example, lets consider the following four arguments:

• The development of the COVID-19 vaccine has been rushed.

• The COVID-19 vaccine reduces the risk of infection.

• The COVID-19 vaccine does not work at all.

• The COVID-19 vaccine is dangerous and has various side effects.

From our first discussion with A we may conclude that they agree with the arguments a and d while disagreeing with b and c. This would then translate to the complete labeling ${\ell }_1=\{\mathsf{in}:\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\mathsf{out}:\{\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\mathsf{undec}:\varnothing \}$ . A complete labeling is defined such that arguments not attacked by an $\mathsf{out}$ -labeled argument must be labeled $\mathsf{in}$ , all arguments attacked by an $\mathsf{in}$ -labeled arguments are labeled $\mathsf{out}$ and otherwise the argument is labeled $\mathsf{undec}$ . If we now try to reconstruct their internal argumentation framework, for example by simply brute-forcing every possible combination of attacks, we will find that multiple argumentation frameworks are consistent with this labeling. See for example the three argumentation frameworks in Fig. 1. At this point, it is impossible for us to decide which argumentation framework correctly represents the reasoning of A. If we were to choose one, we would have to make some additional assumptions and discard all other argumentation frameworks. This may lead to unintentionally discarding the actual framework that we are looking for. For that reason, it is sensible to maintain a representation of all of these argumentation frameworks. This allows us to easily incorporate additional information in the future.

For example, if we want to refine our understanding of A’s reasoning, we could initiate another discussion with them so that we can obtain another complete labeling. After our second discussion, we may get the labeling ${\ell }_2=\{\mathsf{in}:\{\mathit{c}\}\mathrm{,}\mathsf{out}:\{\mathit{a}\}\mathrm{,}\mathsf{undec}:\{\mathit{b}\mathrm{,}\mathit{d}\}\}$ . With this additional labeling, we can again reconstruct argumentation frameworks that are consistent with both ${\ell }_1$ and ${\ell }_2$ . In our example, we will find that only ${\mathit{F}}_2$ and ${\mathit{F}}_3$ from Fig. 1 are consistent with both labelings, while ${\mathit{F}}_1$ is only consistent with ${\ell }_1$ . This again highlights the advantage of maintaining a representation of all consistent argumentation frameworks after each step.

Fig. 1.

Some argumentation frameworks that were reconstructed from the labelings ${\ell }_1$ and ${\ell }_2$ of the arguments $\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ as defined above. Note that these frameworks are not supposed to model factual information but rather the reasoning process of someone with potentially flawed logic or limited understanding of the topic at hand.

With the argumentation framework(s) that we have learned from the labelings, we can then for example try to identify missing or nonsensical attacks (e.g. there should probably be an attack from b on c). Another thing we can do, is identify key arguments that we can disprove to sway the opinion of the person A. For example, if we present some evidence that the vaccine development has in fact not been rushed, A might change their opinion on the argument a and subsequently this could influence their stance on arguments b and c.

In this work, we will answer the following research question:

Research Question.

For a given set of labelings $\mathit{L}=\{{\ell }_1\mathrm{,}\dots \mathrm{,}{\ell }_{\mathit{n}}\}$ and a set of semantics $\mathit{S}=\{{\mathit{\sigma }}_1\mathrm{,}\dots \mathrm{,}{\mathit{\sigma }}_{\mathit{n}}\}$ , how can we compute the set of argumentation frameworks $\mathbb{F}$ such that for all $\mathit{F}\in \mathcal{F}$ the following two conditions hold:

if $\mathit{F}\in \mathbb{F}$ , then $\forall {\ell }_{\mathit{i}}\in \mathit{L}:{\ell }_{\mathit{i}}$ is a ${\mathit{\sigma }}_{\mathit{i}}$ -labeling of F, and

if $\mathit{F}\notin \mathbb{F}$ , then $\exists {\ell }_{\mathit{i}}\in \mathit{L}:{\ell }_{\mathit{i}}$ is not a ${\mathit{\sigma }}_{\mathit{i}}$ -labeling of F.

We explicitly allow the labelings to have different semantics in order to be more general, especially since different semantics have different advantages depending on the application [4]. In other words, for a given set of labelings L with respect to different semantics, we want to define a method to construct the set of all argumentation frameworks F, such that at least all labelings in L are labelings of F. In that case, we will also say that the argumentation framework F is consistent with L.

The general problem of learning argumentation frameworks has only received limited attention so far [23,25] and none of these works are able to address the exact scenario we outlined above. In their paper, Niskanen et al. [23] investigate the synthesis of argumentation frameworks from positive and negative examples. These examples are extensions with respect to conflict-free, admissible, complete or stable semantics. A positive example E is then encoded in some logical formula, representing the information in E. All positive examples are encoded with a corresponding formula for their semantics and the negative examples are encoded as the negation of those formulae. Their approach also allows for the attachment of weights to each example. The encoded examples, together with their weights, are given to a MaxSAT solver, which returns the optimal solution, i.e., an argumentation framework, which is consistent with all or most of the positive examples and the least of the negative examples.

On the other hand, Riveret et al. [25] propose an approach for learning attacks from labelings. Their algorithm is built around the grounded semantics and takes a stream of labelings as input. Since it is not possible to reconstruct the argumentation framework by only knowing the (uniquely determined) grounded extension, Riveret et al. decided to extend their scenario as follows. Their algorithm works with knowledge about the sub-frameworks of the argumentation framework, i.e., restrictions of the graph on different subsets of arguments. The input of their algorithm therefore consists of grounded labelings of different sub-frameworks. For the process of learning the hidden argumentation framework we start with a weighted argumentation framework, where every attack has an initial weight of 0. Then, for each input labeling we iterate over all combinations of two arguments and check whether they satisfy one of four rules, which essentially encode the different conditions a grounded labelings has to fulfill. If a rule is satisfied, the weight of the attacks between these two arguments are updated accordingly. After examining all input labelings we remove all attacks whose weight is below a certain threshold from the argumentation framework. The resulting argumentation framework is then the approximation of the original hidden argumentation framework.

While the above mentioned approaches can be used to construct argumentation frameworks from labelings or extensions, they only return a single argumentation framework as a result. This might not always be desirable, as we illustrated in the above example. In the case of the approach by Riveret et al. [25], their algorithm also relies on additional information about sub-frameworks.

Therefore, in this work, we propose an algorithm that better addresses this scenario by maintaining a representation of all consistent argumentation frameworks at all times. In general, our algorithm works according to the following procedure: We are given a set of arguments $\mathsf{Arg}$ as well as a set of input labelings L. For each input labeling $\ell \in \mathit{L}$ we compute a set of attack constraints ${\mathit{C}}_{\ell }={\{{\mathit{C}}_{\mathit{a}\mathrm{,}\mathit{\sigma }}\}}_{\mathit{a}\in \mathsf{Arg}}$ , depending on its semantics. Afterwards we combine these constraints, so that we have one constraint ${\mathit{C}}_{\mathit{a}}$ for each argument $\mathit{a}\in \mathsf{Arg}$ . Finally, they can then be used to construct a set of argumentation frameworks $\mathbb{F}$ which satisfy all constraints. That means every argumentation framework $\mathit{F}\in \mathbb{F}$ is consistent with the set of input labelings L.

To summarise, the contributions of this paper are as follows:

1. We introduce the concept of attack constraints and define semantic constraint functions that compute attack constraints for a given labeling (Section 3.1–3.2).

2. We define a novel algorithm for learning argumentation frameworks from labelings that utilizes these constraints to maintain a representation of all consistent argumentation frameworks (Section 3.3).

3. We conduct an experimental evaluation of our algorithm, comparing a naive and a parallelized implementation (Section 4).

4. We discuss our algorithm and distinguish it from the existing work on the topic (Section 5).

In Section 2 we introduce the necessary background knowledge on abstract argumentation and labeling-based semantics and Section 6 concludes the paper. Proofs of technical results can be found in the Appendix.

2. Background

We consider abstract argumentation frameworks [15] defined as follows.

Definition 2.1.

An argumentation framework (AF) is a pair $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ where $\mathsf{Arg}$ is a finite set of arguments and where $\mathsf{R}\subseteq \mathsf{Arg}\times \mathsf{Arg}$ is a relation of attack between arguments. We denote by $\mathcal{F}$ the set of all argumentation frameworks.

We say that an argument $\mathit{a}\in \mathsf{Arg}$ attacks an argument $\mathit{b}\in \mathsf{Arg}$ if $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathsf{R}$ . Given a set $\mathit{S}\subseteq \mathsf{Arg}$ we say S attacks a if for some $\mathit{b}\in \mathit{S}$ we have $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathsf{R}$ , and likewise a attacks S if for some $\mathit{b}\in \mathit{S}$ we have $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathsf{R}$ .

A labeling-based semantics maps each argumentation framework to a set of labelings [8,17]. These are functions that assign to each argument a label indicating the acceptance status of the argument. The labeling-based semantics that we focus on in this paper use three labels: $\mathsf{in}$ indicates that the argument is accepted, $\mathsf{out}$ that the argument is rejected, and $\mathsf{undec}$ that the acceptance of the argument is undecided. In this paper we use the labeling-based approach since it allows us to distinguish not only accepted and non-accepted arguments, but also rejected arguments and undecided arguments. We will refer to a labeling-based semantics simply as a semantics.

Definition 2.2.

A labeling of a set $\mathsf{Arg}$ of arguments is a total function $\ell :\mathsf{Arg}\to \{\mathsf{in}\mathrm{,}\mathsf{out}\mathrm{,}\mathsf{undec}\}$ . We use $\mathbb{L}\mathrm{(}\mathsf{Arg}\mathrm{)}$ to denote the set of labelings of $\mathsf{Arg}$ . A labeling of an argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ is a labeling of $\mathsf{Arg}$ . Given a labeling ℓ we use $\mathsf{in}\mathrm{(}\ell \mathrm{)}$ , $\mathsf{out}\mathrm{(}\ell \mathrm{)}$ and $\mathsf{undec}\mathrm{(}\ell \mathrm{)}$ to denote the set of arguments labeled $\mathsf{in}$ , $\mathsf{out}$ and $\mathsf{undec}$ , respectively.

A semantics σ is represented by a condition that determines whether a labeling ℓ of F is a σ-labeling. We now define the semantics that we focus on in this paper, namely the complete, grounded, preferred and stable semantics. While not typically considered to be a semantics, we also define the notion of a conflict-free and admissible labeling and treat these conditions as semantics. For that, we will use the definitions from [8] or definitions that are equivalent to those.

A labeling is conflict-free whenever no two arguments a and b exist such that a attacks b and both are labeled $\mathsf{in}$ .

Definition 2.3.

A labeling ℓ of an argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ is conflict-free if and only if:

if a is labeled $\mathsf{in}$ then no attacker of a is labeled $\mathsf{in}$ .

if a is labeled $\mathsf{out}$ then a has an attacker that is labeled $\mathsf{in}$ .

A labeling is admissible whenever it is conflict-free and, in addition, every argument a that is accepted is attacked only by arguments that are rejected. This amounts to requiring accepted arguments to be defended: in an admissible labeling, if a is accepted then all attackers of a are rejected and thus (as a consequence of Condition 2 in Definition 2.3) a is defended from these attackers by other arguments that are accepted.

Definition 2.4.

A labeling ℓ of an argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ is admissible if and only if:

ℓ is conflict-free.

if a is labeled $\mathsf{in}$ then all attackers of a are labeled $\mathsf{out}$ .

A labeling is complete whenever it is admissible and, in addition, (1) every argument attacked by an accepted argument is rejected, and (2) every argument whose attackers are rejected is accepted. This condition amounts to requiring defended arguments to be accepted: if all attackers of an argument a are attacked by some argument that is accepted, then all attackers of a are rejected and hence a is accepted.

Definition 2.5.

A labeling ℓ of an argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ is complete if and only if:

ℓ is admissible.

if some attacker of a is labeled $\mathsf{in}$ then a is labeled $\mathsf{out}$ .

if all attackers of a are labeled $\mathsf{out}$ then a is labeled $\mathsf{in}$ .

The remaining semantics are all defined in terms of complete labelings. Firstly, a labeling is grounded if it is complete and if it is minimal with respect to accepted arguments. The grounded labeling of an argumentation framework is unique and represents the most skeptical point of view on which arguments to accept [8,15]. A preferred labeling is a complete labeling that is maximal with respect to accepted arguments. Preferred labelings represent maximally credulous points of view on which arguments to accept. Finally, a stable labeling is a complete labeling in which no argument is undecided.

Definition 2.6.

Let $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ be an argumentation framework and let ℓ be a labeling of F.

ℓ is a grounded if it is complete and if there is no complete labeling ${\ell }^{\prime }$ of F such that $\mathsf{in}\mathrm{(}{\ell }^{\prime }\mathrm{)}\subset \mathsf{in}\mathrm{(}\ell \mathrm{)}$ .

ℓ is a preferred if it is complete and if there is no complete labeling ${\ell }^{\prime }$ of F such that $\mathsf{in}\mathrm{(}\ell \mathrm{)}\subset \mathsf{in}\mathrm{(}{\ell }^{\prime }\mathrm{)}$ .

ℓ is a stable if it is complete and if $\mathsf{undec}\mathrm{(}\ell \mathrm{)}=\varnothing$

In the following, we will denote with $\mathit{\sigma }\mathrm{(}\mathit{F}\mathrm{)}$ the set of all σ-labelings of F. The definitions in this section immediately imply the following relationships between the different semantics [8,15]. Proposition 2.1.

Every admissible labeling is conflict-free.

Every complete labeling is admissible.

Every grounded, preferred and stable labeling is complete.

Every stable labeling is preferred.

3. Learning from labelings

In this section, we introduce a novel algorithm for learning argumentation frameworks from labelings with the goal of constructing (or representing) all argumentation frameworks that are relevant to the input labelings. We start with formally defining the AF learning problem that we want to address. Afterwards, we define the concept of attack constraints and finally describe in detail our algorithm to solve this problem.

For the remainder of this work, we will consider the set of arguments $\mathsf{Arg}$ to be fixed. We also denote with $\mathbb{S}$ the set of all semantics. First, we define the notion of an input, which is a pair of the form $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ with a labeling ℓ and some semantics $\mathit{\sigma }\in \mathbb{S}$ .

Definition 3.1.

An input pair is a pair $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ where $\ell \in \mathbb{L}\mathrm{(}\mathsf{Arg}\mathrm{)}$ is a labeling of $\mathsf{Arg}$ and $\mathit{\sigma }\in \mathbb{S}$ is a semantics.

We will also sometimes refer to ℓ as an input labeling. So, given a set of inputs $\mathit{L}=\{\mathrm{(}{\ell }_1\mathrm{,}{\mathit{\sigma }}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathrm{(}{\ell }_{\mathit{n}}\mathrm{,}{\mathit{\sigma }}_{\mathit{n}}\mathrm{)}\}$ , our intention is to construct a set of argumentation frameworks $\mathbb{F}$ , such that for all $\mathit{F}\in \mathbb{F}$ and each $\mathit{i}=1\mathrm{,}\dots \mathrm{,}\mathit{n}$ , we have that ${\ell }_{\mathit{i}}$ is a ${\mathit{\sigma }}_{\mathit{i}}$ -labeling of F. More formally, we are concerned with the following problem:

The general idea behind our approach to solve the AF learning problem is as follows. We use propositional atoms of the form ${\mathit{r}}_{\mathit{b}\mathit{a}}$ to express the existence of attacks $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathsf{R}$ in some argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ . Then, given an input $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ , we construct a set of attack constraints ${\mathit{C}}_{\ell }=\{{\mathit{C}}_{\mathit{a}}|\mathit{a}\in \mathsf{Arg}\}$ . For a labeling ℓ we will therefore have one attack constraint ${\mathit{C}}_{\mathit{a}}$ for each argument $\mathit{a}\in \mathsf{Arg}$ . These attack constraints depend on the semantics σ of the input as well as the labeling ℓ itself. Together, they express what an argumentation framework F has to satisfy such that ℓ is a σ-labeling of F. We will then use the fact that the models of these formulas directly correspond to argumentation frameworks by using the mapping functions described in Definition 3.3.

This approach can then also be extended to a set of input labelings $\mathit{L}=\{\mathrm{(}{\ell }_1\mathrm{,}{\mathit{\sigma }}_1\mathrm{)}\mathrm{,}\dots \mathrm{,}\mathrm{(}{\ell }_{\mathit{n}}\mathrm{,}{\mathit{\sigma }}_{\mathit{n}}\mathrm{)}\}$ . So, for a given set of input labelings L we compute the constraints ${\mathit{C}}_{{\ell }_{\mathit{i}}}$ for each labeling ${\ell }_{\mathit{i}}$ , depending on its semantics ${\mathit{\sigma }}_{\mathit{i}}$ . Then, each interpretation that satisfies all attack constraints of all input labelings represents an argumentation framework F where all labelings ${\ell }_{\mathit{i}}$ are ${\mathit{\sigma }}_{\mathit{i}}$ -labelings of F. It follows, that the set of models that satisfy all attack constraints exactly corresponds to the set of argumentation frameworks $\mathbb{F}$ as specified in the above scenario description. In other words, we construct the set of all argumentation frameworks that have at least the given input as their labelings, but they can also have additional labelings.

3.1. Attack constraints

The key element of our algorithm are the so called attack constraints. Before we define the concept of attack constraints, we first introduce the propositional language that we use to represent attacks in argumentation frameworks.

Let $\mathsf{At}$ be a set of propositional atoms. With $\mathcal{L}\mathrm{(}\mathsf{At}\mathrm{)}$ we denote the corresponding propositional language closed under the usual connectives. Furthermore, we will use the concept of an interpretation $\mathcal{A}$ , a function that assigns to each atom a truth value. If an interpretation $\mathcal{A}$ satisfies a formula $\mathit{f}\in \mathcal{L}\mathrm{(}\mathsf{At}\mathrm{)}$ , i.e., it assigns the value $\mathit{true}$ to it, we may also call $\mathcal{A}$ a model of f. With $\mathcal{M}\mathrm{(}\mathit{f}\mathrm{)}$ we denote the set of all models of f. If G is a set of formulas, we denote with $\mathcal{M}\mathrm{(}\mathit{G}\mathrm{)}$ the set of all models of the conjunction $\mathit{g}={\bigwedge }_{\mathit{f}\in \mathit{G}}\mathit{f}$ .

Definition 3.2.

Let $\mathsf{Arg}$ be the fixed set of arguments and $\mathit{a}\in \mathsf{Arg}$ is an argument. Then we define the set of atoms representing all possible attacks in the argumentation framework F as follows: $$\begin{array}{l}\hfill \mathit{attackAtoms}\mathrm{(}\mathsf{Arg}\mathrm{)}=\{{\mathit{r}}_{\mathit{b}\mathit{a}}|\mathit{a}\mathrm{,}\mathit{b}\in \mathsf{Arg}\}\end{array}$$ and the set of atoms that represent all possible incoming attacks on the argument a as $$\begin{array}{l}\hfill \mathit{inAttacks}\mathrm{(}\mathit{a}\mathrm{)}=\{{\mathit{r}}_{\mathit{b}\mathit{a}}|\mathit{b}\in \mathsf{Arg}\}.\end{array}$$

A positive occurrence ${\mathit{r}}_{\mathit{b}\mathit{a}}$ represents an attack from b to a in the argumentation framework, i.e., $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathsf{R}$ . On the other hand, a negative occurrence $\neg {\mathit{r}}_{\mathit{b}\mathit{a}}$ means there should be no attack from b on a in the argumentation framework, i.e., $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\notin \mathsf{R}$ .

Due to the correspondence between the above defined atoms $\mathit{attackAtoms}\mathrm{(}\mathsf{Arg}\mathrm{)}$ and the attacks of some argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ , we can also define a one-to-one mapping between the models of a formula and attack relations.

Definition 3.3.

$\mathsf{Arg}$ is the set of arguments and $\mathit{f}\in \mathcal{L}\mathrm{(}\mathit{attackAtoms}\mathrm{(}\mathsf{Arg}\mathrm{)}\mathrm{)}$ is a formula. We define the mapping from a model to an attack relation via the function $\mathit{modelToAttacks}:\mathcal{M}\mathrm{(}\mathit{f}\mathrm{)}\to 2^{\mathsf{Arg}\times \mathsf{Arg}}$ as: $$\begin{array}{l}\hfill \mathit{modelToAttacks}\mathrm{(}\mathcal{A}\mathrm{)}:=\mathsf{R}\text{with }\mathsf{R}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}|\mathcal{A}\mathrm{(}{\mathit{r}}_{\mathit{a}\mathit{b}}\mathrm{)}=\mathit{true}\}\end{array}$$ and the mapping from an attack relation to a model $\mathit{attacksToModel}:2^{\mathsf{Arg}\times \mathsf{Arg}}\to \mathcal{M}\mathrm{(}\mathit{f}\mathrm{)}$ as: $$\begin{array}{l}\hfill \mathit{attacksToModel}\mathrm{(}\mathsf{R}\mathrm{)}:=\mathcal{A}\text{with }\mathcal{A}\mathrm{(}{\mathit{r}}_{\mathit{a}\mathit{b}}\mathrm{)}=\left\{\begin{array}{cc}\mathit{true}\hfill & \text{if }\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathsf{R}\hfill \\ \mathit{false}\hfill & \text{otherwise}.\hfill \end{array}\right.\end{array}$$

Together with the fixed set of arguments $\mathsf{Arg}$ , we can then also recover an argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathit{modelToAttacks}\mathrm{(}\mathcal{A}\mathrm{)}\mathrm{)}$ .

Example 1.

Consider the set of arguments $\mathsf{Arg}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ . Then, an attack constraint for the argument a could for instance look like this $$\begin{array}{l}\hfill {\mathit{C}}_{\mathit{a}}=\neg {\mathit{r}}_{\mathit{a}\mathit{a}}\wedge \mathrm{(}{\mathit{r}}_{\mathit{c}\mathit{a}}\vee {\mathit{r}}_{\mathit{d}\mathit{a}}\mathrm{)}.\end{array}$$ For an argumentation framework, this constraint enforces that the argument a cannot be attacked by itself. Furthermore, a must be attacked by either c or d or both. Finally, an attack from b on a might also exist, since the constraint ${\mathit{C}}_{\mathit{a}}$ does not impose any restriction on the variable ${\mathit{r}}_{\mathit{b}\mathit{a}}$ . That means, there exist multiple different argumentation frameworks that satisfy the above attack constraint for a. These argumentation frameworks are represented by the set of models $\mathcal{M}\mathrm{(}{\mathit{C}}_{\mathit{a}}\mathrm{)}$ .

Recalling Section 2, under any semantics an argument can only be accepted if it is not attacked by any other accepted argument (conflict-freeness). In addition to that, the acceptance of an argument also depends on the label of its attackers. If the attackers of the argument a are labeled $\mathsf{out}$ , then a can still be accepted (i.e., labeled $\mathsf{in}$ ). On the other hand, if one of its attackers is labeled $\mathsf{undec}$ (or $\mathsf{in}$ ), then a cannot be accepted under admissible, complete, grounded, preferred or stable semantics. It does not matter in this context what the outgoing attacks of the argument a are. To summarize, if we want to formulate a constraint for the acceptance of an argument, under most semantics we only need to consider its direct attackers and their label in a given labeling.

For that reason, we define the attack constraints from the local perspective of an argument.

Definition 3.4.

Let $\mathit{a}\in \mathsf{Arg}$ be an argument. Then the attack constraint of a is a formula ${\mathit{C}}_{\mathit{a}}\in \mathcal{L}\mathrm{(}\mathit{inAttacks}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}$ .

So, instead of specifying one constraint per input labeling, we will represent a labeling ℓ with a set of attack constraints. For this labeling constraint every model corresponds to an argumentation framework that has ℓ as a σ-labeling.

Definition 3.5.

Let $\mathsf{Arg}$ be the fixed set of arguments and $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ is an input. Then we define the labeling constraint ${\mathit{C}}_{\ell }$ of the input labeling ℓ as a set of attack constraints as follows: $$\begin{array}{l}\hfill {\mathit{C}}_{\ell }=\{{\mathit{C}}_{\mathit{a}}|\mathit{a}\in \mathsf{Arg}\}\mathrm{,}\end{array}$$ such that we have $$\begin{array}{l}\hfill \mathcal{A}\in \mathcal{M}\mathrm{(}{\mathit{C}}_{\ell }\mathrm{)}⟹\ell \text{ is a }\mathit{\sigma }\text{-labeling of }\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathit{modelToAttacks}\mathrm{(}\mathcal{A}\mathrm{)}\mathrm{)}.\end{array}$$

It is also worth noting that by defining the attack constraints as formulas over $\mathit{inAttacks}\mathrm{(}\mathit{a}\mathrm{)}$ , we ensure that the constraints for a labeling are mutually independent.

Proposition 3.1.

Let $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ be an input and ${\mathit{C}}_{\ell }$ is the labeling constraint of ℓ given σ. The attack constraints ${\mathit{C}}_{\mathit{a}}\in {\mathit{C}}_{\ell }$ are mutually independent, i.e., for any two attack constraints ${\mathit{C}}_{\mathit{a}}\mathrm{,}{\mathit{C}}_{\mathit{b}}\in {\mathit{C}}_{\ell }$ , we have that $\mathit{atoms}\mathrm{(}{\mathit{C}}_{\mathit{a}}\mathrm{)}\cap \mathit{atoms}\mathrm{(}{\mathit{C}}_{\mathit{b}}\mathrm{)}=\varnothing$ .

Finally, we may also say that an argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ satisfies a labeling constraint ${\mathit{C}}_{\ell }$ , if there exists a model $\mathcal{A}$ of ${\mathit{C}}_{\ell }$ that can be mapped to the attack relation $\mathsf{R}$ of F. Definition 3.6.

Let $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ be an argumentation framework. Let $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ be an input and ${\mathit{C}}_{\ell }$ is the labeling constraint of ℓ. We say that F satisfies ${\mathit{C}}_{\ell }$ , written as $\mathit{F}\vDash {\mathit{C}}_{\ell }$ , if and only if there is a model $\mathcal{A}$ of ${\mathit{C}}_{\ell }$ such that $\mathit{attacksToModel}\mathrm{(}\mathsf{R}\mathrm{)}=\mathcal{A}$ .

3.2. Semantic constraint functions

To construct the constraints for an input $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ , we need a method that given an argument a and a labeling ℓ computes a valid attack constraint for each argument. Under different semantics, we have different conditions under which arguments are accepted or rejected. Therefore, such a function should be different depending on the associated semantics σ of the input. To compute these constraints for each argument, we will use a semantic constraint function ${\mathit{AttCon}}_{\mathit{\sigma }}$ with the following signature: $$\begin{array}{l}\hfill {\mathit{AttCon}}_{\mathit{\sigma }}:\mathsf{Arg}\times \mathbb{L}\mathrm{(}\mathsf{Arg}\mathrm{)}⟶\mathcal{L}\mathrm{(}\mathit{inAttacks}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}.\end{array}$$

This function then takes the input labeling ℓ and an argument $\mathit{a}\in \mathsf{Arg}$ and returns the attack constraint for this argument. In other words, it computes a formula that represents the information about the acceptance of a that can be extracted from the labeling ℓ under the assumption that ℓ is a σ-labeling.

Recall that in our scenario we want to compute all argumentation frameworks F such that for all inputs $\mathrm{(}{\ell }_{\mathit{i}}\mathrm{,}{\mathit{\sigma }}_{\mathit{i}}\mathrm{)}$ we have that ${\ell }_{\mathit{i}}$ is a ${\mathit{\sigma }}_{\mathit{i}}$ -labeling of F. In order to satisfy this requirement, we have to ensure soundness and completeness in the following sense:

The set of arguments $\mathsf{Arg}$ is fixed. Let $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ be an input and ${\mathit{AttCon}}_{\mathit{\sigma }}$ is a semantic constraint function for σ. The corresponding labeling constraint ${\mathit{C}}_{\ell \mathrm{,}\mathit{\sigma }}$ for ℓ is then the set of attack constraints $$\begin{array}{l}\hfill {\mathit{C}}_{\ell \mathrm{,}\mathit{\sigma }}=\{{\mathit{AttCon}}_{\mathit{\sigma }}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}|\mathit{a}\in \mathsf{Arg}\}.\end{array}$$

Whenever the semantics σ is not relevant or follows from context, we denote the labeling constraint for the labeling ℓ with just ${\mathit{C}}_{\ell }$ .

Then, the following two conditions must hold for all labelings:

1. The semantic constraint function is sound for all labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathcal{A}\in \mathcal{M}\mathrm{(}{\mathit{C}}_{\ell \mathrm{,}\mathit{\sigma }}\mathrm{)}:\ell \text{ is a }\mathit{\sigma }\text{-labeling of }\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathit{modelToAttacks}\mathrm{(}\mathcal{A}\mathrm{)}\mathrm{)}.\end{array}$$

2. The semantic constraint function is complete for all labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}:\ell \text{ is a }\mathit{\sigma }\text{-labeling of }\mathit{F}⟹\exists \mathcal{A}\in \mathcal{M}\mathrm{(}{\mathit{C}}_{\ell \mathrm{,}\mathit{\sigma }}\mathrm{)}:\mathsf{R}=\mathit{modelToAttacks}\mathrm{(}\mathcal{A}\mathrm{)}.\end{array}$$

So, if there exists a semantic constraint function ${\mathit{AttCon}}_{\mathit{\sigma }}$ for a semantics σ that satisfies the above two conditions, then we can use this function to learn argumentation frameworks as specified in the AF learning problem. On the other hand, if no such function exists, then labelings with respect to the semantics σ cannot be used to learn argumentation frameworks.

In the following, we will define the semantic constraint function for conflict-free, admissible, complete and stable semantics and give some examples to illustrate what kind of restrictions the constraints of each semantics impose on an argumentation framework.

3.2.1. Conflict-free semantics

First, we recall the conditions that a labeling ℓ has to satisfy in order to be considered conflict-free:

1. if a is labeled $\mathsf{in}$ then no attacker of a is labeled $\mathsf{in}$ .

2. if a is labeled $\mathsf{out}$ then a has an attacker that is labeled $\mathsf{in}$ .

From this we can derive what an attack constraint for a conflict-free input $\mathrm{(}\ell \mathrm{,}\mathit{cf}\mathrm{)}$ should include. If an argument $\mathit{a}\in \mathsf{Arg}$ is labeled $\mathsf{in}$ or $\mathsf{undec}$ , then it cannot be attacked by any argument $\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}$ . The first case follows from the definition of conflict-freeness, as there cannot be any attacks between $\mathsf{in}$ -labeled arguments (see condition (1) from above). The case $\mathsf{undec}$ follows from the definition of labelings itself, i.e., if an argument is attacked by an $\mathsf{in}$ -labeled argument, then it would have to be labeled $\mathsf{out}$ (see condition (2)). Furthermore, if the argument is labeled $\mathsf{out}$ , then it has to be attacked by at least one argument $\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}$ .

In addition to that, every argument a can be attacked by any other argument c, that does not have the label $\mathsf{in}$ , without influencing the label of a. These attacks, which are not relevant in order to have ℓ as a σ-labeling are not contained in the attack constraint of a.

Definition 3.7.

Let $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ be an argumentation framework and $\mathrm{(}\ell \mathrm{,}\mathit{cf}\mathrm{)}$ be an input. We then define the semantic constraint function for the conflict-free semantics as follows: $$\begin{array}{l}\hfill {\mathit{AttCon}}_{\mathit{cf}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}=\left\{\begin{array}{cc}{\bigwedge }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}\neg {\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}\hfill \\ {\bigvee }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}{\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{out}\mathrm{(}\ell \mathrm{)}\hfill \\ {\bigwedge }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}\neg {\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{undec}\mathrm{(}\ell \mathrm{)}\hfill \end{array}\right.\end{array}$$

The attack constraints computed via the semantic constraint function ${\mathit{AttCon}}_{\mathit{cf}}$ are sound and complete for conflict-free input labelings in the above defined sense. Theorem 3.1.

Let $\mathrm{(}\ell \mathrm{,}\mathit{cf}\mathrm{)}$ be a conflict-free input and ${\mathit{C}}_{\ell }$ is the labeling constraint of ℓ computed via ${\mathit{AttCon}}_{\mathit{cf}}$ . With $\mathbb{F}$ we denote the set of argumentation frameworks that satisfy ${\mathit{C}}_{\ell }$ , i.e for all $\mathit{F}\in \mathbb{F}$ we have that $\mathit{F}\vDash {\mathit{C}}_{\ell }$ .

The semantic constraint function is sound for conflict-free input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}\in \mathbb{F}:\ell \mathit{\text{ is a}}\text{ cf}\mathit{\text{-labeling of }}\mathit{F}\end{array}$$ and the semantic constraint function is complete for conflict-free input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}:\ell \mathit{\text{ is a}}\text{ cf}\mathit{\text{-labeling of }}\mathit{F}⟹\mathit{F}\in \mathbb{F}.\end{array}$$

Example 2.

Consider the set of arguments $\mathsf{Arg}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ and the conflict free input labeling $\ell =\{\mathsf{in}=\{\mathit{a}\mathrm{,}\mathit{b}\}\mathrm{,}\mathsf{out}=\{\mathit{c}\}\mathrm{,}\mathsf{undec}=\{\mathit{d}\}\}$ over these arguments. We can then use the above defined function ${\mathit{AttCon}}_{\mathit{cf}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}$ to compute the attack constraint of each argument in $\mathsf{Arg}$ : $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}}={\mathit{AttCon}}_{\mathit{cf}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{a}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{a}}\\ \hfill & {\mathit{C}}_{\mathit{b}}={\mathit{AttCon}}_{\mathit{cf}}\mathrm{(}\mathit{b}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{a}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{b}}\\ \hfill & {\mathit{C}}_{\mathit{c}}={\mathit{AttCon}}_{\mathit{cf}}\mathrm{(}\mathit{c}\mathrm{,}\ell \mathrm{)}={\mathit{r}}_{\mathit{a}\mathit{c}}\vee {\mathit{r}}_{\mathit{b}\mathit{c}}\\ \hfill & {\mathit{C}}_{\mathit{d}}={\mathit{AttCon}}_{\mathit{cf}}\mathrm{(}\mathit{d}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{a}\mathit{d}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{d}}\end{array}$$

These conditions represent the input labeling ℓ. They capture that the $\mathsf{in}$ -labeled arguments a and b are conflict-free, i.e., there is no attack between them in any direction. In addition to that, the $\mathsf{undec}$ -labeled argument d is also not attacked by a and b, because that would mean d would have to be labeled  $\mathsf{out}$ . The argument c is labeled $\mathsf{out}$ and thus it must be attacked by either a or b in order to satisfy the corresponding attack constraint.

We may also notice that the attack constraints contain no restrictions on attacks originating from c or d. That means these attacks are considered possible and we have to consider any combination of those when constructing the argumentation frameworks consistent with the conditions later.

3.2.2. Admissible semantics

Recalling the definition from Section 2, a labeling ℓ is considered admissible if (1) it is a $\mathit{cf}$ -labeling and (2) we have that if an argument $\mathit{a}\in \mathsf{Arg}$ is labeled $\mathsf{in}$ then all attackers of a are labeled $\mathsf{out}$ .

As the above condition (1) suggests, the attack constraint for an admissible input $\mathrm{(}\ell \mathrm{,}\mathit{a}\mathit{d}\mathrm{)}$ are a strengthened version of the conflict-free constraints. The attack constraint for arguments that are labeled $\mathsf{out}$ is the same as in the conflict-free case, it has to be attacked by at least one argument $\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}$ . Arguments that are labeled $\mathsf{undec}$ cannot be attacked by arguments that have the label $\mathsf{in}$ , just like it was the case for conflict-free labelings. From condition (2) it follows that if the argument is labeled $\mathsf{in}$ the attack constraint now includes that it cannot be attacked by any argument which is labeled $\mathsf{in}$ or $\mathsf{undec}$ . Disallowing attacks from $\mathsf{in}$ -labeled arguments captures the conflict-freeness and is the same as before. Additionally an argument which is accepted under admissible semantics can no longer be attacked by $\mathsf{undec}$ -labeled argument. This captures the defense property of admissibility. An argument with the label $\mathsf{undec}$ is per definition not attacked by any accepted argument and thus any attack from such an argument would be undefended.

However, an $\mathsf{in}$ -labeled argument can be attacked by any argument with the label $\mathsf{out}$ since these arguments are per definition attacked by some $\mathsf{in}$ -labeled argument. Furthermore, arguments that are labeled $\mathsf{out}$ or $\mathsf{undec}$ can additionally be attacked by any argument that does not have the label $\mathsf{in}$ , just like before.

Definition 3.8.

Let $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ be an argumentation framework and $\mathrm{(}\ell \mathrm{,}\mathit{a}\mathit{d}\mathrm{)}$ be an input. We then define the semantic constraint function for the admissible semantics as follows: $$\begin{array}{l}\hfill {\mathit{AttCon}}_{\mathit{a}\mathit{d}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}=\left\{\begin{array}{cc}{\bigwedge }_{\mathit{b}\in \mathsf{Arg}\setminus \mathsf{out}\mathrm{(}\ell \mathrm{)}}\neg {\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}\hfill \\ {\bigvee }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}{\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{out}\mathrm{(}\ell \mathrm{)}\hfill \\ {\bigwedge }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}\neg {\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{undec}\mathrm{(}\ell \mathrm{)}\hfill \end{array}\right.\end{array}$$

The attack constraints computed via the semantic constraint function ${\mathit{AttCon}}_{\mathit{a}\mathit{d}}$ are sound and complete for admissible input labelings. Theorem 3.2.

Let $\mathrm{(}\ell \mathrm{,}\mathit{a}\mathit{d}\mathrm{)}$ be an admissible input and ${\mathit{C}}_{\ell }$ is the labeling constraint of ℓ computed via ${\mathit{AttCon}}_{\mathit{a}\mathit{d}}$ . With $\mathbb{F}$ we denote the set of argumentation frameworks that satisfy ${\mathit{C}}_{\ell }$ , i.e for all $\mathit{F}\in \mathbb{F}$ we have that $\mathit{F}\vDash {\mathit{C}}_{\ell }$ .

The semantic constraint function ${\mathit{AttCon}}_{\mathit{a}\mathit{d}}$ is sound for admissible input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}\in \mathbb{F}:\ell \mathit{\text{ is an}}\text{ ad}\mathit{\text{-labeling of }}\mathit{F}\end{array}$$ and the semantic constraint function ${\mathit{AttCon}}_{\mathit{a}\mathit{d}}$ is complete for admissible input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}:\ell \mathit{\text{ is an}}\text{ ad}\mathit{\text{-labeling of }}\mathit{F}⟹\mathit{F}\in \mathbb{F}.\end{array}$$

Example 3.

Let us consider the set of arguments $\mathsf{Arg}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ and the admissible input labeling $\ell =\{\mathsf{in}=\{\mathit{a}\}\mathrm{,}\mathsf{out}=\{\mathit{c}\}\mathrm{,}\mathsf{undec}=\{\mathit{b}\mathrm{,}\mathit{d}\}\}$ over these arguments. We can then use the above defined function ${\mathit{AttCon}}_{\mathit{a}\mathit{d}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}$ to compute the attack constraint of each argument in $\mathsf{Arg}$ : $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}}={\mathit{AttCon}}_{\mathit{a}\mathit{d}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{a}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{a}}\\ \hfill & {\mathit{C}}_{\mathit{b}}={\mathit{AttCon}}_{\mathit{a}\mathit{d}}\mathrm{(}\mathit{b}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{a}\mathit{b}}\\ \hfill & {\mathit{C}}_{\mathit{c}}={\mathit{AttCon}}_{\mathit{a}\mathit{d}}\mathrm{(}\mathit{c}\mathrm{,}\ell \mathrm{)}={\mathit{r}}_{\mathit{a}\mathit{c}}\\ \hfill & {\mathit{C}}_{\mathit{d}}={\mathit{AttCon}}_{\mathit{a}\mathit{d}}\mathrm{(}\mathit{d}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{a}\mathit{d}}\end{array}$$

These conditions represent the input labeling ℓ and impose some restrictions on any argumentation framework that wants to be consistent with the labeling. For the only $\mathsf{in}$ -labeled argument a we have that it must not be attacked by itself, or any of the $\mathsf{undec}$ -labeled arguments b an d. Otherwise a would not be defended and thus not admissible. Like in the case of conflict-free labelings, the $\mathsf{undec}$ -labeled arguments b and d cannot be attacked by the $\mathsf{in}$ -labeled argument a. Finally, the argument c with the label $\mathsf{out}$ has to be attacked by a, since that is the only $\mathsf{in}$ -labeled argument in this example.

The attacks represented by all atoms $\mathit{r}\in \mathit{attackAtoms}\mathrm{(}\mathsf{Arg}\mathrm{)}$ which are not mentioned in the attack constraints are again considered to be possible but not necessary.

3.2.3. Complete semantics

We recall that a labeling ℓ is considered complete if it satisfies the following three conditions:

1. ℓ is admissible.

2. if some attacker of a is labeled $\mathsf{in}$ then a is labeled $\mathsf{out}$ .

3. if all attackers of a are labeled $\mathsf{out}$ then a is labeled $\mathsf{in}$ .

The attack constraints for a complete input $\mathrm{(}\ell \mathrm{,}\mathit{co}\mathrm{)}$ are therefore a stronger version of the constraints for admissible labelings. The attack constraints for $\mathsf{in}$ -labeled arguments is the same as before, capturing both conflict-freeness and defense. The constraint for arguments with the label $\mathsf{out}$ are also identical and just require some attack from any $\mathsf{in}$ -labeled argument. However, the attack constraint for $\mathsf{undec}$ -labeled arguments is different for complete labelings and now consists of two parts. The first part states that an $\mathsf{undec}$ -labeled argument a cannot be attacked by an $\mathsf{in}$ -labeled argument and is the same as before. But in addition to that the argument a has to be attacked by some $\mathsf{undec}$ -labeled argument in order to be labeled $\mathsf{undec}$ . This can be an attack from some other argument or even the argument a itself. This additional constraint is necessary to capture the completeness property: Every argument that is defended by $\mathsf{in}\mathrm{(}\ell \mathrm{)}$ has to be included in $\mathsf{in}\mathrm{(}\ell \mathrm{)}$ . Assuming that there is no attack from another $\mathsf{undec}$ -labeled argument, then the argument a can only be attacked by arguments with the label $\mathsf{out}$ . But, in that case the argument would be defended by $\mathsf{in}\mathrm{(}\ell \mathrm{)}$ and thus should be labeled $\mathsf{in}$ instead of $\mathsf{undec}$ .

Definition 3.9.

Let $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ be an argumentation framework and $\mathrm{(}\ell \mathrm{,}\mathit{co}\mathrm{)}$ be an input. We then define the semantic constraint function for the complete semantics as follows: $$\begin{array}{l}\hfill {\mathit{AttCon}}_{\mathit{co}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}=\left\{\begin{array}{cc}{\bigwedge }_{\mathit{b}\in \mathsf{Arg}\setminus \mathsf{out}\mathrm{(}\ell \mathrm{)}}\neg {\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}\hfill \\ {\bigvee }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}{\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{out}\mathrm{(}\ell \mathrm{)}\hfill \\ {\bigwedge }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}\neg {\mathit{r}}_{\mathit{b}\mathit{a}}\wedge \mathrm{(}{\bigvee }_{\mathit{c}\in \mathsf{undec}\mathrm{(}\ell \mathrm{)}}{\mathit{r}}_{\mathit{c}\mathit{a}}\mathrm{)}\hfill & \text{if }\mathit{a}\in \mathsf{undec}\mathrm{(}\ell \mathrm{)}\hfill \end{array}\right.\end{array}$$

The attack constraints computed via the semantic constraint function ${\mathit{AttCon}}_{\mathit{co}}$ are sound and complete for complete input labelings. Theorem 3.3.

Let $\mathrm{(}\ell \mathrm{,}\mathit{co}\mathrm{)}$ be a complete input and ${\mathit{C}}_{\ell }$ is the labeling constraint of ℓ computed via ${\mathit{AttCon}}_{\mathit{co}}$ . With $\mathbb{F}$ we denote the set of argumentation frameworks that satisfy ${\mathit{C}}_{\ell }$ , i.e for all $\mathit{F}\in \mathbb{F}$ we have that $\mathit{F}\vDash {\mathit{C}}_{\ell }$ .

The semantic constraint function ${\mathit{AttCon}}_{\mathit{co}}$ is sound for complete input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}\in \mathbb{F}:\ell \mathit{\text{ is a}}\text{ co}\mathit{\text{-labeling of }}\mathit{F}\end{array}$$ and the semantic constraint function ${\mathit{AttCon}}_{\mathit{co}}$ is complete for complete input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}:\ell \mathit{\text{ is a}}\text{ co}\mathit{\text{-labeling of }}\mathit{F}⟹\mathit{F}\in \mathbb{F}.\end{array}$$

Example 4.

Let us consider the set of arguments $\mathsf{Arg}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ and the complete input labeling $\ell =\{\mathsf{in}=\{\mathit{c}\}\mathrm{,}\mathsf{out}=\{\mathit{a}\}\mathrm{,}\mathsf{undec}=\{\mathit{b}\mathrm{,}\mathit{d}\}\}$ over these arguments. We can then use the above defined function ${\mathit{AttCon}}_{\mathit{co}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}$ to compute the attack constraint of each argument in $\mathsf{Arg}$ : $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}}={\mathit{AttCon}}_{\mathit{co}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}={\mathit{r}}_{\mathit{c}\mathit{a}}\\ \hfill & {\mathit{C}}_{\mathit{b}}={\mathit{AttCon}}_{\mathit{co}}\mathrm{(}\mathit{b}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{c}\mathit{b}}\wedge \mathrm{(}{\mathit{r}}_{\mathit{b}\mathit{b}}\vee {\mathit{r}}_{\mathit{d}\mathit{b}}\mathrm{)}\\ \hfill & {\mathit{C}}_{\mathit{c}}={\mathit{AttCon}}_{\mathit{co}}\mathrm{(}\mathit{c}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{b}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{c}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{c}}\\ \hfill & {\mathit{C}}_{\mathit{d}}={\mathit{AttCon}}_{\mathit{co}}\mathrm{(}\mathit{d}\mathrm{,}\ell \mathrm{)}=\neg {\mathit{r}}_{\mathit{c}\mathit{d}}\wedge \mathrm{(}{\mathit{r}}_{\mathit{b}\mathit{d}}\vee {\mathit{r}}_{\mathit{d}\mathit{d}}\mathrm{)}\end{array}$$

Like before, the only $\mathsf{out}$ -labeled argument a must be attacked by the only $\mathsf{in}$ -labeled argument c. The argument c with the label $\mathsf{in}$ can then not be attacked by itself or any of the $\mathsf{undec}$ -labeled arguments b and d. Like in the example for admissible conditions, the arguments b and d are undecided. That means by definition they cannot be attacked by the $\mathsf{in}$ -labeled argument c. However, since the input labeling is complete in addition to that they have to be attacked by any $\mathsf{undec}$ -labeled argument.

We have again a few other possible attacks in this example, for instance the argument a can additionally be attacked by itself, b or d while still satisfying the attack constraints.

3.2.4. Stable semantics

A labeling ℓ is considered stable if it is a $\mathit{co}$ -labeling and we have that $\mathsf{undec}\mathrm{(}\ell \mathrm{)}=\varnothing$ . So, if we have a stable input $\mathrm{(}\ell \mathrm{,}\mathit{st}\mathrm{)}$ we do not have any arguments in $\mathsf{undec}\mathrm{(}\ell \mathrm{)}$ since every argument of the argumentation framework is either in the corresponding stable extension or attacked by it. The constraints for $\mathsf{in}$ and $\mathsf{out}$ -labeled arguments are the same as in the conflict-free case. An argument that is labeled $\mathsf{in}$ cannot be attacked by any argument that is also labeled $\mathsf{in}$ . We longer need to include the defense part of the admissible or complete attack constraints, since there exists no $\mathsf{undec}$ -labeled argument per definition. If an argument is labeled $\mathsf{out}$ it has to be attacked by at least one argument $\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}$ .

Definition 3.10.

Let $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ be an argumentation framework and $\mathrm{(}\ell \mathrm{,}\mathit{st}\mathrm{)}$ be an input. We then define the semantic constraint function for the stable semantics as follows: $$\begin{array}{l}\hfill {\mathit{AttCon}}_{\mathit{st}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}=\left\{\begin{array}{cc}{\bigwedge }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}\neg {\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}\hfill \\ {\bigvee }_{\mathit{b}\in \mathsf{in}\mathrm{(}\ell \mathrm{)}}{\mathit{r}}_{\mathit{b}\mathit{a}}\hfill & \text{if }\mathit{a}\in \mathsf{out}\mathrm{(}\ell \mathrm{)}\hfill \end{array}\right.\end{array}$$

The attack constraints computed via the semantic constraint function ${\mathit{AttCon}}_{\mathit{st}}$ are sound and complete for stable input labelings. Theorem 3.4.

Let $\mathrm{(}\ell \mathrm{,}\mathit{st}\mathrm{)}$ be a stable input and ${\mathit{C}}_{\ell }$ is the labeling constraint of ℓ computed via ${\mathit{AttCon}}_{\mathit{st}}$ . With $\mathbb{F}$ we denote the set of argumentation frameworks that satisfy ${\mathit{C}}_{\ell }$ , i.e for all $\mathit{F}\in \mathbb{F}$ we have that $\mathit{F}\vDash {\mathit{C}}_{\ell }$ .

The semantic constraint function ${\mathit{AttCon}}_{\mathit{st}}$ is sound for stable input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}\in \mathbb{F}:\ell \mathit{\text{ is a}}\text{ st}\mathit{\text{-labeling of }}\mathit{F}\end{array}$$ and the semantic constraint function ${\mathit{AttCon}}_{\mathit{st}}$ is complete for stable input labelings ℓ, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}:\ell \mathit{\text{ is a}}\text{ st}\mathit{\text{-labeling of }}\mathit{F}⟹\mathit{F}\in \mathbb{F}.\end{array}$$

3.2.5. Other semantics

Besides the already mentioned semantics, Dung also introduced the grounded and preferred semantics in his seminal paper [15]. However, for both of these semantics, there exists no semantic constraint function which is sound and complete. The reason for that lies in the minimality and maximality constraints w.r.t. set inclusion for these semantics. The semantic constraint functions are supposed to return local constraints, i.e., a formula in $\mathcal{L}\mathrm{(}\mathit{inAttacks}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}$ . Clearly, such a local formula is not able to express minimality/maximality among multiple labelings.

Proposition 3.2.

There exists no sound and complete semantic constraint function for the grounded semantics.

Proof.

Assume the contrary. Let ${\mathit{AttCon}}_{\mathit{gr}}$ be the semantic constraint function that is sound and complete for $\mathit{gr}$ . Consider the labeling $\ell =\{\mathsf{in}=\{\mathit{a}\mathrm{,}\mathit{c}\}\mathrm{,}\mathsf{out}=\{\mathit{b}\}\mathrm{,}\mathsf{undec}=\varnothing \}$ . One AF which has ℓ as its grounded labeling is the AF $\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ . If we add the attack $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ then ℓ is no longer the grounded labeling of this AF. Soundness then implies that we must have ${\mathit{AttCon}}_{\mathit{gr}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}\vDash \neg {\mathit{r}}_{\mathit{b}\mathit{a}}$ . However, another AF which has ℓ as its grounded labeling is the AF $\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ . This time, if we add the attack $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ , then ℓ is still the grounded labeling of this AF. Completeness then implies that we have ${\mathit{AttCon}}_{\mathit{gr}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}⊭\neg {\mathit{r}}_{\mathit{b}\mathit{a}}$ . This is a contradiction, and hence there is no semantic constraint function that is sound and complete for the grounded semantics. □

Proposition 3.3.

There exists no sound and complete semantic constraint function for the preferred semantics.

Proof.

Assume the contrary. Let ${\mathit{AttCon}}_{\mathit{pr}}:\mathsf{Arg}\times \mathbb{L}\mathrm{(}\mathsf{Arg}\mathrm{)}⟶\mathcal{L}\mathrm{(}\mathit{inAttacks}\mathrm{(}\mathit{a}\mathrm{)}\mathrm{)}$ be the semantic constraint function that is sound and complete for $\mathit{pr}$ . Consider the labeling $\ell =\{\mathsf{in}=\varnothing \mathrm{,}\mathsf{out}=\varnothing \mathrm{,}\mathsf{undec}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\}$ . One AF which has ℓ as a preferred labeling is the AF $\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{c}\mathrm{)}\}\mathrm{)}$ . If we add the attack $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ then ℓ is no longer a preferred labeling of this AF. Soundness then implies that we must have ${\mathit{AttCon}}_{\mathit{pr}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}\vDash \neg {\mathit{r}}_{\mathit{b}\mathit{a}}$ . However, another AF which has ℓ as a preferred labeling is the AF $\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\}\mathrm{)}$ . This time, if we add the attack $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ , then ℓ is still a preferred labeling of this AF. Completeness then implies that we have ${\mathit{AttCon}}_{\mathit{pr}}\mathrm{(}\mathit{a}\mathrm{,}\ell \mathrm{)}⊭\neg {\mathit{r}}_{\mathit{b}\mathit{a}}$ . This is a contradiction, and hence there is no semantic constraint function that is sound and complete for the preferred semantics. □

3.3. Algorithm

In the following we will introduce an algorithm for learning argumentation frameworks from labelings. The input of this algorithm is a set of arguments $\mathsf{Arg}$ and a set of inputs $\mathit{L}=\{\mathrm{(}{\ell }_1\mathrm{,}{\mathit{\sigma }}_1\mathrm{)}\mathrm{,}\dots \}$ . Our algorithm works in an iterative way. That means, each input labeling is processed independently one by one. So, the algorithm is able to consider a stream of input labelings and provide intermediate results after each processed labeling. The procedure for the algorithm is shown in Algorithm 1. In each iteration, the input parameters of the algorithm include a mapping C of the arguments to their current attack constraint. Before processing the first input labeling we assign to each argument a the initial attack constraint ${\mathit{C}}_{\mathit{a}}=\top$ . So, by default no attacks are necessary to satisfy the constraint, which means all argumentation frameworks $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ are consistent with the empty set of conditions, as would be expected.

The main procedure of the algorithm can essentially be split into three parts:

1. Computing the labeling constraint ${\mathit{C}}_{\ell }$ for the input labeling.

2. Combining the labeling constraint ${\mathit{C}}_{\ell }$ with the input constraints C.

3. Constructing the set of argumentation frameworks $\mathbb{F}$ from the constraints in C.

Algorithm 1

Iterative algorithm for learning argumentation frameworks from labelings

In each iteration of the algorithm we take a mapping of constraints C, the set of arguments $\mathsf{Arg}$ and some input $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}\in \mathit{L}$ as input. When we reference the mapping as ${\mathit{C}}_{\mathit{a}}$ we mean the constraint for argument a as stored in the mapping C.

For the input we compute the attack constraint ${\mathit{C}}_{\mathit{a}\mathrm{,}\ell }$ of each argument $\mathit{a}\in \mathsf{Arg}$ via the semantic constraint function ${\mathit{AttCon}}_{\mathit{\sigma }}$ .

In the second step, we combine the labeling constraint ${\mathit{C}}_{\mathit{a}\mathrm{,}\ell }$ for each argument a with the existing attack constraint ${\mathit{C}}_{\mathit{a}}$ . We want to compute argumentation frameworks that satisfy all input labelings, therefore the combined constraint for an argument a is just the logical conjunction of the constraints of the argument for each labeling. The updated constraint overwrites the constraint for the argument in the mapping C.

The third and final step is to construct the set of argumentation frameworks $\mathbb{F}$ for the updated attack constraint mapping C. For this, we use the mapping $\mathit{modelToAttacks}\mathrm{(}\mathcal{A}\mathrm{)}$ described in Definition 3.3. In particular, we compute the set of models ${\mathcal{M}}_{\mathit{a}}$ for each argument $\mathit{a}\in \mathsf{Arg}$ . It should be noted that the model computation for these constraints are independent of each other and thus can be done in parallel. If we then pick one model ${\mathcal{A}}_{\mathit{i}}\in {\mathcal{M}}_{{\mathit{a}}_{\mathit{i}}}$ for each argument, we obtain a consistent argumentation framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathit{modelToAttacks}\mathrm{(}{\mathcal{A}}_1\cup \cdots \cup {\mathcal{A}}_{\mathit{n}}\mathrm{)}\mathrm{)}$ . If we consider all different combinations of models we obtain the set of all consistent argumentation frameworks $\mathbb{F}$ .

This step is optional, since we only need the mapping of attack constraints C with the updated constraints for each argument for further learning. So, after each learning iteration the algorithm returns the updated set of attack constraints C and (if wanted) the set of constructed argumentation frameworks $\mathbb{F}$ .

Regarding the complexity of constructing argumentation frameworks for a set of attack constraints. We can consider the constraints in clausal form, which follows easily from the definition of the semantic constraint functions. A very helpful property of the attack constraints in clausal form is, that all clauses contain at most one negated literal, i.e., each clause is a dual-horn clause. That means, the process of constructing an argumentation framework for a given set of attack constraints can be considered as a Dual-Horn SAT problem, which is P-complete [14]. Thus, the construction argumentation frameworks can be done in polynomial time, more precisely in linear time with respect to the size of the attack constraints which is in $\mathit{O}\mathrm{(}{\mathit{n}}^2|\mathit{L}|\mathrm{)}$ , where n is the number of arguments and L is the set of learned labelings. This can be further improved by using parallel computations, as shown by our experiments in Section 4.

3.3.1. Properties

In the following we will look at some useful properties that the previously defined algorithm satisfies, namely soundness, completeness and monotonicity.

Theorem 3.5.

Let L be a set of inputs and $\mathbb{F}$ is the set of argumentation frameworks constructed by the procedure described in Algorithm  1 by iteratively processing L. For every ${\mathit{\sigma }}_{\mathit{i}}$ in the set of inputs there exists a sound and complete semantic constraint function, i.e., ${\mathit{\sigma }}_{\mathit{i}}\in \{\mathit{cf}\mathrm{,}\mathit{a}\mathit{d}\mathrm{,}\mathit{co}\mathrm{,}\mathit{st}\}$ .

The algorithm is sound for all input labelings, i.e., $$\begin{array}{l}\hfill \forall \mathit{F}\in \mathbb{F}:\forall \mathrm{(}{\ell }_{\mathit{i}}\mathrm{,}{\mathit{\sigma }}_{\mathit{i}}\mathrm{)}\in \mathit{L}:\ell \mathit{\text{ is a }}{\mathit{\sigma }}_{\mathit{i}}\mathit{\text{-labeling of }}\mathit{F}\end{array}$$

The algorithm is complete for all input labelings, i.e., $$\begin{array}{l}\hfill \forall \mathit{G}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}:\mathrm{(}\forall \mathrm{(}{\ell }_{\mathit{i}}\mathrm{,}{\mathit{\sigma }}_{\mathit{i}}\mathrm{)}\in \mathit{L}:\ell \mathit{\text{ is a }}{\mathit{\sigma }}_{\mathit{i}}\mathit{\text{-labeling of }}\mathit{G}\mathrm{)}⟹\mathit{G}\in \mathbb{F}\end{array}$$

As shown in Theorem 3.5 the algorithm based on the above defined attack constraints is sound and complete for any combination of inputs with respect to all four semantics. That means, the algorithm computes exactly the set of argumentation frameworks that are consistent with the input labelings. From the proof of Theorem 3.5 it also follows that the order in which the labelings are processed by the algorithm does not matter.

Proposition 3.4.

Let $\mathsf{Arg}$ be a set of arguments and ${\ell }_1$ , ${\ell }_2$ are labelings. With $\mathbb{F}$ we denote the set of argumentation frameworks constructed by Algorithm  1 for the input labelings ${\ell }_1$ and ${\ell }_2$ .

Then, the order in which the labelings are learned has no influence on the constructed set of argumentation frameworks $\mathbb{F}$ .

Another property of the algorithm is monotonicity (see Theorem 3.6), or more precisely the algorithm is monotonically refining. That means, if we have a set of labelings ${\mathit{L}}_2$ with ${\mathit{L}}_2\supseteq {\mathit{L}}_1$ then the set of argumentation frameworks ${\mathbb{F}}_2$ constructed for ${\mathit{L}}_2$ will be a subset of the frameworks constructed for ${\mathit{L}}_1$ . In other words, if we learn an additional labeling the number of argumentation frameworks that satisfy all attack constraints can only stay the same or become smaller. Theorem 3.6.

Let $\mathsf{Arg}$ be a set of arguments and ${\mathit{L}}_1$ , ${\mathit{L}}_2$ are sets of inputs. ${\mathbb{F}}_1$ , ${\mathbb{F}}_2$ denote the sets of argumentation frameworks constructed by Algorithm  1 for the input labelings in ${\mathit{L}}_1$ and ${\mathit{L}}_2$ respectively.

The algorithm for constructing argumentation frameworks from labelings is monotonically refining, i.e., $$\begin{array}{l}\hfill \forall {\mathit{L}}_1\mathrm{,}{\mathit{L}}_2\in \mathbb{L}\mathrm{(}\mathsf{Arg}\mathrm{)}:{\mathit{L}}_1\supseteq {\mathit{L}}_2⟹{\mathbb{F}}_1\subseteq {\mathbb{F}}_2\end{array}$$

3.4. Example

This section will showcase the application of Algorithm 1. Assume the following situation. Unknown to us, there is the hidden argumentation framework as shown in Fig. 2. Given are only the set of arguments $\mathsf{Arg}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\}$ and the set of inputs $\mathit{L}=\{\mathrm{(}{\ell }_1\mathrm{,}\mathit{a}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}{\ell }_2\mathrm{,}\mathit{co}\mathrm{)}\mathrm{,}\mathrm{(}{\ell }_3\mathrm{,}\mathit{cf}\mathrm{)}\}$ . The three input labelings are shown in Fig. 3. Our goal is to construct all argumentation frameworks that are consistent with these three labelings.

Fig. 2.

The hidden argumentation framework from which the input labelings are generated.

Fig. 3.

The three input labelings: ${\ell }_1$ is admissible, ${\ell }_2$ is complete and ${\ell }_3$ is conflict-free.

We start the process of learning with the admissible labeling ${\ell }_1=\{\mathsf{in}=\{\mathit{a}\}\mathrm{,}\mathsf{out}=\{\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\mathsf{undec}=\{\mathit{d}\mathrm{,}\mathit{e}\}\}$ . The first step is computing the labeling-specific attack constraint for each argument. The labeling ${\ell }_1$ is admissible, so we will use the semantic constraint function ${\mathit{AttCon}}_{\mathit{a}\mathit{d}}$ from Definition 3.8. The argument a is labeled $\mathsf{in}$ , that means it cannot be attacked by any $\mathsf{in}$ - or $\mathsf{undec}$ -labeled argument. b and c are labeled $\mathsf{out}$ , thus they have to be attacked by the only $\mathsf{in}$ -labeled argument a. The arguments d and e are $\mathsf{undec}$ which means they cannot be attacked by the $\mathsf{in}$ -labeled argument a. That leaves us with the following attack constraints after the first labeling: $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}}=\neg {\mathit{r}}_{\mathit{a}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{ea}}\\ \hfill & {\mathit{C}}_{\mathit{b}}={\mathit{r}}_{\mathit{a}\mathit{b}}\\ \hfill & {\mathit{C}}_{\mathit{c}}={\mathit{r}}_{\mathit{a}\mathit{c}}\\ \hfill & {\mathit{C}}_{\mathit{d}}=\neg {\mathit{r}}_{\mathit{a}\mathit{d}}\\ \hfill & {\mathit{C}}_{\mathit{e}}=\neg {\mathit{r}}_{\mathit{ae}}\end{array}$$

After processing the first labeling we know that the argument a must attack b and c. We also know that some attacks cannot exist, but there are still many possibilities for attacks. For example, the argument a can still be attacked by b or c and the resulting frameworks would still be consistent with ${\ell }_1$ . There can also be many different combinations of attacks between the arguments b, c, d and e. This iteration of the algorithm would then return the set of attack constraints $\mathit{C}=\{{\mathit{C}}_{\mathit{a}}\mathrm{,}{\mathit{C}}_{\mathit{b}}\mathrm{,}{\mathit{C}}_{\mathit{c}}\mathrm{,}{\mathit{C}}_{\mathit{d}}\mathrm{,}{\mathit{C}}_{\mathit{e}}\}$ .

Lets consider the next labeling ${\ell }_2=\{\mathsf{in}=\{\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\mathsf{out}=\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\mathsf{undec}=\{\mathit{e}\}\}$ , which is complete. For this labeling we will use the semantic constraint function ${\mathit{AttCon}}_{\mathit{co}}$ (see Definition 3.9). This labeling tells us, for example, that the $\mathsf{out}$ -labeled arguments a and d must be attacked by either b or c. The $\mathsf{in}$ -labeled arguments b and c cannot be attacked by any $\mathsf{in}$ - or $\mathsf{undec}$ -labeled arguments. The argument e is the only $\mathsf{undec}$ -labeled argument and since ${\ell }_2$ is complete it follows that e has to attack itself. This gives us the following set of attack constraints ${\mathit{C}}_{{\ell }_2}$ for the labeling ${\ell }_2$ : $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}\mathrm{,}{\ell }_2}={\mathit{r}}_{\mathit{b}\mathit{a}}\vee {\mathit{r}}_{\mathit{c}\mathit{a}}\\ \hfill & {\mathit{C}}_{\mathit{b}\mathrm{,}{\ell }_2}=\neg {\mathit{r}}_{\mathit{b}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{c}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{eb}}\\ \hfill & {\mathit{C}}_{\mathit{c}\mathrm{,}{\ell }_2}=\neg {\mathit{r}}_{\mathit{b}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{c}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{ec}}\\ \hfill & {\mathit{C}}_{\mathit{d}\mathrm{,}{\ell }_2}={\mathit{r}}_{\mathit{b}\mathit{d}}\vee {\mathit{r}}_{\mathit{c}\mathit{d}}\\ \hfill & {\mathit{C}}_{\mathit{e}\mathrm{,}{\ell }_2}=\neg {\mathit{r}}_{\mathit{be}}\wedge \neg {\mathit{r}}_{\mathit{ce}}\wedge {\mathit{r}}_{\mathit{ee}}\end{array}$$

We now have to combine the constraints C from the last step with the contraints ${\mathit{C}}_{{\ell }_2}$ from this step. Since the argumentation frameworks we are looking for should be consistent with all input labelings we use a conjunction to combine the attack constraints. So, for each argument we set ${\mathit{C}}_{\mathit{a}}={\mathit{C}}_{\mathit{a}}\wedge {\mathit{C}}_{\mathit{a}\mathrm{,}{\ell }_2}$ . If we do this for all arguments, we obtain the following attack constraints: $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}}=\neg {\mathit{r}}_{\mathit{a}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{ea}}\wedge \mathrm{(}{\mathit{r}}_{\mathit{b}\mathit{a}}\vee {\mathit{r}}_{\mathit{c}\mathit{a}}\mathrm{)}\\ \hfill & {\mathit{C}}_{\mathit{b}}={\mathit{r}}_{\mathit{a}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{c}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{eb}}\\ \hfill & {\mathit{C}}_{\mathit{c}}={\mathit{r}}_{\mathit{a}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{c}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{ec}}\\ \hfill & {\mathit{C}}_{\mathit{d}}=\neg {\mathit{r}}_{\mathit{a}\mathit{d}}\wedge \mathrm{(}{\mathit{r}}_{\mathit{b}\mathit{d}}\vee {\mathit{r}}_{\mathit{c}\mathit{d}}\mathrm{)}\\ \hfill & {\mathit{C}}_{\mathit{e}}=\neg {\mathit{r}}_{\mathit{ae}}\wedge \neg {\mathit{r}}_{\mathit{be}}\wedge \neg {\mathit{r}}_{\mathit{ce}}\wedge {\mathit{r}}_{\mathit{ee}}\end{array}$$

We have now reduced the number of possibilities even further. The argument a has to be attacked by either b or c and cannot be attacked by any other argument. The arguments b and c have to be attacked by a. They could also be attacked by d, but this attack is optional. d has to be attacked by b or c and optionally can also be attacked by itself or e. Finally, e has to attack itself and can also optionally be attacked by d. One observation we can make is that most of the uncertainty in the attack constraints is related to the argument d as it can still optionally attack b, c, e and itself. The algorithm then returns the updated set of attack constraints C.

The third and last input labeling ${\ell }_3=\{\mathsf{in}=\{\mathit{d}\}\mathrm{,}\mathsf{out}=\{\mathit{e}\}\mathrm{,}\mathsf{undec}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\}$ is conflict-free. In our current situation it is very helpful to learn this labeling, because the fact that d is labeled $\mathsf{in}$ allows us to clear the uncertainty regarding its outgoing attacks. The labeling tells us that d cannot attack a, b, c and itself. In addition to that, we now know that d has to attack the $\mathsf{out}$ -labeled argument e since d is the only argument with the label $\mathsf{in}$ . For the labeling ${\ell }_3$ we obtain the following attack constraints: $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}\mathrm{,}{\ell }_3}=\neg {\mathit{r}}_{\mathit{d}\mathit{a}}\\ \hfill & {\mathit{C}}_{\mathit{b}\mathrm{,}{\ell }_3}=\neg {\mathit{r}}_{\mathit{d}\mathit{b}}\\ \hfill & {\mathit{C}}_{\mathit{c}\mathrm{,}{\ell }_3}=\neg {\mathit{r}}_{\mathit{d}\mathit{c}}\\ \hfill & {\mathit{C}}_{\mathit{d}\mathrm{,}{\ell }_3}=\neg {\mathit{r}}_{\mathit{d}\mathit{d}}\\ \hfill & {\mathit{C}}_{\mathit{e}\mathrm{,}{\ell }_3}={\mathit{r}}_{\mathit{de}}\end{array}$$

Again, we combine the attack constraints ${\mathit{C}}_{\ell }$ with the constraints C from the previous step via a conjunction. When combining the constraints we can also apply simplifications, however this is not necessary in this example. So, the attack constraints after learning all three labelings look like this: $$\begin{array}{ll}\hfill & {\mathit{C}}_{\mathit{a}}=\neg {\mathit{r}}_{\mathit{a}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{a}}\wedge \neg {\mathit{r}}_{\mathit{ea}}\wedge \mathrm{(}{\mathit{r}}_{\mathit{b}\mathit{a}}\vee {\mathit{r}}_{\mathit{c}\mathit{a}}\mathrm{)}\\ \hfill & {\mathit{C}}_{\mathit{b}}={\mathit{r}}_{\mathit{a}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{c}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{b}}\wedge \neg {\mathit{r}}_{\mathit{eb}}\\ \hfill & {\mathit{C}}_{\mathit{c}}={\mathit{r}}_{\mathit{a}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{b}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{c}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{c}}\wedge \neg {\mathit{r}}_{\mathit{ec}}\\ \hfill & {\mathit{C}}_{\mathit{d}}=\neg {\mathit{r}}_{\mathit{a}\mathit{d}}\wedge \neg {\mathit{r}}_{\mathit{d}\mathit{d}}\wedge \mathrm{(}{\mathit{r}}_{\mathit{b}\mathit{d}}\vee {\mathit{r}}_{\mathit{c}\mathit{d}}\mathrm{)}\\ \hfill & {\mathit{C}}_{\mathit{e}}=\neg {\mathit{r}}_{\mathit{ae}}\wedge \neg {\mathit{r}}_{\mathit{be}}\wedge \neg {\mathit{r}}_{\mathit{ce}}\wedge {\mathit{r}}_{\mathit{de}}\wedge {\mathit{r}}_{\mathit{ee}}\end{array}$$

These attack constraints now represent exactly the set of argumentation frameworks that are consistent with all three input labelings. The final step of the algorithm is now to construct these argumentation frameworks. Here, we use the fact that the atoms used in the attack constraints directly correspond to attacks in an argumentation framework, as described in Definition 3.3. First, we compute the models of the attack constraints of each argument: $$\begin{array}{l}{\mathcal{M}}_{\mathit{a}}=\{[{\mathit{r}}_{\mathit{b}\mathit{a}}\to \mathit{true}]\mathrm{,}[{\mathit{r}}_{\mathit{c}\mathit{a}}\to \mathit{true}]\mathrm{,}[{\mathit{r}}_{\mathit{b}\mathit{a}}\mathrm{,}{\mathit{r}}_{\mathit{c}\mathit{a}}\to \mathit{true}]\}\\ {\mathcal{M}}_{\mathit{b}}=\{[{\mathit{r}}_{\mathit{a}\mathit{b}}\to \mathit{true}]\}\\ {\mathcal{M}}_{\mathit{c}}=\{[{\mathit{r}}_{\mathit{a}\mathit{c}}\to \mathit{true}]\}\\ \begin{array}{cc}\hfill {\mathcal{M}}_{\mathit{d}}=& \{[{\mathit{r}}_{\mathit{b}\mathit{d}}\to \mathit{true}]\mathrm{,}[{\mathit{r}}_{\mathit{c}\mathit{d}}\to \mathit{true}]\mathrm{,}[{\mathit{r}}_{\mathit{b}\mathit{d}}\mathrm{,}{\mathit{r}}_{\mathit{c}\mathit{d}}\to \mathit{true}]\mathrm{,}[{\mathit{r}}_{\mathit{b}\mathit{d}}\mathrm{,}{\mathit{r}}_{\mathit{ed}}\to \mathit{true}]\mathrm{,}\hfill \\ \hfill & [{\mathit{r}}_{\mathit{c}\mathit{d}}\mathrm{,}{\mathit{r}}_{\mathit{ed}}\to \mathit{true}]\mathrm{,}[{\mathit{r}}_{\mathit{b}\mathit{d}}\mathrm{,}{\mathit{r}}_{\mathit{c}\mathit{d}}\mathrm{,}{\mathit{r}}_{\mathit{ed}}\to \mathit{true}]\}\hfill \end{array}\\ {\mathcal{M}}_{\mathit{e}}=\{[{\mathit{r}}_{\mathit{de}}\mathrm{,}{\mathit{r}}_{\mathit{ee}}\to \mathit{true}]\}\end{array}$$

The next step is constructing the corresponding partial attack relations for each model with the method $\mathit{modelToAttacks}\mathrm{(}\mathcal{A}\mathrm{)}$ . This is quite simple, since every atom directly represents an attack. For example, the model ${\mathcal{A}}_{\mathit{a}\mathrm{,}1}=[{\mathit{r}}_{\mathit{b}\mathit{a}}\to \mathit{true}]$ would have the corresponding partial attack relation ${\mathsf{R}}_{\mathit{a}\mathrm{,}1}=\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\}$ , since ${\mathit{r}}_{\mathit{b}\mathit{a}}$ is the only atom which is valuated as true in ${\mathcal{A}}_{\mathit{a}\mathrm{,}1}$ . Overall, we construct the following partial attack relations for each argument: $$\begin{array}{ll}\hfill & {\mathit{R}}_{\mathit{a}}=\left\{\right\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{c}\mathrm{,}\mathit{a}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{a}\mathrm{)}\left\}\right\}\\ \hfill & {\mathit{R}}_{\mathit{b}}=\left\{\right\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\left\}\right\}\\ \hfill & {\mathit{R}}_{\mathit{c}}=\left\{\right\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\left\}\right\}\\ \hfill & {\mathit{R}}_{\mathit{d}}=\left\{\right\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}\}\mathrm{,}\{\mathrm{(}\mathit{b}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}\left\}\right\}\\ \hfill & {\mathit{R}}_{\mathit{e}}=\left\{\right\{\mathrm{(}\mathit{d}\mathrm{,}\mathit{e}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathit{e}\mathrm{)}\left\}\right\}\end{array}$$

Here, we can see that b, c and e only have one partial attack relation while a has 3 and the argument d has 6 corresponding partial attack relations. That means, overall we will have $3\ast 6=18$ different argumentation frameworks. These frameworks are constructed by taking all possible combinations while taking one partial attack relation from each argument, i.e., we obtain the set of all attack relations ${\mathit{R}}_{\mathit{L}}={\mathit{R}}_{\mathit{a}}\times {\mathit{R}}_{\mathit{b}}\times {\mathit{R}}_{\mathit{c}}\times {\mathit{R}}_{\mathit{d}}\times {\mathit{R}}_{\mathit{e}}$ . We then take these attack relations ${\mathsf{R}}_{\mathit{i}}\in {\mathit{R}}_{\mathit{L}}$ and assemble the corresponding argumentation framework ${\mathit{F}}_{\mathit{i}}=\mathrm{(}\mathsf{Arg}\mathrm{,}{\mathsf{R}}_{\mathit{i}}\mathrm{)}$ . The set $\mathbb{F}$ of all argumentation frameworks that are consistent with L then consists of exactly these argumentation frameworks.

All constructed argumentation frameworks are shown in Fig. 4. In the figure, each framework ${\mathit{F}}_{\mathit{i}}$ represents two actual argumentation frameworks: ${\mathit{F}}_{\mathit{i}}$ which is the depicted framework without the attack $\mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}$ and ${\mathit{F}}_{\mathit{i}}^{\prime }$ which does include the optional attack $\mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}$ . All of these argumentation frameworks are consistent with the three input labelings.

Fig. 4.

All 18 constructed argumentation frameworks which are consistent with the labelings ${\ell }_1$ , ${\ell }_2$ and ${\ell }_3$ . Each framework ${\mathit{F}}_{\mathit{i}}$ represents two actual argumentation frameworks: ${\mathit{F}}_{\mathit{i}}$ does not have the attack $\mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}$ and ${\mathit{F}}_{\mathit{i}}^{\prime }$ includes the optional attack $\mathrm{(}\mathit{e}\mathrm{,}\mathit{d}\mathrm{)}$ .

4. Experiments

In this section we will conduct an experimental feasibility study of the approach introduced in Section 3. For that, we will consider both a naive implementation of the algorithm, as well as an optimized implementation with parallelized learning and construction steps. For the evaluation we will measure the performance of the algorithm, i.e., the time the algorithm takes to learn the input labelings and the time for constructing an argumentation framework that satisfies the learned constraints.

We will look at two different scenarios for our experiments. In the first scenario, we will use argumentation frameworks generated with the AFBenchGen2 generators [10] in order to measure how the algorithm’s performance scales with the number of arguments. In the second scenario, we will use the benchmark argumentation frameworks from the ICCMA’19 competition [6] to measure the performance of the algorithm in a more realistic application scenario.

In the following, we briefly describe the system, both implementations and the two main metrics used for the evaluation.

System setup. The experiments were run on a machine with the Ubuntu 20.04 operating system. The machine has a 3.4 GHz Intel Xeon E5-2643v3 CPU with 12 cores and 24 threads and a total of 192 GB DDR4 memory.

Implementation. The implementation1

¹

Link to implementations: https://e.feu.de/aflearner.

has been done in Java as part of the TweetyProject library [26]. For the computation of the models of the attack constraints, needed for the construction of argumentation frameworks in the final step of the algorithm, the Java-based SAT-solver Sat4j2

²

http://www.sat4j.org

is used. In the naive version, all computations are done sequentially. On the other hand, in the optimized implementation, the learning of a labeling is done in parallel, i.e., the computation of the attack constraints for each argument. In addition to that, the computation of models of the constraints in the construction step is also done in parallel.

Metrics. In the following we define some questions that we want to answer with the experiments. Each question has a corresponding metric that will be investigated in order to answer it:

How does the time to learn a single input labeling scale with the number of arguments?

The goal of this question is measuring how the algorithm’s performance scales with the number of arguments that are considered. In order to do that, we consider the time ${\mathit{t}}_{\mathit{learn}}$ the algorithm needs for learning all input labelings and set it in relation to the number of processed input labelings $|\mathit{L}|$ . This removes the distortion of the results caused by the number of learned labelings. That means, we compute the learning time per labeling (TPL) as $$\begin{array}{ll}\hfill {\mathit{t}}_{\mathit{TPL}}& ={\displaystyle \frac{{\mathit{t}}_{\mathit{learn}}}{|\mathit{L}|}}.\end{array}$$

How much time does it take to construct an argumentation framework that is consistent with all input labelings?

For this question we measure the time ${\mathit{t}}_{\mathit{constr}}$ it takes to construct some argumentation framework $\mathit{F}\in \mathbb{F}$ that is consistent with the input labelings. This includes the computation of a model for each attack constraint. This allows us to get an idea of how the construction time scales with the number of arguments and also how effective the parallelization of the model computation is.

How close is the constructed argumentation framework to the original argumentation framework?

For that, we compare the attack relation of the constructed argumentation framework ${\mathit{F}}^{\prime }=\mathrm{(}\mathsf{Arg}\mathrm{,}{\mathsf{R}}^{\prime }\mathrm{)}$ to that of the original framework $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ by counting the number of different attacks ${\mathit{d}}_{\mathit{att}}$ between them normalized by the number of possible attacks, computed as $$\begin{array}{l}\hfill {\mathit{d}}_{\mathit{att}}={\displaystyle \frac{|\mathsf{R}\setminus {\mathsf{R}}^{\prime }|+|{\mathsf{R}}^{\prime }\setminus \mathsf{R}|}{|\mathsf{Arg}\times \mathsf{Arg}|}}.\end{array}$$ Essentially, this will give us some insight on how many uncertainty is still left after learning the input labelings. If the constructed argumentation framework is very far from the original one, i.e., ${\mathit{d}}_{\mathit{att}}\gg 0$ , then the input labelings leave many possibilities for attacks open. On the other hand, if they are close to each other, then we can assume not many argumentation frameworks are consistent with all input labelings.

4.1. Experiment 1: AFBenchGen2

The main goal of our first experiment is to investigate how our algorithm scales with the number of arguments. In particular, we are interested in how the parallelization affects the performance.

For this experiment, we generated a total of 1200 argumentation frameworks $\mathit{F}=\mathrm{(}\mathsf{Arg}\mathrm{,}\mathsf{R}\mathrm{)}$ with $\mathit{n}=|\mathsf{Arg}|=20\mathrm{,}40\mathrm{,}\dots \mathrm{,}200$ arguments with the three AFBenchGen2 generators [10]. So, for each n we have 120 argumentation frameworks, one third generated by each of the generators: WattsStrogatz, ErdösRenyi and BarabasiAlbert. For each argumentation framework we compute all inputs $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ with $\mathit{\sigma }\in \{\mathit{a}\mathit{d}\mathrm{,}\mathit{co}\mathrm{,}\mathit{st}\}$ . Then, we iteratively learn up to 1000 of these input labelings and measure the time the algorithm takes to learn them and to construct a consistent argumentation framework.

4.1.1. Results

Fig. 5.

Learning time per labeling and construction time in relation to the number of arguments for the AFs generated via AFBenchGen2.

Let us first consider the median learning time per labeling ${\mathit{t}}_{\mathit{TPL}}$ . For the naive implementation, the median time per labeling scales from 2 ms for the instances with 20 arguments up to 361 ms for the instances with 200 arguments. While the number of arguments has increased tenfold, the time per labeling has increased by a factor of 172. Fig. 5(a) shows the learning time per labeling in relation to the number of arguments. Note the logarithmic scale of the vertical axis. We can quite clearly see that the time per labeling scales polynomially with the number of arguments for the naive implementation. This is also supported by the fact that the complexity of computing the labeling constraint is in $\mathit{O}\mathrm{(}{\mathit{n}}^2\mathrm{)}$ , as we have to compute n attack constraints, one for each argument a, and for each computation we have to consider all n arguments once to determine their relation to a.

On the other hand, in the optimized implementation the median time per labeling ranges from 477 μs at 20 arguments to only 35 ms at 200 arguments, which is an increase by a factor of 73. That also means, for the smaller instances the parallelization reduces the computing time by approx. 77% and for the largest instances with 200 arguments by over 90%.

For the instances with 120 or more arguments we can observe outliers with significantly lower learning times per labeling. In these cases the argumentation frameworks had only very few labelings and thus less than the intended 1000 labelings were learned. This suggest that there is a positive correlation between the number of learned labelings and the time per labeling ${\mathit{t}}_{\mathit{TPL}}$ .

Fig. 6.

The total learning time ${\mathit{t}}_{\mathit{learn}}$ per instance in relation to the number of arguments $|\mathsf{Arg}|$ of the optimized version for larger AFs generated via AFBenchGen2.

To ensure the observed scaling of the algorithm is accurate and not due to hardware, we consider larger and thus harder instances with up to 2000 arguments, generated in a similar fashion. The results for the total learning time ${\mathit{t}}_{\mathit{learn}}$ for the optimized version of the algorithm are shown in Fig. 6. While the instances with 200 arguments have a total learning time of 13.4 s on average, the largest instances with 2000 arguments have an average total learning time of 1524 s. As before, we can observe a polynomial scaling of the learning time with the number of arguments, even for the harder instances.

We now look at the time it takes to construct an argumentation framework that is consistent with the attack constraints of the learned labelings. This includes computing a model for the attack constraint of each argument as well as converting these models to an attack relation. The time ${\mathit{t}}_{\mathit{constr}}$ it takes to do this has been measured, depending on the number of arguments, and the results are shown in Fig. 5(b). For the naive implementation, the time for constructing ranges from a median of 62 ms for $\mathit{n}=20$ to 9.7 s for the instances with 200 arguments. Similar to the time per labeling ${\mathit{t}}_{\mathit{TPL}}$ , the construction time ${\mathit{t}}_{\mathit{constr}}$ scales polynomially with the number of arguments as already discussed in Section 3.3. The optimized implementation scales a lot better with the number of arguments. The smaller instances with 20 arguments only require about 23 ms on average while the instances with 200 arguments take up to an average of 250 ms for the construction step. This is a near linear increase (factor of 11) of construction time from 20 to 200 arguments, while the naive implementation increased by a factor of 158 over the same span. Furthermore, at 200 arguments the optimized version reduces the computing time by over 97%.

Regarding the difference between original and learned argumentation framework we can observe the following. On average, less than 2% of the possible attacks were different for the instances in this experiment with a standard deviation of 0.01. The biggest difference was only 5.67%. In general, we can observe that the learned argumentation frameworks contained about 55% less attacks than the original one. This is to be expected, since in our scenario we are interested in the argumentation frameworks that produce at least the input labelings. That means, we explicitly allow other labelings to exist in the learned framework. This allows for a less restrictive attack relation, leading to fewer attacks being necessary to represent the labelings.

Overall, we can say that the paralellization is very effective in reducing the computation time for both processing a labeling as well as constructing a consistent argumentation framework in this artificial scenario. It is however more effective in the construction step than in the learning step.

4.2. Experiment 2: ICCMA’19

In the second experiment we will learn argumentation frameworks on the basis of some more realistic data in order to get an idea of the general performance of our algorithm. For that, we will use the argumentation frameworks from the ICCMA’19 competition [6]. In this experiment we consider only admissible, complete and stable labelings. It would not be feasible to construct all argumentation frameworks since there may be millions of frameworks that may be consistent with the input labelings, thus we only construct one argumentation framework that satisfies the attack constraints.

From the benchmark set, we consider all argumentation frameworks that have less than 1,000 arguments. Thus, we have 276 argumentation frameworks with the number of arguments ranging from 4 to 1,000. For each argumentation framework, we compute the inputs $\mathrm{(}\ell \mathrm{,}\mathit{\sigma }\mathrm{)}$ with $\mathit{\sigma }\in \{\mathit{a}\mathit{d}\mathrm{,}\mathit{co}\mathrm{,}\mathit{st}\}$ and randomly learn from up to 1000 input labelings. After learning, we construct one argumentation framework $\mathit{F}\in \mathbb{F}$ that satisfies all learned attack constraints, i.e., we simply take the first model computed by the SAT solver.

4.2.1. Results

In the following, the results of the first experiment are summarized and we look at each of the above defined questions and metrics.

Fig. 7.

Learning time per labeling and construction time in relation to the number of arguments in the experiment with the ICCMA’19 instances.

We consider again the time per labeling ${\mathit{t}}_{\mathit{TPL}}=\frac{{\mathit{t}}_{\mathit{learn}}}{|\mathit{L}|}$ . Fig. 7(a) shows the time per labeling in relation to the number of arguments of the corresponding ICCMA instance.

For the naive version, the time per labeling ranges from 10 μs to 10.6 s with a median of 42.25 ms per labeling. On the other hand the time per labeling ranges from 28 μs to 733 ms with a median of 3.82 ms per labeling for the optimized implementation.

On average, the optimization brings a decrease in computation time by a factor of about 10. The higher the number of arguments the higher the performance improvement. For the smallest instances with less than 10 arguments the naive implementation actually performs better. This is likely due to some computational overhead of the parallelization, but already for instances with 10 or more arguments the optimized implementation consistently and significantly outperforms the naive version.

One observation we can make for both implementations is that there are some instances for which the time per labeling is significantly lower compared to other instances of similar size. Like in the previous experiment, these are instances where less than the intended 1000 labelings have been processed (simply due to the fact that there where not enough labelings for those instances). This is likely due to the fact, that with a growing number of input labelings the attack constraints get more complex and thus it takes longer to check satisfiability.

We now consider the construction times ${\mathit{t}}_{\mathit{constr}}$ for the ICCMA’19 dataset which are shown in Fig. 7(b). The time for constructing a consistent argumentation framework ranges from 94.37 ms to 5527 s with a median of 6 s for the naive implementation. For the optimized version the times range from 51.75 ms to 16.6 s with a median of 996.8 ms. As we have already observed in the previous experiment the effect of the parallelization is even greater for the construction step where the optimized implementation is on average about 22 times faster than the naive version. Even for the smallest instances the optimized implementation is between 1.5 and 2 times faster while for the worst instances it reduces the construction time by a factor of over 200. It should be noted that we can again see the instances with less labelings learned, also being faster than comparable instances in the construction step. However, this seems to only effect the naive algorithm and the optimized algorithm has a lot less variance in its construction times.

Fig. 8.

The frequency distribution of the normalized number of different attacks ${\mathit{d}}_{\mathit{att}}$ for the ICCMA’19 instances.

Finally, Fig. 8 shows the distribution of the normalized number of different attacks ${\mathit{d}}_{\mathit{att}}$ for the ICCMA’19 instances. On average We can see that for the majority of instances the constructed argumentation framework is quite close to the original framework. This suggests that after learning 1000 labelings for these instances, there is not much uncertainty left and only a few argumentation frameworks are consistent with these labelings. However, only very few instances yield the exact same argumentation framework. If we would want to reconstruct the exact argumentation framework, we would either need additional labelings or some other information, e.g., negative examples. Interestingly, there are also a number of instances with a proportion ${\mathit{d}}_{\mathit{att}}$ of over 90%. They all have in common that the attack relation is very dense, i.e., over 90% of all possible attacks are present in the original argumentation framework. That also means these frameworks have only few labelings. Learning these labelings then means we only need very few attacks to ensure consistency with them, since we do not require there to be no further labelings for the constructed argumentation framework. In general, we can observe that the constructed argumentation frameworks contain on average 70% less attacks than the original framework. This is again related to the fact that we allow further labelings to exist in the learned argumentation frameworks.

Overall, this experiment on the ICCMA’19 dataset has confirmed the observation from the first experiment. Our findings suggest a time complexity within $\mathit{O}\mathrm{(}{\mathit{n}}^2|\mathit{L}|\mathrm{)}$ for learning argumentation frameworks from labelings. The parallelization of both the learning and construction step is very effective and significantly improves performance, especially for larger argumentation frameworks.

5. Discussion

In the previous sections we have introduced and discussed an algorithm for learning a set of argumentation frameworks from a given set of labelings. This algorithm computes a set of attack constraints for each labeling. These constraints represent the acceptability of each argument with regards to the labeling. Afterwards they are combined into a single attack constraint per argument. This set of attack constraints then represents all input labelings and can then be used to construct the argumentation frameworks that are consistent with the input labelings.

In this section we will take a closer look at our algorithm and discuss its strengths and weaknesses. Furthermore, we will discuss some existing algorithms from Riveret et al. [25] and Niskanen et al. [23] and the recent work of Mumford et al. [22] on the computational complexity of the AF learning problem.

We will first discuss some key advantages that distinguish our algorithm proposed in this work from the existing algorithms. One key point is the structure of the algorithms. Our algorithm works in an iterative way and can be applied on a stream of input labelings similarly to the algorithm of Riveret et al. [25]. This is an important difference to the algorithm of Niskanen et al. [23] which only works with a set of input extensions. An iterative approach means we are able to get intermediate results after each processed input labeling. It also means that we are able to refine our result at any point by learning more labelings. This would not be possible in the algorithm of Niskanen et al. [23] where we would have to start over and learn all labelings again. The iterative approach also allows us to choose the order in which the labelings are processed. This means we can add an additional layer to the algorithm by deciding which labeling to learn next based on the current status (i.e., the last intermediate result).

Another important difference is related to the conditions that are used to encode the labelings. The algorithm of Niskanen et al. [23] also uses conditions based on the input, however there is an important difference: these conditions model one extension as a whole. So, using the terminology introduced in Section 3, these conditions are formulae over the set $\mathit{attackAtoms}\mathrm{(}\mathsf{Arg}\mathrm{)}$ , i.e., the set of atoms representing all possible attacks over $\mathsf{Arg}$ . On the other hand, in our algorithm we have one condition per argument which are formulae over the set of atoms $\mathit{inAttacks}\mathrm{(}\mathit{a}\mathrm{)}$ , i.e., all attacks onto the argument. In other words, the algorithm of Niskanen et al. [23] uses global conditions while our algorithm uses local conditions from the perspective of arguments. These local conditions are important because they enable us to define the iterative approach mentioned above, since we can easily combine formulae for the same argument. This is considerably harder in the algorithm of Niskanen et al. [23]. The fact that the conditions are local and from the perspective of the individual arguments also makes them easier to understand and modify. Furthermore, as we have seen in Section 4, the local conditions also lead to a significantly better performance both while learning a labeling as well as during the construction of an argumentation framework that satisfies the constraints.

The most important advantage of our algorithm compared to those of Riveret et al. and Niskanen et al. is the following: Our algorithm maintains a representation of all argumentation frameworks that are consistent with the input labelings while both other algorithms simply return one fitting argumentation framework. The algorithm of Riveret et al. [25] only maintains one representation of a weighted argumentation framework internally and returns this at the end. On the other hand, the algorithm of Niskanen et al. [23] computes one condition per labeling and as a result returns just one model that represent an argumentation framework. Our algorithm preserves all of the information that is given to it via the input labelings. This is done by translating the input labelings into a set of attack constraints and then combining and simplifying them. So, internally the algorithm only stores one set of mutually independent attack constraints that represent the set of argumentation frameworks. This approach enables us to incorporate additional input labelings at any point and refine the set of argumentation frameworks further. It also ensures that we do not discard any correct argumentation framework during the learning process, something that can happen in both the algorithms of Riveret et al. [25] and Niskanen et al. [23]. It should be mentioned however, that the algorithm of Niskanen et al. [23] can be modified to also return all consistent argumentation frameworks.

We will now look at some other minor differences between all three algorithms. The input of our algorithm is a set of arguments and a set of input labelings. That means, we assume that all arguments of the hidden framework are known. The same assumption is also made by both other algorithms. The second part of the input is the set of input labelings. In the iterative version this can also be a stream of input labelings, similarly to the algorithm of Riveret et al. [25]. This is a different approach compared to the algorithm of Niskanen et al. [23], which uses positive and negative examples in the form of extensions.

Furthermore, all approaches differ in the semantics that are accepted for the input. The algorithm of Riveret et al. [25] only allows grounded labelings as input, while the algorithm of Niskanen et al. [23] accepts conflict-free, admissible, complete, stable, grounded and preferred extensions. Our algorithm accepts conflict-free, admissible, complete and stable labelings. While the algorithm covers many semantics, it does not support grounded and preferred semantics. The reason for that is related to the definition of these semantics. The grounded labeling is defined as the minimal complete labeling and the preferred labelings are maximally complete. These constraints cannot be encoded in the attack constraints and thus it is not possible to learn these labelings with our algorithm, as already discussed in Section 3.2.5. The same applies to some other semantics proposed in the literature, such as semi-stable [7] which maximizes the attacked arguments of an extension. Similarly, the naive semantics and the semantics based on it, like CF2 [5], work with maximal conflict-free sets and thus cannot be modeled by the algorithm in its current form. However, it might be possible to address these issues by extending the algorithm with some form of global conditions. One possibility would be to use conditions similar to those used by Niskanen et al. [23] for modeling the grounded and preferred extensions and adjust them for the respective labelings. It should be mentioned, that this would of course weaken the advantages of our local constraints.

The algorithm of Riveret et al. [25] uses grounded sub-framework labelings as input. This considerably eases the task of learning from labelings since we can just consider all sub-frameworks with just two arguments and take the grounded labeling of these as input. Our algorithm does not rely on such labelings and is able to reconstruct argumentation frameworks from standard labelings.

Argumentation frameworks may contain self-attacking arguments. The algorithm of Riveret et al. [25] does have problems with such argumentation frameworks and there are cases where this algorithm is not able to reconstruct the hidden argumentation framework if there are self-attacking arguments. Our algorithm does not have any problems in that case and is able to work with self-attacking arguments.

Finally, we will also discuss some weaknesses of our algorithm compared to the existing work. The fact that our algorithm requires labelings instead of extensions as input can be considered a weakness. Labelings are more specific than extensions and hold more information about the argumentation framework that produced them. They make a distinction between directly rejected (out) and indirectly rejected (undecided) arguments. Without this distinction it would not be possible to compute the attack constraints in their current form. This is something that can potentially be worked on in the future.

Another observation regarding the input of the algorithm can be made. Our algorithm cannot handle input noise, i.e., some ‘wrong’ labelings that are not actually produced by the hidden argumentation framework. This is something that the algorithms of Riveret et al. [25] and Niskanen et al. [23] are able to handle. The algorithm of Riveret et al. [25] does this by using an internal weighted argumentation framework. This leaves more room to handle inconsistent input but might also lead to returning an argumentation framework which is not consistent with all of the correct input labelings. The algorithm of Niskanen et al. [23] uses weighted MaxSAT encodings for the input extensions. This allows them so find the argumentation framework which is consistent with the highest number of input extensions even if there are some noisy inputs. It might be possible to apply a similar concept to our attack constraints which is also something that can be tackled in the future. Alternatively, we could consider some paraconsistent logic [24] to interpret the attack constraints instead of the classical propositional logic.

The recent work of Mumford et al. [22] investigates the computational complexity of learning argumentation framework both from labelings and extensions. They focus on the complete semantics, but also consider grounded, preferred and stable semantics. Their results show that learning argumentation frameworks from extensions is NP-complete while learning from labelings is solvable in polynomial time. More specifically, they present an algorithm for constructing one consistent argumentation framework from labelings with a time complexity in $\mathit{O}\mathrm{(}{\mathit{n}}^2|\mathit{L}|\mathrm{)}$ . This nicely complements our experimental findings, which suggest the same time complexity dimension for our algorithm. However, our algorithm can be parallelized, which significantly improves its performance. In addition to that, our approach is also capable of producing all consistent solutions instead of just one. This has one disadvantage however, as the algorithm by Mumford et al. has a space complexity within $\mathit{O}\mathrm{(}{\mathit{n}}^2\mathrm{)}$ , while our algorithm needs more space to maintain a representation of multiple argumentation frameworks. In the worst case, our algorithm has a space complexity in $\mathit{O}\mathrm{(}{\mathit{n}}^2|\mathit{L}|\mathrm{)}$ , which easily follows from the fact that we have one attack constraint ${\mathit{C}}_{\mathit{a}}$ with at most n atoms for each of the n arguments and labelings. However, in practice we will often need less space than that since the attack constraints may be simplified due to overlap or contradictions in the learned labelings.

A final related work worthwhile to mention is [2], where an approach is presented that incrementally computes extensions when changes on the initial argumentation framework are observed, such as adding an attack. The problem faced in this work is somewhat orthogonal to ours, since we consider the argumentation framework to be unknown but fixed, and we process extensions (or more precisely labelings) incrementally.

6. Conclusion

We investigated the AF learning scenario, where we want to reconstruct argumentation frameworks from given labelings. The goal in this scenario is to find all argumentation frameworks that are consistent with at least all input labelings. To address this problem, we introduced a novel algorithm that iteratively processes labelings and translated them to attack constraints for each argument. These attack constraints are mutually independent and together they represent the set of all consistent argumentation frameworks. The independence of these constraints allows us to parallelize both the learning and construction part of the algorithm. Our experiments showed that this leads to a significant increase in performance. In particular, for the ICCMA’19 dataset the learning time has been improved by a factor of 10 while the construction time showed an even greater improvement with it being over 22 times faster. We also highlighted some of the key advantages of our approach compared to other similar existing approaches. These advantages are, among others, the ability to fully parallelize all computations and the fact that the attack constraints maintain a representation of all consistent argumentation frameworks at all times.

For future work, there are several possibilities. One such possibility is extending our algorithm to other AF-based formalisms, such as bipolar argumentation frameworks [9] or attack-support argumentation frameworks [11]. For these frameworks, there also exist acceptability semantics from whose labelings we can learn the respective frameworks. In particular, instances of these formalisms can be transformed into semantically equivalent meta argumentation frameworks [3]. That means, one only needs to deal with the meta arguments that are created by this transformation.

Another direction is to extend the capabilities of our algorithm. This could be done by defining semantic constraint functions for other semantics, e.g., for the strong admissible semantics [4]. We are however not limited to specific semantics. Alternatively, we can define semantic constraint functions for other concepts from the literature such as credulous or skeptical acceptance with respect to some semantics σ or properties like unattackedness. Another possibility would be to adapt the algorithm to be able to process negative examples, like the algorithm of Niskanen et al. [23]. It would also be interesting to convert the algorithm to a extension-based approach, if possible. One weakness of our approach is the inability to deal with noisy input. As already mentioned in Section 5, this could for example be addressed by using some paraconsistent logic [24].

Furthermore, it would also be interesting to consider a scenario where we can only obtain incomplete information in the form of a partial labeling wrt. some semantics where some of the arguments have no specified label. For a scenario like that, we would have to explore under which circumstances it is possible to recover information about the framework from the partial labeling and adapt the semantic constraint functions accordingly.

Another interesting thing to explore would be the relationship of the number of learned labelings and the difference between attacks in the hidden and the constructed argumentation framework. Meaning, we look at how many labelings we would need to learn in order to obtain construct exactly the hidden argumentation framework or some framework with at most k different attacks.

Finally, another interesting direction would be to make the scenario of learning argumentation frameworks from labelings more interactive, similar to the scenario of eliciting argumentation frameworks [19]. In that scenario the goal is to elicit a hidden argumentation framework from an entity by asking questions about the extensions of this framework. In our scenario, we could also include user input to control which labeling to learn next. This can then be used to steer the learning process to learn more “effectively”, i.e., by choosing labelings that shrink the set of consistent argumentation frameworks the most.