# Grounded semantics and principle-based analysis for
incomplete argumentation frameworks

Jean-Guy Mailly

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

► To cite this version:

Jean-Guy Mailly. Grounded semantics and principle-based analysis for incomplete argumentation frameworks. International Journal of Approximate Reasoning, 2024, 175, pp.109282. 10.1016/j.ijar.2024.109282. hal-04948480

HAL Id: hal-04948480

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

Submitted on 14 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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>
<figure><img src="image_3.png" /></figure>

# Grounded semantics and principle-based analysis for incomplete argumentation frameworks

Jean-Guy Mailly

IRIT, Université Toulouse Capitole, 21 allée de Brienne, Toulouse, 31000, France

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

Check for
updates

## ARTICLE INFO

**Keywords:**

Abstract argumentation

Uncertainty

Extension-based semantics

## ABSTRACT

Incomplete Argumentation Frameworks (IAFs) enrich classical abstract argumentation with arguments and attacks whose actual existence is questionable. The usual reasoning approaches rely on the notion of completion, i.e. standard AFs representing “possible worlds” compatible with the uncertain information encoded in the IAF. Recently, extension-based semantics for IAFs that do not rely on the notion of completion have been defined, using instead new versions of conflict-freeness and defense that take into account the (certain or uncertain) nature of arguments and attacks. In this paper, we give new insights on both the “completion-based” and the “direct” reasoning approaches. First, we adapt the well-known grounded semantics to this framework in two different versions that do not rely on completions. After determining that our new semantics are polynomially computable, we provide a principle-based analysis of these semantics, as well as the “direct” semantics previously defined in the literature, namely the complete, preferred and stable semantics. Finally, we also provide new results regarding the satisfaction of principles by the classical “completion-based” semantics.

## 1. Introduction

Abstract argumentation has received much attention since the seminal paper by Dung [1]. An Argumentation Framework (AF) is generally defined as a directed graph where nodes represent arguments, and edges represent attacks between these arguments. Since then, many generalizations of Dung's framework have been proposed, introducing the notion of support between arguments [2], weighted attacks [3] or weighted arguments [4], preferences between arguments [5], and so on.

In this paper, we focus on one such generalization of abstract argumentation, namely Incomplete Argumentation Frameworks (IAFs) [6–8] in which arguments and attacks can be defined as uncertain, meaning that the agent reasoning with such an IAF is not sure whether these arguments or attacks actually exist (e.g. whether they will actually be used at some step of the debate). This is particularly meaningful when modeling an agent’s knowledge about her opponent in a debate [9,10], since it is a reasonable assumption that agents are not always able to assess precisely the uncertainty degree of a piece of information (e.g. meaningful probabilities may not be available). The most classical reasoning approaches with IAFs are based on the notion of completion, i.e. standard AFs that represent different ways to “solve the uncertainty” in the IAF. However, another family of semantics was also proposed in the literature, based on the idea that basic principles of argumentation semantics (namely conflict-freeness and defense) can be adapted to take into account the nature of the pieces of information in the IAF (certain or uncertain) [7,11,12]. While the initial work on this

<footnote>E-mail address: jean-guy.mailly@irit.fr.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 1. Example of AF.</figcaption></figure>

topic focuses on *Partial* AFs (which are IAFs without uncertain arguments) and the preferred semantics [7], the general IAF model and other semantics (namely complete and stable) have also been studied in [11,12].

Now we push further the study of both families of reasoning approaches, the “completion-based” and the “direct” approaches. First, we focus on the adaptation to the direct approach of the last classical semantics initially defined by Dung, namely the grounded semantics. For all the direct semantics defined in the literature and in the present paper, we also investigate the principles they satisfy, following the principle-based approach for analyzing argumentation semantics [13–15]. We also perform the same study for the completion-based versions of the classical Dung semantics.

This paper is an extended version of the conference paper [16]. The original definition of the grounded semantics, the corresponding complexity results, and parts of the principle-based analysis were provided in the conference paper. Compared to this earlier version, the paper has been enriched with various contributions:

* contrary to the conference version, all proofs are provided in the Appendices,

* new results are provided regarding the weak and semi-directionality of the strong and weak stable semantics (Proposition 6),

* a new section (Section 5) has been added, where the classical “completion-based” extension-based semantics for IAFs (i.e. the ones introduce by [17]) are also studied with respect to the principle-based analysis.

Section 2 presents background notions of abstract argumentation. In Section 3, we introduce the grounded semantics of Incomplete Argumentation Frameworks. Sections 4 and 5 describe respectively our principle-based analysis of direct semantics of IAFs and of completion-based semantics of IAFs. Finally, Section 6 discusses some related work and Section 7 concludes the paper and highlights some interesting ideas for future research.

## 2. Background on abstract argumentation

### 2.1. Dung's framework

**Definition 1.** An Argumentation Framework (AF) [1] is a directed graph $\mathcal{F} = (\mathcal{A}, \mathcal{R})$ where $\mathcal{A}$ represents the arguments and $\mathcal{R} \subseteq \mathcal{A} \times \mathcal{A}$ represents the attacks between arguments.

In this paper we assume that AFs are always finite, i.e. $\mathcal{A}$ is a non-empty finite set of arguments. We say that an argument $a \in \mathcal{A}$ (resp. a set $S \subseteq \mathcal{A}$) attacks an argument $b \in \mathcal{A}$ if $(a, b) \in \mathcal{R}$ (resp. there is some $a \in S$ such that $(a, b) \in \mathcal{R}$). Then, $S \subseteq \mathcal{A}$ *defends* $a \in \mathcal{A}$ if for each $b \in \mathcal{A}$ such that $(b, a) \in \mathcal{R}$, $S$ attacks $b$. A set of arguments $S \subseteq \mathcal{A}$ is called *conflict-free* when there is no attack between any $a, b \in S$. In this case we write $S \in \text{cf}(\mathcal{F})$. Dung [1] proposed several semantics for evaluating the acceptability of arguments. Their definitions are based on the characteristic function $\Gamma_F$ of an AF:

**Definition 2.** Given an AF $\mathcal{F} = (\mathcal{A}, \mathcal{R})$, the characteristic function of $\mathcal{F}$ is $\Gamma_F : 2^A \to 2^A$ defined by

$$ \Gamma_F(S) = \{a \mid S \text{ defends } a\} $$

Now, given $S \in \text{cf}(\mathcal{F})$ a conflict-free set of arguments, $S$ is

* admissible iff $S \subseteq \Gamma_F(S)$,

* a complete extension iff $S = \Gamma_F(S)$,

* a preferred extension iff it is a $\subseteq$-maximal admissible set,

* the unique grounded extension iff it is the $\subseteq$-minimal complete extension.

