# Constrained incomplete argumentation frameworks: Expressiveness, complexity and enforcement

Jean-Guy Mailly

<figure><img src="image_1.png" /></figure>

## To cite this version:

Jean-Guy Mailly. Constrained incomplete argumentation frameworks: Expressiveness, complexity and enforcement. AI Communications, 2024, 37 (3), pp.299-322. 10.3233/AIC-220298. hal-04596791

HAL Id: hal-04596791

https://hal.science/hal-04596791

Submitted on 31 May 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>
# Constrained incomplete argumentation frameworks: Expressiveness, complexity and enforcement

Jean-Guy Mailly

<figure><img src="image_1.png" /></figure>

## To cite this version:

Jean-Guy Mailly. Constrained incomplete argumentation frameworks: Expressiveness, complexity and enforcement. AI Communications, 2024, 37 (3), pp.299-322. 10.3233/AIC-220298. hal-04596791

HAL Id: hal-04596791

https://hal.science/hal-04596791v1

Submitted on 31 May 2024

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>
# Constrained Incomplete Argumentation Frameworks: Expressiveness, Complexity and Enforcement

Jean-Guy Mailly

IRIT, Université Toulouse Capitole, Toulouse, France

jean-guy.mailly@irit.fr

## Abstract

Operations like belief change or merging have been adapted to the context of abstract argumentation. However, these operations may require to express some uncertainty or some disjunction in the result, which is not representable in classical AFs. For this reason, some of these earlier works require a set of AFs or a set of extensions as the outcome of the operation, somehow to represent a “disjunction” of AFs or extensions. In parallel, the notion of Incomplete AFs (IAFs) has been developed recently. It corresponds to AFs where the existence of some arguments or attacks may be uncertain. Each IAF can be associated with a set of classical AFs called completions, that correspond to different ways of resolving the uncertainty. While these IAFs could be good candidates for a compact representation of a disjunction of AFs, we prove that this model is not expressive enough. Then we introduce Constrained IAFs, that include a propositional formula allowing to select the set of completions used for reasoning. We prove that this model is expressive enough for representing any set of AFs, or any set of extensions. Moreover, we study the complexity of various decision problems related to the verification of extensions and the acceptability of arguments. While some of them are one level higher in the polynomial hierarchy (compared to their counterpart with standard IAFs), most of them have the same complexity than in the case of IAFs. Finally, we show that CIAFs can be used to model a new form of extension enforcement, where the possible evolutions of an AF are taken into account and modeled by the completions of the CIAF.

**Keywords:** Abstract Argumentation, Uncertainty, Extension Enforcement

**Note:** This work was accepted for publication in a journal. If you refer this work, please cite *Jean-Guy Mailly, Constrained Incomplete Argumentation Frameworks: Expressiveness, Complexity and Enforcement*, AI Communications (2024), doi:10.3233/AIC-220298.

## 1 Introduction

Representing uncertainty and reasoning with uncertain information is of utmost importance in artificial intelligence. Indeed, there are many reasons that may lead an intelligent agent to face uncertainty or impossibility to choose between alternatives. For instance, she can receive information from different sources, which can have different degrees of reliability. This information can be incompatible with her previous knowledge, or with information provided by other sources. This kind of problem can be formalized as belief change operations (“How to incorporate a new piece of information to my knowledge if it is not logically consistent?”) [1, 2, 3] or belief merging (“How to give a coherent representation of several agent’s knowledge even if they are globally inconsistent?”)
# Constrained Incomplete Argumentation Frameworks: Expressiveness, Complexity and Enforcement

Jean-Guy Mailly

IRIT, Université Toulouse Capitole, Toulouse, France

jean-guy.mailly@irit.fr

## Abstract

Operations like belief change or merging have been adapted to the context of abstract argumentation. However, these operations may require to express some uncertainty or some disjunction in the result, which is not representable in classical AFs. For this reason, some of these earlier works require a set of AFs or a set of extensions as the outcome of the operation, somehow to represent a "disjunction" of AFs or extensions. In parallel, the notion of Incomplete AFs (IAFs) has been developed recently. It corresponds to AFs where the existence of some arguments or attacks may be uncertain. Each IAF can be associated with a set of classical AFs called completions, that correspond to different ways of resolving the uncertainty. While these IAFs could be good candidates for a compact representation of a disjunction of AFs, we prove that this model is not expressive enough. Then we introduce Constrained IAFs, that include a propositional formula allowing to select the set of completions used for reasoning. We prove that this model is expressive enough for representing any set of AFs, or any set of extensions. Moreover, we study the complexity of various decision problems related to the verification of extensions and the acceptability of arguments. While some of them are one level higher in the polynomial hierarchy (compared to their counterpart with standard IAFs), most of them have the same complexity than in the case of IAFs. Finally, we show that CIAFs can be used to model a new form of extension enforcement, where the possible evolutions of an AF are taken into account and modeled by the completions of the CIAF.

**Keywords:** Abstract Argumentation, Uncertainty, Extension Enforcement

**Note:** This work was accepted for publication in a journal. If you refer this work, please cite *Jean-Guy Mailly, Constrained Incomplete Argumentation Frameworks: Expressiveness, Complexity and Enforcement*, AI Communications (2024), doi:10.3233/AIC-220298.

## 1 Introduction

Representing uncertainty and reasoning with uncertain information is of utmost importance in artificial intelligence. Indeed, there are many reasons that may lead an intelligent agent to face uncertainty or impossibility to choose between alternatives. For instance, she can receive information from different sources, which can have different degrees of reliability. This information can be incompatible with her previous knowledge, or with information provided by other sources. This kind of problem can be formalized as belief change operations ("How to incorporate a new piece of information to my knowledge if it is not logically consistent?") [1, 2, 3] or belief merging ("How to give a coherent representation of several agent's knowledge even if they are globally inconsistent?")
[4]. In these kinds of applications, a simple way to deal with the uncertainty of the result is the logical disjunction: if the result of revising an agent's knowledge is "I am not sure whether *a* is true or *b* is true.", then it can be expressed with *a* ∨ *b*. This is of course a weak representation of uncertainty, but it is sufficient when there is no more information about the uncertain state of the world (for instance, when there is no available probability regarding the three possible worlds which satisfy *a* ∨ *b*). However, there are formalisms where this kind of simple representation of undecid- edness cannot be done. For instance, in abstract argumentation frameworks (AFs) [5], either there is certainly an attack between two arguments, or there is certainly no attack between them. But an agent cannot express something like "I am not sure whether *a* attacks *b* or not." AFs have been extended in this direction: Partial AFs (PAFs) [6] allow to represent uncertain attacks, and they were first used in a context of merging several AFs. Later, Incomplete AFs (IAFs) [7, 8] have been proposed, as a generalization of PAFs where also arguments can be uncertain. Reasoning with a PAF or an IAF is possible thanks to a set of completions, that are classical AFs that correspond to the different possible worlds encoded in the uncertain information. While this framework allows to express uncertainty in abstract argumentation in a rich way, there are still situations that cannot be modeled. Consider, e.g., that an agent faces the information "Either *a* attacks *b*, or *b* attacks *a*, but I am not sure which one is true.". There is no way to represent this information with an IAF. However, this may be necessary in some situations. For instance, several adaptations of belief change [9, 10] or merging [6, 11] to abstract argumentation lead to results that can contain such an uncertainty over the result, impossible to be represented by a single AF. So, these works propose to represent the "disjunction" in the result as a set of AFs, or even as a set of extensions (and it is also known that not every set of extensions can be represented by a single AF [12]).

A natural question is then “Can we use a framework more expressive than standard AFs to represent the result of these operations (i.e. AF revision or merging) with a single argumentation graph?”. IAFs are a natural candidate to help answer positively to this question, but in this paper we show that IAFs are actually not expressive enough to be used with this purpose. So, our main achievement here is to define a more expressive formalism, and to be precise a formalism that allows to represent any set of completions or any set of extensions with a single argumentation graph. In this formalism, named Constrained IAF (CIAF), we add a propositional formula to an IAF, that allows to specify which subset of the completions of the IAF should be used for reasoning. We show that this framework is more expressive than IAFs, in the sense that any set of AFs can be the set of completions of a CIAF. Also, any set of extensions can be obtained from (the completions of) a CIAF. For this reason, CIAFs provide the positive answer to our question, where IAFs could not. We prove that, despite being more expressive than IAFs, the complexity of reasoning does not increase compared to IAFs under various classical semantics, in most cases, and in the few cases where CIAFs are harder than IAFs, the complexity goes from polynomial to the first level of the polynomial hierarchy.

Interestingly, we also identify a relation between our CIAFs and extension enforcement [13, 14]. This operation consists in modifying an AF such that a given set of arguments becomes part of an extension. Classical enforcement operators are based on expansions, i.e. addition of arguments and attacks such that the attack relation between former arguments remain unchanged. Theoretical results show under which conditions enforcement is possible under expansions. However, these results may suppose the possibility to perform unnatural expansions, like adding a new argument that attacks all the undesired arguments. In a real dialogue, such an “ultimate attacker”, that defeats every unwanted argument, is not likely to exist. We show that completions of a CIAF can be used to model the set of expansions that are available to an agent, and then enforcement is possible if and only if the desired set of arguments is credulously accepted with respect to the CIAF.

This paper extends the conference paper [15, 16] as follows:
[4]. In these kinds of applications, a simple way to deal with the uncertainty of the result is the logical disjunction: if the result of revising an agent's knowledge is "I am not sure whether *a* is true or *b* is true.", then it can be expressed with *a* ∨ *b*. This is of course a weak representation of uncertainty, but it is sufficient when there is no more information about the uncertain state of the world (for instance, when there is no available probability regarding the three possible worlds which satisfy *a* ∨ *b*). However, there are formalisms where this kind of simple representation of undecid- edness cannot be done. For instance, in abstract argumentation frameworks (AFs) [5], either there is certainly an attack between two arguments, or there is certainly no attack between them. But an agent cannot express something like "I am not sure whether *a* attacks *b* or not." AFs have been extended in this direction: Partial AFs (PAFs) [6] allow to represent uncertain attacks, and they were first used in a context of merging several AFs. Later, Incomplete AFs (IAFs) [7, 8] have been proposed, as a generalization of PAFs where also arguments can be uncertain. Reasoning with a PAF or an IAF is possible thanks to a set of completions, that are classical AFs that correspond to the different possible worlds encoded in the uncertain information. While this framework allows to express uncertainty in abstract argumentation in a rich way, there are still situations that cannot be modeled. Consider, e.g., that an agent faces the information "Either *a* attacks *b*, or *b* attacks *a*, but I am not sure which one is true.". There is no way to represent this information with an IAF. However, this may be necessary in some situations. For instance, several adaptations of belief change [9, 10] or merging [6, 11] to abstract argumentation lead to results that can contain such an uncertainty over the result, impossible to be represented by a single AF. So, these works propose to represent the "disjunction" in the result as a set of AFs, or even as a set of extensions (and it is also known that not every set of extensions can be represented by a single AF [12]).

A natural question is then “Can we use a framework more expressive than standard AFs to represent the result of these operations (i.e. AF revision or merging) with a single argumentation graph?”. IAFs are a natural candidate to help answer positively to this question, but in this paper we show that IAFs are actually not expressive enough to be used with this purpose. So, our main achievement here is to define a more expressive formalism, and to be precise a formalism that allows to represent any set of completions or any set of extensions with a single argumentation graph. In this formalism, named Constrained IAF (CIAF), we add a propositional formula to an IAF, that allows to specify which subset of the completions of the IAF should be used for reasoning. We show that this framework is more expressive than IAFs, in the sense that any set of AFs can be the set of completions of a CIAF. Also, any set of extensions can be obtained from (the completions of) a CIAF. For this reason, CIAFs provide the positive answer to our question, where IAFs could not. We prove that, despite being more expressive than IAFs, the complexity of reasoning does not increase compared to IAFs under various classical semantics, in most cases, and in the few cases where CIAFs are harder than IAFs, the complexity goes from polynomial to the first level of the polynomial hierarchy.

Interestingly, we also identify a relation between our CIAFs and extension enforcement [13, 14]. This operation consists in modifying an AF such that a given set of arguments becomes part of an extension. Classical enforcement operators are based on expansions, i.e. addition of arguments and attacks such that the attack relation between former arguments remain unchanged. Theoretical results show under which conditions enforcement is possible under expansions. However, these results may suppose the possibility to perform unnatural expansions, like adding a new argument that attacks all the undesired arguments. In a real dialogue, such an “ultimate attacker”, that defeats every unwanted argument, is not likely to exist. We show that completions of a CIAF can be used to model the set of expansions that are available to an agent, and then enforcement is possible if and only if the desired set of arguments is credulously accepted with respect to the CIAF.

This paper extends the conference paper [15, 16] as follows:
* we provide all the proofs of the results;

* we give background notions on logic and computational complexity (Section 2.1) and discuss more in depth the so-called *disjunction problem* which motivates this work (Section 2.4);

* we provide new complexity results, for verification problems (Section 3.3.1), as well as possible skeptical and necessary credulous acceptability (Section 3.3.2), which were absent from the initial paper;

* we provide the complexity of non-strict parameterized enforcement (Section 4.2);

* we discuss the relative expressiveness of CIAFs with Rich IAFs, a framework that was defined in [17] with a similar purpose to provide a more expressive framework than IAFs (Section 5).

The paper is organized as follows. Section 2 describes background notions of classical logic and computational complexity, as well as the basic notions of (incomplete) abstract argumentation. Our main contributions are presented in Section 3, where we define Constrained Incomplete Argumentation Frameworks, then we prove that this framework allows to express any set of completions or extensions, and finally we study the computational complexity of several classical problems. Section 4 discusses the use of CIAFs to model scenarios of extension enforcement. In Section 5 we formally compare CIAFs with Rich IAFs, and prove that our new framework is strictly more expressive than the previous one. We discuss related work in Section 6, and finally Section 7 concludes the paper and highlights some topics of interest for future research.

# 2 Background

## 2.1 Basic Notions of Logic and Complexity

### 2.1.1 Classical Logic

We first quickly introduce propositional logic. We assume the existence of a set of Boolean variables $V$, where each $x \in V$ can be assigned a truth value in $\mathbb{B} = \{0, 1\}$, where 0 means *false* et 1 means *true*. Given such a set of variables $V$, a propositional language $\mathcal{L}_V$ (or simply $\mathcal{L}$ when there is no ambiguity on $V$) is defined recursively as follows:

* if $x \in V$, then $x \in \mathcal{L}_V$ ($x$ is an *atomic* formula);

* if $\phi \in \mathcal{L}_V$, then $\neg \phi \in \mathcal{L}_V$ (*negation*);

* if $\phi, \psi \in \mathcal{L}_V$ then $\phi \wedge \psi \in \mathcal{L}_V$ (*conjunction*);

* if $\phi, \psi \in \mathcal{L}_V$, then $\phi \vee \psi \in \mathcal{L}_V$ (*disjunction*).

The semantics of such formulas is defined thanks to *interpretations*, which are mappings from $V$ to $\mathbb{B}$, i.e. assignment of a truth value to each variable. Given such a mapping $\omega$, we extend it to arbitrary formulas in $\mathcal{L}_V$ as follows:

* $\omega(\neg \phi) = 1 - \omega(\phi)$;

* $\omega(\phi \wedge \psi) = \min(\omega(\phi), \omega(\psi));$

* $\omega(\phi \vee \psi) = \max(\omega(\phi), \omega(\psi)).$
• we provide all the proofs of the results;

• we give background notions on logic and computational complexity (Section 2.1) and discuss more in depth the so-called *disjunction problem* which motivates this work (Section 2.4);

• we provide new complexity results, for verification problems (Section 3.3.1), as well as possible skeptical and necessary credulous acceptability (Section 3.3.2), which were absent from the initial paper;

• we provide the complexity of non-strict parameterized enforcement (Section 4.2);

• we discuss the relative expressiveness of CIAFs with Rich IAFs, a framework that was defined in [17] with a similar purpose to provide a more expressive framework than IAFs (Section 5).

The paper is organized as follows. Section 2 describes background notions of classical logic and computational complexity, as well as the basic notions of (incomplete) abstract argumentation. Our main contributions are presented in Section 3, where we define Constrained Incomplete Argumentation Frameworks, then we prove that this framework allows to express any set of completions or extensions, and finally we study the computational complexity of several classical problems. Section 4 discusses the use of CIAFs to model scenarios of extension enforcement. In Section 5 we formally compare CIAFs with Rich IAFs, and prove that our new framework is strictly more expressive than the previous one. We discuss related work in Section 6, and finally Section 7 concludes the paper and highlights some topics of interest for future research.

# 2 Background

## 2.1 Basic Notions of Logic and Complexity

### 2.1.1 Classical Logic

We first quickly introduce propositional logic. We assume the existence of a set of Boolean variables $V$, where each $x \in V$ can be assigned a truth value in $\mathbb{B} = \{0, 1\}$, where 0 means *false* et 1 means *true*. Given such a set of variables $V$, a propositional language $\mathcal{L}_V$ (or simply $\mathcal{L}$ when there is no ambiguity on $V$) is defined recursively as follows:

• if $x \in V$, then $x \in \mathcal{L}_V$ ($x$ is an *atomic* formula);

• if $\phi \in \mathcal{L}_V$, then $\neg \phi \in \mathcal{L}_V$ (*negation*);

• if $\phi, \psi \in \mathcal{L}_V$ then $\phi \wedge \psi \in \mathcal{L}_V$ (*conjunction*);

• if $\phi, \psi \in \mathcal{L}_V$, then $\phi \vee \psi \in \mathcal{L}_V$ (*disjunction*).

The semantics of such formulas is defined thanks to *interpretations*, which are mappings from $V$ to $\mathbb{B}$, i.e. assignment of a truth value to each variable. Given such a mapping $\omega$, we extend it to arbitrary formulas in $\mathcal{L}_V$ as follows:

• $\omega(\neg \phi) = 1 - \omega(\phi)$;

• $\omega(\phi \wedge \psi) = \min(\omega(\phi), \omega(\psi))$;

• $\omega(\phi \vee \psi) = \max(\omega(\phi), \omega(\psi))$.
We say that $\omega$ is a *model* of $\phi$ (denoted by $\omega \models \phi$) if $\omega(\phi) = 1$. In that case, we also say that $\omega$ satisfies $\phi$, and $\phi$ is *satisfiable* (or *consistent*). We write $\mathrm{mod}(\phi)$ the set of models of $\phi$. A formula $\phi$ *entails* another formula $\psi$ (denoted by $\phi \vdash \psi$) if $\mathrm{mod}(\phi) \subseteq \mathrm{mod}(\psi)$. Finally, two formulas are equivalent if and only if they entail each other, i.e. $\phi \equiv \psi$ if and only if $\mathrm{mod}(\phi) = \mathrm{mod}(\psi)$.

Additional connectives can be defined, such that their semantics can be obtained from the semantics of the basic connectives. In particular,

* $(\phi \rightarrow \psi) \equiv (\neg\phi \vee \psi)$ (material implication);

* $(\phi \leftrightarrow \psi) \equiv ((\phi \rightarrow \psi) \wedge (\psi \rightarrow \phi))$ (equivalence);

* $(\phi \oplus \psi) \equiv \neg(\phi \leftrightarrow \psi)$ (exclusive or).

### 2.1.2 Computational Complexity

We focus on *decision problems*, i.e. questions that expect a binary answer (roughly speaking, “YES” or “NO”). For such a problem, we want to determine how hard it is (i.e. how much time or how much space we need to solve it) with respect to its size. The size parameter depends on the actual problem (number of variables in a propositional formula, number of nodes in a graph, ...). A complexity class is then a set of (decision) problems which are, in a way, similarly hard to solve.

We will consider three types of algorithms for characterizing the complexity classes mentioned in this paper. First, a *deterministic* algorithm is an algorithm where, at each step of the algorithm, a given configuration always leads to the same result. This means that applying several time this algorithm with the same input data always gives the same result. On the contrary, a *non-deterministic* algorithm includes operations which may have several results for a single configuration, so applying this algorithm to the same input data can lead to different results. Finally, let us mention oracle-based algorithms: this may be any kind of algorithm (deterministic or non-deterministic), with an access to an oracle for a given problem, i.e. a black-box that solves this problems in one computation step.

The first complexity class of interest for us is $\mathbf{P}$, which is the set of decision problems that can be solved in polynomial time with a deterministic algorithm, i.e. with $O(n^k)$ time steps, where $n$ is the size of the problem instance and $k$ is a given natural number. $\mathbf{NP}$ is the equivalent of $\mathbf{P}$, where non-deterministic algorithms are used instead of deterministic ones. It is well-known that $\mathbf{P} \subseteq \mathbf{NP}$, but the question whether the inclusion is strict or not is still open. Then, coNP is the complement class of NP, i.e. the set of decision problems $\mathcal{P}$ such that their complement problem is in NP.<fnref n="1" /> $\mathbf{P} \subseteq \mathrm{coNP}$ holds as well. These classes form the first levels of the *polynomial hierarchy*, which is defined recursively by:

* $\Sigma_0^P = \Pi_0^P = \Delta_0^P = \mathbf{P}$,

* $\Sigma_k^P = \mathbf{NP}^{\Sigma_{k-1}^P}$,

* $\Pi_k^P = \mathrm{coNP}^{\Sigma_{k-1}^P}$,

* $\Delta_k^P = \mathbf{P}^{\Sigma_{k-1}^P}$,

where $C_1^{C_2}$ means that the decision problems can be solved by an algorithm of type $C_1$ with access to an oracle of type $C_2$. For instance, $\Sigma_2^P = \mathbf{NP}^{\mathbf{NP}}$ is the set of decision problems that can be solved in polynomial time by a non-deterministic algorithms, using a NP oracle.

<footnote n="1">¹The complement of a decision problem is obtained by simply “reversing the polarity” of instances, i.e. “YES” instances of $\mathcal{P}$ are “NO” instances of its complement, and vice-versa.</footnote>
We say that $\omega$ is a *model* of $\phi$ (denoted by $\omega \models \phi$) if $\omega(\phi) = 1$. In that case, we also say that $\omega$ satisfies $\phi$, and $\phi$ is *satisfiable* (or *consistent*). We write $\mathrm{mod}(\phi)$ the set of models of $\phi$. A formula $\phi$ *entails* another formula $\psi$ (denoted by $\phi \vdash \psi$) if $\mathrm{mod}(\phi) \subseteq \mathrm{mod}(\psi)$. Finally, two formulas are equivalent if and only if they entail each other, i.e. $\phi \equiv \psi$ if and only if $\mathrm{mod}(\phi) = \mathrm{mod}(\psi)$.

Additional connectives can be defined, such that their semantics can be obtained from the semantics of the basic connectives. In particular,

* $(\phi \rightarrow \psi) \equiv (\neg\phi \vee \psi)$ (material implication);

* $(\phi \leftrightarrow \psi) \equiv ((\phi \rightarrow \psi) \wedge (\psi \rightarrow \phi))$ (equivalence);

* $(\phi \oplus \psi) \equiv \neg(\phi \leftrightarrow \psi)$ (exclusive or).

### 2.1.2 Computational Complexity

We focus on *decision problems*, i.e. questions that expect a binary answer (roughly speaking, “YES” or “NO”). For such a problem, we want to determine how hard it is (i.e. how much time or how much space we need to solve it) with respect to its size. The size parameter depends on the actual problem (number of variables in a propositional formula, number of nodes in a graph, ...). A complexity class is then a set of (decision) problems which are, in a way, similarly hard to solve.