These sets of extensions are denoted (resp. by $\text{ad}(\mathcal{F})$, $\text{co}(\mathcal{F})$, $\text{pr}(\mathcal{F})$ and $\text{gr}(\mathcal{F})$). Finally, a last classical semantics is not based on the characteristic function: $S \in \text{cf}(\mathcal{F})$ is a *stable extension* iff $S$ attacks all the arguments in $\mathcal{A} \setminus S$. The stable extensions are denoted $\text{st}(\mathcal{F})$. We sometimes write $\sigma(\mathcal{F})$ for the set of extensions of $\mathcal{F}$ under an arbitrary semantics $\sigma \in \{\text{cf}, \text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$.

**Example 1.** Fig. 1 describes $\mathcal{F} = (\mathcal{A}, \mathcal{R})$, where the nodes represent $\mathcal{A}$ and the edges represent $\mathcal{R}$. Its extensions for the co, pr, st and gr semantics are given in Table 1.
<table><caption>**Table 1**
Extensions of the AF $\mathcal{F}$.</caption><thead><tr><th>Semantics σ</th><th>Extensions σ(\mathcal{F})</th></tr></thead><tbody><tr><td>co</td><td>{ {a<sub>1</sub>}, {a<sub>1</sub>, a<sub>3</sub>}, {a<sub>1</sub>, a<sub>4</sub>, a<sub>6</sub>} }</td></tr><tr><td>pr</td><td>{ {a<sub>1</sub>, a<sub>3</sub>}, {a<sub>1</sub>, a<sub>4</sub>, a<sub>6</sub>} }</td></tr><tr><td>st</td><td>{ {a<sub>1</sub>, a<sub>4</sub>, a<sub>6</sub>} }</td></tr><tr><td>gr</td><td>{ {a<sub>1</sub>} }</td></tr></tbody></table>

<table><caption>**Table 2**
Complexity of σ-Ver, σ-Cred, σ-Skep, σ-Exist and σ-NE for σ ∈ (cf, ad, gr, st, co, pr). C-c means C-complete. Trivial means that the answer to the problem is always “NO” (for Skep) or always “YES” (for Exist).</caption><thead><tr><th>Semantics σ</th><th>σ-Ver</th><th>σ-Cred</th><th>σ-Skep</th><th>σ-Exist</th><th>σ-NE</th></tr></thead><tbody><tr><td>cf</td><td>in L</td><td>in L</td><td>trivial</td><td>trivial</td><td>in L</td></tr><tr><td>ad</td><td>in L</td><td>NP-c</td><td>trivial</td><td>trivial</td><td>NP-c</td></tr><tr><td>gr</td><td>P-c</td><td>P-c</td><td>P-c</td><td>trivial</td><td>in L</td></tr><tr><td>st</td><td>in L</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>NP-c</td></tr><tr><td>co</td><td>in L</td><td>NP-c</td><td>P-c</td><td>trivial</td><td>NP-c</td></tr><tr><td>pr</td><td>coNP-c</td><td>NP-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>trivial</td><td>NP-c</td></tr></tbody></table>

Various decision problems can be interesting: σ-Ver is the verification that a given set of arguments is a σ extension of a given AF, σ-Cred and σ-Skep consist (resp.) in checking whether a given argument belongs to some or each σ-extension of a given AF. Finally, σ-Exist (resp. σ-NE) is the check whether there is at least one (resp. one non-empty) σ-extension for a given AF. Table 2 summarizes the known complexity for these problems, see [18] for more details.

## 2.2. Incomplete argumentation frameworks

**Incomplete Argumentation Frameworks** (IAFs) generalize AFs by adding a notion of uncertainty on the presence of arguments and attacks, i.e. an IAF is a tuple $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ where $\mathcal{A}, \mathcal{A}^2$ are disjoint sets of arguments, and $\mathcal{R}, \mathcal{R}^2$ are disjoint sets of attacks over $\mathcal{A} \cup \mathcal{A}^2$. The arguments and attacks in $\mathcal{A}$ and $\mathcal{R}$ certainly exist, while those in $\mathcal{A}^2$ and $\mathcal{R}^2$ are uncertain. See [19] for a recent overview of IAFs. In this paper, we focus mainly on the IAF semantics from [7,11,12].<fnref n="1" /> The intuition behind this approach consists in adapting the notions of conflict-freeness and defense to IAFs, in order to define well-suited notions of admissibility and the corresponding semantics.

**Definition 3.** Let $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ be an IAF, and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$ a set of arguments. S is weakly (resp. strongly) conflict-free iff $\forall a, b \in S \cap \mathcal{A}$ (resp. $a, b \in S$), $(a, b) \notin \mathcal{R}$ (resp. $(a, b) \notin \mathcal{R} \cup \mathcal{R}^2$).

**Definition 4.** Let $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ be an IAF, $S \subseteq \mathcal{A} \cup \mathcal{A}^2$ a set of arguments, and $a \in \mathcal{A} \cup \mathcal{A}^2$ an argument. S weakly (resp. strongly) defends a iff $\forall b \in \mathcal{A}$ (resp. $b \in \mathcal{A} \cup \mathcal{A}^2$) s.t. $(b, a) \in \mathcal{R}$ (resp. $(b, a) \in \mathcal{R} \cup \mathcal{R}^2$), $\exists c \in S \cap \mathcal{A}$ s.t. $(c, b) \in \mathcal{R}$.

Combining weak (resp. strong) conflict-freeness with weak (resp. strong) defense yields a notion of weak (resp. strong) admissibility, and the corresponding preferred and complete semantics.

**Definition 5.** Let $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ be an IAF and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$ a set of arguments. S is weakly (resp. strongly) admissible if it is weakly (resp. strongly) conflict-free and it weakly (resp. strongly) defends all its elements.

The weak (resp. strong) conflict-free and admissible sets of an IAF $I$ are denoted by $cf_w(I)$ and $ad_w(I)$ (resp. $cf_s(I)$ and $ad_s(I)$).

**Definition 6.** Let $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ be an IAF, and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$ a set of arguments. S is a

* weak (resp. strong) preferred extension of $I$ if $S$ is a $\subseteq$-maximal weak (resp. strong) admissible set,

* weak (resp. strong) complete extension of $I$ if $S$ is a weak (resp. strong) admissible set which does not weakly (resp. strongly) defend any argument outside of $S$.

These semantics are denoted by $pr_x(I)$ and $co_x(I)$, with $x \in \{w, s\}$. The stable semantics has been adapted as well.

<footnote n="1">¹ See Section 5 for the presentation of the classical completion-based semantics.</footnote>
<figure><img src="image_6.png" /><figcaption>Fig. 2. The IAF *I*.</figcaption></figure>

<table><caption>**Table 3**
Extensions of the IAF *I*.</caption><thead><tr><th>Semantics &sigma;</th><th>Extensions &sigma;(R)</th></tr></thead><tbody><tr><td>co<sub>w</sub></td><td>{ {a<sub>1</sub>, a<sub>2</sub>, a<sub>4</sub>, a<sub>6</sub>, a<sub>7</sub>} }</td></tr><tr><td>pr<sub>w</sub></td><td>{ {a<sub>1</sub>, a<sub>2</sub>, a<sub>4</sub>, a<sub>6</sub>, a<sub>7</sub>} }</td></tr><tr><td>st<sub>w</sub></td><td>{ {a<sub>2</sub>, a<sub>4</sub>, a<sub>6</sub>, a<sub>7</sub>}, {a<sub>2</sub>, a<sub>4</sub>, a<sub>5</sub>, a<sub>6</sub>, a<sub>7</sub>}, {a<sub>1</sub>, a<sub>2</sub>, a<sub>4</sub>, a<sub>5</sub>, a<sub>6</sub>, a<sub>7</sub>} }</td></tr><tr><td>co<sub>s</sub></td><td>{ {a<sub>1</sub>}, {a<sub>1</sub>, a<sub>6</sub>} }</td></tr><tr><td>pr<sub>s</sub></td><td>{ {a<sub>1</sub>, a<sub>6</sub>} }</td></tr><tr><td>st<sub>s</sub></td><td>&empty;</td></tr></tbody></table>

<table><caption>**Table 4**
Complexity of $\sigma_x$-Ver, $\sigma_x$-Cred, $\sigma_x$-Skep, $\sigma_x$-Exist and $\sigma_x$-NE for $\sigma \in \{\text{cf}, \text{ad}, \text{gr}, \text{st}, \text{co}, \text{pr}\}$ and $x \in \{w, s\}$. C-c means C-complete. Trivial means that the answer to the problem is always “NO” (for Skep) or always “YES” (for Exist).</caption><thead><tr><th>Semantics &sigma;<sub>x</sub></th><th>&sigma;<sub>x</sub>-Ver</th><th>&sigma;<sub>x</sub>-Cred</th><th>&sigma;<sub>x</sub>-Skep</th><th>&sigma;<sub>x</sub>-Exist</th><th>&sigma;<sub>x</sub>-NE</th></tr></thead><tbody><tr><td>cf<sub>x</sub></td><td>in L</td><td>in L</td><td>trivial</td><td>trivial</td><td>in L</td></tr><tr><td>ad<sub>x</sub></td><td>in L</td><td>NP-c</td><td>trivial</td><td>trivial</td><td>NP-c</td></tr><tr><td>gr<sub>x</sub></td><td></td><td>P-c</td><td>P-c</td><td>trivial</td><td>in L</td></tr><tr><td>st<sub>x</sub></td><td>in L</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>NP-c</td></tr><tr><td>co<sub>x</sub></td><td>in L</td><td>NP-c</td><td>P-c</td><td>trivial</td><td>NP-c</td></tr><tr><td>pr<sub>x</sub></td><td>coNP-c</td><td>NP-c</td><td>&Pi;<sub>x</sub><sup>P</sup>-c</td><td>trivial</td><td>NP-c</td></tr></tbody></table>

**Definition 7.** Let $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ be an IAF, and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$ a set of arguments. $S$ is a weak (resp. strong) stable extension iff it is a weak (resp. strong) conflict-free set s.t. $\forall a \in \mathcal{A} \setminus S$ (resp. $a \in (\mathcal{A} \cup \mathcal{A}^2) \setminus S$), $\exists b \in S \cap \mathcal{A}$ s.t. $(b, a) \in \mathcal{R}$.

We use $st_x(I)$ with $x \in \{w, s\}$ to denote the weak and strong stable extensions of an IAF.

**Example 2.** Fig. 2 describes an IAF $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ where the dotted nodes (resp. edges) represent the uncertain arguments $\mathcal{A}^2$ (resp. attacks $\mathcal{R}^2$). Certain arguments and attacks are represented as previously. Its extensions are given in Table 3.

The complexity of reasoning with these semantics has been established in [11,12], the results are summarized in Table 4.

### 3. Grounded semantics

Now we fulfill the landscape of “direct” extension-based semantics for IAFs by defining weak and strong variants of the grounded semantics. Following Dung’s original approach, we define characteristic functions of an IAF, corresponding to the notions of weak and strong defense from Definition 4.

**Definition 8 (Characteristic functions).** Given an IAF $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$, the $x$-characteristic function of $I$ (where $x \in \{w, s\}$) is defined by

$$ \Gamma_{x,I}(S) = \{a \in \mathcal{A} \cup \mathcal{A}^2 \mid S \text{ x-defends } a\} $$

We show that the results by Dung regarding the characteristic function of an AF [1, Section 2.2] can be adapted to our framework. The following lemmas are easy to prove. First, the $x$-characteristic function preserves the $x$-conflict-freeness.

**Lemma 1.** Given an IAF $I = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$, $x \in \{w, s\}$ and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$, if $S \in \text{cf}_x(I)$ then $\Gamma_{x,I}(S) \in \text{cf}_x(I)$.
<table><caption>**Algorithm 1** Computation of the x-grounded extension.</caption><thead><tr><th>Require:</th><th>I = &lt;A, A<sup>?</sup>, R, R<sup>?</sup>&gt;, x &isin; {w, s}</th></tr></thead><tbody><tr><td>1:</td><td>result = &Gamma;<sub>x,I</sub>(&emptyset;)</td></tr><tr><td>2:</td><td>while result &ne; &Gamma;<sub>x,I</sub>(result) do</td></tr><tr><td>3:</td><td>result = &Gamma;<sub>x,I</sub>(result)</td></tr><tr><td>4:</td><td>end while</td></tr><tr><td>5:</td><td>return result</td></tr></tbody></table>

The following lemma also shows that the usual relation between admissibility and the characteristic function(s) also works for the strong and weak admissible sets defined in [11,12].

**Lemma 2.** *Given an IAF I = (A, A', R, R'), x ∈ {w, s}, and S ⊆ A ∪ A' such that S ∈ cf<sub>x</sub>(I), S ∈ ad<sub>x</sub>(I) if and only if S ⊆ Γ<sub>x,I</sub>(S).*

Also, the correspondence between fixed-points of the characteristic functions and the strong and weak complete extensions holds in our framework as well.

**Lemma 3.** *Given an IAF I = (A, A', R, R'), x ∈ {w, s}, and S ⊆ A ∪ A' such that S ∈ cf<sub>x</sub>(I), S ∈ co<sub>x</sub>(I) if and only if S = Γ<sub>x,I</sub>(S).*

Now, we prove that the $\Gamma_{x,I}$ functions are monotonic.

**Lemma 4.** *Given an IAF I = (A, A', R, R'), x ∈ {w, s}, and two sets of arguments S, S' ⊆ A ∪ A' such that S, S' are x-conflict-free, if S ⊆ S' then $\Gamma_{x,I}(S) \subseteq \Gamma_{x,I}(S')$.*

Finally we define the grounded semantics of IAFs:

**Definition 9.** Given an IAF $I = (A, A', R, R')$ and $x \in \{w, s\}$, the unique x-grounded extension of I is the least fixed point of the x-characteristic function.

Following the Kleene fixed-point theorem, the x-grounded extension is the fixed point obtained by iteratively applying the x-characteristic function of I using $\emptyset$ as the starting point. This means that we can compute the x-grounded extension with Algorithm 1, which follows the classical approach for computing the grounded extension of an argumentation framework: take the arguments which do not need to be defended (i.e. compute $\Gamma_{x,I}(\emptyset)$, in the case where $x = w$, these are the arguments which are not certainly attacked by certain arguments; in the case where $x = s$ it means that they are not attacked at all). Then, while it is possible, we add to the extension arguments that are defended by the arguments already member of the extension. The process stops when nothing can be added anymore.

**Example 3.** Continuing the previous example, we have $gr_w(I) = \{\{a_1, a_2, a_4, a_6, a_7\}\}$ and $gr_s(I) = \{\{a_1\}\}$.

From Lemma 4, we deduce that the iterations of the loop (line 2 in Algorithm 1) only add arguments to the result being constructed. So the number of iterations of this loop is bounded by the number of arguments, which means that this process is polynomial, as well as all the classical decision problems for these semantics. The P-hardness comes from the known results for standard AFs [18].

**Proposition 1.** For $x \in \{w, s\}$, the problems gr<sub>x</sub>-Ver, gr<sub>x</sub>-Cred and gr<sub>x</sub>-Skep are P-complete, gr<sub>x</sub>-Exist is trivial, and gr<sub>x</sub>-NE is in L.

From Lemma 3, it is obvious that the x-grounded extension of an IAF is also a x-complete extension. It is also the case that any complete extension must contain the arguments which do not need to be x-defended, and then it must contain all the arguments from the x-grounded extension. So the x-grounded extension can be characterized as the (unique) $\subseteq$-minimal x-complete extension, similarly to the “classical” grounded extension. This implies that the coNP upper bound for co<sub>x</sub>-Skep [11] can be made more precise, since co<sub>x</sub>-Skep = gr<sub>x</sub>-Skep.

**Corollary 1.** For $x \in \{w, s\}$, co<sub>x</sub>-Skep is P-complete.

Table 4 summarizes the known complexity results for reasoning with the semantics of IAFs. Grey cells correspond to new results provided in this paper, while the other cells correspond to results from [11] (for $\sigma_x$-Ver, $\sigma_x$-Cred and $\sigma_x$-Skep) and [12] for ($\sigma_x$-Exist and $\sigma_x$-NE).

## 4. Principle-based analysis of IAF semantics

Now we study the properties of the extension-based semantics of IAFs. More precisely, we focus on some principles already mentioned in the literature [14,15]. However, we do not mention some principles which are not relevant here, like admissibility or
reinstatement, which do not make sense if they are directly applied to IAFs. Since our semantics have been defined to satisfy weak or strong counterparts of admissibility (except weak stable semantics), there is nothing to prove regarding these principles adapted to IAFs.

Notice that satisfying principles is not (in general) mandatory to define a “good” semantics, and so it does not mean that a semantics which does not satisfy some principle is inherently “bad”. Principles are meant to help to characterize the behavior of different semantics in some specific situations. If a user of argument-based reasoning is facing some concrete application, then the principle-based analysis of semantics can help to choose a good semantics for this specific application (because it satisfies principles which are desirable in this scenario), but for another application it could be possible to consider other principles as desirable, and thus other semantics would be chosen.

## 4.1. Principles for IAF semantics

We adapt to IAFs several principles from the literature, and show which ones are satisfied by our semantics.

The *I*-maximality principle states that no extension should be a proper subset of another extension. As explained by [13], this principle can be important when one needs to use skeptical reasoning. Indeed, if $S_1$ and $S_2$ are two extensions with $S_1 \subseteq S_2$, then any argument in $S_2 \setminus S_1$ is de facto considered as non-acceptable because it does not belong to the extension $S_1$. In the extreme case where $S_1 = \emptyset$, then no argument can be accepted.

**Principle 1.** An extension-based semantics $\sigma$ satisfies the *I*-maximality principle if, for any AF $I = (\mathcal{A}, \mathcal{A}^?, R, R^?)$, $\forall S, S' \in \sigma(I)$, if $S \subseteq S'$ then $S = S'$.

**Proposition 2.** *I*-maximality is satisfied by $st_S$ as well as $pr_X$ and $gr_X$ for $x \in \{w, s\}$. It is not satisfied by $co_X$ for $x \in \{w, s\}$, nor by $st_w$.

Roughly speaking, the next principle states that if an argument belongs to an extension, and is attacked by another extension, then there should be a third one which abstains to give a status to this argument (i.e. this argument does not belong to the third extension, and is not attacked by it). [14] explains that this principle can be necessary for applications like judgment aggregation [20]: if extensions represent the viewpoints of several agents, such that some agents have good reasons to accept an argument and other agents have good reasons to reject it, then the aggregation should allow to abstain about deciding the acceptance of this argument.

Before giving the principle, we introduce a new notation: given $S \subseteq \mathcal{A} \cup \mathcal{A}^?$, $S^+ = \{a \in \mathcal{A} \cup \mathcal{A}^? \mid \exists b \in S \text{ s.t. } (b, a) \in \mathcal{R} \cup \mathcal{R}^?\}$ is the set of arguments attacked by $S$.

**Principle 2.** An extension-based semantics $\sigma$ satisfies the *allowing abstention principle* if, for any IAF $I = (\mathcal{A}, \mathcal{A}^?, R, R^?)$, and any $a \in \mathcal{A} \cup \mathcal{A}^?$, if there are two extensions $S_1, S_2 \in \sigma(I)$ such that $a \in S_1$ and $a \in S_2^+$, then there is a third extension $S_3 \in \sigma(I)$ such that $a \notin S_3 \cup S_3^+$.

**Proposition 3.** For $x \in \{w, s\}$, $gr_X$ satisfies *allowing abstention*. For $\sigma \in \{\text{pr}, \text{st}\}$ and $x \in \{w, s\}$, $\sigma_X$ does not satisfy *allowing abstention*. Finally, $co_S$ satisfies *allowing abstention*, and $co_w$ does not satisfy *allowing abstention*.

Notice that allowing abstention can be considered either as trivially satisfied (as in [15]) or non-applicable (as in [14]) for single-status semantics like the grounded semantics. Here we use the first option for presenting the results.

The next principle is based on the notion of contaminating framework. To define it, we need to introduce $I_1 \sqcup I_2 = (\mathcal{A}_1 \cup \mathcal{A}_2, \mathcal{A}_1^? \cup \mathcal{A}_2^?, R_1 \cup R_2, R_1^? \cup R_2^?)$.

**Definition 10.** Two IAFs $I_1 = (\mathcal{A}_1, \mathcal{A}_1^?, R_1, R_1^?)$ and $I_2 = (\mathcal{A}_2, \mathcal{A}_2^?, R_2, R_2^?)$ are disjoint if $(\mathcal{A}_1 \cup \mathcal{A}_1^?) \cap (\mathcal{A}_2 \cup \mathcal{A}_2^?) = \emptyset$.

An IAF $I^*$ is contaminating for a semantics $\sigma$ if and only if for each $I$ disjoint from $I^*$, $\sigma(I^*) = \sigma(I^* \sqcup I)$.

The existence of such a contaminating IAF $I^*$ can be seen as a weakness of the semantics, because adding $I^*$ to another IAF $I$ somehow causes a crash of the reasoning in $I$. For instance, in the case of Dung's AFs, consider $F = (\mathcal{A}, R)$, and $a \notin \mathcal{A}$ a fresh argument. It is well-known that adding an isolated self-loop to an AF leads to a new AF without stable extensions, formally, $st((\mathcal{A} \cup \{a\}, R \cup \{(a, a)\})_I) = \emptyset$, even if $st(F) \neq \emptyset$. This is a situation of “reasoning crash” where adding (disconnected) information to an AF leads to only accepting what is accepted in the new information (in this case, it means accepted nothing). It may be important for some applications to guarantee that the semantics avoids this kind of “crash”, which is formally stated (for IAFs) by the following principle.

**Principle 3.** An extension-based semantics $\sigma$ satisfies the *crash resistance principle* iff there is no contaminating IAF for $\sigma$.

**Proposition 4.** For $\sigma \in \{\text{co}, \text{pr}, \text{gr}\}$ and $x \in \{w, s\}$, $\sigma_X$ satisfies *crash resistance*. For $x \in \{w, s\}$, $st_X$ does not satisfy *crash resistance*.
The crash resistance principle only forbids very specific (undesirable) interactions, i.e. the situation where one specific set of arguments and attacks (the contaminating IAF) interferes on the reasoning in every IAF. A more general situation can be captured by the notion of isolated arguments. A set of arguments is called isolated if none of its elements attacks or is attacked by an argument outside the set.

**Definition 11.** Given an IAF $I = \langle A, A^?, R, R^? \rangle$, a set of arguments $S \subseteq A \cup A^?$ is called isolated in $I$ if

$$((S \times ((A \cup A^?) \setminus S)) \cup ((A \cup A^?) \setminus S) \times S)) \cap (R \cup R^?) = \emptyset$$

Given an IAF $I = \langle A, A^?, R, R^? \rangle$ and $S \subseteq A \cup A^?$, $I_{\downarrow S}$ is the IAF defined by $I_{\downarrow S} = \langle A \cap S, A^? \cap S, R \cap (S \times S), R^? \cap (S \times S) \rangle$. The following principle can be seen as a stronger version of crash resistance, since it does not depend on the existence of a (general) contaminating IAF, but can be applied locally at the level of each IAF.

**Principle 4.** An extension-based semantics $\sigma$ satisfies the non-interference principle iff for any IAF $I = \langle A, A^?, R, R^? \rangle$, and for any $S \subseteq A \cup A^?$ isolated in $I$, $\sigma(I_{\downarrow S}) = \{E \cap S | E \in \sigma(I)\}$.

**Proposition 5.** For $\sigma \in \{\text{co, pr, gr}\}$ and $x \in \{w, s\}$, $\sigma_x$ satisfies non-interference. For $x \in \{w, s\}$, $\text{st}_x$ does not satisfy non-interference.

Finally, the three last principles are based on the notion of unattacked sets of arguments, i.e. sets that can attack arguments from outside, but which are not attacked by arguments from the outside (notice that these sets do not have to be conflict-free).

**Definition 12.** Given an IAF $I = \langle A, A^?, R, R^? \rangle$, the set of arguments $S \subseteq A \cup A^?$ is called unattacked in $I$ if and only if $\forall a \in (A \cup A^?) \setminus S, \forall b \in S, (a, b) \notin R \cup R^?$.

The set of unattacked sets of $I$ is denoted by $US(I)$. The following directionality principle (and its variants) strengthen the non-interference principle, by stating (roughly speaking) that a set of arguments $S$ cannot be influenced by arguments outside of it if there are no attacks directed to arguments in $S$ coming from outside of $S$.

**Principle 5.** An extension-based semantics $\sigma$ satisfies the directionality principle iff for any IAF $I = \langle A, A^?, R, R^? \rangle$ and any $S \in US(I)$, $\sigma(I_{\downarrow S}) = \{E \cap S | E \in \sigma(I)\}$.

As in Dung's framework, directionality implies non-interference, which implies crash resistance.

The next principles are weaker versions of directionality, where there is only an inclusion relation between $\sigma(I_{\downarrow S})$ and $\{E \cap S | E \in \sigma(I)\}$ instead of an equality. This means that a semantics which satisfies directionality obviously satisfies both of them, but a semantics which does not satisfy directionality may satisfy one of them (but not both).

**Principle 6.** An extension-based semantics $\sigma$ satisfies the weak directionality principle iff for any IAF $I = \langle A, A^?, R, R^? \rangle$ and any $S \in US(I)$, $\sigma(I_{\downarrow S}) \supseteq \{E \cap S | E \in \sigma(I)\}$.

**Principle 7.** An extension-based semantics $\sigma$ satisfies the semi-directionality principle iff for any IAF $I = \langle A, A^?, R, R^? \rangle$ and any $S \in US(I)$, $\sigma(I_{\downarrow S}) \subseteq \{E \cap S | E \in \sigma(I)\}$.

We prove that both versions of the complete, preferred and grounded semantics satisfy directionality (and obviously weak directionality and semi-directionality as well). We also show that the weak and strong stable semantics satisfy weak directionality but not directionality, which implies that they do not satisfy semi-directionality.

**Proposition 6.** For $\sigma \in \{\text{co, pr, gr}\}$ and $x \in \{w, s\}$, $\sigma_x$ satisfies directionality. For $x \in \{w, s\}$, $\text{st}_x$ does not satisfy directionality nor semi-directionality. $\text{st}_x$ satisfies weak directionality.

## 4.2. Summary

Let us discuss the results of our principle-based analysis, summarized in Table 5. In most of the cases, the semantics of IAFs have the same properties as their counterpart for standard AFs. We notice two exceptions. First, while strong complete semantics has the same properties as the complete semantics of AFs, it is not the case of the weak complete semantics which does not satisfy allowing abstention. Also, while classical stable semantics of AFs and strong stable semantics of IAFs satisfy I-maximality, it is not the case for the weak stable semantics of IAFs.
<caption>**Table 5**</caption>

Satisfaction (✓) or non-satisfaction (✗) of the principles for extension-based semantics of AFs [15] and IAFs (originally from [16]). Grey cells represent new results that were missing in [16].

<table><thead><tr><th>Principles</th><th>co</th><th>gr</th><th>pr</th><th>st</th><th>co<sub>s</sub></th><th>gr<sub>s</sub></th><th>pr<sub>s</sub></th><th>st<sub>s</sub></th><th>co<sub>w</sub></th><th>gr<sub>w</sub></th><th>pr<sub>w</sub></th><th>st<sub>w</sub></th></tr></thead><tbody><tr><td>I-max.</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Allow. abst.</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Crash resist.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Non inter.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Direct.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Weak Direct.</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Semi-Direct.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>**Fig. 3.** The IAF *I* and its completions $comp(I) = \{F_1^*, F_2^*, F_3^*, F_4^*\}$.</figcaption></figure>

# 5. Principle-based analysis of completion-based semantics

In the following section, we provide a comparison between our “direct” semantics and the classical approach based on completions. More precisely, we focus on the so-called *i*-extensions from [17]. We recall the definition of these semantics in Section 5.1, while in Section 5.2 and 5.3 we provide some results regarding the properties of these semantics.

## 5.1. Background on completion-based semantics

Most of the work on Incomplete Argumentation Frameworks and related frameworks are based on the notion of completions, i.e. standard argumentation frameworks representing possible scenarios compatible with the uncertain knowledge embedded in the IAFs.

**Definition 13.** Given $I = (A, A^?, R, R^?)$, the AF $F^? = (A^*, R^*)$ is a completion of *I* if and only if

$$ \cdot A \subseteq A^*, $$

$$ \cdot R \cap (A^* \times A^*) \subseteq R^* \subseteq (R \cup R^?) \cap (A^* \times A^*). $$

We write $comp(I)$ for the set of completions of an IAF $I$.

**Example 4.** Consider the IAF given in Fig. 3a. It has 4 completions, since each uncertain element (the argument $a_5$ and the attack $(a_3, a_4)$) has two possible options regarding its presence – or not – in the completion. We give all its completions (Figs. 3b-3e).

Given the set of completions of an IAF, one can determine its extensions by selecting the extensions which appear in each completion (this is the necessary view) or in at least one completion (this is the possible view).

**Definition 14.** Given an IAF $I = (A, A^?, R, R^?)$ and a semantics $\sigma$, the set of arguments $S \subseteq A \cup A^?$ is a necessary (respectively possible) *i*-extension of *I* with respect to $\sigma$ if and only if $S \in \sigma(F^*)$ for each (respectively for some) $F^* \in comp(I)$.
<table><caption>**Table 6**
Stable extensions of the four completions
$F_j^*, j \in \{1, 2, 3, 4\}$.</caption><thead><tr><th>$F_j^*$</th><th>st($F_j^*$)</th></tr></thead><tbody><tr><td>$F_1^*$</td><td>{$a_1, a_4, a_6, a_7$}}</td></tr><tr><td>$F_2^*$</td><td>{$a_1, a_4, a_6, a_7$}}</td></tr><tr><td>$F_3^*$</td><td>{$a_1, a_3, a_6, a_7$}, {$a_1, a_4, a_6, a_7$}}</td></tr><tr><td>$F_4^*$</td><td>{$a_1, a_3, a_6, a_7$}, {$a_1, a_4, a_6, a_7$}}</td></tr></tbody></table>

$i^*$-extensions were introduced in [17], which studied the extension verification problem for these semantics. We write $\sigma_x^*(I)$ for the set of necessary or possible $i^*$-extensions of $I$, where $x \in \{n, p\}$ stands for necessary or possible.

**Example 5.** For each completion $F_j^*, j \in \{1, 2, 3, 4\}$, we list its stable extensions in Table 6. We observe that one of these extensions is common to all the completions, but some extensions only appear in some completions. We deduce that the (necessary and possible) stable extensions of $I$ are $st_n^*(I) = \{\{a_1, a_4, a_6, a_7\}\}$, and $st_p^*(I) = \{\{a_1, a_3, a_6, a_7\}, \{a_1, a_4, a_6, a_7\}\}$.

## 5.2. Properties of necessary $i^*$-extensions

We start with an observation of a relation between the properties of AF semantics and IAF necessary semantics.

**Proposition 7.** Let $\sigma$ be an extension-based semantics for AFs, and $P$ a property of extension-based semantics. If $P$ is satisfied by the IAF semantics $\sigma_n^*$, then it is satisfied by the AF semantics $\sigma$.

From Proposition 7, we deduce that the properties unsatisfied by AF semantics are not satisfied by the corresponding IAF necessary semantics.

**Corollary 2.** *The following hold:*