We will consider three types of algorithms for characterizing the complexity classes mentioned in this paper. First, a *deterministic* algorithm is an algorithm where, at each step of the algorithm, a given configuration always leads to the same result. This means that applying several time this algorithm with the same input data always gives the same result. On the contrary, a *non-deterministic* algorithm includes operations which may have several results for a single configuration, so applying this algorithm to the same input data can lead to different results. Finally, let us mention oracle-based algorithms: this may be any kind of algorithm (deterministic or non-deterministic), with an access to an oracle for a given problem, i.e. a black-box that solves this problems in one computation step.

The first complexity class of interest for us is $\mathbf{P}$, which is the set of decision problems that can be solved in polynomial time with a deterministic algorithm, i.e. with $O(n^k)$ time steps, where $n$ is the size of the problem instance and $k$ is a given natural number. $\mathbf{NP}$ is the equivalent of $\mathbf{P}$, where non-deterministic algorithms are used instead of deterministic ones. It is well-known that $\mathbf{P} \subseteq \mathbf{NP}$, but the question whether the inclusion is strict or not is still open. Then, coNP is the complement class of NP, i.e. the set of decision problems $\mathcal{P}$ such that their complement problem is in NP.<fnref n="1" /> $\mathbf{P} \subseteq \mathrm{coNP}$ holds as well. These classes form the first levels of the *polynomial hierarchy*, which is defined recursively by:

* $\Sigma_0^P = \Pi_0^P = \Delta_0^P = \mathbf{P}$,

* $\Sigma_k^P = \mathbf{NP}^{\Sigma_{k-1}^P}$,

* $\Pi_k^P = \mathrm{coNP}^{\Sigma_{k-1}^P}$,

* $\Delta_k^P = \mathbf{P}^{\Sigma_{k-1}^P}$,

where $C_1^{C_2}$ means that the decision problems can be solved by an algorithm of type $C_1$ with access to an oracle of type $C_2$. For instance, $\Sigma_2^P = \mathbf{NP}^{\mathbf{NP}}$ is the set of decision problems that can be solved in polynomial time by a non-deterministic algorithms, using a NP oracle.

<footnote n="1">¹The complement of a decision problem is obtained by simply “reversing the polarity” of instances, i.e. “YES” instances of $\mathcal{P}$ are “NO” instances of its complement, and vice-versa.</footnote>
Decision problems can be compared thanks to the notion of *polynomial-time functional reduction*, which is a mapping *f* from the instances of the first problem *P*₁ to instances of the second problem *P*₂ such that:

* for any instance *i* of *P*₁, *f*(*i*) can be computed in polynomial time with respect to the size of *i*,

* *i* is a "YES" instance of *P*₁ if and only if *f*(*i*) is a "YES" instance of *P*₂.

In this case, we write $\mathcal{P}_1 \leq_f^P \mathcal{P}_2$, which means that $\mathcal{P}_2$ is at least as hard as $\mathcal{P}_1$. For a given complexity class $C$, we say that the decision problem $\mathcal{P}$ is $C$-hard if and only if $\mathcal{P}' \leq_f^P \mathcal{P}$ for every $\mathcal{P}' \in C$, meaning that $\mathcal{P}$ is at least as hard as all the problems in $C$. Then $\mathcal{P}$ is $C$-complete if it is $C$-hard and it belongs to $C$. In this case, $\mathcal{P}$ is one of the hardest problems in $C$.

Membership can be shown by a classical *non-deterministic guess and check* approach: for instance, to prove that a problem $\mathcal{P}$ is in NP, for a given instance $i$ of $\mathcal{P}$, guess a potential proof that $i$ is a “YES” instance, and then check in polynomial time that $i$ is actually a “YES” instance. As an example, consider SAT, which was the first problem to be proven NP-complete [18]. This famous decision problem consists in verifying whether a given propositional formula is satisfiable. To prove that $\mathrm{SAT} \in \mathrm{NP}$, assume we are given a formula $\phi$, and guess an interpretation $\omega$. Checking whether $\omega \models \phi$ holds is doable in polynomial time with a deterministic algorithm, so SAT is a NP problem. More generally, if the last step of the *non-deterministic guess and check* approach is doable in the $k^{th}$ level of the polynomial hierarchy, then the given decision problem belongs to the $k + 1^{th}$ level. A variant of this approach also works for the classes based on coNP instead of NP.

## 2.2 Dung's Abstract Argumentation

Abstract argumentation was introduced in [5], where arguments are abstract entities whose origin or internal structure are ignored. The acceptance of arguments is purely defined from the relations between them.

**Definition 1 (Abstract AF).** An abstract argumentation framework (AF) is a directed graph $\mathcal{F} = \langle A, R \rangle$, where $A$ is a set of arguments, and $R \subseteq A \times A$ is an attack relation.

We say that a *attacks* b when $(a, b) \in R$. If $(b, c) \in R$ also holds, then *defends* c against b. Attack and defense can be adapted to sets of arguments: $S \subseteq A$ *attacks* (respectively *defends*) an argument $b \in A$ if $\exists a \in S$ that *attacks* (respectively *defends*) b.

**Example 1.** Let $\mathcal{F} = \langle A, R \rangle$ be the AF depicted in Figure 1, with $A = \{a, b, c, d, e\}$ and $R = \{(b, a), (c, a), (c, d), (d, b), (d, c), (e, a)\}$. Each arrow represents an attack. d defends a against both b and c, since these are attackers of a that are, in turn, both attacked by d.

<figure><img src="image_3.png" /><figcaption>Figure 1: The AF $\mathcal{F}$</figcaption></figure>

Different semantics have been introduced to evaluate the acceptability of arguments [5], relying on two basic concepts: *conflict-freeness* and *admissibility*.
Decision problems can be compared thanks to the notion of polynomial-time functional reduction, which is a mapping $f$ from the instances of the first problem $\mathcal{P}_1$ to instances of the second problem $\mathcal{P}_2$ such that:

* for any instance $i$ of $\mathcal{P}_1$, $f(i)$ can be computed in polynomial time with respect to the size of $i$,

* $i$ is a "YES" instance of $\mathcal{P}_1$ if and only if $f(i)$ is a "YES" instance of $\mathcal{P}_2$.

In this case, we write $\mathcal{P}_1 \leq_f^P \mathcal{P}_2$, which means that $\mathcal{P}_2$ is at least as hard as $\mathcal{P}_1$. For a given complexity class $C$, we say that the decision problem $\mathcal{P}$ is $C$-hard if and only if $\mathcal{P}' \leq_f^P \mathcal{P}$ for every $\mathcal{P}' \in C$, meaning that $\mathcal{P}$ is at least as hard as all the problems in $C$. Then $\mathcal{P}$ is $C$-complete if it is $C$-hard and it belongs to $C$. In this case, $\mathcal{P}$ is one of the hardest problems in $C$.

Membership can be shown by a classical *non-deterministic guess and check* approach: for instance, to prove that a problem $\mathcal{P}$ is in NP, for a given instance $i$ of $\mathcal{P}$, guess a potential proof that $i$ is a "YES" instance, and then check in polynomial time that $i$ is actually a "YES" instance. As an example, consider SAT, which was the first problem to be proven NP-complete [18]. This famous decision problem consists in verifying whether a given propositional formula is satisfiable. To prove that $\mathrm{SAT} \in \mathrm{NP}$, assume we are given a formula $\phi$, and guess an interpretation $\omega$. Checking whether $\omega \models \phi$ holds is doable in polynomial time with a deterministic algorithm, so SAT is a NP problem. More generally, if the last step of the *non-deterministic guess and check* approach is doable in the $k^{th}$ level of the polynomial hierarchy, then the given decision problem belongs to the $k+1^{th}$ level. A variant of this approach also works for the classes based on coNP instead of NP.

## 2.2 Dung's Abstract Argumentation

Abstract argumentation was introduced in [5], where arguments are abstract entities whose origin or internal structure are ignored. The acceptance of arguments is purely defined from the relations between them.

**Definition 1 (Abstract AF).** An abstract argumentation framework (AF) is a directed graph $\mathcal{F} = \langle A, R \rangle$, where $A$ is a set of arguments, and $R \subseteq A \times A$ is an attack relation.

We say that a *attacks* $b$ when $(a, b) \in R$. If $(b, c) \in R$ also holds, then *defends* $c$ against $b$. Attack and defense can be adapted to sets of arguments: $S \subseteq A$ *attacks* (respectively *defends*) an argument $b \in A$ if $\exists a \in S$ that *attacks* (respectively *defends*) $b$.

**Example 1.** Let $\mathcal{F} = \langle A, R \rangle$ be the AF depicted in Figure 1, with $A = \{a, b, c, d, e\}$ and $R = \{(b, a), (c, a), (c, d), (d, b), (d, c), (e, a)\}$. Each arrow represents an *attack*. $d$ *defends* a against both $b$ and $c$, since these are *attackers* of $a$ that are, in turn, both *attacked* by $d$.

<figure><img src="image_3.png" /><figcaption>Figure 1: The AF $\mathcal{F}$</figcaption></figure>

Different semantics have been introduced to evaluate the acceptability of arguments [5], relying on two basic concepts: *conflict-freeness* and *admissibility*.
**Definition 2** (Conflict-freeness and Admissibility). Given $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$ is:

* conflict-free if and only if $\forall a, b \in S, (a, b) \notin R$;

* admissible if and only if it is conflict-free, and defends each $a \in S$ against all its attackers.

We use $\mathrm{cf}(\mathcal{F})$ and $\mathrm{ad}(\mathcal{F})$ for denoting the sets of conflict-free and admissible sets of an argumentation framework $\mathcal{F}$. The intuition behind these principles is that a set of arguments may be accepted only if it is internally consistent (conflict-freeness) and able to defend itself against potential threats (admissibility). The semantics proposed by [5] can be defined as follows.

**Definition 3** (Extension Semantics). Given $\mathcal{F} = \langle A, R \rangle$, an admissible set $S \subseteq A$ is:

* a complete extension if and only if it contains every argument that it defends;

* a preferred extension if and only if it is a $\subseteq$-maximal complete extension;

* the unique grounded extension if and only if it is the $\subseteq$-minimal complete extension;

* a stable extension if and only if it attacks every argument in $A \setminus S$.

The sets of extensions of an AF $\mathcal{F}$, for these semantics, are denoted (respectively) $\mathrm{co}(\mathcal{F})$, $\mathrm{pr}(\mathcal{F})$, $\mathrm{gr}(\mathcal{F})$ and $\mathrm{st}(\mathcal{F})$. Based on these semantics, we can define the status of any (set of) argument(s), namely *skeptically accepted* (belonging to each $\sigma$-extension), *credulously accepted* (belonging to some $\sigma$-extension) and *rejected* (belonging to no $\sigma$-extension). Given an AF $\mathcal{F}$ and a semantics $\sigma$, we use (respectively) $\mathrm{sk}_{\sigma}(\mathcal{F})$, $\mathrm{cr}_{\sigma}(\mathcal{F})$ and $\mathrm{rej}_{\sigma}(\mathcal{F})$ to denote these sets of arguments.

**Example 2.** We consider again $\mathcal{F}$ given in Figure 1. Its extensions for the different semantics, as well as the sets of accepted arguments, are given in Table 1.

<table><caption>Table 1: Extensions and accepted arguments of $\mathcal{F}$ for $\sigma \in \{\mathrm{co}, \mathrm{pr}, \mathrm{gr}, \mathrm{st}\}$</caption><thead><tr><th>σ</th><th>σ(F)</th><th>cr<sub>σ</sub>(F)</th><th>sk<sub>σ</sub>(F)</th><th>rej<sub>σ</sub>(F)</th></tr></thead><tbody><tr><td>co</td><td>{e}, {d, e}, {b, c, e}</td><td>{b, c, d, e}</td><td>{e}</td><td>{a}</td></tr><tr><td>pr</td><td>{d, e}, {b, c, e}</td><td>{b, c, d, e}</td><td>{e}</td><td>{a}</td></tr><tr><td>gr</td><td>{e}</td><td>{e}</td><td>{e}</td><td>{a,b,c,d}</td></tr><tr><td>st</td><td>{d, e}, {b, c, e}</td><td>{b, c, d, e}</td><td>{e}</td><td>{a}</td></tr></tbody></table>

For more details about argumentation semantics and their properties, we refer the interested reader to [5, 19].

Classical reasoning problems in abstract argumentation include the verification that a set of arguments is an extension of a given semantics, i.e. the decision problem $\sigma$-Ver, and the verification that an argument is credulously (respectively skeptically) accepted with respect to a given semantics, i.e. $\sigma$-CA (respectively $\sigma$-SA). Formally:

* $\sigma$-Ver Given an AF $\mathcal{F} = \langle A, R \rangle$ and a set of arguments $S \subseteq A$, does $S \in \sigma(\mathcal{F})$ hold?

* $\sigma$-CA Given an AF $\mathcal{F} = \langle A, R \rangle$ and an argument $a \in A$, does $a \in \mathrm{cr}_{\sigma}(\mathcal{F})$ hold?

* $\sigma$-SA Given an AF $\mathcal{F} = \langle A, R \rangle$ and an argument $a \in A$, does $a \in \mathrm{sk}_{\sigma}(\mathcal{F})$ hold?
**Definition 2** (Conflict-freeness and Admissibility). Given $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$ is:

* conflict-free if and only if $\forall a, b \in S, (a, b) \notin R$;

* admissible if and only if it is conflict-free, and defends each $a \in S$ against all its attackers.

We use $\mathrm{cf}(\mathcal{F})$ and $\mathrm{ad}(\mathcal{F})$ for denoting the sets of conflict-free and admissible sets of an argumentation framework $\mathcal{F}$. The intuition behind these principles is that a set of arguments may be accepted only if it is internally consistent (conflict-freeness) and able to defend itself against potential threats (admissibility). The semantics proposed by [5] can be defined as follows.

**Definition 3** (Extension Semantics). Given $\mathcal{F} = \langle A, R \rangle$, an admissible set $S \subseteq A$ is:

* a complete extension if and only if it contains every argument that it defends;

* a preferred extension if and only if it is a $\subseteq$-maximal complete extension;

* the unique grounded extension if and only if it is the $\subseteq$-minimal complete extension;

* a stable extension if and only if it attacks every argument in $A \setminus S$.

The sets of extensions of an AF $\mathcal{F}$, for these semantics, are denoted (respectively) $\mathrm{co}(\mathcal{F})$, $\mathrm{pr}(\mathcal{F})$, $\mathrm{gr}(\mathcal{F})$ and $\mathrm{st}(\mathcal{F})$. Based on these semantics, we can define the status of any (set of) argument(s), namely *skeptically accepted* (belonging to each $\sigma$-extension), *credulously accepted* (belonging to some $\sigma$-extension) and *rejected* (belonging to no $\sigma$-extension). Given an AF $\mathcal{F}$ and a semantics $\sigma$, we use (respectively) $\mathrm{sk}_{\sigma}(\mathcal{F})$, $\mathrm{cr}_{\sigma}(\mathcal{F})$ and $\mathrm{rej}_{\sigma}(\mathcal{F})$ to denote these sets of arguments.

**Example 2.** We consider again $\mathcal{F}$ given in Figure 1. Its extensions for the different semantics, as well as the sets of accepted arguments, are given in Table 1.

<table><caption>Table 1: Extensions and accepted arguments of $\mathcal{F}$ for $\sigma \in \{\mathrm{co}, \mathrm{pr}, \mathrm{gr}, \mathrm{st}\}$</caption><thead><tr><th>σ</th><th>σ(F)</th><th>cr<sub>σ</sub>(F)</th><th>sk<sub>σ</sub>(F)</th><th>rej<sub>σ</sub>(F)</th></tr></thead><tbody><tr><td>co</td><td>{e}, {d, e}, {b, c, e}</td><td>{b, c, d, e}</td><td>{e}</td><td>{a}</td></tr><tr><td>pr</td><td>{d, e}, {b, c, e}</td><td>{b, c, d, e}</td><td>{e}</td><td>{a}</td></tr><tr><td>gr</td><td>{e}</td><td>{e}</td><td>{e}</td><td>{a,b,c,d}</td></tr><tr><td>st</td><td>{d, e}, {b, c, e}</td><td>{b, c, d, e}</td><td>{e}</td><td>{a}</td></tr></tbody></table>

For more details about argumentation semantics and their properties, we refer the interested reader to [5, 19].

Classical reasoning problems in abstract argumentation include the verification that a set of arguments is an extension of a given semantics, i.e. the decision problem $\sigma$-Ver, and the verification that an argument is credulously (respectively skeptically) accepted with respect to a given semantics, i.e. $\sigma$-CA (respectively $\sigma$-SA). Formally:

* $\sigma$-Ver Given an AF $\mathcal{F} = \langle A, R \rangle$ and a set of arguments $S \subseteq A$, does $S \in \sigma(\mathcal{F})$ hold?

* $\sigma$-CA Given an AF $\mathcal{F} = \langle A, R \rangle$ and an argument $a \in A$, does $a \in \mathrm{cr}_{\sigma}(\mathcal{F})$ hold?