* $co_n^*$ does not satisfy I-maximality,

* $pr_n^*$ does not satisfy allowing abstention,

* $st_n^*$ does not satisfy allowing abstention, crash resistance, non-interference, directionality and semi-directionality.

Now, regarding I-maximality, we show as a general result that its satisfaction by an AF semantics implies its satisfaction by the corresponding IAF necessary semantics.

**Proposition 8.** Let $\sigma$ be an extension-based semantics for AFs. If $\sigma$ satisfies I-maximality, then the semantics $\sigma_n^*$ for IAFs satisfies I-maximality.

We deduce the following result for the grounded, preferred and stable (necessary) semantics:

**Corollary 3.** $gr_n^*$, $pr_n^*$ and $st_n^*$ satisfy I-maximality.

We have already shown that preferred and stable necessary semantics to not satisfy allowing abstention. While this is still an open question for the complete semantics, we prove here that it is satisfied by the grounded necessary semantics.

**Proposition 9.** $gr_n^*$ satisfies allowing abstention.

Finally, crash resistance, non interference and directionality are also satisfied by the same semantics in the case of necessary semantics than in the case of standard AFs. Moreover, we show that if directionality is satisfied by an AF semantics, then it is satisfied as well by the corresponding IAF necessary semantics.

**Proposition 10.** For $\sigma \in \{\text{co}, \text{gr}, \text{pr}\}$, $\sigma_n^*$ satisfies crash resistance.

**Proposition 11.** Let $\sigma$ be an extension-based semantics for AFs. If $\sigma$ satisfies directionality, then the semantics $\sigma_n^*$ for IAFs satisfies directionality.

**Corollary 4.** For $\sigma \in \{\text{co}, \text{pr}, \text{gr}\}$, $\sigma_n^*$ satisfies directionality, hence it satisfies weak directionality, semi-directionality and non interference.
<caption>**Table 7**</caption>

Satisfaction (✓) or non-satisfaction (✗) of the principles for extension-based semantics of AFs [15] and completion-based IAFs semantics. Question marks indicate open questions.

<table><thead><tr><th>Principles</th><th>co</th><th>gr</th><th>pr</th><th>st</th><th>co<sup>*</sup><sub>n</sub></th><th>gr<sup>*</sup><sub>n</sub></th><th>pr<sup>*</sup><sub>n</sub></th><th>st<sup>*</sup><sub>n</sub></th><th>co<sup>*</sup><sub>p</sub></th><th>gr<sup>*</sup><sub>p</sub></th><th>pr<sup>*</sup><sub>p</sub></th><th>st<sup>*</sup><sub>p</sub></th></tr></thead><tbody><tr><td>I-max.</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Allow. abst.</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>?</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><td>Crash resist.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Non inter.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Direct.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td></tr><tr><td>Weak Direct.</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>?</td><td>✓</td><td>✓</td><td>✓</td><td>?</td></tr><tr><td>Semi-Direct.</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>?</td></tr></tbody></table>

### 5.3. Properties of possible i\*-extensions

A first observation regarding possible i\*-extensions is that single-status semantics (like the grounded semantics) may not remain so in this case.

**Example 6.** Continuing the previous example, we observe that $gr(F_1^*) = gr(F_2^*) = \{\{a_1, a_4, a_6, a_7\}\}$, and $gr(F_3^*) = gr(F_4^*) = \{\{a_1\}\}$, so $gr_p^*(I) = \{\{a_1, a_4, a_6, a_7\}, \{a_1\}\}$.

The semantics based on possible i\*-extensions do not satisfy I-maximality nor allowing abstention.