* $\sigma$-SA Given an AF $\mathcal{F} = \langle A, R \rangle$ and an argument $a \in A$, does $a \in \mathrm{sk}_{\sigma}(\mathcal{F})$ hold?
<table><caption>Table 2: Complexity of σ-Ver, σ-CA and σ-SA for $\sigma \in \{\text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$</caption><thead><tr><th>σ</th><th>σ-Ver</th><th>σ-CA</th><th>σ-SA</th></tr></thead><tbody><tr><td>ad</td><td>in L</td><td>NP-c</td><td>trivial</td></tr><tr><td>co</td><td>in L</td><td>NP-c</td><td>P-c</td></tr><tr><td>pr</td><td>coNP-c</td><td>NP-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td></tr><tr><td>gr</td><td>P-c</td><td>P-c</td><td>P-c</td></tr><tr><td>st</td><td>in L</td><td>NP-c</td><td>coNP-c</td></tr></tbody></table>

Table 2 summarizes the complexity of these decision problems for classical semantics. See e.g. [20] for an overview of computational complexity in formal argumentation.

Finally, let us mention the issue of realizability [12]. Intuitively, it consists in a “reverse” argumentation problem: while classically, ones computes extensions from a given AF, realizability is the question of whether a given set of sets of arguments may be the set of extensions of an AF. Formally, given A a set of arguments, and $S \subseteq 2^A$ a set of sets of arguments, we say that $S$ is σ-realizable if there exists some AF $\mathcal{F} = \langle A', R \rangle$ such that $A \subseteq A'$ and $\sigma(\mathcal{F}) = S$.<fnref n="2" /> Realizability (or more precisely, non-realizability) is a major problem in applications like revision or merging of argumentation frameworks [9, 11]. This is precisely the reason why the result of these operations is defined as a “disjunction” of AFs (i.e. a set of AFs). One possible solution consists in adapting the operators for guaranteeing that the resulting extensions will be realizable. While it is doable in some cases (like AF revision [22]), this forbids some natural approaches (for instance, distance-based revision is not possible with the approach from [22]). Moreover, this technique is not applied in the case of AF merging [11]. This is what motivates the study conducted in the present paper, we come back more in depth on this issue in Section 2.4.

## 2.3 Incomplete AFs

Now, we describe Incomplete Argumentation Frameworks [6, 7, 8].

**Definition 4 (Incomplete AF).** An Incomplete Argumentation Framework (IAF) is a tuple $\mathcal{I} = \langle A, A^?, R, R^? \rangle$, where A and $A^?$ are disjoint sets of arguments, and R, $R^?$ ⊆ $(A \cup A^?) \times (A \cup A^?)$ are disjoint sets of attacks.

Elements from A and R are certain arguments and attacks, i.e. the agent is sure that they appear in the framework. On the opposite, $A^?$ and $R^?$ represent uncertain arguments and attacks. For each of them, there is a doubt about their actual existence.

**Example 3.** Let us consider $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ given in Figure 2. We use plain nodes and arrows to represent certain arguments and attacks, i.e. $A = \{a, b, c, d, e\}$ and $R = \{(b, a), (c, a), (d, b), (d, c)\}$. Uncertain arguments are represented as dashed square nodes (i.e. $A^? = \{f\}$) and uncertain attacks are represented as dotted arrows (i.e. $R^? = \{(e, a), (f, d)\}$).

The notion of completion in abstract argumentation was first defined in [6] for Partial AFs (i.e. IAFs with $A^? = \emptyset$), and then adapted to IAFs. Intuitively, a completion is a classical AF which describes a situation of the world coherent with the uncertain information encoded in the IAF.

<footnote n="2">²Moreover, we say that $S$ is *compactly σ-realizable* if $A' = A$ [21].</footnote>
<table><caption>Table 2: Complexity of σ-Ver, σ-CA and σ-SA for $\sigma \in \{\text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$</caption><thead><tr><th>σ</th><th>σ-Ver</th><th>σ-CA</th><th>σ-SA</th></tr></thead><tbody><tr><td>ad</td><td>in L</td><td>NP-c</td><td>trivial</td></tr><tr><td>co</td><td>in L</td><td>NP-c</td><td>P-c</td></tr><tr><td>pr</td><td>coNP-c</td><td>NP-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td></tr><tr><td>gr</td><td>P-c</td><td>P-c</td><td>P-c</td></tr><tr><td>st</td><td>in L</td><td>NP-c</td><td>coNP-c</td></tr></tbody></table>

Table 2 summarizes the complexity of these decision problems for classical semantics. See e.g. [20] for an overview of computational complexity in formal argumentation.

Finally, let us mention the issue of realizability [12]. Intuitively, it consists in a “reverse” argumentation problem: while classically, ones computes extensions from a given AF, realizability is the question of whether a given set of sets of arguments may be the set of extensions of an AF. Formally, given A a set of arguments, and $S \subseteq 2^A$ a set of sets of arguments, we say that $S$ is σ-realizable if there exists some AF $\mathcal{F} = \langle A', R \rangle$ such that $A \subseteq A'$ and $\sigma(\mathcal{F}) = S$.<fnref n="2" /> Realizability (or more precisely, non-realizability) is a major problem in applications like revision or merging of argumentation frameworks [9, 11]. This is precisely the reason why the result of these operations is defined as a “disjunction” of AFs (i.e. a set of AFs). One possible solution consists in adapting the operators for guaranteeing that the resulting extensions will be realizable. While it is doable in some cases (like AF revision [22]), this forbids some natural approaches (for instance, distance-based revision is not possible with the approach from [22]). Moreover, this technique is not applied in the case of AF merging [11]. This is what motivates the study conducted in the present paper, we come back more in depth on this issue in Section 2.4.

## 2.3 Incomplete AFs

Now, we describe Incomplete Argumentation Frameworks [6, 7, 8].

**Definition 4 (Incomplete AF).** An Incomplete Argumentation Framework (IAF) is a tuple $\mathcal{I} = \langle A, A^?, R, R^? \rangle$, where A and $A^?$ are disjoint sets of arguments, and $R, R^? \subseteq (A \cup A^?) \times (A \cup A^?)$ are disjoint sets of attacks.

Elements from A and R are certain arguments and attacks, i.e. the agent is sure that they appear in the framework. On the opposite, $A^?$ and $R^?$ represent uncertain arguments and attacks. For each of them, there is a doubt about their actual existence.

**Example 3.** Let us consider $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ given in Figure 2. We use plain nodes and arrows to represent certain arguments and attacks, i.e. $A = \{a, b, c, d, e\}$ and $R = \{(b, a), (c, a), (d, b), (d, c)\}$. Uncertain arguments are represented as dashed square nodes (i.e. $A^? = \{f\}$) and uncertain attacks are represented as dotted arrows (i.e. $R^? = \{(e, a), (f, d)\}$).

The notion of completion in abstract argumentation was first defined in [6] for Partial AFs (i.e. IAFs with $A^? = \emptyset$), and then adapted to IAFs. Intuitively, a completion is a classical AF which describes a situation of the world coherent with the uncertain information encoded in the IAF.

<footnote n="2">²Moreover, we say that $S$ is *compactly σ-realizable* if $A' = A$ [21].</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 2: The IAF $\mathcal{I}$</figcaption></figure>

**Definition 5 (Completion of an IAF).** Given $\mathcal{I} = \langle A, A^?, R, R^? \rangle$, a completion of $\mathcal{I}$ is $\mathcal{F} = \langle A', R' \rangle$, such that $A \subseteq A' \subseteq A \cup A^?$ and $R_{|A'} \subseteq R' \subseteq R_{|A'} \cup R_{|A'}^?$, where $R_{|A'} = R \cap (A' \times A')$ (and similarly for $R_{|A'}^?$).

The set of completions of an IAF $\mathcal{I}$ is denoted $\text{comp}(\mathcal{I})$.

**Example 4.** We consider again the IAF from Figure 2. Its set of completions is described at Figure 3.

<figure><img src="image_5.png" /><figcaption>Figure 3: The completions of $\mathcal{I}$</figcaption></figure>

Concerning the question of compact representation of a set of AFs by means of an incomplete AF, the following example illustrates that some sets of AFs (even simple ones) cannot be represented by an IAF.

**Example 5.** Suppose that the result of revising an AF [9] is the set $\mathfrak{F} = \{\mathcal{F}_1 = \langle\{a, b\}, \{(b, a)\}\rangle, \mathcal{F}_2 = \langle\{a, c\}, \{(c, a)\}\rangle\}$. The question is to determine whether this set can be compactly represented by a single IAF. Towards a contradiction, suppose that there is an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ such that $\text{comp}(\mathcal{I}) = \mathfrak{F}$. Since $a$ belongs to both $\mathcal{F}_1$ and $\mathcal{F}_2$, it must belong to the certain arguments $A$. On the contrary, the uncertain arguments are $A^? = \{b, c\}$, each of them belongs to some (but not all) completions. $A = \{a\}$ and $A^? = \{b, c\}$ imply the existence of some completions that only contain $a$, and some completions that contain the three arguments $a, b, c$. This is not the case. So $\mathcal{I}$ does not exist.

Classical reasoning problems have been adapted to IAFs. These adaptations take into account the set of completions of IAFs. Similarly to credulous (respectively skeptical) reasoning that quantify existentially (respectively universally) over the set of extensions of an AF, possible (respectively necessary) reasoning quantify existentially (respectively universally) over the set of completions.
<figure><img src="image_4.png" /><figcaption>Figure 2: The IAF $\mathcal{I}$</figcaption></figure>

**Definition 5** (Completion of an IAF). Given $\mathcal{I} = \langle A, A^?, R, R^? \rangle$, a completion of $\mathcal{I}$ is $\mathcal{F} = \langle A', R' \rangle$, such that $A \subseteq A' \subseteq A \cup A^?$ and $R_{|A'} \subseteq R' \subseteq R_{|A'} \cup R_{|A'}^?$, where $R_{|A'} = R \cap (A' \times A')$ (and similarly for $R_{|A'}^?$).

The set of completions of an IAF $\mathcal{I}$ is denoted $\text{comp}(\mathcal{I})$.

**Example 4.** We consider again the IAF from Figure 2. Its set of completions is described at Figure 3.

<figure><img src="image_5.png" /><figcaption>Figure 3: The completions of $\mathcal{I}$</figcaption></figure>

Concerning the question of compact representation of a set of AFs by means of an incomplete AF, the following example illustrates that some sets of AFs (even simple ones) cannot be represented by an IAF.

**Example 5.** Suppose that the result of revising an AF [9] is the set $\mathfrak{F} = \{\mathcal{F}_1 = \langle\{a, b\}, \{(b, a)\}\rangle, \mathcal{F}_2 = \langle\{a, c\}, \{(c, a)\}\rangle\}$. The question is to determine whether this set can be compactly represented by a single IAF. Towards a contradiction, suppose that there is an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ such that $\text{comp}(\mathcal{I}) = \mathfrak{F}$. Since $a$ belongs to both $\mathcal{F}_1$ and $\mathcal{F}_2$, it must belong to the certain arguments $A$. On the contrary, the uncertain arguments are $A^? = \{b, c\}$, each of them belongs to some (but not all) completions. $A = \{a\}$ and $A^? = \{b, c\}$ imply the existence of some completions that only contain $a$, and some completions that contain the three arguments $a, b, c$. This is not the case. So $\mathcal{I}$ does not exist.

Classical reasoning problems have been adapted to IAFs. These adaptations take into account the set of completions of IAFs. Similarly to credulous (respectively skeptical) reasoning that quantify existentially (respectively universally) over the set of extensions of an AF, possible (respectively necessary) reasoning quantify existentially (respectively universally) over the set of completions.
The possible and necessary views for reasoning with IAFs can be applied to any decision problems. This leads to the definition of the following four verification problems: IncPV (respectively IncNV) is the Incomplete Possible (respectively Necessary) Verification and IncPV* (respectively IncNV*) is a variant of it; and the four acceptability problems: PCA, NCA, PSA, NSA where P stands for Possible, N for Necessary, C for Credulous and S for Skeptical.

*-IncPV Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $S \cap A' \in \sigma(\mathcal{F})$?

*-IncNV Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is $S \cap A' \in \sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

*-IncPV* Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $S \in \sigma(\mathcal{F})$?

*-IncNV* Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is $S \in \sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

*-PCA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $a \in \text{cr}_\sigma(\mathcal{F})$?

*-NCA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is $a \in \text{cr}_\sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

*-PSA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $a \in \text{sk}_\sigma(\mathcal{F})$?

*-NSA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is $a \in \text{sk}_\sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

Their complexity for classical semantics has been established, and we summarize the results in Table 3.

<table><caption>Table 3: Complexity of reasoning with IAFs, for $\sigma \in \{\text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$ [7, 23, 24]</caption><thead><tr><th>σ</th><th>σ-IncPV</th><th>σ-IncNV</th><th>σ-IncPV*</th><th>σ-IncNV*</th><th>σ-PCA</th><th>σ-PSA</th><th>σ-NCA</th><th>σ-NSA</th></tr></thead><tbody><tr><td>ad</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>trivial</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>trivial</td></tr><tr><td>co</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>NP-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td></tr><tr><td>pr</td><td>Σ<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td><td>Σ<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td><td>NP-c</td><td>Σ<sup>P</sup><sub>3</sub>-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td></tr><tr><td>gr</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>NP-c</td><td>coNP-c</td><td>coNP-c</td></tr><tr><td>st</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>Σ<sup>P</sup><sub>2</sub>-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td></tr></tbody></table>

While all the acceptability problems are quite intuitive, it was shown in [23] that the original definitions of the verification problems (i.e. IncPV and IncNV) exhibit some bad properties. In particular, if we call a possible (respectively necessary) extension of the IAF a set of arguments such that the answer to IncPV (respectively IncNV) is true, then an extension of the IAF can violate the basic conflict-freeness property (in particular, in the case of the possible view). For this reason, [23] define the IncPV* and IncNV* versions, which do not exhibit this bad behavior, and guarantee better computational properties in the case of the possible view.
The possible and necessary views for reasoning with IAFs can be applied to any decision problems. This leads to the definition of the following four verification problems: IncPV (respectively IncNV) is the Incomplete Possible (respectively Necessary) Verification and IncPV* (respectively IncNV*) is a variant of it; and the four acceptability problems: PCA, NCA, PSA, NSA where P stands for Possible, N for Necessary, C for Credulous and S for Skeptical.

*-IncPV Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $S \cap A' \in \sigma(\mathcal{F})$?

*-IncNV Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is $S \cap A' \in \sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

*-IncPV* Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $S \in \sigma(\mathcal{F})$?

*-IncNV* Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is $S \in \sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

*-PCA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $a \in \text{cr}_\sigma(\mathcal{F})$?

*-NCA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is $a \in \text{cr}_\sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

*-PSA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$ such that $a \in \text{sk}_\sigma(\mathcal{F})$?

*-NSA Given an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ and an argument $a \in A$, is $a \in \text{sk}_\sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{I})$?

Their complexity for classical semantics has been established, and we summarize the results in Table 3.

<table><caption>Table 3: Complexity of reasoning with IAFs, for $\sigma \in \{\text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$ [7, 23, 24]</caption><thead><tr><th>σ</th><th>σ-IncPV</th><th>σ-IncNV</th><th>σ-IncPV*</th><th>σ-IncNV*</th><th>σ-PCA</th><th>σ-PSA</th><th>σ-NCA</th><th>σ-NSA</th></tr></thead><tbody><tr><td>ad</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>trivial</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>trivial</td></tr><tr><td>co</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>NP-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td></tr><tr><td>pr</td><td>Σ<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td><td>Σ<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td><td>NP-c</td><td>Σ<sup>P</sup><sub>3</sub>-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td></tr><tr><td>gr</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>NP-c</td><td>coNP-c</td><td>coNP-c</td></tr><tr><td>st</td><td>NP-c</td><td>P</td><td>P</td><td>P</td><td>NP-c</td><td>Σ<sup>P</sup><sub>2</sub>-c</td><td>Π<sup>P</sup><sub>2</sub>-c</td><td>coNP-c</td></tr></tbody></table>

While all the acceptability problems are quite intuitive, it was shown in [23] that the original definitions of the verification problems (i.e. IncPV and IncNV) exhibit some bad properties. In particular, if we call a possible (respectively necessary) extension of the IAF a set of arguments such that the answer to IncPV (respectively IncNV) is true, then an extension of the IAF can violate the basic conflict-freeness property (in particular, in the case of the possible view). For this reason, [23] define the IncPV* and IncNV* versions, which do not exhibit this bad behavior, and guarantee better computational properties in the case of the possible view.
## 2.4 Motivation: The Disjunction Problem

As mentioned in the introduction, one of the main motivations that conducted to the work presented in this paper is one of the main criticism that was made regarding the approaches defined in earlier work on belief revision [9, 10] or belief merging [6, 11] applied to abstract argumentation. In these works, the result is in general a set of AFs, while it may seem natural to obtain a single AF. In particular, let us illustrate the process underlying the revision operators defined in [9]. As shown by Figure 4, the input of the revision operator is a single AF, and a formula which expresses the new information to be incorporated in the agent's knowledge. Then, a revision in the style of Katsuno and Mendelzon [3] is performed on the set of extensions of $\mathcal{F}$, which play here a role similar to the models of formulas in propositional belief revision. So we obtain the extensions of the result $(\sigma(\mathcal{F} \star \phi))$ before obtaining the result itself $(\mathcal{F} \star \phi)$. To get the latter, a second step called *generation* returns a set of AFs such that the union of their extensions is equal to the revised extensions that were provided by the first step.

<figure><img src="image_6.png" /><figcaption>Figure 4: Schematic explanation of the AF revision from [9]</figcaption></figure>

There is no simple way to be sure that the result is a single AF, since the revised extensions may not be realizable, i.e. there may be an impossibility to represent these extensions with a single AF [12]. This may not be a strong problem, since as explained before, the result of a revision is by nature uncertain, in the sense that the agent may not be sure of what is the state of the world when she received the new information. In classical logic, this is expressed by the notion of disjunction which exists in the language (corresponding to the fact that the revised formula can have several models). As an analogy with this notion of disjunction, we may assume, in abstract argumentation, that the uncertain knowledge of the agent about the state of the world (or the state of the debate) is expressed as a “disjunction” of extensions or a “disjunction” of AFs. However, continuing the analogy with revision in a classical setting, we would like to have a single graphical structure to represent this disjunction, exactly like any set of models can be represented as a single propositional formula. So, the main question we ask is “Is there an abstract argumentation formalism that allows to represent any set of extensions or AFs thanks to a single instance of this formalism?”.

We can show easily that IAFs are not sufficiently expressive to answer positively to this question.

**Example 6.** We want to represent with a single IAF the set of AFs $\mathcal{F} = \{\mathcal{F}_1, \mathcal{F}_2\}$ from Figure 5. Assume there is such an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ with $\mathrm{comp}(\mathcal{I}) = \{\mathcal{F}_1, \mathcal{F}_2\}$. Since $A$ belongs to every completions, and $b$ and $c$ belong to some (but not each) completion, we need to have $A = \{a\}$ and $A^? = \{b, c\}$. Then, since the attack $(b, a)$ appears in every completion where both $a$ and $b$ appear, this attack must belong to $R$, and the same reasoning applies to $(c, a)$. This means that $\mathcal{I}$ should be the IAF depicted in Figure 6a. However, this IAF has two additional (unwanted) completions $\mathcal{F}_3$ and $\mathcal{F}_4$ (respectively Figure 6b and 6c). So we deduce that there is actually no $\mathcal{I}$ with $\mathrm{comp}(\mathcal{I}) = \mathcal{F} = \{\mathcal{F}_1, \mathcal{F}_2\}$.

In Section 3, we answer positively to our question by defining Constrained Incomplete Argumentation Frameworks.
## 2.4 Motivation: The Disjunction Problem

As mentioned in the introduction, one of the main motivations that conducted to the work presented in this paper is one of the main criticism that was made regarding the approaches defined in earlier work on belief revision [9, 10] or belief merging [6, 11] applied to abstract argumentation. In these works, the result is in general a set of AFs, while it may seem natural to obtain a single AF. In particular, let us illustrate the process underlying the revision operators defined in [9]. As shown by Figure 4, the input of the revision operator is a single AF, and a formula which expresses the new information to be incorporated in the agent's knowledge. Then, a revision in the style of Katsuno and Mendelzon [3] is performed on the set of extensions of $\mathcal{F}$, which play here a role similar to the models of formulas in propositional belief revision. So we obtain the extensions of the result $(\sigma(\mathcal{F} \star \phi))$ before obtaining the result itself $(\mathcal{F} \star \phi)$. To get the latter, a second step called *generation* returns a set of AFs such that the union of their extensions is equal to the revised extensions that were provided by the first step.

<figure><img src="image_6.png" /><figcaption>Figure 4: Schematic explanation of the AF revision from [9]</figcaption></figure>

There is no simple way to be sure that the result is a single AF, since the revised extensions may not be realizable, i.e. there may be an impossibility to represent these extensions with a single AF [12]. This may not be a strong problem, since as explained before, the result of a revision is by nature uncertain, in the sense that the agent may not be sure of what is the state of the world when she received the new information. In classical logic, this is expressed by the notion of disjunction which exists in the language (corresponding to the fact that the revised formula can have several models). As an analogy with this notion of disjunction, we may assume, in abstract argumentation, that the uncertain knowledge of the agent about the state of the world (or the state of the debate) is expressed as a “disjunction” of extensions or a “disjunction” of AFs. However, continuing the analogy with revision in a classical setting, we would like to have a single graphical structure to represent this disjunction, exactly like any set of models can be represented as a single propositional formula. So, the main question we ask is “Is there an abstract argumentation formalism that allows to represent any set of extensions or AFs thanks to a single instance of this formalism?”.

We can show easily that IAFs are not sufficiently expressive to answer positively to this question.

**Example 6.** We want to represent with a single IAF the set of AFs $\mathcal{F} = \{\mathcal{F}_1, \mathcal{F}_2\}$ from Figure 5. Assume there is such an IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ with $\mathrm{comp}(\mathcal{I}) = \{\mathcal{F}_1, \mathcal{F}_2\}$. Since $A$ belongs to every completions, and $b$ and $c$ belong to some (but not each) completion, we need to have $A = \{a\}$ and $A^? = \{b, c\}$. Then, since the attack $(b, a)$ appears in every completion where both $a$ and $b$ appear, this attack must belong to $R$, and the same reasoning applies to $(c, a)$. This means that $\mathcal{I}$ should be the IAF depicted in Figure 6a. However, this IAF has two additional (unwanted) completions $\mathcal{F}_3$ and $\mathcal{F}_4$ (respectively Figure 6b and 6c). So we deduce that there is actually no $\mathcal{I}$ with $\mathrm{comp}(\mathcal{I}) = \mathcal{F} = \{\mathcal{F}_1, \mathcal{F}_2\}$.

In Section 3, we answer positively to our question by defining Constrained Incomplete Argumentation Frameworks.
<figure><img src="image_7.png" /><figcaption>Figure 5: Two AFs that cannot be represented by a single IAF</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6: A potential IAF for representing {$\mathcal{F}_1, \mathcal{F}_2$}, and the additional (unwanted) completions</figcaption></figure>

# 3 Constrained Incomplete Argumentation Frameworks

Now we introduce the Constrained Incomplete Argumentation Frameworks, that generalize IAFs by adding a constraint on the set of possible completions. We show that this new framework is expressive enough to solve the disjunction problem illustrated in Section 2.4.

## 3.1 Constraints on Completions

Intuitively, for a given IAF $\mathcal{I}$, a constrained version of it is a pair $\langle \mathcal{I}, C \rangle$ where $C \subseteq \mathrm{comp}(\mathcal{I})$. Then, reasoning on $\langle \mathcal{I}, C \rangle$ requires to use only $C$ instead of the full set of completions of $\mathcal{I}$. But rather than defining the constraint with a set of completions, we define a logical language to express information on the structure of an AF, i.e. a propositional language such that the models of a formula $\phi$ correspond to AFs, inspired by [25] for selecting extensions. This option may provide a more compact representation of the constraint. Moreover, we show later that any $\langle \mathcal{I}, C \rangle$ can be equivalently represented as $\langle \mathcal{I}, \phi \rangle$.

**Definition 6 (Constraint).** Given A a set of arguments, we define the set of propositional atoms $Prop_A = Arg_A \cup Att_A$ where:

* $Arg_A = \{\arg_a | a \in A\}$;

* $Att_A = \{\mathrm{att}_{a,b} | (a,b) \in A \times A\}$.

Then, $\mathcal{L}_A$ is the propositional language built from $Prop_A$.

Any set of connectives can be used for defining $Prop_A$ formulas, e.g. $\{\neg, \vee, \wedge\}$ (representing respectively the negation, the disjunction and the conjunction). Classical syntactic sugar can be used, e.g. $\phi \rightarrow \psi$ for $\neg\phi \vee \psi$ (material implication), $\phi \leftrightarrow \psi$ for $(\phi \rightarrow \psi) \wedge (\psi \rightarrow \phi)$ (equivalence), or $(\phi \oplus \psi)$ for $\neg(\phi \leftrightarrow \psi)$ (exclusive disjunction).

The satisfaction of a constraint by an AF is defined as follows.

**Definition 7 (Constraint Satisfaction).** Given A a set of arguments, and $\phi \in \mathcal{L}_A$ a formula, the set of models of $\phi$ is denoted $\mathrm{mod}(\phi)$. An AF $\mathcal{F} = \langle A', R \rangle$ with $A' \subseteq A$ and $R \subseteq A' \times A'$ satisfies $\phi$ if and only if there is a model $\omega \in \mathrm{mod}(\phi)$ such that

* $A' = \{a \in A | \omega(\mathrm{arg}_a) = 1\}$, and
<figure><img src="image_7.png" /><figcaption>Figure 5: Two AFs that cannot be represented by a single IAF</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 6: A potential IAF for representing {$\mathcal{F}_1, \mathcal{F}_2$}, and the additional (unwanted) completions</figcaption></figure>

# 3 Constrained Incomplete Argumentation Frameworks

Now we introduce the Constrained Incomplete Argumentation Frameworks, that generalize IAFs by adding a constraint on the set of possible completions. We show that this new framework is expressive enough to solve the disjunction problem illustrated in Section 2.4.

## 3.1 Constraints on Completions

Intuitively, for a given IAF $\mathcal{I}$, a constrained version of it is a pair $\langle \mathcal{I}, C \rangle$ where $C \subseteq \text{comp}(\mathcal{I})$. Then, reasoning on $\langle \mathcal{I}, C \rangle$ requires to use only $C$ instead of the full set of completions of $\mathcal{I}$. But rather than defining the constraint with a set of completions, we define a logical language to express information on the structure of an AF, i.e. a propositional language such that the models of a formula $\phi$ correspond to AFs, inspired by [25] for selecting extensions. This option may provide a more compact representation of the constraint. Moreover, we show later that any $\langle \mathcal{I}, C \rangle$ can be equivalently represented as $\langle \mathcal{I}, \phi \rangle$.

**Definition 6 (Constraint).** Given A a set of arguments, we define the set of propositional atoms $Prop_A = Arg_A \cup Att_A$ where:

* $Arg_A = \{\arg_a | a \in A\}$;

* $Att_A = \{\text{att}_{a,b} | (a,b) \in A \times A\}$.

Then, $\mathcal{L}_A$ is the propositional language built from $Prop_A$.

Any set of connectives can be used for defining $Prop_A$ formulas, e.g. $\{\neg, \vee, \wedge\}$ (representing respectively the negation, the disjunction and the conjunction). Classical syntactic sugar can be used, e.g. $\phi \rightarrow \psi$ for $\neg\phi \vee \psi$ (material implication), $\phi \leftrightarrow \psi$ for $(\phi \rightarrow \psi) \wedge (\psi \rightarrow \phi)$ (equivalence), or $(\phi \oplus \psi)$ for $\neg(\phi \leftrightarrow \psi)$ (exclusive disjunction).

The satisfaction of a constraint by an AF is defined as follows.

**Definition 7 (Constraint Satisfaction).** Given A a set of arguments, and $\phi \in \mathcal{L}_A$ a formula, the set of models of $\phi$ is denoted $\text{mod}(\phi)$. An AF $\mathcal{F} = \langle A', R \rangle$ with $A' \subseteq A$ and $R \subseteq A' \times A'$ satisfies $\phi$ if and only if there is a model $\omega \in \text{mod}(\phi)$ such that

* $A' = \{a \in A | \omega(\arg_a) = 1\}$, and
$$ \bullet R = \{(a, b) \in A \times A \mid \omega(\mathrm{att}_{a,b}) = 1\}. $$

**Example 7.** We consider the three AFs $\mathcal{F}_1$, $\mathcal{F}_2$ and $\mathcal{F}_3$ depicted respectively in Figure 7a, 7b and 7c. Assume that the constraints are built on the propositional vocabulary $Prop_A$, where $A = \{a, b, c, d, e\}$. The formula $\phi_1 = \mathrm{arg}_a \wedge (\mathrm{att}_{b,a} \oplus \mathrm{att}_{b,c})$ expresses the fact that a should appear in the AF, and exactly one of the attacks $(b, a)$ and $(b, c)$ should appear as well. This formula is satisfied by $\mathcal{F}_1$, but not by $\mathcal{F}_2$ and $\mathcal{F}_3$. Now let us define the formula $\phi_2 = (\mathrm{arg}_a \vee \mathrm{arg}_d) \wedge \neg \mathrm{arg}_e \wedge (\mathrm{arg}_a \rightarrow \mathrm{att}_{a,b})$. It is satisfied if the AF contains either a or d (or both) but not e, and also if a appears in the AF then it must attack b. This formula is satisfied by the three AFs considered here.

<figure><img src="image_9.png" /><figcaption>Figure 7: Three examples of AFs</figcaption></figure>

## 3.2 Definition and Expressiveness of CIAFs

Now we formally define Constrained IAFs, and prove that this framework solves the Disjunction Problem introduced in Section 2.4.

**Definition 8 (Constrained IAF).** A Constrained Incomplete Argumentation Framework (CIAF) is a tuple $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$, where $\langle A, A^?, R, R^? \rangle$ is an IAF, and $\phi \in \mathcal{L}_{A \cup A^?}$ is a constraint.

The constraint $\phi$ is used to select a subset of the completions of the IAF $\mathcal{I}_C = \langle A, A^?, R, R^? \rangle$. The completions of a CIAF are then defined as follows.

**Definition 9 (Completions of a CIAF).** Given $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ a CIAF, we define its set of completions by $\mathrm{comp}(\mathcal{C}) = \{c \in \mathrm{comp}(\mathcal{I}_C) \mid c \text{ satisfies } \phi\}$ where $\mathcal{I}_C = \langle A, A^?, R, R^? \rangle$.

**Example 8.** Let $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ be a CIAF such that $\mathcal{I}_C = \langle A, A^?, R, R^? \rangle$ is the IAF from Figure 2, and $\phi = \mathrm{att}_{e,a} \wedge \mathrm{arg}_f$. Recall that the completions of $\mathcal{I}_C$ are given in Figure 3. Only two of them satisfy $\phi$, namely $\mathcal{F}_5$ (Fig. 3e) and $\mathcal{F}_6$ (Fig. 3f). So $\mathrm{comp}(\mathcal{C}) = \{\mathcal{F}_5, \mathcal{F}_6\}$.

Let us mention that, in order to be meaningful, the constraint $\phi$ must satisfy some conditions. Indeed, there must be at least one model of $\phi$ such that $\mathrm{arg}_a$ is true for each $a \in A$, $\mathrm{att}_{a,b}$ is true for each $(a, b) \in R$, and $\mathrm{att}_{a,b}$ is false for each $(a, b) \in ((A \cup A^?) \times (A \cup A^?)) \setminus (R \cup R^?)$. Otherwise, $\mathrm{comp}(\mathcal{C})$ is trivially empty. More generally, a CIAF $\mathcal{C}$ is over-constrained when $\mathrm{comp}(\mathcal{C}) = \emptyset$.

Now, we focus on the expressiveness of CIAFs, i.e. given a set of AFs (or a set of extensions), is there a CIAF such that its completions (or the extensions of its completions) correspond to the given set? We show that, in both cases, the answer is yes.

**Representing a Set of AFs** First, we define a particular formula, that is only satisfied by one given AF.

**Definition 10.** Given A a set of arguments, and $\mathcal{F} = \langle A', R \rangle$ with $A' \subseteq A$, and $R \subseteq A' \times A'$, we define $\psi_{\mathcal{F}} \in \mathcal{L}_A$ as

$$ \psi_{\mathcal{F}} = ( \bigwedge_{a \in A'} \mathrm{arg}_a ) \wedge ( \bigwedge_{a \in A \setminus A'} \neg \mathrm{arg}_a ) \wedge ( \bigwedge_{(a,b) \in R} \mathrm{att}_{a,b} ) \wedge ( \bigwedge_{(a,b) \in (A \times A) \setminus R} \neg \mathrm{att}_{a,b} ) $$
$$ \bullet R = \{(a, b) \in A \times A \mid \omega(\mathrm{att}_{a,b}) = 1\}. $$

**Example 7.** We consider the three AFs $\mathcal{F}_1$, $\mathcal{F}_2$ and $\mathcal{F}_3$ depicted respectively in Figure 7a, 7b and 7c. Assume that the constraints are built on the propositional vocabulary $Prop_A$, where $A = \{a, b, c, d, e\}$. The formula $\phi_1 = \mathrm{arg}_a \wedge (\mathrm{att}_{b,a} \oplus \mathrm{att}_{b,c})$ expresses the fact that a should appear in the AF, and exactly one of the attacks $(b, a)$ and $(b, c)$ should appear as well. This formula is satisfied by $\mathcal{F}_1$, but not by $\mathcal{F}_2$ and $\mathcal{F}_3$. Now let us define the formula $\phi_2 = (\mathrm{arg}_a \vee \mathrm{arg}_d) \wedge \neg \mathrm{arg}_e \wedge (\mathrm{arg}_a \rightarrow \mathrm{att}_{a,b})$. It is satisfied if the AF contains either a or d (or both) but not e, and also if a appears in the AF then it must attack b. This formula is satisfied by the three AFs considered here.

<figure><img src="image_9.png" /><figcaption>Figure 7: Three examples of AFs</figcaption></figure>

## 3.2 Definition and Expressiveness of CIAFs

Now we formally define Constrained IAFs, and prove that this framework solves the Disjunction Problem introduced in Section 2.4.

**Definition 8 (Constrained IAF).** A Constrained Incomplete Argumentation Framework (CIAF) is a tuple $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$, where $\langle A, A^?, R, R^? \rangle$ is an IAF, and $\phi \in \mathcal{L}_{A \cup A^?}$ is a constraint.

The constraint $\phi$ is used to select a subset of the completions of the IAF $\mathcal{I}_C = \langle A, A^?, R, R^? \rangle$. The completions of a CIAF are then defined as follows.

**Definition 9 (Completions of a CIAF).** Given $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ a CIAF, we define its set of completions by $\mathrm{comp}(\mathcal{C}) = \{c \in \mathrm{comp}(\mathcal{I}_C) \mid c \text{ satisfies } \phi\}$ where $\mathcal{I}_C = \langle A, A^?, R, R^? \rangle$.

**Example 8.** Let $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ be a CIAF such that $\mathcal{I}_C = \langle A, A^?, R, R^? \rangle$ is the IAF from Figure 2, and $\phi = \mathrm{att}_{e,a} \wedge \mathrm{arg}_f$. Recall that the completions of $\mathcal{I}_C$ are given in Figure 3. Only two of them satisfy $\phi$, namely $\mathcal{F}_5$ (Fig. 3e) and $\mathcal{F}_6$ (Fig. 3f). So $\mathrm{comp}(\mathcal{C}) = \{\mathcal{F}_5, \mathcal{F}_6\}$.

Let us mention that, in order to be meaningful, the constraint $\phi$ must satisfy some conditions. Indeed, there must be at least one model of $\phi$ such that $\mathrm{arg}_a$ is true for each $a \in A$, $\mathrm{att}_{a,b}$ is true for each $(a, b) \in R$, and $\mathrm{att}_{a,b}$ is false for each $(a, b) \in ((A \cup A^?) \times (A \cup A^?)) \setminus (R \cup R^?)$. Otherwise, $\mathrm{comp}(\mathcal{C})$ is trivially empty. More generally, a CIAF $\mathcal{C}$ is over-constrained when $\mathrm{comp}(\mathcal{C}) = \emptyset$.

Now, we focus on the expressiveness of CIAFs, i.e. given a set of AFs (or a set of extensions), is there a CIAF such that its completions (or the extensions of its completions) correspond to the given set? We show that, in both cases, the answer is yes.

**Representing a Set of AFs** First, we define a particular formula, that is only satisfied by one given AF.

**Definition 10.** Given A a set of arguments, and $\mathcal{F} = \langle A', R \rangle$ with $A' \subseteq A$, and $R \subseteq A' \times A'$, we define $\psi_{\mathcal{F}} \in \mathcal{L}_A$ as

$$ \psi_{\mathcal{F}} = ( \bigwedge_{a \in A'} \mathrm{arg}_a ) \wedge ( \bigwedge_{a \in A \setminus A'} \neg \mathrm{arg}_a ) \wedge ( \bigwedge_{(a,b) \in R} \mathrm{att}_{a,b} ) \wedge ( \bigwedge_{(a,b) \in (A \times A) \setminus R} \neg \mathrm{att}_{a,b} ) $$
**Proposition 1.** Let $\mathfrak{F} = \{\mathcal{F}_1 = \langle A_1, R_1 \rangle, \dots, \mathcal{F}_n = \langle A_n, R_n \rangle\}$ be a set of AFs. There is a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$.

Intuitively, a simple CIAF that does the job consists of all the arguments and attacks from $\mathfrak{F}$ defined as uncertain, and then $\phi$ is the disjunction of the $\psi_{\mathcal{F}}$ formulas, for $\mathcal{F} \in \mathfrak{F}$.

*Proof.* Let us build a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$. To do that, we first choose $A = \emptyset$ and $A^? = \bigcup_{i=1}^n A_i$, i.e. all the arguments that appear in an AF from $\mathfrak{F}$ are uncertain. Similarly, all the attacks are uncertain, i.e. $R = \emptyset$ and $R^? = \bigcup_{i=1}^n R_i$. With all these choices, we define an IAF that has all the possible completions on arguments and attacks from $\mathfrak{F}$. In order to restrict the completions to exactly the AFs in $\mathfrak{F}$, we define $\phi = \bigvee_{i=1}^n \psi_{\mathcal{F}_i}$, where $\psi_{\mathcal{F}_i}$ is the formula that is only satisfied by the AF $\mathcal{F}_i$, following Definition 10. The AFs that satisfy $\phi$ are exactly the ones in $\mathfrak{F}$, so we have $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$. $\square$

**Example 9.** We continue Example 5. For $\mathfrak{F} = \{\mathcal{F}_1 = \langle \{a, b\}, \{ (b, a) \} \rangle, \mathcal{F}_2 = \langle \{a, c\}, \{ (c, a) \} \rangle \}$, we define $\mathcal{C} = \langle A, A^?, R, R^?, \phi, \rangle$, with $A = \emptyset$, $A^? = \{a, b, c\}$, $R = \emptyset$, $R^? = \{ (b, a), (c, a) \}$, $\phi = \psi_{\mathcal{F}_1} \lor \psi_{\mathcal{F}_2}$, where

$$ \psi_{\mathcal{F}_1} = \arg_a \wedge \arg_b \wedge \neg \arg_c \wedge \mathrm{att}_{b,a} \wedge ( \bigwedge_{(x,y) \in (\{a,b,c\} \times \{a,b,c\}) \setminus \{(b,a)\}} \neg \mathrm{att}_{x,y} ) $$

and

$$ \psi_{\mathcal{F}_2} = \arg_a \wedge \neg \arg_b \wedge \arg_c \wedge \mathrm{att}_{c,a} \wedge ( \bigwedge_{(x,y) \in (\{a,b,c\} \times \{a,b,c\}) \setminus \{(c,a)\}} \neg \mathrm{att}_{x,y} ) $$

We have $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$.

**Representing a Set of Extensions** Now, we focus on the expressibility of a set of extensions with a CIAF.

**Proposition 2.** Let $\mathfrak{E} = \{E_1, \dots, E_n\}$ be a set of extensions, and $\sigma \in \{\mathrm{co}, \mathrm{pr}, \mathrm{gr}\}$. There is a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\bigcup_{c \in \mathrm{comp}(\mathcal{C})} \sigma(c) = \mathfrak{E}$. Moreover, if $E_i \neq \emptyset$ for all $i \in \{1, \dots, n\}$, then there is a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\bigcup_{c \in \mathrm{comp}(\mathcal{C})} \mathrm{st}(c) = \mathfrak{E}$.

*Proof.* We consider first the case where $E_i \neq \emptyset$ for all $i \in \{1, \dots, n\}$. Let us define $A = \bigcup_{i=1}^n E_i$, i.e. it is the set of all the arguments that appear in some extension. Then, for each $E_i \in \mathfrak{E}$, we define $\mathcal{F}_i = \langle A, R_i \rangle$ such that $R_i = \{(a, b) \mid a \in E_i, b \in A \setminus E_i\}$, i.e. each argument in $E_i$ is unattacked, and it attacks all the arguments that are not in the extension. For any $\sigma$ defined in this paper,$^3$ $E_i$ is the only extension of $\mathcal{F}_i$. Thus, $\bigcup_{i=1}^n \sigma(\mathcal{F}_i) = \mathfrak{E}$. From Proposition 1, there is $\mathcal{C}$ such that $\mathrm{comp}(\mathcal{C}) = \{\mathcal{F}_1, \dots, \mathcal{F}_n\}$.

Now, suppose that $\sigma \in \{\mathrm{co}, \mathrm{pr}, \mathrm{gr}\}$, and $E_i = \emptyset$ for some $i \in \{1, \dots, n\}$. For each $E_j \neq E_i$, the AF $\mathcal{F}_j$ can be constructed with the same method as in the previous case. The AF $\mathcal{F}_i$ corresponding to $E_i = \emptyset$ is constructing by making each argument self-attacking, i.e. $\mathcal{F}_i = \langle A, \{(a, a) \mid a \in A\} \rangle$, which satisfies $\sigma(\mathcal{F}_i) = \{\emptyset\}$. Again, Proposition 1 implies the existence of a $\mathcal{C}$ such that $\mathrm{comp}(\mathcal{C}) = \{\mathcal{F}_1, \dots, \mathcal{F}_n\}$.

This concludes the proof. $\square$

Of course, the constructions described in the previous proofs only show the existence of a CIAF that satisfies the expected property (i.e. representing a given set of AFs, or a given set of extensions). This does not mean that this CIAF is the best way to represent the set of AFs (or extensions). A

<footnote>$^3$And arguably most semantics defined in the literature.</footnote>
**Proposition 1.** Let $\mathfrak{F} = \{\mathcal{F}_1 = \langle A_1, R_1 \rangle, \dots, \mathcal{F}_n = \langle A_n, R_n \rangle\}$ be a set of AFs. There is a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$.

Intuitively, a simple CIAF that does the job consists of all the arguments and attacks from $\mathfrak{F}$ defined as uncertain, and then $\phi$ is the disjunction of the $\psi_{\mathcal{F}}$ formulas, for $\mathcal{F} \in \mathfrak{F}$.

*Proof.* Let us build a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$. To do that, we first choose $A = \emptyset$ and $A^? = \bigcup_{i=1}^n A_i$, i.e. all the arguments that appear in an AF from $\mathfrak{F}$ are uncertain. Similarly, all the attacks are uncertain, i.e. $R = \emptyset$ and $R^? = \bigcup_{i=1}^n R_i$. With all these choices, we define an IAF that has all the possible completions on arguments and attacks from $\mathfrak{F}$. In order to restrict the completions to exactly the AFs in $\mathfrak{F}$, we define $\phi = \bigvee_{i=1}^n \psi_{\mathcal{F}_i}$, where $\psi_{\mathcal{F}_i}$ is the formula that is only satisfied by the AF $\mathcal{F}_i$, following Definition 10. The AFs that satisfy $\phi$ are exactly the ones in $\mathfrak{F}$, so we have $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$. $\square$

**Example 9.** We continue Example 5. For $\mathfrak{F} = \{\mathcal{F}_1 = \langle \{a, b\}, \{ (b, a) \} \rangle, \mathcal{F}_2 = \langle \{a, c\}, \{ (c, a) \} \rangle \}$, we define $\mathcal{C} = \langle A, A^?, R, R^?, \phi, \rangle$, with $A = \emptyset$, $A^? = \{a, b, c\}$, $R = \emptyset$, $R^? = \{ (b, a), (c, a) \}$, $\phi = \psi_{\mathcal{F}_1} \lor \psi_{\mathcal{F}_2}$, where

$$ \psi_{\mathcal{F}_1} = \arg_a \wedge \arg_b \wedge \neg \arg_c \wedge \mathrm{att}_{b,a} \wedge ( \bigwedge_{(x,y) \in (\{a,b,c\} \times \{a,b,c\}) \setminus \{(b,a)\}} \neg \mathrm{att}_{x,y} ) $$

and

$$ \psi_{\mathcal{F}_2} = \arg_a \wedge \neg \arg_b \wedge \arg_c \wedge \mathrm{att}_{c,a} \wedge ( \bigwedge_{(x,y) \in (\{a,b,c\} \times \{a,b,c\}) \setminus \{(c,a)\}} \neg \mathrm{att}_{x,y} ) $$

We have $\mathrm{comp}(\mathcal{C}) = \mathfrak{F}$.

**Representing a Set of Extensions** Now, we focus on the expressibility of a set of extensions with a CIAF.

**Proposition 2.** Let $\mathfrak{E} = \{E_1, \dots, E_n\}$ be a set of extensions, and $\sigma \in \{\mathrm{co}, \mathrm{pr}, \mathrm{gr}\}$. There is a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\bigcup_{c \in \mathrm{comp}(\mathcal{C})} \sigma(c) = \mathfrak{E}$. Moreover, if $E_i \neq \emptyset$ for all $i \in \{1, \dots, n\}$, then there is a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ such that $\bigcup_{c \in \mathrm{comp}(\mathcal{C})} \mathrm{st}(c) = \mathfrak{E}$.

*Proof.* We consider first the case where $E_i \neq \emptyset$ for all $i \in \{1, \dots, n\}$. Let us define $A = \bigcup_{i=1}^n E_i$, i.e. it is the set of all the arguments that appear in some extension. Then, for each $E_i \in \mathfrak{E}$, we define $\mathcal{F}_i = \langle A, R_i \rangle$ such that $R_i = \{(a, b) \mid a \in E_i, b \in A \setminus E_i\}$, i.e. each argument in $E_i$ is unattacked, and it attacks all the arguments that are not in the extension. For any $\sigma$ defined in this paper,<fnref n="3" /> $E_i$ is the only extension of $\mathcal{F}_i$. Thus, $\bigcup_{i=1}^n \sigma(\mathcal{F}_i) = \mathfrak{E}$. From Proposition 1, there is $\mathcal{C}$ such that $\mathrm{comp}(\mathcal{C}) = \{\mathcal{F}_1, \dots, \mathcal{F}_n\}$.

Now, suppose that $\sigma \in \{\mathrm{co}, \mathrm{pr}, \mathrm{gr}\}$, and $E_i = \emptyset$ for some $i \in \{1, \dots, n\}$. For each $E_j \neq E_i$, the AF $\mathcal{F}_j$ can be constructed with the same method as in the previous case. The AF $\mathcal{F}_i$ corresponding to $E_i = \emptyset$ is constructing by making each argument self-attacking, i.e. $\mathcal{F}_i = \langle A, \{(a, a) \mid a \in A\} \rangle$, which satisfies $\sigma(\mathcal{F}_i) = \{\emptyset\}$. Again, Proposition 1 implies the existence of a $\mathcal{C}$ such that $\mathrm{comp}(\mathcal{C}) = \{\mathcal{F}_1, \dots, \mathcal{F}_n\}$.

This concludes the proof. $\square$

Of course, the constructions described in the previous proofs only show the existence of a CIAF that satisfies the expected property (i.e. representing a given set of AFs, or a given set of extensions). This does not mean that this CIAF is the best way to represent the set of AFs (or extensions). A

<footnote n="3">³And arguably most semantics defined in the literature.</footnote>
first possible simplification consists in choosing $A = \bigcap_{i=1}^{n} A_i$ and $A^? = \bigcup_{i=1}^{n} A_i \setminus A$. This natural simplification means that an argument that appears in every AF must be considered as certain. A similar reasoning can be made with the attacks, and the constraint can also be simplified. In a context of belief revision [9, 10] or belief merging [6, 11], it is important to ensure that the resulting CIAF is as close as possible to the initial AF(s). This question is out of the scope of this paper, and is kept for future research.

## 3.3 Complexity Issues

Let us start with this basic observation:

**Observation 3.** Given an AF $\mathcal{F} = \langle A', R \rangle$ with $A' \subseteq A$ and a constraint $\phi \in \mathcal{L}_A$, checking whether $\mathcal{F}$ satisfies $\phi$ is doable in polynomial time.

*Proof.* Build $\omega_{\mathcal{F}}$ such that $\omega(\arg_a) = 1$ if and only if $a \in A'$ and $\omega(\mathrm{att}_{a,b}) = 1$ if and only if $(a,b) \in R$. This is a polynomial task. Checking whether $\omega_{\mathcal{F}}$ satisfies $\phi$ is also a (well-known) polynomial task. $\square$

This means that, given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$, guessing a completion of $C$ is equivalent to guessing a set of arguments $A \subseteq A' \subseteq A^?$, a set of attacks $R_{|A'} \subseteq R' \subseteq R^?_{|A'}$, and verifying (in polynomial time) whether $\langle A', R' \rangle$ satisfies $\phi$. This will be useful in the proofs of complexity results.

Now we formally adapt classical decision problems from IAFs to CIAFs. We split our study in two parts, the first one concerning verification problems, namely Incomplete Possible Verification (IncPV*) and Incomplete Necessary Verification (IncNV*):

*   **$\sigma$-IncPV*** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is there $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$ such that $S \in \sigma(\mathcal{F})$?

*   **$\sigma$-IncNV*** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is $S \in \sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$?

We study these problems in Section 3.3.1. Notice that we ignore here the original versions of the verification problem [7], because the second version due to [23] seems more intuitive, and as it was shown in [23], the original definition of the verification problem yields extensions with bad properties (e.g. violating conflict-freeness), especially in the case of possible verification.

The second part concerns acceptability problems, where $P$ stands again for Possible and $N$ for Necessary, while $C$ and $S$ respectively mean Credulous and Skeptical:

*   **$\sigma$-PCA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$ such that $a \in \mathrm{cr}_{\sigma}(\mathcal{F})$?

*   **$\sigma$-NCA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is $a \in \mathrm{cr}_{\sigma}(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$?

*   **$\sigma$-PSA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$ such that $a \in \mathrm{sk}_{\sigma}(\mathcal{F})$?

*   **$\sigma$-NSA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is $a \in \mathrm{sk}_{\sigma}(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$?

We focus on these problems in Section 3.3.2.
first possible simplification consists in choosing $A = \bigcap_{i=1}^{n} A_i$ and $A^? = \bigcup_{i=1}^{n} A_i \setminus A$. This natural simplification means that an argument that appears in every AF must be considered as certain. A similar reasoning can be made with the attacks, and the constraint can also be simplified. In a context of belief revision [9, 10] or belief merging [6, 11], it is important to ensure that the resulting CIAF is as close as possible to the initial AF(s). This question is out of the scope of this paper, and is kept for future research.

## 3.3 Complexity Issues

Let us start with this basic observation:

**Observation 3.** Given an AF $\mathcal{F} = \langle A', R \rangle$ with $A' \subseteq A$ and a constraint $\phi \in \mathcal{L}_A$, checking whether $\mathcal{F}$ satisfies $\phi$ is doable in polynomial time.

*Proof.* Build $\omega_{\mathcal{F}}$ such that $\omega(\arg_a) = 1$ if and only if $a \in A'$ and $\omega(\mathrm{att}_{a,b}) = 1$ if and only if $(a,b) \in R$. This is a polynomial task. Checking whether $\omega_{\mathcal{F}}$ satisfies $\phi$ is also a (well-known) polynomial task. $\square$

This means that, given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$, guessing a completion of $C$ is equivalent to guessing a set of arguments $A \subseteq A' \subseteq A^?$, a set of attacks $R_{|A'} \subseteq R' \subseteq R^?_{|A'}$, and verifying (in polynomial time) whether $\langle A', R' \rangle$ satisfies $\phi$. This will be useful in the proofs of complexity results.

Now we formally adapt classical decision problems from IAFs to CIAFs. We split our study in two parts, the first one concerning verification problems, namely Incomplete Possible Verification (IncPV*) and Incomplete Necessary Verification (IncNV*):

*   **$\sigma$-IncPV*** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is there $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$ such that $S \in \sigma(\mathcal{F})$?

*   **$\sigma$-IncNV*** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and a set of arguments $S \subseteq A \cup A^?$, is $S \in \sigma(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$?

We study these problems in Section 3.3.1. Notice that we ignore here the original versions of the verification problem [7], because the second version due to [23] seems more intuitive, and as it was shown in [23], the original definition of the verification problem yields extensions with bad properties (e.g. violating conflict-freeness), especially in the case of possible verification.

The second part concerns acceptability problems, where P stands again for Possible and N for Necessary, while C and S respectively mean Credulous and Skeptical:

*   **$\sigma$-PCA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$ such that $a \in \mathrm{cr}_{\sigma}(\mathcal{F})$?

*   **$\sigma$-NCA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is $a \in \mathrm{cr}_{\sigma}(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$?

*   **$\sigma$-PSA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is there $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$ such that $a \in \mathrm{sk}_{\sigma}(\mathcal{F})$?

*   **$\sigma$-NSA** Given a CIAF $C = \langle A, A^?, R, R^?, \phi \rangle$ and an argument $a \in A$, is $a \in \mathrm{sk}_{\sigma}(\mathcal{F})$ true for each $\mathcal{F} = \langle A', R' \rangle \in \mathrm{comp}(C)$?

We focus on these problems in Section 3.3.2.
### 3.3.1 Complexity of Verification

Recent work has shown that $\sigma$-IncPV* is NP-c for $\sigma \in \{\text{ad, st, co, gr}\}$ and $\Sigma_2^P$-c for $\sigma = \text{pr}$, for some subclasses of CIAFs [26, 27] (namely, the Arg-IAFs and Att-IAFs with dependencies<fnref n="4" /> that we discuss in Section 6). This provides lower bounds for the complexity of $\sigma$-IncPV* for CIAFs, we show here that the complexity of this problem for the general CIAF model is the same as for these subclasses.

**Proposition 4.** *The following holds:*

1. For $\sigma \in \{\text{ad, st, co, gr}\}$, $\sigma$-IncPV* is NP-complete.

2. pr-IncPV* is $\Sigma_2^P$-complete.

*Proof.* Hardness comes from the known complexity of $\sigma$-IncPV* for Arg-IAFs with dependencies and Att-IAFs with dependencies [26, 27], i.e. it is NP-hard for $\sigma \in \{\text{ad, st, co, gr}\}$ and $\Sigma_2^P$-hard for $\sigma = \text{pr}$. Membership comes from the following classical verification algorithm:

1. Non-deterministically guess a completion $\mathcal{F}$ of $\langle A, A^?, R, R^? \rangle$.

2. Check (in polynomial time, see Observation 3) whether $\mathcal{F}$ satisfies $\phi$.

3. Check whether $S$ is a $\sigma$-extension of $\mathcal{F}$.

The last check is either polynomial (for $\sigma \in \{\text{ad, st, co, gr}\}$), or in coNP (for $\sigma = \text{pr}$) [20], hence the result. $\square$

Now we focus on the necessary verification problem.

**Proposition 5.** *For $\sigma \in \{\text{ad, st, co, gr, pr}\}$, $\sigma$-IncNV* is coNP-complete.

*Proof.* The proof for the membership follows the same mechanism as the proof of Proposition 4. More precisely, considering $\sigma \in \{\text{ad, st, co, gr}\}$, for solving the complement problem of $\sigma$-IncNV* (let us write $\overline{\sigma - \text{IncNV}^*}$ this complement problem):

1. Non-deterministically guess a completion $\mathcal{F}$ of $\langle A, A^?, R, R^? \rangle$.

2. Check (in polynomial time, see Observation 3) whether $\mathcal{F}$ satisfies $\phi$.

3. Check whether $S$ is not a $\sigma$-extension of $\mathcal{F}$.

Since the last check is polynomial for all the considered semantics, we deduce the NP upper bound for $\overline{\sigma - \text{IncNV}^*}$, and thus the coNP upper bound for $\sigma$-IncNV*.

For $\sigma = \text{pr}$, the process is almost the same:

1. Non-deterministically guess a completion $\mathcal{F}$ of $\langle A, A^?, R, R^? \rangle$, and a set of arguments $S'$ such that $S \subset S'$.

2. Check (in polynomial time, see Observation 3) whether $\mathcal{F}$ satisfies $\phi$.

3. Check whether $S$ is not an admissible set in $\mathcal{F}$, or whether $S'$ is an admissible set in $\mathcal{F}$.

<footnote n="4">⁴An Arg-IAF [28] is an IAF where only arguments can be uncertain, i.e. $R^? = \emptyset$, while an Att-IAF [29] is an IAF where only attacks can be uncertain, i.e. $A^? = \emptyset$. Arg-IAFs and Att-IAFs with dependencies [26, 27] also take into consideration some constraint over the set of completions.</footnote>
### 3.3.1 Complexity of Verification

Recent work has shown that $\sigma$-IncPV* is NP-c for $\sigma \in \{\text{ad, st, co, gr}\}$ and $\Sigma_2^P$-c for $\sigma = \text{pr}$, for some subclasses of CIAFs [26, 27] (namely, the Arg-IAFs and Att-IAFs with dependencies<fnref n="4" /> that we discuss in Section 6). This provides lower bounds for the complexity of $\sigma$-IncPV* for CIAFs, we show here that the complexity of this problem for the general CIAF model is the same as for these subclasses.

**Proposition 4.** *The following holds:*

1. For $\sigma \in \{\text{ad, st, co, gr}\}$, $\sigma$-IncPV* is NP-complete.

2. pr-IncPV* is $\Sigma_2^P$-complete.

*Proof.* Hardness comes from the known complexity of $\sigma$-IncPV* for Arg-IAFs with dependencies and Att-IAFs with dependencies [26, 27], i.e. it is NP-hard for $\sigma \in \{\text{ad, st, co, gr}\}$ and $\Sigma_2^P$-hard for $\sigma = \text{pr}$. Membership comes from the following classical verification algorithm:

1. Non-deterministically guess a completion $\mathcal{F}$ of $\langle A, A^?, R, R^? \rangle$.

2. Check (in polynomial time, see Observation 3) whether $\mathcal{F}$ satisfies $\phi$.

3. Check whether $S$ is a $\sigma$-extension of $\mathcal{F}$.

The last check is either polynomial (for $\sigma \in \{\text{ad, st, co, gr}\}$), or in coNP (for $\sigma = \text{pr}$) [20], hence the result. □

Now we focus on the necessary verification problem.

**Proposition 5.** For $\sigma \in \{\text{ad, st, co, gr, pr}\}$, $\sigma$-IncNV* is coNP-complete.

*Proof.* The proof for the membership follows the same mechanism as the proof of Proposition 4. More precisely, considering $\sigma \in \{\text{ad, st, co, gr}\}$, for solving the complement problem of $\sigma$-IncNV* (let us write $\overline{\sigma - \text{IncNV}^*}$ this complement problem):

1. Non-deterministically guess a completion $\mathcal{F}$ of $\langle A, A^?, R, R^? \rangle$.

2. Check (in polynomial time, see Observation 3) whether $\mathcal{F}$ satisfies $\phi$.

3. Check whether $S$ is not a $\sigma$-extension of $\mathcal{F}$.

Since the last check is polynomial for all the considered semantics, we deduce the NP upper bound for $\overline{\sigma - \text{IncNV}^*}$, and thus the coNP upper bound for $\sigma$-IncNV*.

For $\sigma = \text{pr}$, the process is almost the same:

1. Non-deterministically guess a completion $\mathcal{F}$ of $\langle A, A^?, R, R^? \rangle$, and a set of arguments $S'$ such that $S \subset S'$.

2. Check (in polynomial time, see Observation 3) whether $\mathcal{F}$ satisfies $\phi$.

3. Check whether $S$ is not an admissible set in $\mathcal{F}$, or whether $S'$ is an admissible set in $\mathcal{F}$.

<footnote n="4">⁴An Arg-IAF [28] is an IAF where only arguments can be uncertain, i.e. $R^? = \emptyset$, while an Att-IAF [29] is an IAF where only attacks can be uncertain, i.e. $A^? = \emptyset$. Arg-IAFs and Att-IAFs with dependencies [26, 27] also take into consideration some constraint over the set of completions.</footnote>
This non-deterministic algorithm polynomially check whether $S$ is not a necessary preferred extension of $\mathcal{C}$, so we can conclude that $\text{pr-IncNV}^*$ is in $\text{coNP}$.

Now let us prove the coNP-hardness. We consider the NP-complete problem SAT, and for each propositional formula $\psi$ we will build a CIAF $C_\psi$ and a set of arguments $S$ such that $\psi$ is satisfiable if and only if $S$ is not a $\sigma$ extension of some completion of $C_\psi$. This will prove the NP-hardness of the $\sigma$-IncNV$^*$, and thus the coNP-hardness of IncNV$^*$.

The reduction is as follows. Assume that the formula $\psi$ is built on the set of Boolean variables $\mathcal{Y} = \{y_1, \dots, y_n\}$. We build the CIAF $C_\psi = (A, A^?, R, R^?, \phi)$ with $A = \{y_1, \dots, y_n\}$, $A^? = \{s\}$, $R = \{(s, y_i) \mid y_i \in \mathcal{Y}\}$, $R^? = \emptyset$ and $\phi = \psi' \lor \arg_s$, where $\psi'$ is a transformed version of $\psi$ such that each variable $y_i$ is replaced by the variable $\arg_{y_i}$. The reduction is illustrated by Figure 8, which shows the “IAF part” of $C_\psi$, i.e. $\langle A, A^?, R, R^? \rangle$. The goal is to determine whether $S = \{s\}$ is a necessary $\sigma$-extension of $C_\psi$, under $\sigma \in \{\text{ad}, \text{st}, \text{co}, \text{gr}, \text{pr}\}$.

<figure><img src="image_10.png" /><figcaption>Figure 8: An illustration of the reduction from SAT, with $\psi$ built on $\{y_1, \dots, y_n\}$</figcaption></figure>

It is obvious that any interpretation $\omega$ over $\mathcal{Y}$ can be transformed into an interpretation $\omega'$ over $\mathcal{Y}' = \{\arg_{y_1}, \dots, \arg_{y_n}\}$ such that $\omega \models \psi'$ if and only if $\omega' \models \psi'$. Then, assume that $\psi$ is satisfiable, and let $\omega'$ be such an interpretation satisfying $\psi'$. $\omega'$ can be extended into a model $\omega^*$ of $\phi$ by stating $\omega^*(\arg_{y_i}) = \omega'(\arg_{y_i})$ for any $y_i \in \mathcal{Y}$, and $\omega^*(\arg_s) = 0$. This means that $\mathcal{F}_1^* = \langle A, \emptyset \rangle$ is a completion of $C_\psi$, where $s$ does not appear, and so obviously $S = \{s\}$ is not a $\sigma$ extension of $\mathcal{F}_1^*$ for any $\sigma$.

Now, assume that $\psi$ is not satisfiable, then $\psi'$ is not satisfiable either, and so any model of $\phi = \psi' \lor \arg_s$ must assign to $\arg_s$ the value 1. This implies that the single completion of $C_\psi$ is $\mathcal{F}_2^* = \langle A \cup A^?, R \rangle$, which has a single extension $S = \{s\}$ under all semantics $\sigma$ considered here except $\sigma = \text{ad}$. For this last case, we observe that $\text{ad}(\mathcal{F}_2^*) = \{\emptyset, \{s\}\}$. So $S = \{s\}$ is a necessary $\sigma$-extension for all the semantics $\sigma$ considered.

This concludes the proof that $\text{SAT} \le_f^P \sigma - \text{IncNV}^*$, thus $\sigma - \text{IncNV}^*$ is NP-hard, and $\sigma$-IncNV$^*$ is coNP-hard. $\square$

### 3.3.2 Complexity of Acceptability

Now we focus on the various acceptability problems for CIAFs, and we show that they have the same complexity as their counterpart for (standard) IAFs.

First of all, notice that all the hardness results can be deduced from the known results for IAFs [8], since any IAF can be transformed into a CIAF with a tautological constraint.

Let us start with both variants of credulous acceptability.

**Proposition 6.** For $\sigma \in \{\text{ad}, \text{st}, \text{co}, \text{gr}, \text{pr}\}$, $\sigma$-PCA is NP-complete.

*Proof.* Recall that an IAF is a CIAF with $\phi = \top$, and $\sigma$-PCA is NP-complete for IAFs under all the considered semantics [8], hence the NP-hardness for CIAFs.

We prove membership by the following non-deterministic polynomial algorithm. Guess a completion $\mathcal{F} = \langle A', R' \rangle$ of $\mathcal{C}$, and a set of arguments $S \subseteq A'$ such that $a \in S$. Checking whether $\mathcal{F}$ satisfies
This non-deterministic algorithm polynomially check whether $S$ is not a necessary preferred extension of $\mathcal{C}$, so we can conclude that $\text{pr-IncNV}^*$ is in $\text{coNP}$.

Now let us prove the coNP-hardness. We consider the NP-complete problem SAT, and for each propositional formula $\psi$ we will build a CIAF $C_\psi$ and a set of arguments $S$ such that $\psi$ is satisfiable if and only if $S$ is not a $\sigma$ extension of some completion of $C_\psi$. This will prove the NP-hardness of the $\sigma$-IncNV$^*$, and thus the coNP-hardness of IncNV$^*$.

The reduction is as follows. Assume that the formula $\psi$ is built on the set of Boolean variables $\mathcal{Y} = \{y_1, \dots, y_n\}$. We build the CIAF $C_\psi = (A, A^?, R, R^?, \phi)$ with $A = \{y_1, \dots, y_n\}$, $A^? = \{s\}$, $R = \{(s, y_i) \mid y_i \in \mathcal{Y}\}$, $R^? = \emptyset$ and $\phi = \psi' \lor \arg_s$, where $\psi'$ is a transformed version of $\psi$ such that each variable $y_i$ is replaced by the variable $\arg_{y_i}$. The reduction is illustrated by Figure 8, which shows the “IAF part” of $C_\psi$, i.e. $\langle A, A^?, R, R^? \rangle$. The goal is to determine whether $S = \{s\}$ is a necessary $\sigma$-extension of $C_\psi$, under $\sigma \in \{\text{ad}, \text{st}, \text{co}, \text{gr}, \text{pr}\}$.

<figure><img src="image_10.png" /><figcaption>Figure 8: An illustration of the reduction from SAT, with $\psi$ built on $\{y_1, \dots, y_n\}$</figcaption></figure>

It is obvious that any interpretation $\omega$ over $\mathcal{Y}$ can be transformed into an interpretation $\omega'$ over $\mathcal{Y}' = \{\arg_{y_1}, \dots, \arg_{y_n}\}$ such that $\omega \models \psi'$ if and only if $\omega' \models \psi'$. Then, assume that $\psi$ is satisfiable, and let $\omega'$ be such an interpretation satisfying $\psi'$. $\omega'$ can be extended into a model $\omega^*$ of $\phi$ by stating $\omega^*(\arg_{y_i}) = \omega'(\arg_{y_i})$ for any $y_i \in \mathcal{Y}$, and $\omega^*(\arg_s) = 0$. This means that $\mathcal{F}_1^* = \langle A, \emptyset \rangle$ is a completion of $C_\psi$, where $s$ does not appear, and so obviously $S = \{s\}$ is not a $\sigma$ extension of $\mathcal{F}_1^*$ for any $\sigma$.

Now, assume that $\psi$ is not satisfiable, then $\psi'$ is not satisfiable either, and so any model of $\phi = \psi' \lor \arg_s$ must assign to $\arg_s$ the value 1. This implies that the single completion of $C_\psi$ is $\mathcal{F}_2^* = \langle A \cup A^?, R \rangle$, which has a single extension $S = \{s\}$ under all semantics $\sigma$ considered here except $\sigma = \text{ad}$. For this last case, we observe that $\text{ad}(\mathcal{F}_2^*) = \{\emptyset, \{s\}\}$. So $S = \{s\}$ is a necessary $\sigma$-extension for all the semantics $\sigma$ considered.

This concludes the proof that $\text{SAT} \le_f^P \sigma - \text{IncNV}^*$, thus $\sigma - \text{IncNV}^*$ is NP-hard, and $\sigma$-IncNV$^*$ is coNP-hard. $\square$

### 3.3.2 Complexity of Acceptability

Now we focus on the various acceptability problems for CIAFs, and we show that they have the same complexity as their counterpart for (standard) IAFs.

First of all, notice that all the hardness results can be deduced from the known results for IAFs [8], since any IAF can be transformed into a CIAF with a tautological constraint.

Let us start with both variants of credulous acceptability.

**Proposition 6.** For $\sigma \in \{\text{ad}, \text{st}, \text{co}, \text{gr}, \text{pr}\}$, $\sigma$-PCA is NP-complete.

*Proof.* Recall that an IAF is a CIAF with $\phi = \top$, and $\sigma$-PCA is NP-complete for IAFs under all the considered semantics [8], hence the NP-hardness for CIAFs.

We prove membership by the following non-deterministic polynomial algorithm. Guess a completion $\mathcal{F} = \langle A', R' \rangle$ of $\mathcal{C}$, and a set of arguments $S \subseteq A'$ such that $a \in S$. Checking whether $\mathcal{F}$ satisfies
$\phi$ is polynomial. Checking whether $S$ is a $\sigma$-extension of $\mathcal{F}$ is polynomial for $\sigma \in \{\text{ad, st, co, gr}\}$. For $\sigma = \text{pr}$, checking whether $S$ is admissible is enough for proving that $a$ belongs to some preferred extension. Hence the result. $\square$

**Proposition 7.** For $\sigma \in \{\text{ad, st, co, pr}\}$, $\sigma$-NCA is $\Pi_2^P$-complete, and gr-NCA is coNP-complete.

*Proof.* Hardness results come again from the known complexity of $\sigma$-NCA for IAFs, which is $\Pi_2^P$-complete for $\sigma \in \{\text{ad, st, co, pr}\}$ and coNP-complete for $\sigma = \text{gr}$ [8].

The membership proof uses again a non-deterministic guess and check algorithm. Guess a completion $\mathcal{F}$, check whether it satisfies $\phi$, and check whether $a$ is credulously accepted in $\mathcal{F}$. Credulous acceptability for AFs is in NP for $\sigma \in \{\text{ad, st, co, pr}\}$ [20], so $\sigma$-NCA is in $\Pi_2^P$ for these semantics. Since credulous acceptability for AFs is polynomial for $\sigma = \text{gr}$, we obtain the last result. $\square$

Concerning skeptical reasoning, the problem is trivial under $\sigma = \text{ad}$, as usual, since $\emptyset$ is admissible in any AF, there is no skeptically accepted argument in any completion.

**Proposition 8.** For $\sigma \in \{\text{st, co, gr}\}$, $\sigma$-NSA is coNP-complete, and pr-NSA is $\Pi_2^P$-complete.

*Proof.* coNP-hardness (for $\sigma \in \{\text{st, co, gr}\}$) and $\Pi_2^P$-hardness (for $\sigma = \text{pr}$) can be deduced from the same hardness for $\sigma$-NSA in the case of IAFs [8].

For $\sigma \in \{\text{st, co, gr}\}$, we prove the membership thanks to the following non-deterministic algorithm for checking that $a$ is *not* necessarily skeptically accepted, i.e. this algorithm solves the complement problem of $\sigma$-NSA. Guess a completion and a set of arguments $S$ that does not contain $a$, and check (in polynomial time) whether the completion satisfies the constraint $\phi$. Then check (in polynomial time) whether $S$ is a $\sigma$-extension. This is a NP algorithm, so we deduce that $\sigma$-NSA is in coNP. Finally, the algorithm is the same for $\sigma = \text{pr}$, except that the last check is in coNP, hence the higher complexity upper bound. $\square$

We conclude with possible skeptical acceptability.

**Proposition 9.** For $\sigma \in \{\text{co, gr}\}$, $\sigma$-PSA is NP-complete, st-PSA is $\Sigma_2^P$-complete, and pr-PSA is $\Sigma_3^P$-complete.

*Proof.* Hardness results follow from the known complexity of $\sigma$-PSA for IAFs [8], namely NP-hardness for $\sigma \in \{\text{co, gr}\}$, $\Sigma_2^P$-hardness for $\sigma = \text{st}$ and $\Sigma_3^P$-hardness for $\sigma = \text{pr}$.

The generic non-deterministic algorithm for solving $\sigma$-PSA is as follows: guess a completion $\mathcal{F}$, check in polynomial time whether it satisfies $\phi$, and finally check whether $a$ is skeptically accepted in $\mathcal{F}$. This algorithm (non-deterministically) solves $\sigma$-PSA since it returns “YES” if the guessed completion is a valid completion of the CIAF (with respect to $\phi$) which skeptically accepts $a$. Since the last check is polynomial for $\sigma \in \{\text{co, gr}\}$, in coNP for $\sigma = \text{st}$, and in $\Pi_2^P$ for $\sigma = \text{pr}$ [20], we can deduce the membership result. $\square$

### 3.3.3 Summary

Table 4 summarizes our complexity results regarding CIAFs. We observe that verifying whether a set is a (possible or necessary) extension is one level higher in the polynomial hierarchy compared to standard IAFs, except for the preferred semantics which remains at the second level for the possible variant and the first level for the necessary variant. However, we observe that all the acceptability problems have the same complexity as in the case of standard IAFs. This interesting results suggests that acceptability of arguments in CIAFs could be computed with similar approaches to the ones used for IAFs [30, 24]. Finally, let us mention that credulous and skeptical acceptability can be generalized to sets of arguments without increasing the complexity.
$\phi$ is polynomial. Checking whether $S$ is a $\sigma$-extension of $\mathcal{F}$ is polynomial for $\sigma \in \{\text{ad, st, co, gr}\}$. For $\sigma = \text{pr}$, checking whether $S$ is admissible is enough for proving that $a$ belongs to some preferred extension. Hence the result. $\square$

**Proposition 7.** For $\sigma \in \{\text{ad, st, co, pr}\}$, $\sigma$-NCA is $\Pi_2^P$-complete, and gr-NCA is coNP-complete.

*Proof.* Hardness results come again from the known complexity of $\sigma$-NCA for IAFs, which is $\Pi_2^P$-complete for $\sigma \in \{\text{ad, st, co, pr}\}$ and coNP-complete for $\sigma = \text{gr}$ [8].

The membership proof uses again a non-deterministic guess and check algorithm. Guess a completion $\mathcal{F}$, check whether it satisfies $\phi$, and check whether $a$ is credulously accepted in $\mathcal{F}$. Credulous acceptability for AFs is in NP for $\sigma \in \{\text{ad, st, co, pr}\}$ [20], so $\sigma$-NCA is in $\Pi_2^P$ for these semantics. Since credulous acceptability for AFs is polynomial for $\sigma = \text{gr}$, we obtain the last result. $\square$

Concerning skeptical reasoning, the problem is trivial under $\sigma = \text{ad}$, as usual, since $\emptyset$ is admissible in any AF, there is no skeptically accepted argument in any completion.

**Proposition 8.** For $\sigma \in \{\text{st, co, gr}\}$, $\sigma$-NSA is coNP-complete, and pr-NSA is $\Pi_2^P$-complete.

*Proof.* coNP-hardness (for $\sigma \in \{\text{st, co, gr}\}$) and $\Pi_2^P$-hardness (for $\sigma = \text{pr}$) can be deduced from the same hardness for $\sigma$-NSA in the case of IAFs [8].

For $\sigma \in \{\text{st, co, gr}\}$, we prove the membership thanks to the following non-deterministic algorithm for checking that $a$ is *not* necessarily skeptically accepted, i.e. this algorithm solves the complement problem of $\sigma$-NSA. Guess a completion and a set of arguments $S$ that does not contain $a$, and check (in polynomial time) whether the completion satisfies the constraint $\phi$. Then check (in polynomial time) whether $S$ is a $\sigma$-extension. This is a NP algorithm, so we deduce that $\sigma$-NSA is in coNP. Finally, the algorithm is the same for $\sigma = \text{pr}$, except that the last check is in coNP, hence the higher complexity upper bound. $\square$

We conclude with possible skeptical acceptability.

**Proposition 9.** For $\sigma \in \{\text{co, gr}\}$, $\sigma$-PSA is NP-complete, st-PSA is $\Sigma_2^P$-complete, and pr-PSA is $\Sigma_3^P$-complete.

*Proof.* Hardness results follow from the known complexity of $\sigma$-PSA for IAFs [8], namely NP-hardness for $\sigma \in \{\text{co, gr}\}$, $\Sigma_2^P$-hardness for $\sigma = \text{st}$ and $\Sigma_3^P$-hardness for $\sigma = \text{pr}$.

The generic non-deterministic algorithm for solving $\sigma$-PSA is as follows: guess a completion $\mathcal{F}$, check in polynomial time whether it satisfies $\phi$, and finally check whether $a$ is skeptically accepted in $\mathcal{F}$. This algorithm (non-deterministically) solves $\sigma$-PSA since it returns “YES” if the guessed completion is a valid completion of the CIAF (with respect to $\phi$) which skeptically accepts $a$. Since the last check is polynomial for $\sigma \in \{\text{co, gr}\}$, in coNP for $\sigma = \text{st}$, and in $\Pi_2^P$ for $\sigma = \text{pr}$ [20], we can deduce the membership result. $\square$

### 3.3.3 Summary

Table 4 summarizes our complexity results regarding CIAFs. We observe that verifying whether a set is a (possible or necessary) extension is one level higher in the polynomial hierarchy compared to standard IAFs, except for the preferred semantics which remains at the second level for the possible variant and the first level for the necessary variant. However, we observe that all the acceptability problems have the same complexity as in the case of standard IAFs. This interesting results suggests that acceptability of arguments in CIAFs could be computed with similar approaches to the ones used for IAFs [30, 24]. Finally, let us mention that credulous and skeptical acceptability can be generalized to sets of arguments without increasing the complexity.
<table><caption>Table 4: Summary of complexity results for CIAFs, for $\sigma \in \{\text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$. Cells with grey background correspond to cases where the complexity is higher than for standard IAFs.</caption><thead><tr><th>σ</th><th>σ-IncPV*</th><th>σ-IncNV*</th><th>σ-PCA</th><th>σ-PSA</th><th>σ-NCA</th><th>σ-NSA</th></tr></thead><tbody><tr><td>ad</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>trivial</td><td>Π<sup>P</sup><sub>2-c</sub></td><td>trivial</td></tr><tr><td>co</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>NP-c</td><td>Π<sup>P</sup><sub>2-c</sub></td><td>coNP-c</td></tr><tr><td>pr</td><td>Σ<sup>P</sup><sub>2-c</sub></td><td>coNP-c</td><td>NP-c</td><td>Σ<sup>P</sup><sub>3-c</sub></td><td>Π<sup>P</sup><sub>2-c</sub></td><td>Π<sup>P</sup><sub>2-c</sub></td></tr><tr><td>gr</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>NP-c</td><td>coNP-c</td><td>coNP-c</td></tr><tr><td>st</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>Σ<sup>P</sup><sub>2-c</sub></td><td>Π<sup>P</sup><sub>2-c</sub></td><td>coNP-c</td></tr></tbody></table>

# 4 CIAFs and Extension Enforcement

This section focuses on extension enforcement [13, 14, 31], a major approach for argumentation dynamics [32]. We show that CIAFs can be useful for defining new extension enforcement operators.

## 4.1 Expansion-based Enforcement

Now we introduce the notions of AF expansion and extension enforcement [13, 14, 31].

**Definition 11.** Let $\mathcal{F} = \langle A, R \rangle$ be an AF. An expansion of $\mathcal{F}$ is an AF $\mathcal{F}' = \langle A \cup A', R \cup R' \rangle$ such that $A' \neq \emptyset$ and $A \cap A' = \emptyset$. An expansion is called normal if $\forall (a, b) \in R'$, $a \in A'$ or $b \in A'$. Moreover, a normal expansion is strong (respectively weak) if $\forall (a, b) \in R'$, $a \notin A$ (respectively $b \notin A$).

In words, an expansion adds some arguments, and possibly attacks. In the case of a normal expansion, the only added attacks concern at least one new arguments, i.e. the attacks between the former arguments are not modified. Finally, a normal expansion is strong (respectively weak) if it adds only strong (respectively weak) arguments, i.e. arguments that are not attacked by (respectively do not attack) the former arguments. The fact that $\mathcal{F}'$ is an expansion of $\mathcal{F}$ is denoted $\mathcal{F} \preceq_E \mathcal{F}'$ (and normal, strong, weak expansions are denoted by $\preceq_N, \preceq_S, \preceq_W$).

**Example 10.** Let $\mathcal{F} = \langle A, R \rangle$ be the AF depicted in Figure 9a. Figure 9b shows an expansion of $\mathcal{F}$: some argument f has been added, as well as some attacks (including an attack between the previous arguments a and c). Then, $\mathcal{F}_2$ from Figure 9c is a normal expansion of $\mathcal{F}$: there is no new attack between the previous arguments (but the new arguments can attack each other, attack the previous arguments, or be attacked by the previous arguments). Finally, $\mathcal{F}_3$ (Figure 9d) is a strong expansion of $\mathcal{F}$ (the new arguments cannot be attacked by the previous ones), while $\mathcal{F}_4$ (Figure 9e) is a weak expansion (the new arguments cannot attack the previous ones).

Expansions can be used to modify an AF such that a given set of arguments becomes (a part of) an extension in the new AF. This operation is called the (expansion-based) enforcement of the set of arguments.

**Definition 12.** Given $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, and a semantics $\sigma$, the AF $\mathcal{F}'$ is a non-strict normal (respectively strong, weak) $\sigma$-enforcement of $S$ in $\mathcal{F}$ if and only if $\mathcal{F}'$ is a normal (respectively strong, weak) expansion of $\mathcal{F}$, and $\exists E \in \sigma(\mathcal{F}')$ such that $S \subseteq E$.

Definition 12 considers non-strict enforcement, i.e. the desired set of arguments must be included in an extension of the new AF. Strict enforcement is defined in a similar manner, but the desired set of arguments must exactly correspond to an extension:
<table><caption>Table 4: Summary of complexity results for CIAFs, for $\sigma \in \{\text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$. Cells with grey background correspond to cases where the complexity is higher than for standard IAFs.</caption><thead><tr><th>σ</th><th>σ-IncPV*</th><th>σ-IncNV*</th><th>σ-PCA</th><th>σ-PSA</th><th>σ-NCA</th><th>σ-NSA</th></tr></thead><tbody><tr><td>ad</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>trivial</td><td>Π<sup>P</sup><sub>2-c</sub></td><td>trivial</td></tr><tr><td>co</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>NP-c</td><td>Π<sup>P</sup><sub>2-c</sub></td><td>coNP-c</td></tr><tr><td>pr</td><td>Σ<sup>P</sup><sub>2-c</sub></td><td>coNP-c</td><td>NP-c</td><td>Σ<sup>P</sup><sub>3-c</sub></td><td>Π<sup>P</sup><sub>2-c</sub></td><td>Π<sup>P</sup><sub>2-c</sub></td></tr><tr><td>gr</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>NP-c</td><td>coNP-c</td><td>coNP-c</td></tr><tr><td>st</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>Σ<sup>P</sup><sub>2-c</sub></td><td>Π<sup>P</sup><sub>2-c</sub></td><td>coNP-c</td></tr></tbody></table>

# 4 CIAFs and Extension Enforcement

This section focuses on extension enforcement [13, 14, 31], a major approach for argumentation dynamics [32]. We show that CIAFs can be useful for defining new extension enforcement operators.

## 4.1 Expansion-based Enforcement

Now we introduce the notions of AF expansion and extension enforcement [13, 14, 31].

**Definition 11.** Let $\mathcal{F} = \langle A, R \rangle$ be an AF. An expansion of $\mathcal{F}$ is an AF $\mathcal{F}' = \langle A \cup A', R \cup R' \rangle$ such that $A' \neq \emptyset$ and $A \cap A' = \emptyset$. An expansion is called normal if $\forall (a, b) \in R'$, $a \in A'$ or $b \in A'$. Moreover, a normal expansion is strong (respectively weak) if $\forall (a, b) \in R'$, $a \notin A$ (respectively $b \notin A$).

In words, an expansion adds some arguments, and possibly attacks. In the case of a normal expansion, the only added attacks concern at least one new arguments, i.e. the attacks between the former arguments are not modified. Finally, a normal expansion is strong (respectively weak) if it adds only strong (respectively weak) arguments, i.e. arguments that are not attacked by (respectively do not attack) the former arguments. The fact that $\mathcal{F}'$ is an expansion of $\mathcal{F}$ is denoted $\mathcal{F} \preceq_E \mathcal{F}'$ (and normal, strong, weak expansions are denoted by $\preceq_N, \preceq_S, \preceq_W$).

**Example 10.** Let $\mathcal{F} = \langle A, R \rangle$ be the AF depicted in Figure 9a. Figure 9b shows an expansion of $\mathcal{F}$: some argument f has been added, as well as some attacks (including an attack between the previous arguments a and c). Then, $\mathcal{F}_2$ from Figure 9c is a normal expansion of $\mathcal{F}$: there is no new attack between the previous arguments (but the new arguments can attack each other, attack the previous arguments, or be attacked by the previous arguments). Finally, $\mathcal{F}_3$ (Figure 9d) is a strong expansion of $\mathcal{F}$ (the new arguments cannot be attacked by the previous ones), while $\mathcal{F}_4$ (Figure 9e) is a weak expansion (the new arguments cannot attack the previous ones).

Expansions can be used to modify an AF such that a given set of arguments becomes (a part of) an extension in the new AF. This operation is called the (expansion-based) enforcement of the set of arguments.

**Definition 12.** Given $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, and a semantics $\sigma$, the AF $\mathcal{F}'$ is a non-strict normal (respectively strong, weak) $\sigma$-enforcement of $S$ in $\mathcal{F}$ if and only if $\mathcal{F}'$ is a normal (respectively strong, weak) expansion of $\mathcal{F}$, and $\exists E \in \sigma(\mathcal{F}')$ such that $S \subseteq E$.

Definition 12 considers non-strict enforcement, i.e. the desired set of arguments must be included in an extension of the new AF. Strict enforcement is defined in a similar manner, but the desired set of arguments must exactly correspond to an extension:
<figure><img src="image_11.png" /><figcaption>Figure 9: An AF and several possible expansions</figcaption></figure>

**Definition 13.** Given $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, and a semantics $\sigma$, the AF $\mathcal{F}'$ is a strict normal (respectively strong, weak) $\sigma$-enforcement of $S$ in $\mathcal{F}$ if and only if $\mathcal{F}'$ is a normal (respectively strong, weak) expansion of $\mathcal{F}$, and $S \in \sigma(\mathcal{F}')$.

Some (im)possibility results for these operations have been presented in [13]. However, some of these results rely on examples that do not seem realistic in argumentation-based dialogues, like the existence of one argument that could defeat all the arguments that the agent performing the enforcement wants to defeat. The following example is inspired by [13, Theorem 4].

**Example 11.** Let $\mathcal{F} = \langle A, R \rangle$ be the AF given in Figure 1. Recall that its stable extensions are $\text{st}(\mathcal{F}) = \{\{d, e\}, \{b, c, e\}\}$. Now let $S = \{a, d\}$ be the set of arguments to be enforced. We can define the (strong) expansion $\mathcal{F}' = \langle A \cup \{x\}, R \cup R' \rangle$ where $x$ is a fresh argument, and $R' = \{(x, y) \mid y \in A \setminus S\}$. $\mathcal{F}'$ is shown at Figure 10. With this new AF $\mathcal{F}'$, $\text{st}(\mathcal{F}') = \{\{x, a, d\}\}$, thus $\mathcal{F}'$ is a (non-strict) strong enforcement of $S$ in $\mathcal{F}$.

<figure><img src="image_12.png" /><figcaption>Figure 10: The expansion $\mathcal{F}'$ enforces $S = \{a, d\}$</figcaption></figure>

Example 11 illustrates the (theoretical) possibility to enforce any (conflict-free) set of arguments if strong (or normal) expansions are permitted. However, in an application context like dialogue (e.g. argument-based negotiation [33] or persuasion [34]), the existence of an “ultimate” attacker like $x$, that defeats all the undesired arguments, is unlikely.
<figure><img src="image_11.png" /><figcaption>Figure 9: An AF and several possible expansions</figcaption></figure>

**Definition 13.** Given $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, and a semantics $\sigma$, the AF $\mathcal{F}'$ is a strict normal (respectively strong, weak) $\sigma$-enforcement of $S$ in $\mathcal{F}$ if and only if $\mathcal{F}'$ is a normal (respectively strong, weak) expansion of $\mathcal{F}$, and $S \in \sigma(\mathcal{F}')$.

Some (im)possibility results for these operations have been presented in [13]. However, some of these results rely on examples that do not seem realistic in argumentation-based dialogues, like the existence of one argument that could defeat all the arguments that the agent performing the enforcement wants to defeat. The following example is inspired by [13, Theorem 4].

**Example 11.** Let $\mathcal{F} = \langle A, R \rangle$ be the AF given in Figure 1. Recall that its stable extensions are $\text{st}(\mathcal{F}) = \{\{d, e\}, \{b, c, e\}\}$. Now let $S = \{a, d\}$ be the set of arguments to be enforced. We can define the (strong) expansion $\mathcal{F}' = \langle A \cup \{x\}, R \cup R' \rangle$ where $x$ is a fresh argument, and $R' = \{(x, y) \mid y \in A \setminus S\}$. $\mathcal{F}'$ is shown at Figure 10. With this new AF $\mathcal{F}'$, $\text{st}(\mathcal{F}') = \{\{x, a, d\}\}$, thus $\mathcal{F}'$ is a (non-strict) strong enforcement of $S$ in $\mathcal{F}$.

<figure><img src="image_12.png" /><figcaption>Figure 10: The expansion $\mathcal{F}'$ enforces $S = \{a, d\}$</figcaption></figure>

Example 11 illustrates the (theoretical) possibility to enforce any (conflict-free) set of arguments if strong (or normal) expansions are permitted. However, in an application context like dialogue (e.g. argument-based negotiation [33] or persuasion [34]), the existence of an “ultimate” attacker like $x$, that defeats all the undesired arguments, is unlikely.
## 4.2 Non-Strict Enforcement as Possible Credulous Acceptability in CIAFs

To handle the problem highlighted by Example 11, we propose to take into account the set of arguments $\mathcal{A}$ and attacks $\mathcal{R}$ that an agent has at her disposal for participating to the debate. This means that we parameterize the expansion operation by the set of possible expanded AFs resulting of using some of the available arguments and attacks.

**Definition 14.** Given $\mathcal{F} = \langle A, R \rangle$ an AF, $\mathcal{A}$ a set of available arguments such that $A \cap \mathcal{A} = \emptyset$, and $\mathcal{R} \subseteq ((A \cup \mathcal{A}) \times (A \cup \mathcal{A})) \setminus (A \times A)$, we say that $\mathcal{F}' = \langle A', R' \rangle$ is an $\mathcal{A}-\mathcal{R}$-parameterized expansion of $\mathcal{F}$ (denoted by $\mathcal{F} \preceq_{\mathcal{A},\mathcal{R}} \mathcal{F}'$) if and only if

* $\mathcal{F} \preceq_{\mathcal{E}} \mathcal{F}'$,

* $A \subseteq A' \subseteq A \cup \mathcal{A}$,

* $R' = (R \cup \mathcal{R}) \cap (A' \times A')$.

We use $\preceq_{\mathcal{N}}^{\mathcal{A},\mathcal{R}}$ (respectively $\preceq_{\mathcal{S}}^{\mathcal{A},\mathcal{R}}$, $\preceq_{\mathcal{W}}^{\mathcal{A},\mathcal{R}}$) to denote $\mathcal{A}-\mathcal{R}$-parameterized normal (respectively strong, weak) expansions, i.e. $\mathcal{A}-\mathcal{R}$-parameterized expansions where $\mathcal{F}'$ is (additionally) normal (respectively strong, weak). This definition allows to take into account the arguments and attacks that are actually known by an agent that participates in a debate. We can show that a set of arguments that can be enforced with an arbitrary (strong) expansion (like in Example 11) may not be enforceable with parameterized expansions.

**Example 12.** We continue Example 11. Suppose that the available arguments and attacks are $\mathcal{A} = \{f,g\}$ and $\mathcal{R} = \{(f,c), (g,b)\}$. Figure 11 depicts the agent's possible actions: say nothing (i.e. keep the initial AF, Fig. 11a), say “f attacks c” (Fig 11b), say “g attacks b” (Fig 11c), or both (Fig. 11d). In all the possible cases, $S = \{a,d\}$ is not enforced, since a is never defended against e.

<figure><img src="image_13.png" /><figcaption>Figure 11: The agent's possible actions</figcaption></figure>

What we call here the “possible actions” of the agent can actually be seen as the set of completions of a CIAF, and the possibility of enforcing a set of arguments corresponds to the credulous acceptance of this set with respect to the CIAF.
## 4.2 Non-Strict Enforcement as Possible Credulous Acceptability in CIAFs

To handle the problem highlighted by Example 11, we propose to take into account the set of arguments $\mathcal{A}$ and attacks $\mathcal{R}$ that an agent has at her disposal for participating to the debate. This means that we parameterize the expansion operation by the set of possible expanded AFs resulting of using some of the available arguments and attacks.

**Definition 14.** Given $\mathcal{F} = \langle A, R \rangle$ an AF, $\mathcal{A}$ a set of available arguments such that $A \cap \mathcal{A} = \emptyset$, and $\mathcal{R} \subseteq ((A \cup \mathcal{A}) \times (A \cup \mathcal{A})) \setminus (A \times A)$, we say that $\mathcal{F}' = \langle A', R' \rangle$ is an $\mathcal{A}-\mathcal{R}$-parameterized expansion of $\mathcal{F}$ (denoted by $\mathcal{F} \preceq_{\mathcal{A},\mathcal{R}} \mathcal{F}'$) if and only if

* $\mathcal{F} \preceq_{\mathcal{E}} \mathcal{F}'$,

* $A \subseteq A' \subseteq A \cup \mathcal{A}$,

* $R' = (R \cup \mathcal{R}) \cap (A' \times A')$.

We use $\preceq_{\mathcal{N}}^{\mathcal{A},\mathcal{R}}$ (respectively $\preceq_{\mathcal{S}}^{\mathcal{A},\mathcal{R}}$, $\preceq_{\mathcal{W}}^{\mathcal{A},\mathcal{R}}$) to denote $\mathcal{A}-\mathcal{R}$-parameterized normal (respectively strong, weak) expansions, i.e. $\mathcal{A}-\mathcal{R}$-parameterized expansions where $\mathcal{F}'$ is (additionally) normal (respectively strong, weak). This definition allows to take into account the arguments and attacks that are actually known by an agent that participates in a debate. We can show that a set of arguments that can be enforced with an arbitrary (strong) expansion (like in Example 11) may not be enforceable with parameterized expansions.

**Example 12.** We continue Example 11. Suppose that the available arguments and attacks are $\mathcal{A} = \{f,g\}$ and $\mathcal{R} = \{(f,c), (g,b)\}$. Figure 11 depicts the agent's possible actions: say nothing (i.e. keep the initial AF, Fig. 11a), say “f attacks c” (Fig 11b), say “g attacks b” (Fig 11c), or both (Fig. 11d). In all the possible cases, $S = \{a,d\}$ is not enforced, since a is never defended against e.

<figure><img src="image_13.png" /><figcaption>Figure 11: The agent's possible actions</figcaption></figure>

What we call here the “possible actions” of the agent can actually be seen as the set of completions of a CIAF, and the possibility of enforcing a set of arguments corresponds to the credulous acceptance of this set with respect to the CIAF.
**Definition 15.** Given $\mathcal{F}$ an AF, $\mathcal{A}$ a set of arguments, $\mathcal{R}$ a set of attacks, and $X \in \{E, N, S, W\}$ denoting the type of expansion, we define $\mathcal{F} = \{\mathcal{F}\} \cup \{\mathcal{F}' \mid \mathcal{F} \preceq_X^{\mathcal{A}, \mathcal{R}} \mathcal{F}'\}$. Then, $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$ is a CIAF such that $\text{comp}(C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}) = \mathcal{F}$.

The existence of $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$ is guaranteed by Proposition 1. The construction illustrated by Example 9 provides a suitable $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$. However, other CIAFs can be defined, for instance it seems natural that all the arguments and attacks from the initial $\mathcal{F}$ can be defined as certain elements. Proposition 10 states that CIAFs can be used as a computational tool for determining the possibility of enforcement. Before proving this result, we need to generalize the decision problem $\sigma$-PCA to take into account a set of arguments:

**$\sigma$-SPCA** Given a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ and a set of arguments $S \subseteq A$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{C})$ such that $S \subseteq E$ for some $E \in \sigma(\mathcal{F})$?

This set-based version of possible credulous acceptability is obviously NP-complete as well for usual semantics: NP-hardness is deduced from the NP-hardness of $\sigma$-PCA, and NP-membership is deduced thanks to the classical non-deterministic guess and check algorithm that was used to prove other membership results (guess a completion and a superset $S'$ of $S$, check whether the completion satisfies the constraint, and check whether $S'$ is an extension). Now we show that non-strict enforcement can be reduced to $\sigma$-SPCA.

**Proposition 10.** Given an AF $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, $X \in \{E, N, S, W\}$, A a set of arguments and $\mathcal{R}$ a set of attacks, and a semantics $\sigma$, $S$ can be non-strictly $\sigma$-enforced in $\mathcal{F}$ by means of a $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion if and only if $S$ is possibly credulously accepted in $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$ with respect to $\sigma$.

*Proof.* The result is a consequence of the definitions: $S$ can be enforced if and only if one of the “possible actions” yields an AF $\mathcal{F}'$ such that $S \subseteq S'$ for some $S' \in \sigma(\mathcal{F}')$. This is equivalent to saying that $S$ is included in some $\sigma$-extension of some completion of $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$. $\square$

Now we prove that determining whether a set of arguments can be enforced with a $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion is a NP-complete problem under various classical semantics.

**Proposition 11.** Given an AF $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, $X \in \{E, N, S, W\}$, A a set of arguments and $\mathcal{R}$ a set of attacks, and a semantics $\sigma$, determining whether $S$ can be non-strictly $\sigma$-enforced in $\mathcal{F}$ by means of a $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion is NP-complete under $\sigma \in \{\text{co}, \text{st}, \text{pr}, \text{ad}\}$.

*Proof.* For proving the lower bound, we consider the problem of credulous acceptability in AFs. This problem is NP-complete under $\sigma \in \{\text{co}, \text{st}, \text{pr}, \text{ad}\}$ [20]. Given an instance $(\mathcal{F} = \langle A, R \rangle, a \in A)$ of this problem, we build an instance of our problem by defining $S = \{a\}$, $\mathcal{A} = \emptyset$ and $\mathcal{R} = \emptyset$. For any $X \in \{E, N, S, W\}$, the only $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion of $\mathcal{F}$ is $\mathcal{F}$ itself. This means that $a$ is credulously acceptable in $\mathcal{F}$ with respect to the semantics $\sigma$ if and only if $S$ can be enforced. This concludes the proof that the problem is NP-hard.

Now let us prove that the problem belongs to NP. First, we consider the following non-deterministic algorithm for $\sigma \in \{\text{co}, \text{st}, \text{ad}\}$:

1. Non-deterministically guess a set of arguments $A' \subseteq \mathcal{A}$, a set of attacks $R' \subseteq \mathcal{R}$, and a set of arguments $S'$ with $S \subseteq S' \subseteq A \cup A'$;

2. Compute $\mathcal{F}' = \langle A \cup A', R \cup R' \rangle$, and check (in polynomial time) whether $S' \in \sigma(\mathcal{F}')$.
**Definition 15.** Given $\mathcal{F}$ an AF, $\mathcal{A}$ a set of arguments, $\mathcal{R}$ a set of attacks, and $X \in \{E, N, S, W\}$ denoting the type of expansion, we define $\mathcal{F} = \{\mathcal{F}\} \cup \{\mathcal{F}' \mid \mathcal{F} \preceq_X^{\mathcal{A}, \mathcal{R}} \mathcal{F}'\}$. Then, $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$ is a CIAF such that $\text{comp}(C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}) = \mathcal{F}$.

The existence of $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$ is guaranteed by Proposition 1. The construction illustrated by Example 9 provides a suitable $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$. However, other CIAFs can be defined, for instance it seems natural that all the arguments and attacks from the initial $\mathcal{F}$ can be defined as certain elements. Proposition 10 states that CIAFs can be used as a computational tool for determining the possibility of enforcement. Before proving this result, we need to generalize the decision problem $\sigma$-PCA to take into account a set of arguments:

**$\sigma$-SPCA** Given a CIAF $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ and a set of arguments $S \subseteq A$, is there $\mathcal{F} = \langle A', R' \rangle \in \text{comp}(\mathcal{C})$ such that $S \subseteq E$ for some $E \in \sigma(\mathcal{F})$?

This set-based version of possible credulous acceptability is obviously NP-complete as well for usual semantics: NP-hardness is deduced from the NP-hardness of $\sigma$-PCA, and NP-membership is deduced thanks to the classical non-deterministic guess and check algorithm that was used to prove other membership results (guess a completion and a superset $S'$ of $S$, check whether the completion satisfies the constraint, and check whether $S'$ is an extension). Now we show that non-strict enforcement can be reduced to $\sigma$-SPCA.

**Proposition 10.** Given an AF $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, $X \in \{E, N, S, W\}$, $\mathcal{A}$ a set of arguments and $\mathcal{R}$ a set of attacks, and a semantics $\sigma$, $S$ can be non-strictly $\sigma$-enforced in $\mathcal{F}$ by means of a $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion if and only if $S$ is possibly credulously accepted in $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$ with respect to $\sigma$.

*Proof.* The result is a consequence of the definitions: $S$ can be enforced if and only if one of the “possible actions” yields an AF $\mathcal{F}'$ such that $S \subseteq S'$ for some $S' \in \sigma(\mathcal{F}')$. This is equivalent to saying that $S$ is included in some $\sigma$-extension of some completion of $C_{\mathcal{F},X}^{\mathcal{A},\mathcal{R}}$. $\square$

Now we prove that determining whether a set of arguments can be enforced with a $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion is a NP-complete problem under various classical semantics.

**Proposition 11.** Given an AF $\mathcal{F} = \langle A, R \rangle$, a set of arguments $S \subseteq A$, $X \in \{E, N, S, W\}$, $\mathcal{A}$ a set of arguments and $\mathcal{R}$ a set of attacks, and a semantics $\sigma$, determining whether $S$ can be non-strictly $\sigma$-enforced in $\mathcal{F}$ by means of a $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion is NP-complete under $\sigma \in \{\text{co}, \text{st}, \text{pr}, \text{ad}\}$.

*Proof.* For proving the lower bound, we consider the problem of credulous acceptability in AFs. This problem is NP-complete under $\sigma \in \{\text{co}, \text{st}, \text{pr}, \text{ad}\}$ [20]. Given an instance $(\mathcal{F} = \langle A, R \rangle, a \in A)$ of this problem, we build an instance of our problem by defining $S = \{a\}$, $\mathcal{A} = \emptyset$ and $\mathcal{R} = \emptyset$. For any $X \in \{E, N, S, W\}$, the only $\mathcal{A}-\mathcal{R}$-parameterized $X$-expansion of $\mathcal{F}$ is $\mathcal{F}$ itself. This means that $a$ is credulously acceptable in $\mathcal{F}$ with respect to the semantics $\sigma$ if and only if $S$ can be enforced. This concludes the proof that the problem is NP-hard.

Now let us prove that the problem belongs to NP. First, we consider the following non-deterministic algorithm for $\sigma \in \{\text{co}, \text{st}, \text{ad}\}$:

1. Non-deterministically guess a set of arguments $A' \subseteq \mathcal{A}$, a set of attacks $R' \subseteq \mathcal{R}$, and a set of arguments $S'$ with $S \subseteq S' \subseteq A \cup A'$;

2. Compute $\mathcal{F}' = \langle A \cup A', R \cup R' \rangle$, and check (in polynomial time) whether $S' \in \sigma(\mathcal{F}')$.
A positive answer to the test at step (2) proves that the considered instance of the problem is a "YES" instance. This means that this non-deterministic algorithm solves the problem in polynomial time, thus the problem is in NP for $\sigma \in \{\text{co}, \text{st}, \text{ad}\}$. Finally, for $\sigma = \text{pr}$, notice that the algorithm for ad works as well, since a set of arguments is included in a preferred extension if and only if it is included in an admissible set. $\square$

Intuitively, we could adapt our approach to strict enforcement (i.e. the set $S$ must be *exactly* an extension of the new AF), using the possible verification of the set $S$ (i.e. $\sigma$-IncPV*). However, strict enforcement based on the addition of new arguments is rarely possible: in most cases, either the set $S$ is already an extension (and thus there is nothing to do), or it will be included in an extension where the new arguments also appear. Strict enforcement is mainly achievable through other techniques, where the attacks between existing arguments can be modified [35, 36].

# 5 Relative Expressiveness of CIAFs vs RIAFs

In a recent work [17], we have studied another generalization of Incomplete AFs. In this section, we compare the expressiveness of this formalism, called Rich IAFs (RIAFs), with the expressiveness of CIAFs. We show that RIAFs are strictly more expressive than IAFs, but strictly less than CIAFs.

The idea behind the definition of RIAFs is to add another kind of (uncertain) attack relation to IAFs, $\leftrightarrow^?$, such that $(a, b) \in \leftrightarrow^?$ means that there (certainly) is a conflict between $a$ and $b$, but there is some uncertainty on the direction of the attack: either $a$ attacks $b$, or $b$ attacks $a$, or both at the same time. This concept was first defined in the context of Control AFs [37]. Formally,

**Definition 16 (Rich IAF).** A Rich Incomplete Argumentation Framework (RIAF) is a tuple $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$, where $A$ and $A^?$ are disjoint sets of arguments, and $R, R^?, \leftrightarrow^? \subseteq (A \cup A^?) \times (A \cup A^?)$ are disjoint sets of attacks such that $\leftrightarrow^?$ is symmetric.

**Example 13.** Let $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$ be the RIAF depicted at Figure 12, where $A = \{a, b, c\}$, $A^? = \{d\}$, $R = \{(d, b)\}$, $R^? = \{c, b\}$ and $\leftrightarrow^? = \{(a, b), (b, a)\}$. While $A, A^?, R$ and $R^?$ have the same

<figure><img src="image_14.png" /><figcaption>Figure 12: An example of RIAF</figcaption></figure>

meaning as in IAFs, the relation $\leftrightarrow^?$ (represented by the two-headed dashed arrow) means that there is a conflict between $a$ and $b$, but we are not sure of the direction of this conflict.

The notion of completion is adapted to RIAFs as follows.

**Definition 17 (Completions of RIAFs).** Given $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$, a completion of $\mathcal{R}$ is $\mathcal{F} = \langle A', R' \rangle$, such that

* $A \subseteq A' \subseteq A \cup A^?;$

* $R_{|A'} \subseteq R' \subseteq (R \cup R^? \cup \leftrightarrow^?)_{|A'};$

* if $(a, b) \in \leftrightarrow^?$, then $(a, b) \in R'$ or $(b, a) \in R'$ (or both);

where $R_{|A'} = R \cap (A' \times A')$ (and similarly for $(R \cup R^? \cup \leftrightarrow^?)$).
A positive answer to the test at step (2) proves that the considered instance of the problem is a "YES" instance. This means that this non-deterministic algorithm solves the problem in polynomial time, thus the problem is in NP for $\sigma \in \{\text{co}, \text{st}, \text{ad}\}$. Finally, for $\sigma = \text{pr}$, notice that the algorithm for ad works as well, since a set of arguments is included in a preferred extension if and only if it is included in an admissible set. $\square$

Intuitively, we could adapt our approach to strict enforcement (i.e. the set $S$ must be *exactly* an extension of the new AF), using the possible verification of the set $S$ (i.e. $\sigma$-IncPV*). However, strict enforcement based on the addition of new arguments is rarely possible: in most cases, either the set $S$ is already an extension (and thus there is nothing to do), or it will be included in an extension where the new arguments also appear. Strict enforcement is mainly achievable through other techniques, where the attacks between existing arguments can be modified [35, 36].

# 5 Relative Expressiveness of CIAFs vs RIAFs

In a recent work [17], we have studied another generalization of Incomplete AFs. In this section, we compare the expressiveness of this formalism, called Rich IAFs (RIAFs), with the expressiveness of CIAFs. We show that RIAFs are strictly more expressive than IAFs, but strictly less than CIAFs.

The idea behind the definition of RIAFs is to add another kind of (uncertain) attack relation to IAFs, $\leftrightarrow^?$, such that $(a, b) \in \leftrightarrow^?$ means that there (certainly) is a conflict between $a$ and $b$, but there is some uncertainty on the direction of the attack: either $a$ attacks $b$, or $b$ attacks $a$, or both at the same time. This concept was first defined in the context of Control AFs [37]. Formally,

**Definition 16 (Rich IAF).** A Rich Incomplete Argumentation Framework (RIAF) is a tuple $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$, where $A$ and $A^?$ are disjoint sets of arguments, and $R, R^?, \leftrightarrow^? \subseteq (A \cup A^?) \times (A \cup A^?)$ are disjoint sets of attacks such that $\leftrightarrow^?$ is symmetric.

**Example 13.** Let $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$ be the RIAF depicted at Figure 12, where $A = \{a, b, c\}$, $A^? = \{d\}$, $R = \{(d, b)\}$, $R^? = \{c, b\}$ and $\leftrightarrow^? = \{(a, b), (b, a)\}$. While $A, A^?, R$ and $R^?$ have the same

<figure><img src="image_14.png" /><figcaption>Figure 12: An example of RIAF</figcaption></figure>

meaning as in IAFs, the relation $\leftrightarrow^?$ (represented by the two-headed dashed arrow) means that there is a conflict between $a$ and $b$, but we are not sure of the direction of this conflict.

The notion of completion is adapted to RIAFs as follows.

**Definition 17 (Completions of RIAFs).** Given $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$, a completion of $\mathcal{R}$ is $\mathcal{F} = \langle A', R' \rangle$, such that

* $A \subseteq A' \subseteq A \cup A^?;$

* $R_{|A'} \subseteq R' \subseteq (R \cup R^? \cup \leftrightarrow^?)_{|A'};$

* if $(a, b) \in \leftrightarrow^?$, then $(a, b) \in R'$ or $(b, a) \in R'$ (or both);

where $R_{|A'} = R \cap (A' \times A')$ (and similarly for $(R \cup R^? \cup \leftrightarrow^?)$).
<figure><img src="image_15.png" /><figcaption>Figure 13: The completions of $\mathcal{R}$ from Figure 12</figcaption></figure>

**Example 14.** The completions of $\mathcal{R}$ from Figure 12 are given in Figure 13.

It is proven in [17, Proposition 2] that RIAFs are strictly more expressive than IAFs. Trivially, any IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ is a particular RIAF with $\leftrightarrow^? = \emptyset$, while the converse is not true: there are some RIAFs that cannot be “translated” into an IAF with the same set of completions. This increase of expressiveness does not come at the price of a complexity shift.

**Proposition 12** ([17]). • For any IAF $\mathcal{I}$, there exists a RIAF $\mathcal{R}$ such that $\mathrm{comp}(\mathcal{I}) = \mathrm{comp}(\mathcal{R})$.

• There exists a RIAF $\mathcal{R}$ such that there is no IAF $\mathcal{I}$ with $\mathrm{comp}(\mathcal{I}) = \mathrm{comp}(\mathcal{R})$.

*Proof*. The first item is straightforward: any IAF is a RIAF with $\leftrightarrow^? = \emptyset$. For the second item, consider $\mathcal{R} = \langle \{a, b\}, \emptyset, \emptyset, \emptyset, \{(a, b), (b, a)\} \rangle$. This RIAF and its three completions $\{\mathcal{F}_1, \mathcal{F}_2, \mathcal{F}_3\}$ are given at Figure 14.

<figure><img src="image_16.png" /><figcaption>Figure 14: A RIAF and its Completions</figcaption></figure>

Now, let us prove that there is no IAF with the same set of completions. Reasoning towards a contradiction, suppose that such a IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ exists. Since all the completions have the same set of arguments $\{a, b\}$, there cannot be uncertain argument, i.e. $A^? = \emptyset$.

Let us now consider the different options for $R$ and $R^?$. If $(a, b) \in R$ (respectively $(b, a) \in R$), then there is an attack from $a$ to $b$ (respectively from $b$ to $a$) in every completion. This is not the case. Similarly, there cannot be any self attack in $R$ (since there is no such attack in any completion). Thus $R = \emptyset$.

In the case where only $(a, b)$ (respectively $(b, a)$) belongs to $R^?$, then the completions with $(b, a)$ (respectively $(a, b)$) do not belong to $\mathrm{comp}(\mathcal{I})$. On the contrary, if both $(a, b)$ and $(b, a)$ belong to $R^?$, then a fourth completion where there is no attack between $a$ and $b$ belongs to $\mathrm{comp}(\mathcal{I})$. Of course, self-attacks in $R^?$ are not possible, since they would yield additional completions (with the same self-attack appearing in them).

So we can conclude that $\mathcal{I}$ does not exist.

<figure><img src="image_17.png" /></figure>
<figure><img src="image_15.png" /><figcaption>Figure 13: The completions of $\mathcal{R}$ from Figure 12</figcaption></figure>

**Example 14.** The completions of $\mathcal{R}$ from Figure 12 are given in Figure 13.

It is proven in [17, Proposition 2] that RIAFs are strictly more expressive than IAFs. Trivially, any IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ is a particular RIAF with $\leftrightarrow^? = \emptyset$, while the converse is not true: there are some RIAFs that cannot be “translated” into an IAF with the same set of completions. This increase of expressiveness does not come at the price of a complexity shift.

**Proposition 12** ([17]). • For any IAF $\mathcal{I}$, there exists a RIAF $\mathcal{R}$ such that $\mathrm{comp}(\mathcal{I}) = \mathrm{comp}(\mathcal{R})$.

• There exists a RIAF $\mathcal{R}$ such that there is no IAF $\mathcal{I}$ with $\mathrm{comp}(\mathcal{I}) = \mathrm{comp}(\mathcal{R})$.

*Proof*. The first item is straightforward: any IAF is a RIAF with $\leftrightarrow^? = \emptyset$. For the second item, consider $\mathcal{R} = \langle \{a, b\}, \emptyset, \emptyset, \emptyset, \{(a, b), (b, a)\} \rangle$. This RIAF and its three completions $\{\mathcal{F}_1, \mathcal{F}_2, \mathcal{F}_3\}$ are given at Figure 14.

<figure><img src="image_16.png" /><figcaption>Figure 14: A RIAF and its Completions</figcaption></figure>

Now, let us prove that there is no IAF with the same set of completions. Reasoning towards a contradiction, suppose that such a IAF $\mathcal{I} = \langle A, A^?, R, R^? \rangle$ exists. Since all the completions have the same set of arguments $\{a, b\}$, there cannot be uncertain argument, i.e. $A^? = \emptyset$.

Let us now consider the different options for $R$ and $R^?$. If $(a, b) \in R$ (respectively $(b, a) \in R$), then there is an attack from $a$ to $b$ (respectively from $b$ to $a$) in every completion. This is not the case. Similarly, there cannot be any self attack in $R$ (since there is no such attack in any completion). Thus $R = \emptyset$.

In the case where only $(a, b)$ (respectively $(b, a)$) belongs to $R^?$, then the completions with $(b, a)$ (respectively $(a, b)$) do not belong to $\mathrm{comp}(\mathcal{I})$. On the contrary, if both $(a, b)$ and $(b, a)$ belong to $R^?$, then a fourth completion where there is no attack between $a$ and $b$ belongs to $\mathrm{comp}(\mathcal{I})$. Of course, self-attacks in $R^?$ are not possible, since they would yield additional completions (with the same self-attack appearing in them).

So we can conclude that $\mathcal{I}$ does not exist. □
Now, we prove that CIAFs are more expressive than RIAFs.<fnref n="5" />

**Proposition 13.** For any RIAF $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$, there is a CIAF $\mathcal{C}$ such that $\mathrm{comp}(\mathcal{C}) = \mathrm{comp}(\mathcal{R})$. The converse does not hold.

*Proof.* The first part is a corollary of Proposition 1. Let us thus prove that not all CIAFs can be expressed as RIAFs. Consider $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ depicted at Figure 15a, where $\phi = \arg_a \oplus \arg_b$. Its completions are $\mathcal{F}_1$ (Figure 15b) and $\mathcal{F}_2$ (Figure 15c). Suppose the existence of $\mathcal{R} = \langle A, A^?, R, R^?_R, \leftrightarrow^? \rangle$ with the same set of completions. If $(a, b)$, $(b, a) \in R^?_R$, then there are four completions (the one with none of the attacks, and the one with both attacks, must be considered as well). If $(a, b)$, $(b, a) \in \leftrightarrow^?$, then there are three completions (only the one without any attack is forbidden). There is no such $\mathcal{R}$ with $\mathrm{comp}(\mathcal{R}) = \mathrm{comp}(\mathcal{C})$. $\square$

<figure><img src="image_18.png" /><figcaption>Figure 15: The CIAF $\mathcal{C}$ and its completions</figcaption></figure>

# 6 Related Work

## 6.1 Other Work on CIAFs

Interestingly, other authors have investigated Constrained Incomplete AFs (or subclasses thereof) independently of the original conference paper on CIAFs [15, 16]. Let us briefly discuss these related contributions. We start with [38, 39]. The first contribution of this paper is the encoding of reasoning tasks of Incomplete AFs and Control AFs [37, 40, 41] in dynamic logic of propositional assignments (DL-PA) [42]. The authors compare the expressiveness of these frameworks, and propose a maximally expressive framework that they also call Constrained IAF. However, contrary to our approach, they remove the graphical part and only keep the propositional formula which characterizes the set of authorized completions. We believe that our framework offers an advantage regarding the syntax of the formula, which can be simpler with our formalism. Indeed, we express the certain information about (non-)existence of arguments and attacks in the graph part of the CIAF, which is more natural in the abstract argumentation literature. Only the constraints on the uncertain elements need to appear in the formula. However, from the point of view of expressiveness, both frameworks are equivalent: a CIAF as defined here can be translated into a CIAF as defined by [38, 39], by simply adding to the logical formula some information about the arguments and attacks that certainly exist (or certainly do not exist); and the other way around a CIAF as defined by [38, 39] can be seen as a CIAF as defined here, we just need to consider that all arguments (and all possible attacks between them) are uncertain, and then the constraint remains the same. This means that both approaches can be used to represent the result of AF revision or merging, or for reasoning with the enforcement scenario mentioned before.

Then, [26] study what they call dependencies in Argument-Incomplete AFs (recall that these are IAFs with only incomplete knowledge regarding arguments, i.e. $R^? = \emptyset$). These dependencies are expressed as formulas of a simple nature (e.g. disjunctions or implications), and they are obviously special cases of our propositional constraints. They study the complexity of the decision problems

<footnote n="5">⁵The same question has been recently studied independently by [38].</footnote>
Now, we prove that CIAFs are more expressive than RIAFs.<fnref n="5" />

**Proposition 13.** For any RIAF $\mathcal{R} = \langle A, A^?, R, R^?, \leftrightarrow^? \rangle$, there is a CIAF $\mathcal{C}$ such that $\mathrm{comp}(\mathcal{C}) = \mathrm{comp}(\mathcal{R})$. The converse does not hold.

*Proof.* The first part is a corollary of Proposition 1. Let us thus prove that not all CIAFs can be expressed as RIAFs. Consider $\mathcal{C} = \langle A, A^?, R, R^?, \phi \rangle$ depicted at Figure 15a, where $\phi = \arg_a \oplus \arg_b$. Its completions are $\mathcal{F}_1$ (Figure 15b) and $\mathcal{F}_2$ (Figure 15c). Suppose the existence of $\mathcal{R} = \langle A, A^?, R, R_R^? \leftrightarrow^? \rangle$ with the same set of completions. If $(a, b)$, $(b, a) \in R_R^?$, then there are four completions (the one with none of the attacks, and the one with both attacks, must be considered as well). If $(a, b)$, $(b, a) \in \leftrightarrow^?$, then there are three completions (only the one without any attack is forbidden). There is no such $\mathcal{R}$ with $\mathrm{comp}(\mathcal{R}) = \mathrm{comp}(\mathcal{C})$. $\square$

<figure><img src="image_17.png" /><figcaption>Figure 15: The CIAF $\mathcal{C}$ and its completions</figcaption></figure>

# 6 Related Work

## 6.1 Other Work on CIAFs

Interestingly, other authors have investigated Constrained Incomplete AFs (or subclasses thereof) independently of the original conference paper on CIAFs [15, 16]. Let us briefly discuss these related contributions. We start with [38, 39]. The first contribution of this paper is the encoding of reasoning tasks of Incomplete AFs and Control AFs [37, 40, 41] in dynamic logic of propositional assignments (DL-PA) [42]. The authors compare the expressiveness of these frameworks, and propose a maximally expressive framework that they also call Constrained IAF. However, contrary to our approach, they remove the graphical part and only keep the propositional formula which characterizes the set of authorized completions. We believe that our framework offers an advantage regarding the syntax of the formula, which can be simpler with our formalism. Indeed, we express the certain information about (non-)existence of arguments and attacks in the graph part of the CIAF, which is more natural in the abstract argumentation literature. Only the constraints on the uncertain elements need to appear in the formula. However, from the point of view of expressiveness, both frameworks are equivalent: a CIAF as defined here can be translated into a CIAF as defined by [38, 39], by simply adding to the logical formula some information about the arguments and attacks that certainly exist (or certainly do not exist); and the other way around a CIAF as defined by [38, 39] can be seen as a CIAF as defined here, we just need to consider that all arguments (and all possible attacks between them) are uncertain, and then the constraint remains the same. This means that both approaches can be used to represent the result of AF revision or merging, or for reasoning with the enforcement scenario mentioned before.

Then, [26] study what they call dependencies in Argument-Incomplete AFs (recall that these are IAFs with only incomplete knowledge regarding arguments, i.e. $R^? = \emptyset$). These dependencies are expressed as formulas of a simple nature (e.g. disjunctions or implications), and they are obviously special cases of our propositional constraints. They study the complexity of the decision problems

<footnote n="5">⁵The same question has been recently studied independently by [38].</footnote>
DSAT and PDVER, respectively deciding whether the set of dependencies is satisfiable and deciding whether a set of arguments is an extension of some completion which satisfies the dependencies (the equivalent of IncPV*). The complexity is established with respect to some categories of dependencies (e.g. only disjunctions, only implications, or some combinations of the various kinds of dependencies). Their most general case is then a special case of IncPV* studied in this paper. A similar study was then conducted about Attack-Incomplete AFs (i.e. IAFs with $A^2 = \emptyset$) [27].

## 6.2 Other Related Work

We have already mentioned the main results on Incomplete Argumentation Frameworks. The interested reader can find a recent overview in [43]. Besides IAFs, our contribution is related to other previous works. Using propositional formulas as constraints in an argumentation framework has been originally proposed in [25], which defines Constrained Argumentation Frameworks. In this setting, the propositional formula is a constraint on arguments that is used for selecting the best extensions. Intuitively, we use here the constraint in CIAFs in a similar way, but for selecting completions of an IAF instead of selecting the extensions of a (classical) AF.

We have shown how to represent any set of extensions with a single CIAF. The question of representing sets of extensions has already arisen in classical AFs. This corresponds to the notion of realizability in the literature [21, 12], i.e. given a set of extensions *E* and a semantics *σ*, is there an AF *F* such that $σ(F) = E$. Existing results show that it is not possible in general for most classical semantics. The non-realizability of some sets of extensions is the reason why some operations (like belief revision or merging) cannot be easily adapted to AFs, as mentioned in the introduction. With Proposition 2, we continue this line of research, by proving the realizability of any set of extensions by means of CIAFs. Another recent work has focused on the issue of realizability, proposing logical encodings for the (newly introduced) problem of *k*-m-realizability, i.e. determining whether a set of extensions can be realized by a set of *m* AFs using *k* auxiliary arguments (those which do not appear in any of the given extensions) [44]. This work is clearly related to the contributions described in this paper since it proposes a way to compute the result in the AF revision or merging scenario. The set of AFs provided by this approach could be used to provide a “better” CIAF than the one which is built in the proof of Proposition 2, where one completion corresponds to one extension. A deeper study of the connection between the present paper and [44] is kept for future work.

Regarding extension enforcement, it has been proven that (non-strict) enforcement is NP-complete [36] for another type of authorized change: argument-fixed enforcement [35], where the set of arguments cannot be modified, but all the attacks (or non-attacks) can be questioned. Although this is out of the scope of this paper, we believe that this kind of enforcement can also be captured by the CIAF setting, which will allow to define a parameterized version of argument-fixed enforcement. The parameters *A* and *R* are also reminiscent of the “control part” of Control AFs [37, 40, 41], that allows to enforce a set of arguments in presence of uncertainty.

Constraints that express dependencies between arguments of an ADF [45] in a dynamic context have been studied in [46]. While there is some similarity between these constraints and the ones defined here, both studies have different purposes. Indeed, [46] does not focus on uncertain environment as we do here, but only on dynamic scenarios. Connections with enforcement based on *A*-*R*-parameterized expansions will be studied.

Finally, [47] proposes the notion of abstract argumentation framework with *attack points*. These attack points are the “weaknesses” of an arguments, that could be source of contradiction coming from other arguments. An example of an attack point would be an assumption in an Assumption-based Argumentation (ABA) framework [48]. The possible expansions of an AF with attack points are then constrained by the attack points: for instance, if the argument *a* has no attack point, then
DSAT and PDVER, respectively deciding whether the set of dependencies is satisfiable and deciding whether a set of arguments is an extension of some completion which satisfies the dependencies (the equivalent of IncPV*). The complexity is established with respect to some categories of dependencies (e.g. only disjunctions, only implications, or some combinations of the various kinds of dependencies). Their most general case is then a special case of IncPV* studied in this paper. A similar study was then conducted about Attack-Incomplete AFs (i.e. IAFs with $A^2 = \emptyset$) [27].

## 6.2 Other Related Work

We have already mentioned the main results on Incomplete Argumentation Frameworks. The interested reader can find a recent overview in [43]. Besides IAFs, our contribution is related to other previous works. Using propositional formulas as constraints in an argumentation framework has been originally proposed in [25], which defines Constrained Argumentation Frameworks. In this setting, the propositional formula is a constraint on arguments that is used for selecting the best extensions. Intuitively, we use here the constraint in CIAFs in a similar way, but for selecting completions of an IAF instead of selecting the extensions of a (classical) AF.

We have shown how to represent any set of extensions with a single CIAF. The question of representing sets of extensions has already arisen in classical AFs. This corresponds to the notion of realizability in the literature [21, 12], i.e. given a set of extensions *E* and a semantics *σ*, is there an AF *F* such that $σ(F) = E$. Existing results show that it is not possible in general for most classical semantics. The non-realizability of some sets of extensions is the reason why some operations (like belief revision or merging) cannot be easily adapted to AFs, as mentioned in the introduction. With Proposition 2, we continue this line of research, by proving the realizability of any set of extensions by means of CIAFs. Another recent work has focused on the issue of realizability, proposing logical encodings for the (newly introduced) problem of *k*-m-realizability, i.e. determining whether a set of extensions can be realized by a set of *m* AFs using *k* auxiliary arguments (those which do not appear in any of the given extensions) [44]. This work is clearly related to the contributions described in this paper since it proposes a way to compute the result in the AF revision or merging scenario. The set of AFs provided by this approach could be used to provide a “better” CIAF than the one which is built in the proof of Proposition 2, where one completion corresponds to one extension. A deeper study of the connection between the present paper and [44] is kept for future work.

Regarding extension enforcement, it has been proven that (non-strict) enforcement is NP-complete [36] for another type of authorized change: argument-fixed enforcement [35], where the set of arguments cannot be modified, but all the attacks (or non-attacks) can be questioned. Although this is out of the scope of this paper, we believe that this kind of enforcement can also be captured by the CIAF setting, which will allow to define a parameterized version of argument-fixed enforcement. The parameters *A* and *R* are also reminiscent of the “control part” of Control AFs [37, 40, 41], that allows to enforce a set of arguments in presence of uncertainty.

Constraints that express dependencies between arguments of an ADF [45] in a dynamic context have been studied in [46]. While there is some similarity between these constraints and the ones defined here, both studies have different purposes. Indeed, [46] does not focus on uncertain environment as we do here, but only on dynamic scenarios. Connections with enforcement based on *A*-*R*-parameterized expansions will be studied.

Finally, [47] proposes the notion of abstract argumentation framework with *attack points*. These attack points are the “weaknesses” of an arguments, that could be source of contradiction coming from other arguments. An example of an attack point would be an assumption in an Assumption-based Argumentation (ABA) framework [48]. The possible expansions of an AF with attack points are then constrained by the attack points: for instance, if the argument *a* has no attack point, then
no expansion of the AF can contain a new argument that attacks *a*. The notion of allowed expansion seems to be similar to our approach for expansion-based extension enforcement (Section 4), and it would be interesting to investigate the connexions between CIAFs and AFs with attack points. Notice however that the main study of [47] is the individual dialectical strength of arguments, so it is not concerned with extension-based semantics like our work.

# 7 Conclusion

We have defined Constrained Incomplete Argumentation Frameworks (or CIAFs, for short) that generalize IAFs by adding a constraint over the set of completions. This new framework increases the expressiveness of IAFs without a gap in complexity for the standard acceptability decision problems, and paves the way for the definition of revision or merging operators for AFs that return a CIAF, i.e. a more compact result than a (potentially exponentially large) set of AFs or extensions. However, the CIAF that we have exhibited here to prove the representability of any set of AFs or extensions may not be a suitable solution in scenarios like belief revision or belief merging, where the notion of minimal change is important. We will study how to generate a CIAF that is optimal in such contexts. Knowledge compilation [49] is an interesting way for providing a succinct equivalent propositional constraint such that relevant reasoning tasks are polynomially doable. Another interesting future work is the implementation of efficient algorithms (e.g. based on Boolean encoding, in the line of [30]) for reasoning with CIAFs. We will also study how to encode other extension enforcement operators as CIAF-based reasoning, in particular operators in the vein of the so-called argument-fixed enforcement from [35]. Finally, it would be interesting to generalize IAFs and CIAFs to take into account information like "I am less sure of the existence of the argument *a* than the existence of the argument *b*". This would induce a plausibility ordering of completions, and decision problems like "does the argument *a* belong to some extension of one of the most plausible completions?", which allows to provide a better representation and reasoning capability about argumentative scenarios with uncertainty.

# Acknowledgement

The author warmly thanks Antonio Yuste-Ginel for the interesting discussion that lead to this work, as well as the reviewers that provided valuable feedback on this paper and the preliminary conference versions.

This work benefited from the support of the project AGGREEY ANR-22-CE23-0005 of the French National Research Agency (ANR).

# References

[1] C.E. Alchourrón, P. Gärdenfors and D. Makinson, On the Logic of Theory Change: Partial Meet Contraction and Revision Functions, *J. Symb. Log.* **50**(2) (1985), 510–530.

[2] H. Katsuno and A.O. Mendelzon, On the Difference between Updating a Knowledge Base and Revising It, in: *Proc. of KR’91*, 1991, pp. 387–394.

[3] H. Katsuno and A.O. Mendelzon, Propositional Knowledge Base Revision and Minimal Change, *Artif. Intell.* **52**(3) (1992), 263–294.
no expansion of the AF can contain a new argument that attacks *a*. The notion of allowed expansion seems to be similar to our approach for expansion-based extension enforcement (Section 4), and it would be interesting to investigate the connexions between CIAFs and AFs with attack points. Notice however that the main study of [47] is the individual dialectical strength of arguments, so it is not concerned with extension-based semantics like our work.

# 7 Conclusion

We have defined Constrained Incomplete Argumentation Frameworks (or CIAFs, for short) that generalize IAFs by adding a constraint over the set of completions. This new framework increases the expressiveness of IAFs without a gap in complexity for the standard acceptability decision problems, and paves the way for the definition of revision or merging operators for AFs that return a CIAF, *i.e.* a more compact result than a (potentially exponentially large) set of AFs or extensions. However, the CIAF that we have exhibited here to prove the representability of any set of AFs or extensions may not be a suitable solution in scenarios like belief revision or belief merging, where the notion of minimal change is important. We will study how to generate a CIAF that is optimal in such contexts. Knowledge compilation [49] is an interesting way for providing a succinct equivalent propositional constraint such that relevant reasoning tasks are polynomially doable. Another interesting future work is the implementation of efficient algorithms (*e.g.* based on Boolean encoding, in the line of [30]) for reasoning with CIAFs. We will also study how to encode other extension enforcement operators as CIAF-based reasoning, in particular operators in the vein of the so-called argument-fixed enforcement from [35]. Finally, it would be interesting to generalize IAFs and CIAFs to take into account information like “I am less sure of the existence of the argument *a* than the existence of the argument *b*”. This would induce a plausibility ordering of completions, and decision problems like “does the argument *a* belong to some extension of one of the most plausible completions?”, which allows to provide a better representation and reasoning capability about argumentative scenarios with uncertainty.

# Acknowledgement

The author warmly thanks Antonio Yuste-Ginel for the interesting discussion that lead to this work, as well as the reviewers that provided valuable feedback on this paper and the preliminary conference versions.

This work benefited from the support of the project AGGREEY ANR-22-CE23-0005 of the French National Research Agency (ANR).

# References

[1] C.E. Alchourrón, P. Gärdenfors and D. Makinson, On the Logic of Theory Change: Partial Meet Contraction and Revision Functions, *J. Symb. Log.* **50**(2) (1985), 510–530.

[2] H. Katsuno and A.O. Mendelzon, On the Difference between Updating a Knowledge Base and Revising It, in: *Proc. of KR'91*, 1991, pp. 387–394.

[3] H. Katsuno and A.O. Mendelzon, Propositional Knowledge Base Revision and Minimal Change, *Artif. Intell.* **52**(3) (1992), 263–294.
[4] S. Konieczny and R.P. Pérez, Merging Information Under Constraints: A Logical Framework, *J. Log. Comput.* **12**(5) (2002), 773–808.

[5] P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, *Art. Intel.* **77** (1995), 321–357.

[6] S. Coste-Marquis, C. Devred, S. Konieczny, M. Lagasquie-Schiex and P. Marquis, On the merging of Dung’s argumentation systems, *Artif. Intell.* **171**(10–15) (2007), 730–753.

[7] D. Baumeister, D. Neugebauer, J. Rothe and H. Schadrack, Verification in incomplete argumentation frameworks, *Artif. Intell.* **264** (2018), 1–26.

[8] D. Baumeister, D. Neugebauer and J. Rothe, Credulous and Skeptical Acceptance in Incomplete Argumentation Frameworks, in: *Proc. of COMMA’18*, 2018, pp. 181–192.

[9] S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, On the Revision of Argumentation Systems: Minimal Change of Arguments Statuses, in: *Proc. of KR’14*, 2014.

[10] S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, A Translation-based Approach for Revision of Argumentation Frameworks, in: *Proc. of JELIA’14*, 2014, pp. 77–85.

[11] J. Delobelle, A. Haret, S. Konieczny, J.-G. Mailly, J. Rossit and S. Woltran, Merging of Abstract Argumentation Frameworks, in: *Proc. of KR’16*, 2016, pp. 33–42.

[12] P.E. Dunne, W. Dvorák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, *Artif. Intell.* **228** (2015), 153–178.

[13] R. Baumann and G. Brewka, Expanding Argumentation Frameworks: Enforcing and Monotonicity Results, in: *Proc. of COMMA’10*, Vol. 216, 2010, pp. 75–86.

[14] R. Baumann, S. Doutre, J.-G. Mailly and J.P. Wallner, Enforcement in Formal Argumentation, *Journal of Applied Logics - IfCoLog Journal of Logics and their Applications* **8**(6) (2021), 1623–1677.

[15] J.-G. Mailly, Constrained Incomplete Argumentation Frameworks, in: *Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 16th European Conference, ECSQARU 2021, Prague, Czech Republic, September 21-24, 2021, Proceedings*, J. Vejnarová and N. Wilson, eds, Lecture Notes in Computer Science, Vol. 12897, Springer, 2021, pp. 103–116.

[16] J.-G. Mailly, Constrained Incomplete Argumentation Frameworks, in: *15èmes Journées d'Intelligence Artificielle Fondamentale*, Z. Bouraoui and S. Doutre, eds, 2021, pp. 6–14.

[17] J.-G. Mailly, A Note on Rich Incomplete Argumentation Frameworks, *CoRR abs/2009.04869* (2020). https://arxiv.org/abs/2009.04869

[18] S. Cook, The Complexity of Theorem-Proving Procedures, in: *Proceedings of the 3rd Annual ACM Symposium on Theory of Computing*, 1971, pp. 151–158.

[19] P. Baroni, M. Caminada and M. Giacomin, Abstract Argumentation Frameworks and Their Semantics, in: *Handbook of Formal Argumentation*, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 159–236.
[4] S. Konieczny and R.P. Pérez, Merging Information Under Constraints: A Logical Framework, *J. Log. Comput.* **12**(5) (2002), 773–808.

[5] P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, *Art. Intel.* **77** (1995), 321–357.

[6] S. Coste-Marquis, C. Devred, S. Konieczny, M. Lagasquie-Schiex and P. Marquis, On the merging of Dung's argumentation systems, *Artif. Intell.* **171**(10–15) (2007), 730–753.

[7] D. Baumeister, D. Neugebauer, J. Rothe and H. Schadrack, Verification in incomplete argumentation frameworks, *Artif. Intell.* **264** (2018), 1–26.

[8] D. Baumeister, D. Neugebauer and J. Rothe, Credulous and Skeptical Acceptance in Incomplete Argumentation Frameworks, in: *Proc. of COMMA'18*, 2018, pp. 181–192.

[9] S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, On the Revision of Argumentation Systems: Minimal Change of Arguments Statuses, in: *Proc. of KR'14*, 2014.

[10] S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, A Translation-based Approach for Revision of Argumentation Frameworks, in: *Proc. of JELIA'14*, 2014, pp. 77–85.

[11] J. Delobelle, A. Haret, S. Konieczny, J.-G. Mailly, J. Rossit and S. Woltran, Merging of Abstract Argumentation Frameworks, in: *Proc. of KR'16*, 2016, pp. 33–42.

[12] P.E. Dunne, W. Dvorák, T. Linsbichler and S. Woltran, Characteristics of multiple viewpoints in abstract argumentation, *Artif. Intell.* **228** (2015), 153–178.

[13] R. Baumann and G. Brewka, Expanding Argumentation Frameworks: Enforcing and Monotonicity Results, in: *Proc. of COMMA'10*, Vol. 216, 2010, pp. 75–86.

[14] R. Baumann, S. Doutre, J.-G. Mailly and J.P. Wallner, Enforcement in Formal Argumentation, *Journal of Applied Logics - IfCoLog Journal of Logics and their Applications* **8**(6) (2021), 1623–1677.

[15] J.-G. Mailly, Constrained Incomplete Argumentation Frameworks, in: *Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 16th European Conference, ECSQARU 2021, Prague, Czech Republic, September 21-24, 2021, Proceedings*, J. Vejnarová and N. Wilson, eds, Lecture Notes in Computer Science, Vol. 12897, Springer, 2021, pp. 103–116.

[16] J.-G. Mailly, Constrained Incomplete Argumentation Frameworks, in: *15èmes Journées d'Intelligence Artificielle Fondamentale*, Z. Bouraoui and S. Doutre, eds, 2021, pp. 6–14.

[17] J.-G. Mailly, A Note on Rich Incomplete Argumentation Frameworks, *CoRR abs/2009.04869* (2020). https://arxiv.org/abs/2009.04869

[18] S. Cook, The Complexity of Theorem-Proving Procedures, in: *Proceedings of the 3rd Annual ACM Symposium on Theory of Computing*, 1971, pp. 151–158.

[19] P. Baroni, M. Caminada and M. Giacomin, Abstract Argumentation Frameworks and Their Semantics, in: *Handbook of Formal Argumentation*, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 159–236.
[20] W. Dvorák and P.E. Dunne, Computational Problems in Formal Argumentation and their Complexity, in: *Handbook of Formal Argumentation*, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 631–688.

[21] R. Baumann, W. Dvorák, T. Linsbichler, H. Strass and S. Woltran, Compact Argumentation Frameworks, in: *Proc. of ECAI'14*, Vol. 263, 2014, pp. 69–74.

[22] M. Diller, A. Haret, T. Linsbichler, S. Rümmele and S. Woltran, An extension-based approach to belief revision in abstract argumentation, *Int. J. Approx. Reason.* **93** (2018), 395–423.

[23] B. Fazzinga, S. Flesca and F. Furfaro, Revisiting the Notion of Extension over Incomplete Abstract Argumentation Frameworks, in: *Proc. of IJCAI'20*, 2020, pp. 1712–1718.

[24] D. Baumeister, M. Järvisalo, D. Neugebauer, A. Niskanen and J. Rothe, Acceptance in incomplete argumentation frameworks, *Artif. Intell. 295* (2021), 103470.

[25] S. Coste-Marquis, C. Devred and P. Marquis, Constrained Argumentation Frameworks, in: *Proc. of KR'06*, 2006, pp. 112–122.

[26] B. Fazzinga, S. Flesca and F. Furfaro, Reasoning over Argument-Incomplete AAFs in the Presence of Correlations, in: *Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021*, Z. Zhou, ed., ijcai.org, 2021, pp. 189–195.

[27] B. Fazzinga, S. Flesca and F. Furfaro, Reasoning over Attack-incomplete AAFs in the Presence of Correlations, in: *Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021*, M. Bienvenu, G. Lakemeyer and E. Erdem, eds, 2021, pp. 301–311.

[28] D. Baumeister, J. Rothe and H. Schadrack, Verification in Argument-Incomplete Argumentation Frameworks, in: *Proc. of ADT'15*, 2015, pp. 359–376.

[29] D. Baumeister, D. Neugebauer and J. Rothe, Verification in Attack-Incomplete Argumentation Frameworks, in: *Proc. of ADT'15*, 2015, pp. 341–358.

[30] A. Niskanen, D. Neugebauer, M. Järvisalo and J. Rothe, Deciding Acceptance in Incomplete Argumentation Frameworks, in: *Proc. of AAAI'20*, 2020, pp. 2942–2949.

[31] R. Baumann, S. Doutre, J.-G. Mailly and J.P. Wallner, Enforcement in Formal Argumentation, in: *Handbook of Formal Argumentation*, Vol. 2, D. Gabbay, M. Giacomin, G.R. Simari and M. Thimm, eds, College Publications, 2021, Chapter 8.

[32] S. Doutre and J.-G. Mailly, Constraints and changes: A survey of abstract argumentation dynamics, *Argument & Computation* **9**(3) (2018), 223–248.

[33] Y. Dimopoulos, J.-G. Mailly and P. Moraitis, Argumentation-based Negotiation with Incomplete Opponent Profiles, in: *Proc. of AAMAS'19*, 2019, pp. 1252–1260.

[34] E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, A Parametrized Ranking-Based Semantics for Persuasion, in: *Proc. of SUM'17*, 2017, pp. 237–251.

[35] S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, Extension Enforcement in Abstract Argumentation as an Optimization Problem, in: *Proc. of IJCAI'15*, 2015, pp. 2876–2882.
[20] W. Dvorák and P.E. Dunne, Computational Problems in Formal Argumentation and their Complexity, in: *Handbook of Formal Argumentation*, P. Baroni, D. Gabbay, M. Giacomin and L. van der Torre, eds, College Publications, 2018, pp. 631–688.

[21] R. Baumann, W. Dvorák, T. Linsbichler, H. Strass and S. Woltran, Compact Argumentation Frameworks, in: *Proc. of ECAI'14*, Vol. 263, 2014, pp. 69–74.

[22] M. Diller, A. Haret, T. Linsbichler, S. Rümmele and S. Woltran, An extension-based approach to belief revision in abstract argumentation, *Int. J. Approx. Reason.* **93** (2018), 395–423.

[23] B. Fazzinga, S. Flesca and F. Furfaro, Revisiting the Notion of Extension over Incomplete Abstract Argumentation Frameworks, in: *Proc. of IJCAI'20*, 2020, pp. 1712–1718.

[24] D. Baumeister, M. Järvisalo, D. Neugebauer, A. Niskanen and J. Rothe, Acceptance in incomplete argumentation frameworks, *Artif. Intell.* **295** (2021), 103470.

[25] S. Coste-Marquis, C. Devred and P. Marquis, Constrained Argumentation Frameworks, in: *Proc. of KR'06*, 2006, pp. 112–122.

[26] B. Fazzinga, S. Flesca and F. Furfaro, Reasoning over Argument-Incomplete AAFs in the Presence of Correlations, in: *Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021*, Z. Zhou, ed., ijcai.org, 2021, pp. 189–195.

[27] B. Fazzinga, S. Flesca and F. Furfaro, Reasoning over Attack-incomplete AAFs in the Presence of Correlations, in: *Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021*, M. Bienvenu, G. Lakemeyer and E. Erdem, eds, 2021, pp. 301–311.

[28] D. Baumeister, J. Rothe and H. Schadrack, Verification in Argument-Incomplete Argumentation Frameworks, in: *Proc. of ADT'15*, 2015, pp. 359–376.

[29] D. Baumeister, D. Neugebauer and J. Rothe, Verification in Attack-Incomplete Argumentation Frameworks, in: *Proc. of ADT'15*, 2015, pp. 341–358.

[30] A. Niskanen, D. Neugebauer, M. Järvisalo and J. Rothe, Deciding Acceptance in Incomplete Argumentation Frameworks, in: *Proc. of AAAI'20*, 2020, pp. 2942–2949.

[31] R. Baumann, S. Doutre, J.-G. Mailly and J.P. Wallner, Enforcement in Formal Argumentation, in: *Handbook of Formal Argumentation*, Vol. 2, D. Gabbay, M. Giacomin, G.R. Simari and M. Thimm, eds, College Publications, 2021, Chapter 8.

[32] S. Doutre and J.-G. Mailly, Constraints and changes: A survey of abstract argumentation dynamics, *Argument & Computation* **9**(3) (2018), 223–248.

[33] Y. Dimopoulos, J.-G. Mailly and P. Moraitis, Argumentation-based Negotiation with Incomplete Opponent Profiles, in: *Proc. of AAMAS'19*, 2019, pp. 1252–1260.

[34] E. Bonzon, J. Delobelle, S. Konieczny and N. Maudet, A Parametrized Ranking-Based Semantics for Persuasion, in: *Proc. of SUM'17*, 2017, pp. 237–251.

[35] S. Coste-Marquis, S. Konieczny, J.-G. Mailly and P. Marquis, Extension Enforcement in Abstract Argumentation as an Optimization Problem, in: *Proc. of IJCAI'15*, 2015, pp. 2876–2882.