**Proposition 12.** For $\sigma \in \{\text{co}, \text{pr}, \text{gr}, \text{st}\}$, $\sigma_p^*$ does not satisfy I-maximality.

Easy counter-examples can be given to show that. For instance, consider the IAF made only of one certain argument *a* and one uncertain argument *b*. The completions are the AFs containing either only *a*, or both *a* and *b*, with no attacks. So the extensions are $\{\{a\}, \{a, b\}\}$ for all considered semantics, hence the non-satisfaction of I-maximality.

**Proposition 13.** For $\sigma \in \{\text{co}, \text{pr}, \text{gr}, \text{st}\}$, $\sigma_p^*$ does not satisfy allowing abstention.

The counter-example is similar to the one for I-maximality, we only need to consider also an attack from *b* to *a*. This time, the extensions are $\{\{a\}, \{b\}\}$, with the first extension containing *a* and the second extension attacking *a*, but no third extension allowing abstention.

For the other properties, their satisfaction is in line with standard results.

**Proposition 14.** For $\sigma \in \{\text{co}, \text{gr}, \text{pr}\}$, $\sigma_p^*$ satisfies crash resistance. $st_p^*$ does not satisfy it.

The fact that $st_p^*$ does not satisfy crash resistance induces that it does not satisfy non-interference and directionality.

**Corollary 5.** $st_p^*$ does not satisfy non-interference and directionality.

**Proposition 15.** Let $\sigma$ be an extension-based semantics for AFs. If $\sigma$ satisfies directionality, then the semantics $\sigma_p^*$ for IAFs satisfies directionality.

As usual, the satisfaction of directionality implies the satisfaction of several weaker properties.

**Corollary 6.** For $\sigma \in \{\text{co}, \text{pr}, \text{gr}\}$, $\sigma_p^*$ satisfies directionality, hence it satisfies weak directionality, semi-directionality and non interference.

### 5.4. Summary

Table 7 summarizes our results regarding the properties of completion-based semantics of Incomplete Argumentation Frameworks. While in most cases, the properties of the semantics coincide with the properties of their counterparts for standard AFs, an important difference between the necessary and possible families of semantics can be observed with the results for I-maximality and allowing abstention, which are never satisfied for the possible family.

A few questions remain open, regarding the weak and semi-directionality of the variants of stable semantics and allowing abstention for the necessary complete semantics.
## 6. Related work

The original work on Incomplete AFs was actually only limited to uncertainty regarding the attacks, i.e. focusing on IAFs with $A^? = \emptyset$. This framework, coined *Partial AF*, was initially proposed as a tool in a merging process for standard AFs [6]. Then, “direct” extension-based semantics for these Partial AFs were proposed in [7], where several variants of admissibility and preferred semantics were defined for this framework.

Then, various works by Baumeister and colleagues have generalized the Partial AFs into Incomplete AFs, adding the possibility to have uncertain arguments as well [21,8]. These works mainly focus on the complexity of various decision problems as well as SAT-based computational approaches, but do not study the principles of the IAF semantics. In particular, the notion of (possible or necessary) extension-based semantics that can be derived from the extension verification problem defined in [21] is different from what we have studied here. Indeed, for them, a possible extension of the IAF is a set of arguments $S$ such that $S \cap A^*$ is an extension of some completion $F^* = \langle A^*, R^* \rangle$. This implies that possible extensions, following this definition, can have different properties than expected (e.g. a set $S = \{a, b\}$ with $(a, b) \in R$ can be a possible extension because $S \cap \{a\}$ is an extension of a completion where $A^* = \{a\}$). For this reason, so-called $i^*$-extensions have been defined by [17]. We use their notion of extension in Section 5. In this work, they define the necessary and possible extensions as we have used them in this paper, and they show how the modified definition impacts the complexity of reasoning, compared to the previous work from [21]. In [22,23], the authors define three new properties of IAFs, namely *totality* (the fact that a given argument is never undecided for any extension of any completion, i.e. it belongs or is attacked by every extension), *determinism* (the fact that a given argument has the same status for every extension of every completion) and *functionality* (the combination of totality and determinism). They provide complexity results for these problems under several classical semantics.

The authors of [24] study arguments acceptability in probabilistic argumentation frameworks, and show a correspondence between reasoning with an IAF and reasoning with a probabilistic AF where all uncertain elements have a probability of 0.5.

Finally, the recent works by [25–27] define *Incomplete Bipolar Argumentation Frameworks* (IBAFs), where IAFs are combined with Bipolar AFs [28]. They provide complexity results under classical decision problems that have been adapted from IAFs to IBAFs (notably, credulous and skeptical acceptability of arguments with respect to some or each possible completion of the IBAF). Moreover, [27] shows that taking into account the meaning of the notion of support (e.g. necessary [29], deductive [30]) can be done by adapting the notion of completion, which can have an impact on the complexity of reasoning.

None of these existing works on completion-based semantics provided a principle-based analysis like the one we provide here.

## 7. Conclusion

This paper describes new results on a new family of reasoning approaches for Incomplete Argumentation Frameworks (IAFs), inspired by the original semantics for Partial AFs, a subclass of IAFs. We have shown that Dung’s grounded semantics can be adapted to IAFs in two variants, namely weak and strong grounded semantics. As it is usually the case, reasoning with such semantics is doable in polynomial time. Then, we have established which principles from the literature are satisfied by our new semantics, as well as the extension-based semantics for IAFs defined in previous work. Finally, we have also studied the existing “completion-based” semantics of IAFs in the light of these principles.

We envision several research tracks for future work, the first one being to fill the remaining gaps in the principle-based analysis of the completion-based approach, i.e. removing the question marks in Table 7. Also, it would be interesting to study whether there are connections between the acceptability of argument with respect to our semantics and their status with respect to completion-based reasoning methods. Then, we wish to determine whether applying our semantics in a context of controllability [31,32] or automated negotiation [10] can bring some advantage e.g., thanks to their complexity. Indeed, adapting the negotiation protocol from [10] to use lower complexity semantics could have a practical impact if the negotiations are time-constrained. Also, it would be interesting to parameterize the weak semantics by the number of uncertain conflicts that can be contained in a weak extension, in a way in the same spirit as weighted argumentation frameworks [3].

Finally, in line with the recent definition of the Incomplete Bipolar Argumentation Frameworks [25–27], we wish to determine if it is possible to define a “direct” approach for reasoning with various kinds of supports without relying on completions.

### CRediT authorship contribution statement

Jean-Guy Mailly: Writing – review & editing, Writing – original draft, Formal analysis, Conceptualization.

### Declaration of competing interest

The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Jean-Guy Mailly reports financial support was provided by French National Research Agency. If there are other authors, they declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

### Data availability

No data was used for the research described in the article.
Acknowledgement

This work benefited from the support of the projects AGGREEY (ANR-22-CE23-0005) and AIDAL (ANR-22-CPJ1-0061-01) of the French National Research Agency (ANR).

**Appendix A. Proofs of Section 3**

**Lemma 1.** Given an IAF $I = \langle \mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2 \rangle$, $x \in \{w, s\}$ and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$, if $S \in \mathrm{cf}_x(I)$ then $\Gamma_{x,I}(S) \in \mathrm{cf}_x(I)$.

**Proof.** Assume that $S \in \mathrm{cf}_w(I)$, i.e. $\forall a, b \in S \cap \mathcal{A}$, $(a, b) \notin \mathcal{R}$. Now consider $S' = \Gamma_{w,I}(S)$, and reasoning towards a contradiction assume that $S' \notin \mathrm{cf}_w(I)$, i.e. $\exists a, b \in S' \cap \mathcal{A}$ such that $(a, b) \in \mathcal{R}$. Since $S$ weakly defends $b$, there is $c \in S \cap \mathcal{A}$ such that $(c, a) \in \mathcal{R}$. Then, since $S$ weakly defends $a$, there is $d \in S \cap \mathcal{A}$ such that $(d, c) \in \mathcal{R}$. Hence $S$ is not weakly conflict-free, which contradicts the hypothesis. So $S' = \Gamma_{w,I}(S)$ is weakly conflict-free.

Now we do a similar reasoning for strong conflict-freeness. Assume that $S \in \mathrm{cf}_s(I)$, meaning that $\forall a, b \in S$, $(a, b) \notin \mathcal{R} \cup \mathcal{R}^2$. Considering $S' = \Gamma_{s,I}(S)$, assume that $S'$ is not strongly conflict-free, i.e. there are $a, b \in S'$ such that $(a, b) \in \mathcal{R} \cup \mathcal{R}^2$. Since $S$ strongly defends $b$, there is $c \in S \cap \mathcal{A}$ such that $(c, a) \in \mathcal{R}$, and then since $S$ strongly defends $a$ there is $d \in S \cap \mathcal{A}$ such that $(d, c) \in \mathcal{R}$. So $S$ is not strongly conflict-free, which is a contradiction. □

**Lemma 2.** Given an IAF $I = \langle \mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2 \rangle$, $x \in \{w, s\}$, and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$ such that $S \in \mathrm{cf}_x(I)$, $S \in \mathrm{ad}_x(I)$ if and only if $S \subseteq \Gamma_{x,I}(S)$.

**Proof.** The proof is obvious. For the first direction of the equivalence, if $S \in \mathrm{ad}_x(I)$ then $S$ x-defends all its elements, which means that $S$ is included in $\Gamma_{x,I}(S)$. For the other direction, since $S$ is x-conflict-free (from Lemma 1) and x-defends all its elements, it is x-admissible. □

**Lemma 3.** Given an IAF $I = \langle \mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2 \rangle$, $x \in \{w, s\}$, and $S \subseteq \mathcal{A} \cup \mathcal{A}^2$ such that $S \in \mathrm{cf}_x(I)$, $S \in \mathrm{co}_x(I)$ if and only if $S = \Gamma_{x,I}(S)$.

**Proof.** The proof follows Lemma 2 and the definition of x-complete extensions. □

**Lemma 4.** Given an IAF $I = \langle \mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2 \rangle$, $x \in \{w, s\}$, and two sets of arguments $S, S' \subseteq \mathcal{A} \cup \mathcal{A}^2$ such that $S, S'$ are x-conflict-free, if $S \subseteq S'$ then $\Gamma_{x,I}(S) \subseteq \Gamma_{x,I}(S')$.

**Proof.** Assume that $S, S'$ are x-conflict-free sets such that $S \subseteq S'$. Now consider $a \in \Gamma_{x,I}(S)$, and let us prove that $a \in \Gamma_{x,I}(S)$.

First, consider the case where $x = w$. Since $S$ weakly defends $a$, for all $b \in \mathcal{A}$ such that $(b, a) \in \mathcal{R}$, there is $c \in S \cap \mathcal{A}$ such that $(c, b) \in \mathcal{R}$. Since $S \subseteq S'$, obviously there is no certain argument in $S'$ which certainly attacks $a$ (otherwise, there would be a contradiction either with the fact that $S$ weakly defends $a$, or with the fact that $S'$ is weakly conflict-free). So $S'$ weakly defends $a$, and we can conclude that $\Gamma_{w,I}(S) \subseteq \Gamma_{w,I}(S')$.

Now consider $x = s$. Since $S$ strongly defends $a$, for all $b \in \mathcal{A} \cup \mathcal{A}^2$ such that $(b, a) \in \mathcal{R} \cup \mathcal{R}^2$, there is $c \in S \cap \mathcal{A}$ such that $(c, b) \in \mathcal{R}$. Since $S \subseteq S'$ and $S'$ is strongly conflict-free, there is no argument in $S'$ which attacks $a$, for similar reasons to the previous case $x = w$. So $S'$ strongly defends $a$, and $\Gamma_{s,I}(S) \subseteq \Gamma_{s,I}(S')$. □

**Proposition 1.** For $x \in \{w, s\}$, the problems gr<sub>x</sub>-Ver, gr<sub>x</sub>-Cred and gr<sub>x</sub>-Skep are P-complete, gr<sub>x</sub>-Exist is trivial, and gr<sub>x</sub>-NE is in L.

**Proof.** P-membership is obvious, since the unique x-grounded extension $S$ can be computed in polynomial time using Algorithm 1. Then, it can be checked in polynomial time whether the given set is equal to $S$ (for gr<sub>x</sub>-Ver), or whether the given argument belongs to $S$ (for gr<sub>x</sub>-Cred and gr<sub>x</sub>-Skep). For gr<sub>x</sub>-Exist, any *I* has exactly one x-grounded extension, so it is trivial. Finally, gr<sub>x</sub>-NE can be solved by checking, for each argument, whether it needs to be x-defended or not. As soon as some argument does not need to be x-defended, the answer to gr<sub>x</sub>-NE is YES. This check can be done in polynomial time and logarithmic space, hence the result.

Finally, P-hardness for gr<sub>x</sub>-Ver, gr<sub>x</sub>-Cred and gr<sub>x</sub>-Skep come from the hardness of the corresponding problems for the grounded semantics of AFs [18], and the fact that any AFI $\langle \mathcal{A}, \emptyset, \mathcal{R}, \emptyset \rangle$ is an IAF $\langle \mathcal{A}, \emptyset, \mathcal{R}, \emptyset \rangle$. A similar transformation is used for proving hardness results in the case of other semantics [11,12]. □

**Appendix B. Proofs of Section 4**

**Proposition 2.** *I*-maximality is satisfied by st<sub>s</sub> as well as pr<sub>x</sub> and gr<sub>x</sub> for $x \in \{w, s\}$. It is not satisfied by co<sub>x</sub> for $x \in \{w, s\}$, nor by st<sub>w</sub>.

**Proof.** For pr<sub>x</sub>, this is obvious by definition of the semantics. Similarly, since gr<sub>x</sub> only contains a single extension, it is obviously minimal. For the co<sub>x</sub> semantics, it does not work because there are examples of IAFs with several co<sub>x</sub> extensions, including one of them which is included in all the other ones (the gr<sub>x</sub> extension). It works for the st<sub>s</sub> semantics because st<sub>s</sub>(I) ⊆ pr<sub>s</sub>(I) for any IAF.
Finally, for $st_w$, consider $I = \{(a), \{b,c\}, \{(b,c), (c,b)\}, \emptyset\}$. Its extensions are $st_w(I) = \{{\{a\}}, \{a,b\}, \{a,c\}, \{a,b,c\}\}$, so obviously it is not $I$-maximal. $\square$

**Proposition 3.** For $x \in \{w, s\}$, $gr_x$ satisfies allowing abstention. For $\sigma \in \{pr, st\}$ and $x \in \{w, s\}$, $\sigma_x$ does not satisfy allowing abstention. Finally, $co_s$ satisfies it, and $co_w$ does not satisfy it.

**Proof.** Consider first $co_s$. Assume an argument $a \in A \cup A^?$ such that $a \in S_1$ and $a \in S_2^+$, for $S_1, S_2 \in co_s(I)$. Let us call $S_3$ the unique $gr_s$-extension. Since $a$ is attacked by $S_2$, $a \notin S_3$. Similarly, since $a \in S_1$, $a$ is not attacked by $S_3$. This proves the result for $co_s$. For $co_w$, a counterexample is the IAF $I = \{(a,d), \{b,c\}, \{(a,d), (d,a), (b,c), (c,b), (b,a)\}, \emptyset\}$. Its extensions are $co_w(I) = \{{\{b,c\}}, \{a,b,c\}, \{d,b,c\}\}$, so e.g. $a$ belongs to some extension and is attacked by all the other ones, there is no possible abstention.

The result is obvious of $gr_x$.

Finally, consider the IAF $I = \{(a,b), \emptyset, \{(a,b), (b,a)\}, \emptyset\}$, i.e. there are only two certain arguments $a$ and $b$ which certainly attack each other. For any $\sigma \in \{pr, st\}$ and $x \in \{w, s\}$, there are exactly two $\sigma_x$-extensions $\sigma_x(I) = \{{\{a\}}, \{b\}\}$, so obviously $\sigma_x$ does not satisfy allowing abstention. $\square$

**Proposition 4.** For $\sigma \in \{co, pr, gr\}$ and $x \in \{w, s\}$, $\sigma_x$ satisfies crash resistance. For $x \in \{w, s\}$, $st_x$ does not satisfy crash resistance.

**Proof.** For the weak and strong stable semantics, the usual counterexample still works. Consider $I^* = \{(a), \emptyset, \{(a,a)\}, \emptyset\}$, i.e. it is made of a single self-contradictory argument. $I^*$ does not have any weak or strong stable extension. It is also the case for $I \sqcup I^*$, for any $I$. This means that $I^*$ is contaminating for weak and strong stable semantics. For the other semantics, one can combine an extension of $I_1$ with and extension of $I_2$ to obtain an extension of $I_1 \sqcup I_2$, so there cannot be a contaminating IAF. $\square$

**Proposition 5.** For $\sigma \in \{co, pr, gr\}$ and $x \in \{w, s\}$, $\sigma_x$ satisfies non-interference. For $x \in \{w, s\}$, $st_x$ does not satisfy non-interference.

**Proof.** The case of $st_x$ is obvious: consider the IAF $I = \langle A, A^?, R, R^? \rangle$ with $A = \{a, b\}$, $R = \{(a, a)\}$, and $A^? = R^? = \emptyset$. In this case, weak and strong stable semantics coincide with the stable semantics of standard AFs, so there is no $x$-stable extension for $I$, but there is one for $I_{\downarrow\{b\}}$.

Now consider the case of $\sigma = co_x$, and $E \in co_x(I)$. Since $E$ is $x$-conflict-free, $E \cap S$ is obviously $x$-conflict-free as well. Moreover, since $E$ $x$-defends all its elements and $S$ is an isolated set, if there is an argument in $S$ attacking an argument in $E \cap S$, then there is necessarily an argument in $E \cap S$ which $x$-defends the attacked argument. Finally, since $E$ does not $x$-defend any argument outside of $E$ and $S$ is an isolated set of arguments, then, $E \cap S$ does not $x$-defend any argument outside of it. So $E \cap S \in co_x(I_{\downarrow S})$, and we obtain $\{E \cap S \mid E \in co_x(I)\} \subseteq co_x(I_{\downarrow S})$. Let us show the second inclusion. Consider $E' \in co_x(I_{\downarrow S})$. By definition, $E'$ is $x$-conflict-free and $x$-defends all its elements in $I_{\downarrow S}$. Since $S$ is an isolated set in $I$, none of its elements is attacked by arguments of $(A \cup \text{arg}^?) \setminus S$, so $E'$ also $x$-defends all its elements in $I$. This means that $E'$ is $x$-admissible in $I$, and so there exists $E$ a $x$-preferred extension of $I$ such that $E' \subseteq E$, with $E' = E \cap S$. Since $E$ is a $x$-complete extension of $I$, we deduce the result.

Now focus on the case of $x$-preferred semantics. Let us consider $E \in pr_x(I)$. We know that $E \in co_x(I)$ as well, so following the previous result we know that $E \cap S \in co_x(I_{\downarrow S})$. Towards a contradiction, assume that $E \cap S \notin pr_x(I_{\downarrow S})$. This means that there is $E' \in pr_x(I_{\downarrow S})$ such that $E \cap S \subset E'$. We write $E'' = E' \setminus (E \cap S)$. The set $E \cup E''$ is a strict superset of $E$, and it is an admissible set in $I$. So $E \notin pr_x(I)$, which is a contradiction. We can thus conclude that $E \cap S \notin pr_x(I_{\downarrow S})$, and we obtain the first inclusion $\{E \cap S \mid E \in pr_x(I)\} \subseteq pr_x(I_{\downarrow S})$. For the second inclusion, consider $E' \in pr_x(I_{\downarrow S})$. By definition, $E' \in co_x(I_{\downarrow S})$ as well, and so following the previous result we know that there is $E \in co_x(I)$ such that $E \cap S = E'$. If $E$ is also a $x$-preferred extension of $I$, we obtain the result. Otherwise, it is possible to find a strict superset $E''$ of $E$ such that $E''$ is a $x$-preferred extension of $I$, and again we can observe that $E'' \cap S = E$, hence the result.

Finally, consider $E = gr_x(I)$ the $x$-grounded extension of the IAF. It is a $x$-complete extension, so we know that $E \cap S$ is a $x$-complete extension of $I_{\downarrow S}$. Towards a contradiction, assume that it is not the $\subseteq$-minimal one, i.e. there is $E' \subset (E \cap S)$ a $x$-complete extension of $I_{\downarrow S}$. Let $a \in (E \cap S) \setminus E'$ be an argument from $E \cap S$ not belonging to this new extension $E'$. This means that $E'$ does not $x$-defend $a$ in $I_{\downarrow S}$. Now, considering $I$, $E'$ is included in a $x$-complete extension $E''$ (following the previous result for $x$-complete semantics), but this $E''$ does not defend $a$ (again, this can be deduced from the fact that $S$ is an isolated set), so $a \notin E''$. So, we have exhibited an argument belonging to the $x$-grounded extension of $I$, which does not belong to some $x$-complete extension. This is a contradiction, so we can conclude that $E \cap S$ is the $x$-grounded extension of $I_{\downarrow S}$. Now, let us prove that the other inclusion also holds. Consider $E'$ the $x$-grounded extension of $I_{\downarrow S}$. $E'$ is included in all the $x$-complete extensions $E''$ of $I_{\downarrow S}$, and each of them is included in a $x$-complete extension $E$ of $I$. So $E'$ is included in all the $x$-complete extensions of $I$, including the $x$-grounded extension $E$, and since $S$ is an isolated set we have $E \cap S = E'$, hence the result. $\square$

**Proposition 6.** For $\sigma \in \{co, pr, gr\}$ and $x \in \{w, s\}$, $\sigma_x$ satisfies directionality. For $x \in \{w, s\}$, $st_x$ does not satisfy directionality nor semi-directionality. $st_x$ satisfies weak directionality.

**Proof.** Consider an unattacked set $S \in \mathcal{U}S(I)$. Now consider a weak complete extension $E \in co_w(I)$, and let us prove that $E \cap S \in co_w(I_{\downarrow S})$. Obviously, $E \cap S$ is weakly conflict-free. Then, since $E$ weakly defends all its elements in $I$, when we restrict the IAF to $I_{\downarrow S}$, any $a \in S$ which attacks an element from $E$ has to be counterattacked by some $b \in E \cap S$ (because $E$ weakly defends all its
elements, and since $S$ is unattacked no $b \in E \setminus S$ can attack a). So $E \cap S$ is weakly admissible. Finally, it is obvious that $E \cap S$ does not weakly defend any argument outside of it, since $E$ does not (more precisely, if $E \cap S$ defends some outsider arguments, then they belong to $E \setminus S$ and thus they are not in the restricted IAF $I_{\downarrow S}$). So $E \cap S$ is a weak complete extension of $I_{\downarrow S}$. This proves that $\co_w(I_{\downarrow S}) \supseteq \{E \cap S \mid E \in \co_w(I)\}$. Now let us consider some $E_{\downarrow} \in \co_w(I_{\downarrow S})$. By defining, $E_{\downarrow}$ is weakly admissible in $I_{\downarrow S}$, and since $S$ is unattacked then $E_{\downarrow}$ is not attacked by any argument in $(A \cup A') \setminus S$. So $E_{\downarrow}$ is weakly admissible in $I$, and thus it is included in a weak preferred extension $E$ of $I$. By definition, $E$ is also a weak complete extension of $I$. So we have $E_{\downarrow} = E \cap S$. This shows that $\co_w(I_{\downarrow S}) \subseteq \{E \cap S \mid E \in \co_w(I)\}$. We conclude that the weak complete semantics satisfies directionality.

We can observe that the previous reasoning holds with strong complete semantics as well.

Now we consider a weak preferred extension $E \in \mathrm{pr}_w(I)$, and let us prove that $E \cap S \in \mathrm{pr}_w(I_{\downarrow S})$. The result follows the fact that the weak complete semantics satisfies directionality: since $E$ is a weak complete extension, $E \cap S$ is a weak complete extension of $I_{\downarrow S}$. Assuming that $E \cap S$ is not a weak preferred extension of $I_{\downarrow S}$, this means that some argument $a \in S \setminus E$ must exist such that $(E \cap S) \cup \{a\}$ is weakly admissible in the restricted IAF, and then $E \cup \{a\}$ is admissible in the initial IAF, which is contradictory with the fact that $E$ is a weak preferred extension. So $\mathrm{pr}_w(I_{\downarrow S}) \supseteq \{E \cap S \mid E \in \mathrm{pr}_w(I)\}$. The other inclusion is even more straightforward, since the same reasoning as in the weak complete semantics case can be used. Finally, notice that this reasoning holds for the strong preferred semantics as well. So both the weak and strong preferred semantics satisfy directionality.

Focusing on the x-grounded semantics, reasoning follows from the previous result for the x-complete semantics, and is analogous to the reasoning for the non-interference principle.

Finally, for the x-stable semantics, the same counterexample as in the case of non-interference can be used. Assume an IAF made of two certain arguments, $a$ and $b$, with the only attack being $(a, a)$. The set $S = \{b\}$ is unattacked but the extensions of the IAF restricted to $S$ (i.e. $\mathrm{st}_x(I_{\downarrow S}) = \{\{b\}\}$) are not in correspondence with the extensions of the original IAF (which does not have any x-stable extension). So it does not satisfy directionality.

Now we prove the result for weak directionality and $\mathrm{st}_w$. First, assume that $E \in \mathrm{st}_w(I)$ and $S \in \mathcal{U}S(I)$. We need to prove that $E \cap S \in \mathrm{st}_w(I_{\downarrow S})$. Obviously, since $E$ is weakly conflict-free, any of its subsets is weakly conflict-free, so $E \cap S$ is weakly conflict-free. Then, we know that $\forall a \in A \setminus E, \exists b \in E \cap A$ such that $(b, a) \in R$. So, when we restrict to $I_{\downarrow S}$, let $a \in (A \cap S) \setminus (E \cap S)$ be an argument in the restricted $I$ that does not belong to $E \cap S$. Obviously, since $a \notin E$ and $E$ is weakly stable, there is an argument $b \in E \cap A$ attacking $a$. And since $S$ is an unattacked set, this argument $b$ cannot be outside of $S$. So we prove that $\exists b \in E \cap S \cap A$ such that $(b, a) \in R$. This reasoning holds for any $a \in (A \cap S) \setminus (E \cap S)$, so $E \in \mathrm{st}_w(I_{\downarrow S})$, and we conclude that $\mathrm{st}_w$ satisfies weak directionality. In turn, since $\mathrm{st}_w$ does not satisfy directionality, it does not satisfy semi-directionality.

The reasoning is analogous for strong stable semantics. ☐

# Appendix C. Proofs for Section 5

## C.1. Necessary i\*-extensions

**Proposition 7.** Let $\sigma$ be an extension-based semantics for AFs, and $\mathcal{P}$ a property of extension-based semantics. If $\mathcal{P}$ is satisfied by the IAF semantics $\sigma_n^*$, then it is satisfied by the AF semantics $\sigma$.

**Proof.** It comes from the fact that an AF $\mathcal{F} = \langle A, \mathcal{R} \rangle$ is a particular IAF $I_{\mathcal{F}} = \langle A, \emptyset, \mathcal{R}, \emptyset \rangle$ with a single completion equal to $\mathcal{F}$, so if $\mathcal{P}$ holds for the necessary extensions of $I_{\mathcal{F}}$, it holds for the (standard) extensions of $\mathcal{F}$. ☐

**Proposition 8.** Let $\sigma$ be an extension-based semantics for AFs. If $\sigma$ satisfies I-maximality, then the semantics $\sigma_n^*$ for IAFs satisfies I-maximality.

**Proof.** From the definition, $\sigma_n^*(I) \subseteq \sigma(F^*)$ for each $F^* \in \mathrm{comp}(I)$. Since $\sigma$ satisfies I-maximality, there are no $S, S' \in \sigma(F^*)$ such that $S \subset S'$, hence the result. ☐

**Proposition 9.** $\mathrm{gr}_n^*$ satisfies allowing abstention.

**Proof.** Since there is a single grounded extension for each completion, two options are possible regarding $\mathrm{gr}_n^*$: either all the completions have the same grounded extension, which is also the unique necessary grounded extension of the IAF; or they do not all have the same grounded extension, in which case $\mathrm{gr}_n^*(I) = \emptyset$. In both cases, allowing abstention is trivially satisfied, like in the case of AFs. ☐

**Proposition 10.** For $\sigma \in \{\mathrm{co}, \mathrm{gr}, \mathrm{pr}\}$, $\sigma_n^*$ satisfies crash resistance.

**Proof.** For any of the considered semantics and any disjoint IAFs $I_1, I_2$, we can combine a necessary $\sigma$-extension of $I_1$ and a necessary $\sigma$-extension of $I_2$ to form a necessary extension of $I_1 \sqcup I_2$, so there cannot be a contaminating $I$. ☐

**Proposition 11.** Let $\sigma$ be an extension-based semantics for AFs. If $\sigma$ satisfies directionality, then the semantics $\sigma_n^*$ for IAFs satisfies directionality.
**Proof.** Recall that $\sigma_n^*(I) = \bigcap_{F^* \in \text{comp}(I)} \sigma(F^*)$. If $\sigma$ satisfies directionality, then for any completion $\mathcal{F}^*$, and any $S \in \mathcal{V}S(F^*)$, $\sigma(F_{\downarrow S}^*) = \{E \cap S | E \in \sigma(F^*)\}$.

We can observe that unattacked sets of an IAF are unattacked in each of its completions as well. Also, the completions of the reduced IAF $I_{\downarrow S}$ are the completions of $I$ reduced to $S$, i.e. $\text{comp}(I_{\downarrow S}) = \{\mathcal{F}_{\downarrow S}^* | \mathcal{F}^* \in \text{comp}(I)\}$.

Now consider $S \in \mathcal{V}S(I)$, and $\sigma_n^*(I_{\downarrow S}) = \bigcap_{F^* \in \text{comp}(I_{\downarrow S})} \sigma(F^*)$. From the previous observation, $\sigma_n^*(I_{\downarrow S}) = \bigcap_{F_{\downarrow S}^* \text{ s.t. } F^* \in \text{comp}(I)} \sigma(F_{\downarrow S}^*)$. From $\sigma$ satisfying directionality, we obtain $\sigma_n^*(I_{\downarrow S}) = \bigcap_{F_{\downarrow S}^* \text{ s.t. } F^* \in \text{comp}(I)} \{E \cap S | E \in \sigma(F_{\downarrow S}^*)\}$, hence $\sigma_n^*(I_{\downarrow S}) = \{E \cap S | E \in \sigma(I_{\downarrow S}^*)\}$, so $\sigma_n^*$ satisfies directionality. $\square$

### C.2. Possible $i^*$-extensions

**Proposition 12.** For $\sigma \in \{\text{co}, \text{pr}, \text{gr}, \text{st}\}$, $\sigma_p^*$ does not satisfy I-maximality.

**Proof.** Consider the IAF $I = \{(a), \{b\}, \emptyset, \emptyset\}$. It has two completions, one of them containing only the argument $a$, the other one containing both $a$ and $b$. In both cases there are no attacks. So for all the considered semantics, there are two possible $i^*$-extensions: $\{a\}$ and $\{a, b\}$. So the semantics does not satisfy I-maximality. $\square$

**Proposition 13.** For $\sigma \in \{\text{co}, \text{pr}, \text{gr}, \text{st}\}$, $\sigma_p^*$ does not satisfy allowing abstention.

**Proof.** Consider the IAF $I = \{(a), \{b\}, \{(b, a)\}, \emptyset\}$. It has two completions, one of them containing only the argument $a$, the other one containing both $a$ and $b$. In the first case there are no attacks, in the second case there is an attack from $b$ to $a$. So for all the considered semantics, there are two possible $i^*$-extensions: $\{a\}$ (which contains $a$) and $\{b\}$ (which attacks $a$), but there is no extension such that $a$ is neither in it nor attacked by it. So the semantics does not satisfy allowing abstention. $\square$

**Proposition 14.** For $\sigma \in \{\text{co}, \text{gr}, \text{pr}\}$, $\sigma_p^*$ satisfies crash resistance. $\text{st}_p^*$ does not satisfy it.

**Proof.** For $\sigma \in \{\text{co}, \text{gr}, \text{pr}\}$ and any disjoint IAFs $I_1, I_2$, we can combine a possible $\sigma$-extension of $I_1$ and a possible $\sigma$-extension of $I_2$ to form a possible extension of $I_1 \sqcup I_2$, so there cannot be a contaminating $I$.

For $\text{st}_p^*$, the usual example works: the IAF $I^* = \{(a), \emptyset, \{(a, a)\}, \emptyset\}$ is a contaminating IAF, since $\text{st}_p^*(I \cup I^*) = \emptyset = \text{st}_p(I^*)$ for any $I$. $\square$

**Proposition 15.** Let $\sigma$ be an extension-based semantics for AFs. If $\sigma$ satisfies directionality, then the semantics $\sigma_p^*$ for IAFs satisfies directionality.

**Proof.** Recall that $\sigma_p^*(I) = \bigcup_{F^* \in \text{comp}(I)} \sigma(F^*)$. If $\sigma$ satisfies directionality, then for any completion $\mathcal{F}^*$, and any $S \in \mathcal{V}S(F^*)$, $\sigma(F_{\downarrow S}^*) = \{E \cap S | E \in \sigma(F^*)\}$.

We can observe that unattacked sets of an IAF are unattacked in each of its completions as well. Also, the completions of the reduced IAF $I_{\downarrow S}$ are the completions of $I$ reduced to $S$, i.e. $\text{comp}(I_{\downarrow S}) = \{\mathcal{F}_{\downarrow S}^* | \mathcal{F}^* \in \text{comp}(I)\}$.

Now consider $S \in \mathcal{V}S(I)$, and $\sigma_p^*(I_{\downarrow S}) = \bigcup_{F^* \in \text{comp}(I_{\downarrow S})} \sigma(F^*)$. From the previous observation, $\sigma_p^*(I_{\downarrow S}) = \bigcup_{F_{\downarrow S}^* \text{ s.t. } F^* \in \text{comp}(I)} \sigma(F_{\downarrow S}^*)$. From $\sigma$ satisfying directionality, we obtain $\sigma_p^*(I_{\downarrow S}) = \bigcup_{F_{\downarrow S}^* \text{ s.t. } F^* \in \text{comp}(I)} \{E \cap S | E \in \sigma(F_{\downarrow S}^*)\}$, hence $\sigma_p^*(I_{\downarrow S}) = \{E \cap S | E \in \sigma(I_{\downarrow S}^*)\}$, so $\sigma_p^*$ satisfies directionality. $\square$

### References

[1] P.M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artif. Intell. 77 (1995) 321–358.

[2] L. Amgoud, C. Cayrol, M. Lagasquie-Schiex, P. Livet, On bipolarity in argumentation frameworks, Int. J. Intell. Syst. 23 (2008) 1062–1093.

[3] P.E. Dunne, A. Hunter, P. McBurney, S. Parsons, M.J. Wooldridge, Weighted argument systems: basic definitions, algorithms, and complexity results, Artif. Intell. 175 (2011) 457–486.

[4] J. Rossit, J.-G. Mailly, Y. Dimopoulos, P. Moraitis, United we stand: accruals in strength-based argumentation, Argument Comput. 12 (2021) 87–113.

[5] L. Amgoud, C. Cayrol, A reasoning model based on the production of acceptable arguments, Ann. Math. Artif. Intell. 34 (2002) 197–215.

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

[7] C. Cayrol, C. Devred, M. Lagasquie-Schiex, Handling ignorance in argumentation: semantics of partial argumentation frameworks, in: 9th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2007), 2007, pp. 259–270.

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

[9] Y. Dimopoulos, J.-G. Mailly, P. Moraitis, Argumentation-based negotiation with incomplete opponent profiles, in: 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019), 2019, pp. 1252–1260.

[10] J. Dimopoulos, J.-G. Mailly, P. Moraitis, Arguing and negotiating using incomplete negotiators profiles, Auton. Agents Multi-Agent Syst. 35 (2021).

[11] J.-G. Mailly, Extension-based semantics for incomplete argumentation frameworks, in: Logic and Argumentation - 4th International Conference, CLAR 2021, Hangzhou, China, October 20-22, 2021, Proceedings, 2021, pp. 322–341.

[12] J.-G. Mailly, Extension-based semantics for incomplete argumentation frameworks: properties, complexity and algorithms, J. Log. Comput. 33 (2023) 406–435.

[13] P. Baroni, M. Giacomini, On principle-based evaluation of extension-based argumentation semantics, Artif. Intell. 171 (2007) 675–700, https://doi.org/10.1016/j.artint.2007.04.004.
[14] P. Baroni, M. Caminada, M. Giacomini, An introduction to argumentation semantics, Knowl. Eng. Rev. 26 (2011) 365-410.

[15] L. van der Torre, S. Vesic, The principle-based approach to abstract argumentation semantics, in: P. Baroni, D. Gabbay, M. Giacomini, L. van der Torre (Eds.), Handbook of Formal Argumentation, College Publications, 2018, pp. 797-837.

[16] J. Mailly, Extension-based semantics for incomplete argumentation frameworks: grounded semantics and principles, in: Z. Bouraoui, S. Vesic (Eds.), Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 17th European Conference, ECSQARU 2023, Arras, France, September 19-22, 2023, Proceedings, in: Lecture Notes in Computer Science, vol. 14294, Springer, 2023, pp. 84-94.

[17] B. Fazzinga, S. Flesca, F. Furfaro, Revisiting the notion of extension over incomplete abstract argumentation frameworks, in: 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), 2020, pp. 1712-1718.

[18] W. Dvorák, P.E. Dunne, Computational problems in formal argumentation and their complexity, in: P. Baroni, D. Gabbay, M. Giacomini, L. van der Torre (Eds.), Handbook of Formal Argumentation, College Publications, 2018, pp. 631-688.

[19] J.-G. Mailly, Yes, no, maybe, I don't know: complexity and application of abstract argumentation with incomplete knowledge, Argument Comput. 13 (2022) 291-324, https://doi.org/10.3233/AAC-210010.

[20] M. Caminada, G. Pigozzi, On judgment aggregation in abstract argumentation, Auton. Agents Multi-Agent Syst. 22 (2011) 64-102, https://doi.org/10.1007/s10458-009-9116-7.

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

[22] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, On properties and complexity of incomplete argumentation framework, in: R. Confalonieri, D. Porello (Eds.), Proceedings of the 6th Workshop on Advances in Argumentation in Artificial Intelligence 2022 co-located with the 21st International Conference of the Italian Association for Artificial Intelligence (AIxIA 2022), Udine, Italy, November 28, 2022, in: CEUR Workshop Proceedings, vol. 3354, CEUR-WS.org, 2022-2022, https://ceur-ws.org/Vol-3354/paper3.pdf.

[23] G. Alfano, S. Greco, F. Parisi, I. Trubitsyna, Incomplete argumentation frameworks: properties and complexity, in: Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, the Twelfth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, AAAI Press, 2022, pp. 5451-5460.

[24] G. Alfano, M. Calautti, S. Greco, F. Parisi, I. Trubitsyna, Explainable acceptance in probabilistic and incomplete abstract argumentation frameworks, Artif. Intell. 323 (2023) 103967, https://doi.org/10.1016/j.artint.2023.103967.

[25] B. Fazzinga, S. Flesca, F. Furfaro, Incomplete bipolar argumentation frameworks, in: K. Gal, A. Nowé, G.J. Nalepa, R. Fairstein, R. Radulescu (Eds.), ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Kraków, Poland - Including 12th Conference on Prestigious Applications of Intelligent Systems (PAIS 2023), in: Frontiers in Artificial Intelligence and Applications, vol. 372, IOS Press, 2023, pp. 684-691.

[26] B. Fazzinga, S. Flesca, F. Furfaro, On merging incompleteness and bipolarity in abstract argumentation, in: G. Alfano, S. Ferilli (Eds.), Proceedings of the 7th Workshop on Advances in Argumentation in Artificial Intelligence (AI'3 2023) co-located with the 22nd International Conference of the Italian Association for Artificial Intelligence (AIxIA 2023), Rome, Italy, November 9, 2023, in: CEUR Workshop Proceedings, vol. 3546, CEUR-WS.org, 2023, https://ceur-ws.org/Vol-3546/paper02.pdf.

[27] M.-C. Lagasquie-Schiex, J.-G. Mailly, A. Yuste-Ginel, How to manage supports in incomplete argumentation, in: Proceedings of the 13th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2024), 2024.

[28] C. Cayrol, M. Lagasquie-Schiex, Bipolar abstract argumentation systems, in: G.R. Simari, I. Rahwan (Eds.), Argumentation in Artificial Intelligence, Springer, 2009, pp. 65-84.

[29] F. Nouioua, V. Risch, Argumentation frameworks with necessities, in: SUM 2011, 2011, pp. 163-176.

[30] G. Boella, D. Gabbay, L. van der Torre, S. Villata, Support in abstract argumentation, in: Proc. of COMMA'10, 2010, pp. 111-122.

[31] Y. Dimopoulos, J.-G. Mailly, P. Moraitis, Control argumentation frameworks, in: 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), 2018, pp. 4678-4685.

[32] J.-G. Mailly, Possible controllability of control argumentation frameworks, in: 8th International Conference on Computational Models of Argument (COMMA 2020), 2020, pp. 283-294.