Structural constraints for dynamic operators in abstract argumentation

Abstract

Many recent studies of dynamics in formal argumentation within AI focus on the well-known formalism of Dung’s argumentation frameworks (AFs). Despite the usefulness of AFs in many areas of argumentation, their abstract notion of arguments creates a barrier for operators that modify a given AF, e.g., in the case that dependencies between arguments have been abstracted away that are important for subsequent modifications. In this paper we aim to support development of dynamic operators on formal models in abstract argumentation by providing constraints imposed on the modification of the structure that can be used to incorporate information that has been abstracted away. Towards a broad reach, we base our results on the general formalism of abstract dialectical frameworks (ADFs) in abstract argumentation. To show applicability, we present two cases studies that adapt an existing extension enforcement operator that modifies AFs: in the first case study, we show how to utilize constraints in order to obtain an enforcement operator on ADFs that is allowed to only add support relations between arguments, and in the second case study we show how an enforcement operator on AFs can be defined that respects dependencies between arguments. We show feasibility of our approach by studying the complexity of the proposed structural constraints and the operators arising from the case studies, and by an experimental evaluation of an answer set programming (ASP) implementation of the enforcement operator based on supports.

1. Introduction

In the last decades there has been a steady stream of advances in formal approaches to argumentation within artificial intelligence (AI) [4,19]. Central to many formal models in argumentation are argumentation frameworks (AFs) due to the work by Dung in 1995 [53]. AFs can be seen as a reasoning formalism that is both foundational and simple: AFs consist of abstract arguments and directed attacks (conflicts) between these arguments. The simplicity of AFs is an appealing quality, which is witnessed by the fact that several approaches use AFs as their core reasoning engine [22,23,28,45,54,85,86]. Reasoning in this way is done via instantiating AFs in a principled way such that the arguments capture what can be argued for, and the attacks cover ways in which the arguments are conflicting. Semantics of AFs provide different means of conflict handling, in order to find acceptable arguments. Importantly, semantics of AFs only rely on the abstract view of AFs, i.e., abstract arguments and their conflict relations suffice to find acceptable arguments from an argumentative point of view for many applications. By inspecting the content of acceptable arguments one can trace back concrete claims that are acceptable.

AFs are also prominent as a formal basis for an emergent topic in formal argumentation, namely that of dynamics of argumentation [10,34,44,48,52], which can partially also be attributed to the easy-to-grasp conceptual nature of AFs. The investigation of dynamics of argumentation arose naturally in the research community since argumentation is an inherently dynamic process of, e.g., posing arguments and counterarguments towards goals in a debate.

In their initial usage, AFs were applied on “static” forms of reasoning, i.e., reasoning in contexts that give rise to AFs that do not change. While the principles of dynamic scenarios are compatible with AFs, in that AFs can be dynamically adapted, care needs to be taken when utilizing AFs in a dynamic context. For instance, dynamic operations, if solely done on AFs, may miss certain dependencies between arguments that are apparent when considering the internal structure of the arguments, but which have been “abstracted away” during instantiation.

Example 1.

Consider two arguments, ${\mathit{a}}_1$ and ${\mathit{a}}_2$ , and assume that ${\mathit{a}}_1$ is a sub argument of ${\mathit{a}}_2$ , e.g., because ${\mathit{a}}_1$ concludes a premise of ${\mathit{a}}_2$ . When both arguments are part of an AF then a modification of that AF may add an attack on ${\mathit{a}}_1$ , say by a counter to the premise of ${\mathit{a}}_1$ . In many cases such a counter is deemed to, also, attack the super argument ${\mathit{a}}_2$ , since its premise is attacked. However, if no further information than the AF is available, then this interdependency might be missed, which may lead to unintended results, like rejecting ${\mathit{a}}_1$ but finding ${\mathit{a}}_2$ to be acceptable, even though one is the premise of the other.

While certain generalizations of AFs [31,39], particularly those that incorporate support relations, e.g., based on necessary supports [92], make it possible to explicate the apparently implicit support relation between ${\mathit{a}}_1$ and ${\mathit{a}}_2$ , ultimately the same underlying problem remains: modifications on abstract frameworks may miss interdependencies between arguments.

In this paper we argue that despite these drawbacks of AFs when utilizing them in dynamic operations, abstract argumentation formalisms, as introduced by Dung [53] and to which this special issue is dedicated, are still a very useful notion for studying dynamics of argumentation. We argue that existing dynamic operators, and new ones, can be augmented to incorporate key structural constraints. Our goal in this paper is to provide means with which dynamic operations on abstract arguments can be extended so that (i) certain structural constraints are taken into account and (ii) operators can still work on a convenient and (partial) abstract level.

Towards our goal, we view dynamic operations on abstract arguments (and their relations) as operators working in three layers: a semantic layer, a structural layer, and a syntax layer. In the first layer, a semantical change is specified by an operator. As a concrete example, consider extension enforcement as defined in [10]: given an AF and a set of arguments, the output is a modified AF whose semantics contains the given set of arguments as an extension. This operator finds interpretations as strategic moves in an argumentation [58]. Enforcement defines certain conditions on the semantics of the output (or, equivalently, constraints on the semantics of an output AF). On the structural side, extension enforcement specifies that the output AF shall be close to the input AF (via a defined notion of distance between input and output AF structures). Finally, syntactically, the operator requires that the output is, again, an AF.

Fig. 1.

(a) Three layers for dynamic operators and (b) outcomes that satisfy constraints of each layer.

More broadly, we find that the semantical layer of a dynamic operator defines semantical constraints on the output, the structural layer specifies constraints on the structure of the output, and the syntax layer specifies the concrete syntax an output shall have. We illustrate this “workflow” in Fig. 1(a). Analogously, one can view each layer of an operator as (a set of) constraints, each constraining the possible candidate solutions, see Fig. 1(b). In the case of enforcement, the first layer constrains the set of candidate AFs to be those that satisfy the semantical constraint, then the second layer constrains to choose, among those satisfying the first layer, those structures that are close to the input.

With this article, we contribute to the second layer, the structural layer, by giving properties that can be required by an output structurally, with the aim of giving developers of dynamic operators a further handle to extend operators to cover more application scenarios. As the formal foundation, we use abstract dialectical frameworks (ADFs) [30,55] as the formal model that undergoes a change in this paper. Although ADFs are more complex than AFs, in the sense that the acceptance conditions of arguments can be specified in a liberal manner, they are still an abstract formalism with abstract arguments, and, importantly, have been shown to capture several abstract formalisms in argumentation in AI [95], and, thus, extend the reach of our contributions also to other formalisms than AFs.

To further our aim of supporting development of dynamic operators, we utilize the proposed constraints in two case studies. In the first case study we show how enforcement on AFs can be adapted to ADFs such that relations between arguments may only be modified in a way that corresponds to support between arguments, in contrast to attacks on AFs. In this way, we both aim to present a showcase of the constraints and show how to generalize existing dynamic operators on AFs to the more general setting of ADFs. Indeed, many dynamic approaches are currently restricted to AFs only. By using ADFs, and applying suitable structural constraints, one can lift current operators on AFs to ADFs, while keeping the intuitions of the operators.

In a second case study, we stay on the level of AFs, but adapt the existing enforcement operator to respect information of the instantiation. Concretely, for a general view on structured argumentation formalisms, we show how the constraints can be applied so that modifications to an AF do not miss interdependencies between arguments on their internal structure.

Since dynamic operators are, even without further constraints, often computationally hard [44,102], we study the complexity of the constraints we consider in this paper, and also the operators arising from the two case studies, in order to show which constraints can be feasibly “added” to operators. In order to have a clearer picture, we present an implementation in answer set programming (ASP) [29,71,88] and an empirical evaluation of the support enforcement on ADFs from the first case study. Our findings are that even when working in a more general abstract framework, and with complex constraints, state-of-the-art search engines (such as ASP) are capable of feasibly solving many instances up to certain sizes.

We summarize the main contributions of this article in the following.

• To situate our proposal in more concrete terms, we first adapt an existing extension enforcement operator for AFs [9,10,44] to ADFs.

• We give a list of structural constraints on ADFs, i.e., constraints on the structure of ADFs, exemplify their use for dynamics, and study some of their properties.

• We give two case studies for the constraints and adaptions of extension enforcement: one enforcement operation on ADFs that deals with supports and one enforcement operation on AFs that respects internal structure of arguments.

• To demonstrate feasibility, we show the theoretical complexity of checking whether an ADF satisfies the constraints, which is decidable in polynomial time in many cases, and we study the complexity of the operators arising from the case studies under admissible semantics.

• We implemented a prototype of the enforcement operation on ADFs using supports based on the Diamond system [62,63], and performed an experimental evaluation, showing good performance for a variety of ADF instances.

The article begins with recalling background in Section 2 (AFs and ADFs) and Section 3 (enforcement). We present and exemplify structural constraints in Section 4, and proceed to the case studies in Section 5 and Section 6. Our analysis of complexity of constraints and case studies is presented in Section 7, and our prototype implementation and experiments in Section 8. We close with a discussion on further existing operators for which our constraints can be applied (Section 9) and on related work (Section 10). This article significantly extends the conference version [101] by expanded discussion and illustration, more formal details on the first case study, inclusion of the second case study, giving full proofs, and updated experiments.

2. Abstract argumentation frameworks

In this section we recall the basics of two well-known abstract argumentation frameworks, namely Dung’s argumentation frameworks (AFs) [53] and abstract dialectical frameworks (ADFs) [30]. There exists a whole range of abstract formalisms for argumentation, such as bipolar frameworks (BAFs) [3,36], extended argumentation frameworks (EAFs) [83], argumentation frameworks with recursive attacks (AFRAs) [6] and their subsequent extensions [35,40,65], value-based frameworks (VAFs) [18], and preference-based frameworks (PAFs) [2], to name some of the prominent formalisms, which are also surveyed in recent articles [31,39]. Our choice of AFs and ADFs is justified by AFs being the common core to all these other approaches, and that ADFs generalize (translate to) many other approaches [95].

2.1. Argumentation frameworks

We start the formal preliminaries with Dung’s argumentation frameworks (AFs) [53] and semantics for these frameworks [5]. An AF consists of a set of abstract arguments and directed attacks between these arguments.

Definition 1.

An argumentation framework (AF) is a pair $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ , where A is a finite set of arguments and $\mathit{R}\subseteq \mathit{A}\times \mathit{A}$ is the attack relation. The pair $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}$ means that a attacks b.

Example 2.

AFs have a natural representation as directed graphs. Consider an AF $\mathit{F}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\mathit{R}\mathrm{)}$ with four arguments and the following attacks: $\mathit{R}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\}$ . This AF is illustrated in Fig. 2(a).

Fig. 2.

Illustrations of the AF and the corresponding ADF from Example 3 and Example 4.

A central notion towards the semantics of AFs is that of defense of arguments.

Definition 2.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be an AF. An argument $\mathit{a}\in \mathit{A}$ is defended (in F) by a set $\mathit{S}\subseteq \mathit{A}$ if for each $\mathit{b}\in \mathit{A}$ such that $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}$ there exists a $\mathit{c}\in \mathit{S}$ such that $\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}$ .

Semantics for argumentation frameworks are defined through a function σ which assigns to each AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ a set $\mathit{\sigma }\mathrm{(}\mathit{F}\mathrm{)}\subseteq 2^{\mathit{A}}$ of extensions. We consider for σ the functions $\mathit{\text{cf}}$ , $\mathit{\text{adm}}$ , $\mathit{\text{com}}$ , $\mathit{\text{grd}}$ , and $\mathit{\text{prf}}$ , which stand for conflict-free, admissible, complete, grounded, and preferred, respectively. Towards the definition we make use of the characteristic function of AFs, defined for an AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ by ${\mathcal{F}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}=\{\mathit{x}\in \mathit{A}\mid \mathit{x}\text{ is defended by }\mathit{S}\}$ .

Table 1

Extensions of semantics σ from Example 2

σ	$\mathit{\sigma }\mathrm{(}\mathit{F}\mathrm{)}$
$\mathit{\text{cf}}$	$\{\varnothing \mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\mathrm{,}\{\mathit{c}\}\mathrm{,}\{\mathit{d}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{d}\}\}$
$\mathit{\text{adm}}$	$\{\varnothing \mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{d}\}\}$
$\mathit{\text{com}}$	$\{\varnothing \mathrm{,}\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{d}\}\}$
$\mathit{\text{grd}}$	$\{\varnothing \}$
$\mathit{\text{prf}}$	$\{\{\mathit{a}\mathrm{,}\mathit{d}\}\mathrm{,}\{\mathit{b}\mathrm{,}\mathit{d}\}\}$

Definition 3.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be an AF. An $\mathit{S}\subseteq \mathit{A}$ is conflict-free (in F) if there are no $\mathit{a}\mathrm{,}\mathit{b}\in \mathit{S}$ such that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{R}$ . We denote the set of conflict-free sets by $\mathit{\text{cf}}\mathrm{(}\mathit{F}\mathrm{)}$ . For an $\mathit{S}\in \mathit{\text{cf}}\mathrm{(}\mathit{F}\mathrm{)}$ it holds that

$\mathit{S}\in \mathit{\text{adm}}\mathrm{(}\mathit{F}\mathrm{)}$ iff $\mathit{S}\subseteq {\mathcal{F}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ ;

$\mathit{S}\in \mathit{\text{com}}\mathrm{(}\mathit{F}\mathrm{)}$ iff $\mathit{S}={\mathcal{F}}_{\mathit{F}}\mathrm{(}\mathit{S}\mathrm{)}$ ;

$\mathit{S}\in \mathit{\text{grd}}\mathrm{(}\mathit{F}\mathrm{)}$ iff S is the least fixed-point of ${\mathcal{F}}_{\mathit{F}}$ ; and

$\mathit{S}\in \mathit{\text{prf}}\mathrm{(}\mathit{F}\mathrm{)}$ iff $\mathit{S}\in \mathit{\text{adm}}\mathrm{(}\mathit{F}\mathrm{)}$ and there is no $\mathit{T}\in \mathit{\text{adm}}\mathrm{(}\mathit{F}\mathrm{)}$ with $\mathit{S}\subset \mathit{T}$ .

It is well-known that for any AF F it holds that $\mathit{\text{cf}}\mathrm{(}\mathit{F}\mathrm{)}\supseteq \mathit{\text{adm}}\mathrm{(}\mathit{F}\mathrm{)}\supseteq \mathit{\text{com}}\mathrm{(}\mathit{F}\mathrm{)}\supseteq \mathit{\text{prf}}\mathrm{(}\mathit{F}\mathrm{)}$ . We use the term σ-extension to refer to an extension under a semantics $\mathit{\sigma }\in \{\mathit{\text{cf}}\mathrm{,}\mathit{\text{adm}}\mathrm{,}\mathit{\text{com}}\mathrm{,}\mathit{\text{grd}}\mathrm{,}\mathit{\text{prf}}\}$ . We note that conflict-free sets and admissible sets are usually not referred to as a semantics, since, commonly, these two notions are seen as auxiliary concepts. Nevertheless, for the sake of uniformity, we will refer to the set of conflict-free sets and the set of admissible sets as conflict-free and admissible semantics. However, we do emphasize that by referring to conflict-free sets or admissible sets by conflict-free semantics or admissible semantics does not imply a prescriptive endeavor of placing these two concepts into the set of “full” argumentative semantics. Similarly, we sometimes call conflict-free sets or admissible sets conflict-free or admissible extensions, likewise with no intention of viewing them as being on the same level as extensions of other semantics.

Example 3.

Consider the AF F in Example 2. For the considered semantics σ we show the corresponding extensions in Table 1.

2.2. Abstract dialectical frameworks

We recall ADFs from [30], which are based on earlier works [32]. We begin with basics from propositional logic and three-valued interpretations. Let A be a finite set of arguments (statements). An interpretation is a function I mapping arguments to one of the three truth values $\mathit{I}:\mathit{A}\to \{\mathbf{t}\mathrm{,}\mathbf{f}\mathrm{,}\mathbf{u}\}$ . That is, an interpretation maps each argument to either true (t), false (f), or undefined (u). An interpretation I is two-valued if $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ for all $\mathit{a}\in \mathit{A}$ , and trivial, denoted as ${\mathit{I}}_{\mathbf{u}}$ , if $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ for all $\mathit{a}\in \mathit{A}$ . Further, let ${\mathit{I}}_{\mathbf{t}}$ ( ${\mathit{I}}_{\mathbf{f}}$ ) be the interpretation assigning all arguments to t (f).

For Boolean formulas φ we consider the classical connectives of logical conjunction “∧”, logical disjunction “∨”, logical negation “¬”, and material implication “→”. A two-valued interpretation I extends to the evaluation of a formula φ under I as usual, denoted by $\mathit{I}\mathrm{(}\mathit{\phi }\mathrm{)}$ .

For a formula φ and a three-valued interpretation I let $\mathit{\phi }[\mathit{I}]$ be the formula obtained from φ with each argument that I assigns to either true or false being replaced by the corresponding truth constant, i.e., $\mathit{\phi }[\mathit{I}]=\mathit{\phi }[\mathit{x}\mapsto \top \mid \mathit{I}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}][\mathit{x}\mapsto \perp \mid \mathit{I}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{f}]$ ; arguments assigned to undefined are not modified.

An interpretation I is equally or more informative than J, denoted by $\mathit{J}{⩽}_{\mathit{i}}\mathit{I}$ , if $\mathit{J}\mathrm{(}\mathit{a}\mathrm{)}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ implies $\mathit{J}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}$ for all $\mathit{a}\in \mathit{A}$ . We denote by ${\mathrm{<}}_{\mathit{i}}$ the strict version of ${⩽}_{\mathit{i}}$ , i.e., $\mathit{J}{\mathrm{<}}_{\mathit{i}}\mathit{I}$ if $\mathit{J}{⩽}_{\mathit{i}}\mathit{I}$ and $\exists \mathit{a}\in \mathit{A}$ s.t. $\mathit{J}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ and $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ .

Definition 4.

An ADF is a tuple $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ where A is a set of arguments, $\mathit{L}\subseteq \mathit{A}\times \mathit{A}$ is a set of links, and $\mathit{C}={\{{\mathit{\phi }}_{\mathit{a}}\}}_{\mathit{a}\in \mathit{A}}$ is a collection of acceptance conditions, each given by a formula over the parents of an argument: ${\mathit{par}}_{\mathit{D}}\mathrm{(}\mathit{a}\mathrm{)}=\{\mathit{b}\in \mathit{A}\mid \mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{L}\}$ .

Example 4.

Fig. 2(b) shows an ADF $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ with $\mathit{L}=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\}$ . The acceptance conditions are shown close to the arguments.

The semantics of ADFs are based on the characteristic function ${\mathrm{\Gamma }}_{\mathit{D}}$ mapping interpretations to updated interpretations.

Definition 5.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF. The characteristic function ${\mathrm{\Gamma }}_{\mathit{D}}$ is defined by ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}=\mathit{J}$ with $$\begin{array}{l}\hfill \mathit{J}\mathrm{(}\mathit{a}\mathrm{)}=\left\{\begin{array}{cc}\mathbf{t}\hfill & \text{if }{\mathit{\phi }}_{\mathit{a}}[\mathit{I}]\text{ is a tautology, }\hfill \\ \mathbf{f}\hfill & \text{if }{\mathit{\phi }}_{\mathit{a}}[\mathit{I}]\text{ is unsatisfiable, and }\hfill \\ \mathbf{u}\hfill & \text{otherwise. }\hfill \end{array}\right.\end{array}$$

Semantics of ADFs are defined in a similar fashion as for AFs, based on the characteristic function.

Definition 6.

Given an ADF D, an interpretation I

is admissible in D iff $\mathit{I}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}$ ;

is complete in D iff $\mathit{I}={\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}$ ;

is grounded in D iff I is the least fixed-point of ${\mathrm{\Gamma }}_{\mathit{D}}$ ; and

is preferred in D iff I is ${⩽}_{\mathit{i}}$ -maximal admissible in D.

We refer to the set of all admissible, complete, grounded, and preferred interpretations of an ADF D by $\mathit{\text{adm}}\mathrm{(}\mathit{D}\mathrm{)}$ , $\mathit{\text{com}}\mathrm{(}\mathit{D}\mathrm{)}$ , $\mathit{\text{grd}}\mathrm{(}\mathit{D}\mathrm{)}$ , and $\mathit{\text{prf}}\mathrm{(}\mathit{D}\mathrm{)}$ , respectively. In any ADF D, it holds that $\mathit{\text{prf}}\mathrm{(}\mathit{D}\mathrm{)}\subseteq \mathit{\text{com}}\mathrm{(}\mathit{D}\mathrm{)}\subseteq \mathit{\text{adm}}\mathrm{(}\mathit{D}\mathrm{)}$ . Further, by definition, it holds that the grounded interpretation is a complete interpretation.

Example 5.

For the ADF from Example 4, the σ-interpretations are shown in Table 2. Admissible interpretations are not shown due to their number: there are 11 admissible interpretations for this ADF.

Table 2

Interpretations of semantics σ from Example 4

σ	$\mathit{\sigma }\mathrm{(}\mathit{D}\mathrm{)}$
$\mathit{\text{com}}$	$\{\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}$ ,
	$\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{t}\}$ ,
	$\{\mathit{a}\mapsto \mathbf{f}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{t}\}\}$
$\mathit{\text{grd}}$	$\{\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{u}\}\}$
$\mathit{\text{prf}}$	$\{\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{t}\}$ ,
	$\{\mathit{a}\mapsto \mathbf{f}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\mathrm{,}\mathit{d}\mapsto \mathbf{t}\}\}$

We will also make use of a fragment of ADFs, called bipolar ADFs. Towards the definition, we recall the notion of attacking and supporting relations, as specified in ADFs.1

¹

We remark that the notion of “support” in abstract argumentation is not uniform. Common interpretations of support include support relation seen as deductive support [27], as necessary support [91,92], or as evidential support [93,94], see also [36].

Formally, we make use of an auxiliary notion: we denote the update of an interpretation I with truth value $\mathbf{x}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\mathrm{,}\mathbf{u}\}$ for argument b by $\mathit{I}{|}_{\mathbf{x}}^{\mathit{b}}$ , i.e., $\mathit{I}{|}_{\mathbf{x}}^{\mathit{b}}\mathrm{(}\mathit{b}\mathrm{)}=\mathbf{x}$ and $\mathit{I}{|}_{\mathbf{x}}^{\mathit{b}}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}$ for $\mathit{a}\ne \mathit{b}$ .

Definition 7.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF. We say that a link $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{L}$ is

supporting (in D) if for every two-valued interpretation I, $\mathit{I}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ implies $\mathit{I}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{t}$ ; and

attacking (in D) if for every two-valued interpretation I, $\mathit{I}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ implies $\mathit{I}{|}_{\mathbf{t}}^{\mathit{b}}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}=\mathbf{f}$ .

Intuitively, if a link from a to b is attacking (supporting), then it cannot be the case that acceptance of a leads to a change of b’s status to that of being accepted (not accepted).

An ADF D is called bipolar (is a BADF) if each link $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{L}$ is attacking or supporting. A link that is both attacking and supporting is called redundant.

An AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ can be translated to an ADF by defining ${\mathit{D}}_{\mathit{F}}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{,}\mathit{C}\mathrm{)}$ with ${\mathit{\phi }}_{\mathit{a}}={\bigwedge }_{\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\in \mathit{R}}\neg \mathit{b}$ (see also Fig. 2). Note that the resulting ADF ${\mathit{D}}_{\mathit{F}}$ has only attacking links which are not supporting. The semantics of an AF and its corresponding ADF coincide (by relating an extension E with interpretation I via $\mathit{E}=\{\mathit{a}\mid \mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\}$ [30]).

3. Enforcement on argumentation frameworks

Enforcement on AFs deals with the task of how to modify a given AF such that the modified AF satisfies certain semantical constraints. Usually also the number of modifications has to be minimum. Enforcement has been studied from several angles: possibility and impossibility results [9,10], representational aspects and use cases in a logical setting [25,51,58], computational aspects [44,90,102], and axiomatic studies [11,51,58,73].

Several variants of enforcement have been defined. For the purposes of this paper, we look at the enforcement variant called non-strict enforcement under strong expansions with a bounded number of expanded arguments [44]. This choice is mostly due to illustrative reasons; other variants fit the aims of the paper, as well. We base our results on this variant, since it is intuitively appealing: expansions relate to addition of arguments, with the strong variant indicating attacks originating only from new arguments. Compared to other operations studied, “strict” variants would place more restrictions on the semantic goal, and other types of expansions [8] have different restrictions which attacks may be added.

For an AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ , an expansion of F is any ${\mathit{F}}^{\prime }=\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{R}}^{\prime }\mathrm{)}$ with $\mathit{A}\subseteq {\mathit{A}}^{\prime }$ and $\mathit{R}\subseteq {\mathit{R}}^{\prime }$ (new arguments and new attacks may be added arbitrarily). Given an AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ , a strong expansion of F that adds new arguments ${\mathit{A}}^{\prime }$ , with $\mathit{A}\cap {\mathit{A}}^{\prime }=\varnothing$ , is a modified AF ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{,}{\mathit{R}}^{\prime }\mathrm{)}$ with $\mathit{R}\subseteq {\mathit{R}}^{\prime }$ (all original attacks are in ${\mathit{R}}^{\prime }$ ) and if an attack $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{R}}^{\prime }\setminus \mathit{R}$ was added, then $\mathit{a}\in {\mathit{A}}^{\prime }$ and $\mathit{b}\in \mathit{A}$ (new attacks originate from new arguments onto original arguments only).

Based on strong expansions, we define enforcement as follows.

Definition 8.

Let $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ be an AF, σ be a semantics, ${\mathit{A}}^{\prime }$ be a set with $\mathit{A}\cap {\mathit{A}}^{\prime }=\varnothing$ , and $\mathit{S}\subseteq \mathit{A}\cup {\mathit{A}}^{\prime }$ . An AF ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{,}{\mathit{R}}^{\prime }\mathrm{)}$ non-strictly enforces S under σ if

$\mathit{R}\subseteq {\mathit{R}}^{\prime }$ ,

for any $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{R}}^{\prime }\setminus \mathit{R}$ we have $\mathit{a}\in {\mathit{A}}^{\prime }$ and $\mathit{b}\in \mathit{A}$ , and

$\exists {\mathit{S}}^{\prime }\in \mathit{\sigma }\mathrm{(}{\mathit{F}}^{\prime }\mathrm{)}$ with $\mathit{S}\subseteq {\mathit{S}}^{\prime }$ .

That is, one needs to find a modified AF ${\mathit{F}}^{\prime }$ that strongly expands F by new arguments ${\mathit{A}}^{\prime }$ and S must be part of a σ-extension of ${\mathit{F}}^{\prime }$ . Among all candidates, typically, one further restricts solution AFs to be optimal w.r.t. the modifications to the attacks. This is specified by finding an optimal AF ${\mathit{F}}^{\ast }=\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{,}{\mathit{R}}^{\ast }\mathrm{)}$ that non-strictly enforces S under σ and there is no ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{,}{\mathit{R}}^{\prime }\mathrm{)}$ that non-strictly enforces S under σ and $|\mathrm{(}\mathit{R}\mathrm{\Delta }{\mathit{R}}^{\prime }\mathrm{)}|\mathrm{<}|\mathrm{(}\mathit{R}\mathrm{\Delta }{\mathit{R}}^{\ast }\mathrm{)}|$ , with Δ the usual symmetric difference: $\mathit{X}\mathrm{\Delta }\mathit{Y}=\mathrm{(}\mathit{X}\setminus \mathit{Y}\mathrm{)}\cup \mathrm{(}\mathit{Y}\setminus \mathit{X}\mathrm{)}$ .

Example 6.

Consider the AF from Example 3. Say we want to enforce $\{\mathit{a}\mathrm{,}\mathit{d}\}$ to be part of the grounded extension in a strongly expanded AF that can add argument e (i.e. ${\mathit{A}}^{\prime }=\{\mathit{e}\}$ ). This can be achieved by adding the attack $\mathrm{(}\mathit{e}\mathrm{,}\mathit{b}\mathrm{)}$ , resulting in ${\mathit{F}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{R}}^{\ast }\mathrm{)}$ with ${\mathit{A}}^{\ast }=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\mathrm{,}\mathit{e}\}$ and ${\mathit{R}}^{\ast }=\{\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{a}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{d}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{e}\mathrm{,}\mathit{b}\mathrm{)}\}$ . We have $\mathit{\text{grd}}\mathrm{(}{\mathit{F}}^{\ast }\mathrm{)}=\{\mathit{e}\mathrm{,}\mathit{a}\mathrm{,}\mathit{d}\}$ , implying that $\{\mathit{a}\mathrm{,}\mathit{d}\}$ is non-strictly enforced under grounded semantics. The modified AF ${\mathit{F}}^{\ast }$ is optimal: only one attack was added, and without modifications $\{\mathit{a}\mathrm{,}\mathit{d}\}$ is not part of the grounded extension (the grounded extension is empty in the unmodified AF). See Fig. 3 for an illustration.

Fig. 3.

Enforcing $\{\mathit{a}\mathrm{,}\mathit{d}\}$ being part of the grounded extension, by adding argument e and attack $\mathrm{(}\mathit{e}\mathrm{,}\mathit{b}\mathrm{)}$ (Example 6).

4. Structural constraints for dynamic operators

This section introduces several constraints to be used to extend current dynamic operators, and support development of new operators. From a principled point of view, we consider dynamic operators that take an ADF D as input and produce a modified ADF ${\mathit{D}}^{\ast }$ as output. For the sake of readability, we will, unless stated otherwise, refer to a modified ADF by ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ . A dynamic operator then defines certain constrains on the output, namely on (i) the semantics, (ii) the structure, and (iii) the concrete syntax. We first exemplify constraints on the enforcement operator from Section 3 when lifted from AFs to ADFs.

Definition 9.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF, σ be a semantics, ${\mathit{A}}^{\prime }$ be a set of arguments to expand, and I be a three-valued interpretation over $\mathit{A}\cup {\mathit{A}}^{\prime }$ . An ADF ${\mathit{D}}^{\prime }=\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{,}{\mathit{L}}^{\prime }\mathrm{,}{\mathit{C}}^{\prime }\mathrm{)}$ non-strictly enforces I under σ if

$\mathit{L}\subseteq {\mathit{L}}^{\prime }$ ,

for any $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{\prime }\setminus \mathit{L}$ we have $\mathit{a}\in {\mathit{A}}^{\prime }$ and $\mathit{b}\in \mathit{A}$ , and

$\exists {\mathit{I}}^{\prime }\in \mathit{\sigma }\mathrm{(}{\mathit{D}}^{\prime }\mathrm{)}$ s.t. $\mathit{I}{⩽}_{\mathit{i}}{\mathit{I}}^{\prime }$ .

That is, we want to enforce that I is “part” of a σ-interpretation by modifying D in the following way: there has to be a σ-interpretation ${\mathit{I}}^{\prime }$ such that if an argument a is assigned true (false) by I, then ${\mathit{I}}^{\prime }$ assigns true (false) to a, as well. Further, analogously as for AFs, one can look at optimality constraints: we say that an ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ is an optimal solution to non-strict enforcement if ${\mathit{D}}^{\ast }$ non-strictly enforces I under σ, and there is no ${\mathit{D}}^{\prime }=\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{L}}^{\prime }\mathrm{,}{\mathit{C}}^{\prime }\mathrm{)}$ with $|\mathrm{(}\mathit{L}\mathrm{\Delta }{\mathit{L}}^{\prime }\mathrm{)}|\mathrm{<}|\mathrm{(}\mathit{L}\mathrm{\Delta }{\mathit{L}}^{\ast }\mathrm{)}|$ that non-strictly enforces I under σ. Intuitively, there has to be a σ-interpretation ${\mathit{I}}^{\prime }$ in the modified ${\mathit{D}}^{\ast }$ such that the requirements of I are met (some arguments have to be true, some false, undecided arguments are not constrained). Compared to Definition 8 the only major change is to respect the three-valued semantics of ADFs.

Within the three-layered view, this adapted enforcement operator works as follows:

1. the semantical constraint specifies the “goal”, i.e., the arguments to be true/false in a σ-interpretation,

2. the structural constraints state that only expansions of the original ADF may be considered (with possibly only considering optimal solutions), and

3. a syntactical constraint stating that the output shall be an ADF (leaving the form of acceptance conditions, e.g., regarding normal forms, open).

Example 7.

Consider again the ADF D from Example 4. Say we want to enforce that both a and d are true in the grounded interpretation. Further, say we may add only argument e. This means, we desire to enforce interpretation $\mathit{I}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\mathrm{,}\mathit{d}\mapsto \mathbf{t}\mathrm{,}\mathit{e}\mapsto \mathbf{u}\}$ (a and d must be true, all other arguments are unconstrained). Unmodified, both arguments are undecided in the grounded interpretation of D, since the grounded interpretation assigns all arguments to undecided. The enforcement can be achieved by adding an argument e (similarly as in Example 6 for enforcement on AFs) that “attacks” argument b, by adapting the acceptance condition of b to ${\mathit{\phi }}_{\mathit{b}}^{\prime }=\neg \mathit{a}\wedge \neg \mathit{e}$ (from originally ${\mathit{\phi }}_{\mathit{b}}=\neg \mathit{a}$ ). This enforcement is shown in Fig. 4.

Fig. 4.

Enforcing $\{\mathit{a}\mathrm{,}\mathit{d}\}$ being true in the grounded interpretation: adding argument e, with ${\mathit{\phi }}_{\mathit{e}}=\top$ and adapting ${\mathit{\phi }}_{\mathit{b}}$ to ${\mathit{\phi }}_{\mathit{b}}^{\prime }=\neg \mathit{a}\wedge \neg \mathit{e}$ (Example 7).

We now proceed to introducing several structural constraints that are intended to refine candidate ADFs for a dynamic operator on ADFs. The enforcement operator defined above is one example for such an operator, but in the following we do not assume a concrete operator (however, we connect several constraints to the enforcement operator). Formally, a constraint c is specified in such a way that one can decide whether an ADF satisfies the constraint. The intention is then to choose, among all ADFs satisfying the given semantical constraints, e.g., from the ADF enforcement operator defined above, one ADF satisfying a given structural constraint c. Many of the subsequent constraints are intended to be used in a mix of several constraints. That is why we begin with defining how to state combinations of constraints.

Boolean combinations of constraints. In the following, when $\mathit{K}=\{{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}$ is a set of (structural) constraints, we consider also the constraint that is a Boolean combination of these constraints. That is, a Boolean formula Φ that has as its variables constraints in K. Satisfaction, for an ADF D, of Φ is then defined in a standard way: if D satisfies a ${\mathit{c}}_{\mathit{i}}\in \mathit{K}$ , then $\mathrm{\Phi }={\mathit{c}}_{\mathit{i}}$ is satisfied by D; if $\mathrm{\Phi }=\neg {\mathit{c}}_{\mathit{i}}$ , then D satisfies Φ if it does not satisfy ${\mathit{c}}_{\mathit{i}}$ ; the connectives of conjunction and disjunction are defined in the standard way, as well.

General constraints. For concrete atomic constraints, we start with basic constraints, namely ones that specify limits of arguments and links. That is, for a given ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ (a potential output ADF), argument sets A and ${\mathit{A}}^{\prime }$ , and sets of links L and ${\mathit{L}}^{\prime }$ , we define the following constraints, with $\mathit{L}{|}_{{\mathit{A}}^{\ast }}=\mathit{L}\cap \mathrm{(}{\mathit{A}}^{\ast }\times {\mathit{A}}^{\ast }\mathrm{)}$ .

$\mathit{A}\subseteq {\mathit{A}}^{\ast }\subseteq {\mathit{A}}^{\prime }$

$\mathit{L}{|}_{{\mathit{A}}^{\ast }}\subseteq {\mathit{L}}^{\ast }\subseteq {\mathit{L}}^{\prime }{|}_{{\mathit{A}}^{\ast }}$

These constraints specify which arguments may be in the output (G1) and which links may be present (G2). For instance, via (G1), one can specify for enforcement under expansions how many arguments the expansion may add to the original framework (in the constraints A and L give a lower bound and ${\mathit{A}}^{\prime }$ and ${\mathit{L}}^{\prime }$ give an upper bound).

Argument constraints. The next basic constraint gives a concrete handle which arguments are present in the output. For an ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ and argument a we define:

$\mathit{a}\in {\mathit{A}}^{\ast }$

Example 8.

Assume an enforcement operator that can expand the set of arguments, but the operator is not required to add all possible arguments (in contrast to the enforcement operator defined above). Say, that we can expand by arguments ${\mathit{a}}_1$ and ${\mathit{a}}_2$ . Suppose further that by adding ${\mathit{a}}_1$ to the original framework we can enforce the given interpretation. However, consider now the case that ${\mathit{a}}_1$ is a super argument of ${\mathit{a}}_2$ , which is specified by the contents of both arguments. Simple addition of ${\mathit{a}}_1$ might be reasonable, in certain cases, but it is likewise adequate to require that all sub arguments have to be present, as well. This can be specified by an implication: $\mathrm{(}\mathrm{(}{\mathit{a}}_1\in {\mathit{A}}^{\ast }\mathrm{)}\to \mathrm{(}{\mathit{a}}_2\in {\mathit{A}}^{\ast }\mathrm{)}\mathrm{)}$ . That is, this Boolean constraint specifies that whenever ${\mathit{a}}_1$ is part of the output ADF ${\mathit{D}}^{\ast }$ (e.g., by expansion), then also ${\mathit{a}}_2$ must be present in ${\mathit{D}}^{\ast }$ . In Section 6 further uses of such implications are exemplified for an enforcement operator respecting the internal structure of arguments.

Constraints on links. Next, we consider constraints on links. For notation, we say that, in the ADF ${\mathit{D}}^{\ast }$ , links ${\mathit{L}}^{+}$ are supporting links and ${\mathit{L}}^{-}$ are attacking links. For a link l define:

1. $\mathit{l}\in {\mathit{L}}^{\ast }$

2. $\mathit{l}\in {\mathit{L}}^{+}$

3. $\mathit{l}\in {\mathit{L}}^{-}$

4. $\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{)}$ belongs to specified graph class

Example 9.

Constraining the type of links can imply that the output ADF belongs to a proper sub-family of ADFs: if we require each link to be either attacking or supporting (via $\mathrm{(}\mathit{l}\in {\mathit{L}}^{\ast }\mathrm{)}\to \mathrm{(}\mathrm{(}\mathit{l}\in {\mathit{L}}^{+}\mathrm{)}\vee \mathrm{(}\mathit{l}\in {\mathit{L}}^{-}\mathrm{)}\mathrm{)}$ ), the output ADF is a BADF. Similarly, one can constrain that a part of the ADF is a BADF.

If each link is constrained to be attacking and not supporting, then the output ADF belongs to the family of frameworks defined in [87], which we call SETAFs here, in case no acceptance condition is unsatisfiable. These SETAFs are similar to AFs, but sets of arguments attack an argument.

That ADFs with only attacking links and SETAFs have a connection has been established by a translation of SETAFs to ADFs [95]. That ADFs with only attacking links have a corresponding form as SETAFs, in case no acceptance condition is unsatisfiable, can be shown by considering that each acceptance condition in an attack-only ADF can be represented via a Boolean formula in conjunctive normal form with only negative literals. A similar result has been shown for BADFs in [61, Theorem 3.1.23]; we specialize this result to attack-only ADFs and state a direct proof for the sake of completeness.

Proposition 1.

If an ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ satisfies constraint $\mathit{K}={\bigwedge }_{\mathit{l}\in {\mathit{L}}^{\ast }}\mathrm{(}\mathrm{(}\mathit{l}\in {\mathit{L}}^{-}\mathrm{)}\wedge \neg \mathrm{(}\mathit{l}\in {\mathit{L}}^{+}\mathrm{)}\mathrm{)}$ , then each acceptance condition ${\mathit{\phi }}_{\mathit{a}}^{\ast }\in {\mathit{C}}^{\ast }$ with ${\mathit{par}}_{{\mathit{D}}^{\ast }}\mathrm{(}\mathit{a}\mathrm{)}\ne \varnothing$ can be expressed as a Boolean formula in conjunctive normal form (CNF) with only negative literals.

Proof.

Let $\mathit{a}\in {\mathit{A}}^{\ast }$ . If ${\mathit{par}}_{{\mathit{D}}^{\ast }}\mathrm{(}\mathit{a}\mathrm{)}\ne \varnothing$ , then ${\mathit{\phi }}_{\mathit{a}}^{\ast }$ is neither tautological nor unsatisfiable, since the incoming links are not redundant (are not supporting). Thus, ${\mathit{\phi }}_{\mathit{a}}^{\ast }$ is both satisfiable and refutable. Consider a two-valued interpretation I s.t. $\mathit{I}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}^{\ast }\mathrm{)}$ evaluates to false. By property of attacking-only links, it follows that switching the truth value of any set of parents to true in I does not change the outcome. Now, take each interpretation I s.t. (i) $\mathit{I}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}^{\ast }\mathrm{)}$ evaluates to false and (ii) there is no ${\mathit{I}}^{\prime }$ s.t. ${\mathit{I}}^{\prime }\mathrm{(}{\mathit{\phi }}_{\mathit{a}}^{\ast }\mathrm{)}$ evaluates to false and $\{\mathit{x}\mid {\mathit{I}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}\}⊊\{\mathit{x}\mid \mathit{I}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}\}$ (I is subset-minimal w.r.t. arguments assigned to true). Let $\mathcal{I}$ be all such interpretations. Define ${\mathit{\phi }}_{\mathit{a}}^{\prime }={\bigwedge }_{\mathit{I}\in \mathcal{I}}\mathrm{(}{\bigvee }_{\mathit{I}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}}\neg \mathit{x}\mathrm{)}$ . We show that ${\mathit{\phi }}_{\mathit{a}}^{\ast }\equiv {\mathit{\phi }}_{\mathit{a}}^{\prime }$ holds. Let J be a two-valued interpretation satisfying ${\mathit{\phi }}_{\mathit{a}}^{\ast }$ . Then for each $\mathit{I}\in \mathcal{I}$ we have $\{\mathit{x}\mid \mathit{I}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}\}⊈\{\mathit{x}\mid \mathit{J}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}\}$ (otherwise J would not satisfy ${\mathit{\phi }}_{\mathit{a}}^{\ast }$ ). Thus, J satisfies ${\bigvee }_{\mathit{I}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}}\neg \mathit{x}$ (at least one argument assigned to true by I is false in J). This implies that J satisfies ${\mathit{\phi }}_{\mathit{a}}^{\prime }$ . Assume that J satisfies ${\mathit{\phi }}_{\mathit{a}}^{\prime }$ . If J does not satisfy ${\mathit{\phi }}_{\mathit{a}}^{\ast }$ then there is a ${\mathit{J}}^{\prime }\in \mathcal{I}$ s.t. $\{\mathit{x}\mid {\mathit{J}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}\}\subseteq \{\mathit{x}\mid \mathit{J}\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}\}$ . This implies a clause ${\bigvee }_{{\mathit{J}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}=\mathbf{t}}\neg \mathit{x}$ in ${\mathit{\phi }}_{\mathit{a}}^{\prime }$ . This implies that J does not satisfy this clause, a contradiction. Thus, J satisfies ${\mathit{\phi }}_{\mathit{a}}^{\ast }$ . □

From this result it can be inferred, via [78, Proposition 1], that if each acceptance condition is either equal to ⊤ or in CNF with negative literals, the ADF in question can be written as a SETAF. However, unsatisfiable conditions ( ${\mathit{\phi }}_{\mathit{a}}=\perp$ ) have no direct analogue. The underlying intuition is that if a set of arguments X attacks, in a SETAF, an argument a, then this can be written as ${\bigvee }_{\mathit{b}\in \mathit{X}}\neg \mathit{b}$ (one of the attackers must be “out” or false for the set-attack to be countered). If more sets attacking a exist, then this can be represented as a Boolean formula in CNF: ${\bigwedge }_{\mathrm{(}\mathit{X}\mathrm{,}\mathit{a}\mathrm{)}}{\bigvee }_{\mathit{b}\in \mathit{X}}\neg \mathit{b}$ . An unsatisfiable formula $\mathit{\phi }\equiv \perp$ cannot be directly represented in this way.

Example 10.

Constraining that the output ${\mathit{D}}^{\ast }$ belongs to a sub-family of ADFs also may lead to the case that there is no ADF (of that sub-family) that satisfies the given constraints. Consider constraining the output to have two arguments $\{\mathit{a}\mathrm{,}\mathit{b}\}$ , and the output shall have as its complete semantics the exact correspondence $\mathrm{\Sigma }=\{\{\mathit{a}\mid \mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}\}\mid \mathit{I}\in \mathit{\text{com}}\mathrm{(}{\mathit{D}}^{\ast }\mathrm{)}\}$ with $\mathrm{\Sigma }=\{\varnothing \mathrm{,}\{\mathit{a}\}\mathrm{,}\{\mathit{b}\}\mathrm{,}\{\mathit{a}\mathrm{,}\mathit{b}\}\}$ . That is, the semantical constraint states that there has to be a complete interpretation assigning no argument to true, one that assigns only a to true, one that assigns only b to true, and one that assigns both arguments to true. Such a semantical constraint does not correspond to the requirement we defined for enforcement, however, dynamic operators requiring exact semantics in the output framework exist, we recall some in Section 9. Requiring that each link in the output is attacking and non-supporting leads to non-existence of solution ADFs. If there is no link in the ADF, then there would be only one complete (grounded) interpretation. If there is a link, such a link has to originate from either a or b and lead to either a or b. Since this link is not supporting, but attacking, it follows that one acceptance condition is not equivalent to ⊤ or ⊥. This implies that assigning one argument to true (or both) leads to non-acceptance of an argument. This implies that $\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\}$ is not complete. Another way of seeing this fact is by considering any (set-)attack: such an attack cannot exist, since $\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{t}\}$ is complete. To have Σ as the semantical result under complete semantics on AFs, one needs more arguments (see [12,57]). In general ADFs, such a correspondence is possible without more arguments when allowing the use of supports.

Constraining the underlying graph structure of an ADF, i.e., $\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{)}$ , can be useful, as well, e.g., with constraint (L4). Example graph classes are directed acyclic graphs or bipartite graphs. For instance, directed acyclic graphs have appealing properties: one can view “leaf” arguments (i.e., arguments x whose dependencies ${\mathit{par}}_{\mathit{D}}\mathrm{(}\mathit{x}\mathrm{)}$ are empty) as, e.g., undisputed or evidential facts, or assumptions. In some formal approaches to (abstract) argumentation, arguments without dependencies are necessary, for instance for evidential argumentation systems (EASes) [93]. Computationally, acyclicity exhibits milder complexity than general graph structures, for several reasoning tasks, both for AFs [53,59,60] and for ADFs [77]. Bipartite graphs also enjoy interesting properties [56], and can be seen as arguments from two parties corresponding to the bipartite partition.

Constraints on acceptance conditions. We proceed to constraints on acceptance conditions. Given an ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ , a ${\mathit{\phi }}_{\mathit{s}}\in {\mathit{C}}^{\ast }$ , $\mathit{v}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ , a three-valued interpretation I, a two-valued interpretation ${\mathit{I}}^{\prime }$ , and a formula ψ, we define the following constraints. Recall that by $\mathit{\phi }[\mathit{I}]$ we denote the formula obtained by replacing arguments assigned to true by ⊤ and to false by ⊥, and by ${\mathit{I}}^{\prime }\mathrm{(}\mathit{\phi }\mathrm{)}$ we denote the evaluation of the Boolean formula φ by a two-valued interpretation ${\mathit{I}}^{\prime }$ .

${\mathit{I}}^{\prime }\mathrm{(}{\mathit{\phi }}_{\mathit{s}}\mathrm{)}=\mathit{v}$

${\mathit{\phi }}_{\mathit{s}}[\mathit{I}]$ satisfiable (refutable, tautological, or unsatisfiable)

${\mathit{\phi }}_{\mathit{s}}=\mathit{\psi }$

${\mathit{\phi }}_{\mathit{s}}[\mathit{I}]\equiv \mathit{\psi }$

That is, (C1) specifies that the acceptance condition of argument s shall evaluate to truth value v for a given two-valued interpretation ${\mathit{I}}^{\prime }$ . Constraints of type (C2) state that the partially evaluated acceptance condition of argument s must be satisfiable (or refutable, tautological, or unsatisfiable), indicating, e.g., that an argument can be accepted, in a certain context (or not). The third type of constraints says that an acceptance condition must be (exactly) equal to a given formula, and the last one that a partially evaluated acceptance condition (under three-valued interpretation I) must be equivalent to a given formula.

Example 11.

Constraints of type (C2) can be used, e.g., to require the output ADF to belong to the subclass of AFs. Let ${\mathit{I}}_{\mathbf{u}}$ ( ${\mathit{I}}_{\mathbf{f}}$ ) be an interpretation with all arguments assigned to undecided (false). One can require that $\mathrm{(}\mathit{b}\in {\mathit{A}}^{\ast }\to {\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}_{\mathbf{f}}]\text{ tautological}\mathrm{)}$ and $\mathrm{(}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{\ast }\to {\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}_{\mathbf{u}}{|}_{\mathbf{t}}^{\mathit{a}}]\text{ unsatisfiable}\mathrm{)}$ for parents of b. In other words, argument b is acceptable if all parents are false ( ${\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}_{\mathbf{f}}]$ is tautological), and not acceptable if parent a is true ( ${\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}_{\mathbf{u}}{|}_{\mathbf{t}}^{\mathit{a}}]$ updates parent a to true and then b is not acceptable if the resulting formula is unsatisfiable). To make this concrete, consider that argument b shall be attacked by arguments a and c, in the sense of an AF. Say one specifies that a and c are the only parents of b. Define ${\mathit{I}}_1=\{\mathit{a}\mapsto \mathbf{f}\mathrm{,}\mathit{b}\mapsto \mathbf{f}\mathrm{,}\mathit{c}\mapsto \mathbf{f}\}$ and ${\mathit{I}}_2=\{\mathit{a}\mapsto \mathbf{u}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\}$ . Stating $\mathrm{(}\mathit{b}\in {\mathit{A}}^{\ast }\to {\mathit{\phi }}_{\mathit{a}}[{\mathit{I}}_1]\text{ tautological}\mathrm{)}$ says that, if b is in the output ADF, then ${\mathit{\phi }}_{\mathit{a}}[{\mathit{I}}_1]\equiv \top$ (when all arguments are false, b is acceptable). Further, by stating $\mathrm{(}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{\ast }\to {\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}_2{|}_{\mathbf{t}}^{\mathit{a}}\text{ unsatisfiable}\mathrm{)}$ we get an attack from a onto b: ${\mathit{I}}_2{|}_{\mathbf{t}}^{\mathit{a}}=\{\mathit{a}\mapsto \mathbf{t}\mathrm{,}\mathit{b}\mapsto \mathbf{u}\mathrm{,}\mathit{c}\mapsto \mathbf{u}\}$ and ${\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}_2{|}_{\mathbf{t}}^{\mathit{a}}]\equiv \perp$ . Taken together, they imply that an argument can be accepted if all arguments are assigned false and assigning one argument with an incoming link to true implies non-acceptance.

Another use case for the constraints is when considering the internal structure of arguments. If two structures of arguments are logically inconsistent, and this is to be expressed directly within acceptance conditions, the preceding attack-like constraint can be used as well.

Further, one can constrain supports. For instance, one can specify that supporting links are a kind of necessary support: $\mathrm{(}\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{+}\mathrm{)}\to \mathrm{(}{\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}_{\mathbf{u}}{|}_{\mathbf{f}}^{\mathit{a}}]\text{ unsatisfiable}\mathrm{)}$ . Intuitively, this specifies that if a parent is false then the child argument cannot be acceptable.

Another type of constraint that can be expressed is to require no change between certain dependencies between arguments. For instance, say an argument a has several parents in an original ADF and a new one (b) in a modified ADF. Further, we want to state that in the output ADF all dependencies from parents, except b, are unchanged if b is false. This can be written as ${\mathit{\phi }}_{\mathit{s}}^{\ast }[{\mathit{I}}_{\mathbf{u}}{|}_{\mathbf{f}}^{\mathit{b}}]\equiv {\mathit{\phi }}_{\mathit{s}}$ (C4), with ${\mathit{\phi }}_{\mathit{s}}$ being the original acceptance condition of s. A use case of such constraints is also discussed in the first case study in Section 5.

Constraints on characteristic functions. Next we introduce a different type of constraint on the characteristic functions of ADFs ${\mathrm{\Gamma }}_{{\mathit{D}}^{\ast }}$ . Let $\mathit{v}\mathrm{,}{\mathit{v}}^{\prime }\in \{\mathbf{t}\mathrm{,}\mathbf{f}\mathrm{,}\mathbf{u}\}$ , and s and ${\mathit{s}}^{\prime }$ be arguments.

for each three-valued interpretation I it holds that ${\mathrm{\Gamma }}_{{\mathit{D}}^{\ast }}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{s}\mathrm{)}=\mathit{v}$ implies ${\mathrm{\Gamma }}_{{\mathit{D}}^{\ast }}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}{\mathit{s}}^{\prime }\mathrm{)}={\mathit{v}}^{\prime }$

Note that we restrict the three-valued interpretations I to be over the universe of arguments of ${\mathit{D}}^{\ast }$ .

Example 12.

A use case for this constraint is to state that two arguments cannot be both acceptable at the same time, even if there is no link between them. Consider $\forall \mathit{I}\mathrm{,}{\mathrm{\Gamma }}_{{\mathit{D}}^{\ast }}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{s}\mathrm{)}=\mathbf{t}$ implies ${\mathrm{\Gamma }}_{{\mathit{D}}^{\ast }}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}{\mathit{s}}^{\prime }\mathrm{)}=\mathbf{f}$ , which implies that if s accepted, in a scenario encoded by an interpretation I, then ${\mathit{s}}^{\prime }$ cannot be accepted. Similarly, one may encode positive relations. Note that it is not required that s is a parent of ${\mathit{s}}^{\prime }$ or vice versa. A potential use of this constraint is that an argument shall be rejected whenever one of its sub arguments is rejected (e.g. via an attack from another argument). While this seemingly contradicts an intuition that dependencies between arguments are to be expressed as links, such indirect dependencies can occur: e.g., consider three arguments a, b, and c, with b a sub argument of c. When acceptance of a leads to non-acceptance of b, e.g., through an attack from a, then c should be, likewise, rejected (unless exceptional cases occur). While this can be expressed via links from b to c, a constraint of type (Char) can express such behavior inside acceptance conditions, modeling potentially more complex scenarios. For instance, in some approaches to instantiation of AFs, no direct relation between sub arguments is specified.

Weights and optimization. For optimization constraints, define the cost of an ADF D via $\mathit{cost}\mathrm{(}\mathit{D}\mathrm{)}$ . For this paper, we let the cost function be abstract.

$\mathit{cost}\mathrm{(}{\mathit{D}}^{\ast }\mathrm{)}⩽\mathit{k}$

$\mathit{cost}\mathrm{(}{\mathit{D}}^{\ast }\mathrm{)}$ minimum over all ADFs

Example 13.

A straightforward way to define weights, and costs, is exemplified by the extension enforcement operation, where a modified attack contributes unit weight to the overall cost. That is, for an input ADF $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ and output ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ the cost is $\mathit{cost}\mathrm{(}{\mathit{D}}^{\ast }\mathrm{)}=|\mathit{L}\mathrm{\Delta }{\mathit{L}}^{\ast }|$ , i.e., the cost is the cardinality of the symmetric difference between the input and output links.

5. Case study: An enforcement operator for ADFs based on supports

In this section we use some of the proposed constraints to adapt the enforcement operator on ADFs to allow for only supporting links to be added. For the sake of readability, we will continually develop this operator.

We adapt non-strict enforcement under strong expansions of ADFs, as defined in Definition 9. We briefly recall this operator. Given an ADF $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ , a semantics σ, an interpretation I, and arguments to expand ${\mathit{A}}^{\prime }$ , it holds that ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ is a solution if two conditions hold. First $\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{)}$ is to be a strong expansion of $\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{)}$ (first two items of Definition 9). The second condition is that $\exists {\mathit{I}}^{\prime }\in \mathit{\sigma }\mathrm{(}{\mathit{D}}^{\ast }\mathrm{)}$ s.t. $\mathit{I}{⩽}_{\mathit{i}}{\mathit{I}}^{\prime }$ . For illustrative purposes, we initially drop the condition of optimality on modified links.

Consider, first, a variant of this operator that respects the following constraint: $$\begin{array}{c}\mathrm{\left(}\mathrm{\right(}{\mathit{a}}^{\prime }\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{\ast }\mathrm{)}\to \mathrm{(}{\mathit{a}}^{\prime }\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{+}\text{for each }\mathit{b}\in \mathit{A}\text{ and }{\mathit{a}}^{\prime }\in {\mathit{A}}^{\prime }.\end{array}$$ That is, all new links shall be supporting. While, technically, this achieves a “support enforcement” operation, we remark that such an operator enjoys rather high freedom in achieving the enforcement.

Example 14.

Consider ADF $\mathit{D}=\mathrm{(}\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ with ${\mathit{\phi }}_{\mathit{a}}=\mathit{b}$ , ${\mathit{\phi }}_{\mathit{b}}=\mathit{c}$ , and ${\mathit{\phi }}_{\mathit{c}}=\perp$ . Assume that we expand with an argument d and that we want to enforce a to be true in an admissible interpretation. This can be achieved simply by modifying ${\mathit{\phi }}_{\mathit{a}}$ to ${\mathit{\phi }}_{\mathit{a}}^{\prime }=\mathit{b}\vee \neg \mathit{b}$ (see Fig. 5(a)). Note that this modified ADF is an expansion, and new links are supporting (there are no new links).

Another potentially unintended example is when we desire to have an argument a false in an admissible interpretation of an expanded ADF. Say we have only one argument a, and may add argument b. The following modification can be applied: ${\mathit{\phi }}_{\mathit{a}}^{\ast }={\mathit{\phi }}_{\mathit{a}}\wedge \mathit{b}$ and ${\mathit{\phi }}_{\mathit{b}}^{\ast }\equiv \perp$ . That is, one can specify that argument a is accepted only if b is true, and stating that b is never acceptable. Intuitively, one “supports” an argument by requiring a new argument, and declaring that the new argument is not acceptable.

Fig. 5.

Enforcing a being true in an admissible interpretation via support enforcement: without further constraints (a), without modifying acceptance conditions when expanded arguments are rejected (b), and additionally when optimizing added links (Example 14).

Let us utilize the structural constraints to specify permissible changes in a more rigorous way. Consider that acceptance conditions shall be unchanged if new arguments are rejected (similarly as in Example 11 and constraint type (C4)): $$\begin{array}{c}{\mathit{I}}_{\mathbf{u}}{|}_{\mathbf{f}}^{{\mathit{A}}^{\prime }}\mathrm{\left(}{\mathit{\phi }}_{\mathit{a}}^{\ast }\mathrm{\right)}\equiv {\mathit{\phi }}_{\mathit{a}}\text{for each }\mathit{a}\in \mathit{A}.\end{array}$$ That is, when evaluating an acceptance condition partially under the interpretation assigning all expanded arguments ${\mathit{A}}^{\prime }$ to false, the resulting formula shall be equivalent to the original (unmodified) acceptance condition.

Example 15.

Continuing Example 14, under the new constraint, the modification shown in Fig. 5(a) is not allowed anymore. The reason for this is that the constraint just introduced is violated: ${\mathit{\phi }}_{\mathit{a}}^{\prime }{|}_{\mathbf{f}}^{\mathit{d}}=\mathit{b}\vee \neg \mathit{b}[\mathit{d}\mapsto \perp ]=\mathit{b}\vee \neg \mathit{b}\not\equiv {\mathit{\phi }}_{\mathit{a}}$ . That is, when evaluating the modified acceptance conditions partially for when d is false, the resulting formula is not equivalent to the original acceptance condition. One way to achieve the enforcement request of having a being true in an admissible interpretation is shown in Fig. 5(b), where several links were added from expanded argument d onto all others, requiring now d to be true.

In light of the preceding example, in addition we now specify that the cost of a solution ${\mathit{D}}^{\ast }$ is $|\mathit{L}\mathrm{\Delta }{\mathit{L}}^{\ast }|$ (similarly as for enforcement on AFs). A solution ${\mathit{D}}^{\ast }$ is optimal if there is no other solution with strictly less cost.

Example 16.

Under the optimization constraint, an optimal solution, for enforcement of Example 14, would be to having d support c, by modifying the acceptance condition to ${\mathit{\phi }}_{\mathit{c}}^{\prime }=\mathit{d}$ (see Fig. 5(c)). Another optimal solution is to directly support a via d, by modifying ${\mathit{\phi }}_{\mathit{a}}$ to ${\mathit{\phi }}_{\mathit{a}}^{\prime }=\mathit{b}\vee \mathit{d}$ .

Finally, we specify that expanded arguments are always acceptable: for each ${\mathit{a}}^{\prime }\in {\mathit{A}}^{\prime }$ we have ${\mathit{\phi }}_{{\mathit{a}}^{\prime }}^{\ast }\equiv \top$ . Summarizing, we use the following constraints (with constraint type on the right): $$\begin{array}{cc}\mathrm{\left(}\mathrm{\right(}{\mathit{a}}^{\prime }\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{\ast }\mathrm{)}\to \mathrm{(}{\mathit{a}}^{\prime }\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{L}}^{+}\forall \mathit{b}\in \mathit{A}\forall {\mathit{a}}^{\prime }\in {\mathit{A}}^{\prime }\hfill & \text{(L1)}\mathrm{,}\text{(L2)}\hfill \\ {\mathit{I}}_{\mathbf{u}}{|}_{\mathbf{f}}^{{\mathit{A}}^{\prime }}\mathrm{\left(}{\mathit{\phi }}_{\mathit{a}}^{\ast }\mathrm{\right)}\equiv {\mathit{\phi }}_{\mathit{a}}\forall \mathit{a}\in \mathit{A}\hfill & \text{(C4)}\hfill \\ {\mathit{\phi }}_{{\mathit{a}}^{\prime }}^{\ast }\equiv \top \forall {\mathit{a}}^{\prime }\in {\mathit{A}}^{\prime }\hfill & \text{(C4)}\hfill \end{array}$$

Additionally, this operator uses constraints of type (A1) and (L1) in order to specify expansions, and (O2) for the optimization. We call the corresponding operator that is defined via Definition 9 and respects these three constraints support enforcement.

Example 17.

Support enforcement can lead to rejection of arguments. Assume two arguments, a and b with ${\mathit{\phi }}_{\mathit{a}}=\neg \mathit{b}$ and ${\mathit{\phi }}_{\mathit{b}}=\perp$ . Enforcing a to be false in an admissible interpretation can be achieved via supporting b (e.g. via modification ${\mathit{\phi }}_{\mathit{b}}^{\ast }=\mathit{c}$ for a supporter c).

Support enforcement, however, is not always possible: assume that we want to enforce that a is false in an admissible interpretation. If ${\mathit{\phi }}_{\mathit{a}}\equiv \top$ , then supporting enforcement fails (support cannot make a modification to a, or any other part of an ADF, that leads to a being false in an admissible interpretation).

As the reader might have guessed, when looking at Example 16, support enforcement is possible if no argument is enforced to be false.

Proposition 2.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF, I be a three-valued interpretation over ${\mathit{A}}^{\ast }=\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{)}$ with $\mathit{A}\cap {\mathit{A}}^{\prime }=\varnothing$ for a non-empty ${\mathit{A}}^{\prime }$ , and σ be a semantics. If $\nexists \mathit{a}\in {\mathit{A}}^{\ast }$ s.t. $\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{f}$ then there exists an ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ that enforces I under σ for the support enforcement operator.

Proof.

For any argument a that is assigned true by I one can modify the acceptance condition by ${\mathit{\phi }}_{\mathit{a}}^{\ast }={\mathit{\phi }}_{\mathit{a}}\vee \mathit{b}$ for any $\mathit{b}\in {\mathit{A}}^{\prime }$ (then a is true in the grounded interpretation of the resulting modified ADF). □

The preceding proposition implies straightforward solutions to the support enforcement for arguments to be enforced to be true. The same simple modification is not applicable for arguments to be enforced to be false: a direct support of a new argument onto such an argument can only lead to more cases of acceptance. In such a case, an indirect support of, e.g., an attacker can lead to a successful enforcement. In any case, while we abstain in the above definition from introducing further constraints to support enforcement, several further constraints can be feasibly added, such as constraints which links are allowed to be added, and how acceptance conditions may change. In Section 7, we investigate which further constraints can be added to support enforcement (or other operations) without increased computational complexity.

Further, if enforcement is possible (independently of whether arguments are to be true/false), for a concrete instance, then it is possible with a singleton argument to expand, whenever the interpretation that represents the enforcement goal assigns undecided to the expanded arguments (if two ore more expanded arguments must be true, then one cannot restrict to one expanded argument). Formally, if one can enforce the desired status among the original arguments, then one can do so, for the original arguments, with a single new argument. Proposition 3.

Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF, I be a three-valued interpretation over ${\mathit{A}}^{\ast }=\mathrm{(}\mathit{A}\cup {\mathit{A}}^{\prime }\mathrm{)}$ with $\mathit{A}\cap {\mathit{A}}^{\prime }=\varnothing$ for a non-empty ${\mathit{A}}^{\prime }$ , and σ be a semantics. If there is an ADF ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ that enforces I under σ for the support enforcement operator, then there also exists an ADF ${\mathit{D}}_1^{\ast }=\mathrm{(}\mathit{A}\cup \{{\mathit{a}}^{\prime }\}\mathrm{,}{\mathit{L}}_1^{\ast }\mathrm{,}{\mathit{C}}_1^{\ast }\mathrm{)}$ , that enforces ${\mathit{I}}^{\prime }=\{\mathit{I}\mathrm{(}\mathit{a}\mathrm{)}\mid \mathit{a}\in \mathit{A}\}\cup \{{\mathit{a}}^{\prime }\mapsto \mathbf{t}\}$ under σ for the support enforcement operator for a singleton expanded argument set $\{{\mathit{a}}^{\prime }\}$ .

Proof.

Assume that ${\mathit{D}}^{\ast }$ enforces I under σ, for any of the considered semantics, and that there is a $\mathit{J}\in \mathit{\sigma }\mathrm{(}{\mathit{D}}^{\ast }\mathrm{)}$ with $\mathit{I}{⩽}_{\mathit{i}}\mathit{J}$ . Construct ${\mathit{D}}_1^{\ast }$ from ${\mathit{D}}^{\ast }$ by replacing each newly added variable (argument in ${\mathit{A}}^{\prime }$ ) by a distinguished argument ${\mathit{a}}^{\prime }$ . We claim that ${\mathit{I}}^{\prime }$ is enforced under σ with ${\mathit{D}}_1^{\ast }$ . Consider first that J is complete (which is the case when $\mathit{\sigma }\in \{\mathit{\text{com}}\mathrm{,}\mathit{\text{prf}}\mathrm{,}\mathit{\text{grd}}\}$ ). We argue that ${\mathrm{\Gamma }}_{{\mathit{D}}^{\ast }}\mathrm{(}\mathit{J}\mathrm{)}\mathrm{(}\mathit{x}\mathrm{)}={\mathrm{\Gamma }}_{{\mathit{D}}_1^{\ast }}\mathrm{(}\mathit{J}\mathrm{)}\mathrm{(}\mathit{x}\mathrm{)}$ for each $\mathit{x}\in \mathit{A}\cup \{{\mathit{a}}^{\prime }\}$ . Since J is complete it follows that J assigns t to all arguments in ${\mathit{A}}^{\prime }$ (they have tautological acceptance conditions). Replacing them with a single argument does not change (partial) evaluation of acceptance conditions. From this, it follows that J, when restricted to arguments $\mathit{A}\cup \{{\mathit{a}}^{\prime }\}$ is complete in ${\mathit{D}}_1^{\ast }$ . For complete-base semantics, the result follows in a straightforward fashion: if J is grounded (preferred) in ${\mathit{D}}^{\ast }$ , then J, projected onto arguments in ${\mathit{D}}_1^{\ast }$ , is grounded (preferred) in ${\mathit{D}}_1^{\ast }$ (since partial evaluations under three-valued interpretations that assign true to all expanded arguments are preserved from one framework to the other).

Consider now that $\mathit{J}\in \mathit{\text{adm}}\mathrm{(}{\mathit{D}}^{\ast }\mathrm{)}$ is admissible, but not necessarily complete. Let ${\mathit{J}}^{\prime }$ be the same interpretation, but restricted to $\mathit{A}\cup \{{\mathit{a}}^{\prime }\}$ and assigning true to ${\mathit{a}}^{\prime }$ . Let $\mathit{a}\in \mathit{A}$ be an arbitrary argument in the original ADF. Let ${\mathit{\phi }}_{\mathit{a}}$ be the original acceptance condition of a, and ${\mathit{\phi }}_{\mathit{a}}^{\ast }$ be the modified one in ${\mathit{D}}^{\ast }$ . Let ${\mathit{\phi }}_{\mathit{a}}^{\prime }={\mathit{\phi }}_{\mathit{a}}^{\ast }[{\mathit{A}}^{\prime }\mapsto {\mathit{a}}^{\prime }]$ , i.e., each expanded argument is replaced by ${\mathit{a}}^{\prime }$ . If $\mathit{J}\mathrm{(}\mathit{a}\mathrm{)}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ , then ${\mathit{\phi }}_{\mathit{a}}^{\ast }[\mathit{J}]$ is tautological or unsatisfiable. In both cases, ${\mathit{\phi }}_{\mathit{a}}^{\prime }[{\mathit{J}}^{\prime }]$ has the same property, i.e., is tautological if ${\mathit{\phi }}_{\mathit{a}}^{\ast }[\mathit{J}]$ is tautological and is unsatisfiable if ${\mathit{\phi }}_{\mathit{a}}^{\ast }[\mathit{J}]$ is unsatisfiable (possibly, more arguments are assigned to be true in ${\mathit{J}}^{\prime }$ than in J w.r.t. a’s acceptance condition, yet this preserves tautologies and unsatisfiability; due to expanded arguments’ tautological acceptance conditions, no expanded argument is assigned false). Consider the last case, i.e., that a is assigned undecided by J. Then ${\mathit{\phi }}_{\mathit{a}}^{\ast }[\mathit{J}]$ and ${\mathit{\phi }}_{\mathit{a}}^{\prime }[{\mathit{J}}^{\prime }]$ might not share the property of being a tautology or being unsatisfiable, yet, ${\mathit{J}}^{\prime }$ is, nevertheless, admissible (whenever ${\mathit{J}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ it holds trivially that ${\mathit{J}}^{\prime }\mathrm{(}\mathit{a}\mathrm{)}{⩽}_{\mathit{i}}{\mathrm{\Gamma }}_{{\mathit{D}}^{\ast }}\mathrm{(}{\mathit{J}}^{\prime }\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}$ ). In conclusion, ${\mathit{J}}^{\prime }$ is admissible in ${\mathit{D}}_1^{\ast }$ and, by construction, ${\mathit{I}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}{⩽}_{\mathit{i}}{\mathit{J}}^{\prime }\mathrm{(}\mathit{x}\mathrm{)}$ for each $\mathit{x}\in \mathit{A}$ . This achieves the enforcement request. □

6. Case study: An enforcement operator for structured argumentation

In this section we will use our structural constraints to adapt the non-strict enforcement operator on AFs (Definition 8) to respect knowledge bases from structured argumentation the AF was instantiated from. On a high-level, the enforcement operator we define receives as input an AF instantiated by a part of a given knowledge base, and aims to find an expansion of that AF enforcing certain arguments, with expansions respecting the knowledge base. Formal approaches to structured argumentation are quite heterogeneous [7], which is why we abstract from these approaches, in order to capture the intuitions of several formalisms.

Structured argumentation approaches [21,22,28,68,72,85] provide formal recipes for instantiating arguments and their relationships from a given knowledge base. In several cases the formalism that is instantiated is an AF [28,85]. We assume that a knowledge base is given as a set B of elements. This set may contain facts, rules, or further ingredients required to instantiate arguments. In this paper we do not specify these elements. For our purposes we assume only a few functions that a structured argumentation approach is composed of: (i) a function $\mathit{args}$ that returns all (abstract) arguments that can be generated from a knowledge base, (ii) a given function $\mathit{kb}$ that returns for a set of arguments their contents, i.e., returns the subset ${\mathit{B}}^{\prime }\subseteq \mathit{B}$ that is needed to instantiate the arguments, and (iii) a function $\mathit{att}$ that returns all attacks that can be instantiated. Formally, we also assume that the functions behave well, i.e., we have $\mathit{kb}\mathrm{(}\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}\subseteq \mathit{B}$ for any knowledge base B (every knowledge base element, when inspecting instantiated arguments from knowledge base B, is in B) and we assume that it holds that $\mathit{A}\subseteq \mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}\mathit{A}\mathrm{)}$ (when looking at the base of a set of arguments, then all these arguments can be constructed from that base). For $\mathit{att}$ , we assume that $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{att}\mathrm{(}\mathit{B}\mathrm{)}$ implies $\{\mathit{a}\mathrm{,}\mathit{b}\}\subseteq \mathit{args}\mathrm{(}\mathit{B}\mathrm{)}$ . Further, we assume that for ${\mathit{B}}^{\prime }\subseteq \mathit{B}$ we get $\mathit{f}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\subseteq \mathit{f}\mathrm{(}\mathit{B}\mathrm{)}$ for $\mathit{f}\in \{\mathit{args}\mathrm{,}\mathit{att}\}$ , and for argument sets ${\mathit{A}}^{\prime }\subseteq \mathit{A}$ we have $\mathit{kb}\mathrm{(}{\mathit{A}}^{\prime }\mathrm{)}\subseteq \mathit{kb}\mathrm{(}\mathit{A}\mathrm{)}$ . This means that all functions $\mathit{args}$ , $\mathit{att}$ , and $\mathit{kb}$ are ⊆-monotone. While subset monotonicity for the functions $\mathit{args}$ and $\mathit{kb}$ appear rational, there are cases when $\mathit{att}$ is, in fact, not subset-monotone: in presence of preferences, that are to be included in a knowledge base, addition of preferences might affect presence of attacks non-monotonically. We discuss impact of this at the end of this section, but leave the main part of this section to deal with the case of ⊆-monotone $\mathit{att}$ functions.

Example 18.

We exemplify the functions $\mathit{args}$ , $\mathit{kb}$ , and $\mathit{att}$ by a simple knowledge base, and associated AF that is constructed in the case of assumption-based argumentation frameworks (ABA) [28]. Similar functions can be defined, e.g., for the ASPIC+ framework [85]. We will not explicate the definitions of ABA, but stay on an intuitive level, and also, for illustration purposes, simplify some notions.

Two main ingredients for ABA are assumptions and rules. Say we have four assumptions $\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ , and rules as shown in Fig. 6: from a one can derive x, from b one can derive the negation (contrary) of a, from c one can derive the negation of b, from a and c together one can derive y, and finally from d one can derive z. These derivations directly correspond to the arguments ${\mathit{a}}_1$ to ${\mathit{a}}_5$ . By the contraries the arguments derive, one can infer that ${\mathit{a}}_2$ attacks ${\mathit{a}}_1$ and that ${\mathit{a}}_3$ attacks ${\mathit{a}}_2$ . That is, for $\mathit{B}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ we get $\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}=\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\mathrm{,}{\mathit{a}}_4\mathrm{,}{\mathit{a}}_5\}$ , $\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}=\{\mathrm{(}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_1\mathrm{)}\mathrm{,}\mathrm{(}{\mathit{a}}_3\mathrm{,}{\mathit{a}}_2\mathrm{)}\}$ , and e.g., $\mathit{kb}\mathrm{(}\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_4\}\mathrm{)}=\{\mathit{a}\mathrm{,}\mathit{c}\}$ .2

²

In this example we included only assumptions as part of B, i.e., only assumptions as part of the knowledge base, and incorporated the rules (and contraries) into the functions $\mathit{kb}$ , $\mathit{args}$ , and $\mathit{att}$ . We have chosen this way mainly for illustration. Including rules and contraries into the knowledge base B, and adapting the functions accordingly, poses no barrier to our approach. In fact, in the definition of ABA [28] one usually includes rules and contraries in a deductive system that can be seen as part of a knowledge base. With our formalization the enforcement operator we will define presumes that rules and contraries have to be included in a solution AF, while assumptions are optional. Finally, we note that in the original ABA definition further arguments are present, namely those that correspond to assumptions without application of rules, e.g., an argument corresponding only to assumption a without derivation of x. We omitted these arguments, again, for illustration purposes.

In Fig. 7 we show for each ${\mathit{B}}^{\prime }\supseteq \{\mathit{a}\mathrm{,}\mathit{b}\}$ the corresponding abstract argumentation framework. For instance, for ${\mathit{B}}^{\prime }=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}$ we have ${\mathit{F}}_3$ .

Fig. 6.

A simple structured (assumption-based) argumentation framework (Example 18). For the ABA framework consisting of four assumptions a, b, c, and d, and rules as shown in (b), several arguments can be constructed, with five arguments shown in (a). Attacks arise when an argument concludes a negated assumption of another argument (e.g., argument ${\mathit{a}}_2$ attacks argument ${\mathit{a}}_1$ on assumption a).

In the following we assume that we are given both a knowledge base B, and an AF $\mathit{F}=\mathrm{(}\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}$ instantiated from this base. Further, we assume a subframework ${\mathit{F}}^{\prime }=\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{R}}^{\prime }\mathrm{)}$ as the current state of argumentation such that ${\mathit{B}}^{\prime }\subseteq \mathit{B}$ and ${\mathit{A}}^{\prime }=\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}$ and ${\mathit{R}}^{\prime }=\mathit{att}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}$ . One interpretation of this context is that the arguments in ${\mathit{F}}^{\prime }$ have been uttered, while the remaining part of the knowledge base $\mathit{B}\setminus {\mathit{B}}^{\prime }$ has not been uttered (or, is “private” to an agent). For instance, in Fig. 7, ${\mathit{F}}_4$ corresponds to the full AF, for the knowledge base from Example 18, and ${\mathit{F}}_1$ could be a current AF.

The enforcement operator we now define aims to provide means to find a knowledge base ${\mathit{B}}^{\ast }$ , with $\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\subseteq \mathit{args}\mathrm{(}{\mathit{B}}^{\ast }\mathrm{)}\subseteq \mathit{args}\mathrm{(}\mathit{B}\mathrm{)}$ , such that a desired argument (or set of arguments) is acceptable, under a certain semantics σ. Towards the operator, we again adapt the existing enforcement operator in AFs (recall Definition 8), and modify this operator, as follows (the full definition is given in Definition 10). First, for the expansion we do not require strongness nor addition of all arguments that may added. Further, we apply the following constraints (the arguments that may be added are $\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\setminus \mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}$ ).

$\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\subseteq {\mathit{A}}^{\ast }\subseteq \mathit{args}\mathrm{(}\mathit{B}\mathrm{)}$

$\mathit{att}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}{|}_{{\mathit{A}}^{\ast }}\subseteq {\mathit{R}}^{\ast }\subseteq \mathit{att}\mathrm{(}\mathit{B}\mathrm{)}{|}_{{\mathit{A}}^{\ast }}$

$\mathrm{(}{\mathit{a}}_1\in {\mathit{A}}^{\ast }\wedge \cdots \wedge {\mathit{a}}_{\mathit{n}}\in {\mathit{A}}^{\ast }\mathrm{)}\to \mathit{b}\in {\mathit{A}}^{\ast }$ $\forall \mathit{b}\in \mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}\mathrm{)}\mathrm{)}$ and each $\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}\subseteq \mathit{args}\mathrm{(}\mathit{B}\mathrm{)}$

$\mathrm{(}\mathit{a}\in {\mathit{A}}^{\ast }\wedge \mathit{b}\in {\mathit{A}}^{\ast }\mathrm{)}\to \mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{R}}^{\ast }$ for $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{att}\mathrm{(}\mathit{B}\mathrm{)}$

In words, we aim to find an AF ${\mathit{F}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{R}}^{\ast }\mathrm{)}$ such that (1) the set of arguments shall be between the current state, $arg\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}$ , and the full knowledge base $arg\mathrm{(}\mathit{B}\mathrm{)}$ ; similarly (2) specifies that the attacks shall be between those two extremes, (3) states that whenever an argument b can be constructed from the components of existing arguments in ${\mathit{A}}^{\ast }$ it has to be included, and (4) requires that no attack between arguments may be omitted. We dub the resulting operator structured enforcement. For clarity, the full formal definition is also given next.

Definition 10.

Let B be a knowledge base and ${\mathit{B}}^{\prime }\subseteq \mathit{B}$ . Let $\mathit{F}=\mathrm{(}{\mathit{A}}^{\prime }\mathrm{,}{\mathit{R}}^{\prime }\mathrm{)}$ be an AF such that $\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}={\mathit{A}}^{\prime }$ and $\mathit{att}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}={\mathit{R}}^{\prime }$ , σ be a semantics, and $\mathit{S}\subseteq {\mathit{A}}^{\prime }$ . An AF ${\mathit{F}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{R}}^{\ast }\mathrm{)}$ non-strictly enforces S under σ if

$\exists {\mathit{S}}^{\prime }\in \mathit{\sigma }\mathrm{(}{\mathit{F}}^{\ast }\mathrm{)}$ such that $\mathit{S}\subseteq {\mathit{S}}^{\prime }$ ,

the constraints (1)–(4) are satisfied, and

$|{\mathit{R}}^{\prime }\mathrm{\Delta }{\mathit{R}}^{\ast }|$ is minimum over all AFs satisfying the previous conditions.

Example 19.

Consider again Example 18 and the corresponding knowledge base B. Say we desire to enforce (via structured enforcement) argument ${\mathit{a}}_1$ to be part of an admissible set, and the given AF (current state) is ${\mathit{F}}_1=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ with $\mathit{A}=\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\}$ and $\mathit{R}=\{\mathrm{(}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_1\mathrm{)}\}$ . In this AF, we have $\mathit{\text{adm}}\mathrm{(}{\mathit{F}}_1\mathrm{)}=\{\varnothing \mathrm{,}\{{\mathit{a}}_2\}\}$ . Since we have to include both ${\mathit{a}}_1$ and ${\mathit{a}}_2$ , achieving ${\mathit{a}}_1$ being in an admissible set requires addition of ${\mathit{a}}_3$ that defeats ${\mathit{a}}_2$ and defends ${\mathit{a}}_1$ . Note that simple addition of ${\mathit{a}}_3$ is not allowed, since ${\mathit{a}}_4\in \mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}\{{\mathit{a}}_1\mathrm{,}{\mathit{a}}_2\mathrm{,}{\mathit{a}}_3\}\mathrm{)}\mathrm{)}$ , and, thus, we have to satisfy the constraint $\mathrm{(}{\mathit{a}}_1\in {\mathit{A}}^{\ast }\wedge {\mathit{a}}_2\in {\mathit{A}}^{\ast }\wedge {\mathit{a}}_3\in {\mathit{A}}^{\ast }\mathrm{)}\to {\mathit{a}}_4\in {\mathit{A}}^{\ast }$ . One solution is ${\mathit{F}}_3$ , shown in Fig. 7, where we have added both ${\mathit{a}}_3$ and ${\mathit{a}}_4$ , corresponding to addition of c to ${\mathit{B}}^{\prime }=\{\mathit{a}\mathrm{,}\mathit{b}\}$ (the base for ${\mathit{F}}_1$ ) in order to get ${\mathit{B}}^{\ast }=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}$ . See also Fig. 7, which shows all AFs that satisfy the structural constraints. For instance, ${\mathit{F}}_4$ also has an admissible set containing a, and is another solution to the instance for the structured enforcement operator (same number of attacks added).

Fig. 7.

AFs associated to parts of the knowledge base that contain a and b (Examples 18 and 19). For each AF ${\mathit{F}}_{\mathit{x}}$ ( $\mathit{x}\in \{1\mathrm{,}\dots \mathrm{,}4\}$ ) the corresponding knowledge base ${\mathit{B}}_{\mathit{x}}$ is shown above. It holds that $\mathit{kb}\mathrm{(}{\mathit{A}}_{\mathit{x}}\mathrm{)}={\mathit{B}}_{\mathit{x}}$ with ${\mathit{A}}_{\mathit{x}}$ the argument set of ${\mathit{F}}_{\mathit{x}}$ .

Next we show that the structured enforcement operator behaves “well” regarding the given knowledge base. That is, if B is the full knowledge base and ${\mathit{F}}^{\prime }$ is the current AF, then (i) no elements outside the knowledge base are invented, (ii) a solution AF ${\mathit{F}}^{\ast }$ contains all arguments that can be constructed when considering its base, and (iii) no attack was omitted.

Proposition 4.

Let B be a knowledge base, ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\mathrm{)}$ an AF for some ${\mathit{B}}^{\prime }\subseteq \mathit{B}$ , $\mathit{S}\subseteq \mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}$ , and σ be a semantics. If ${\mathit{F}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{R}}^{\ast }\mathrm{)}$ non-strictly enforces S under σ for the structured enforcement operator for ${\mathit{F}}^{\prime }$ , then it holds that

$\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}\subseteq \mathit{B}$ ,

$\mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}\mathrm{)}={\mathit{A}}^{\ast }$ , and

if $\mathit{a}\mathrm{,}\mathit{b}\in {\mathit{A}}^{\ast }$ holds we have $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{att}\mathrm{(}\mathit{B}\mathrm{)}$ iff $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{R}}^{\ast }$ .

Proof.

Recall that for any B we assume that $\mathit{kb}\mathrm{(}arg\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}\subseteq \mathit{B}$ holds, and that all functions $\mathit{args}$ , $\mathit{att}$ , and $\mathit{kb}$ are ⊆-monotone. For the first item, since $\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\subseteq {\mathit{A}}^{\ast }\subseteq \mathit{args}\mathrm{(}\mathit{B}\mathrm{)}$ (by constraint (1)), it follows that $\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}\subseteq \mathit{kb}\mathrm{(}\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}\subseteq \mathit{B}$ . By constraint (3) we get that for any argument $\mathit{b}\in \mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}\mathrm{)}$ the implication ${\bigwedge }_{{\mathit{a}}^{\ast }\in {\mathit{A}}^{\ast }}{\mathit{a}}^{\ast }\in {\mathit{A}}^{\ast }\to \mathit{b}\in {\mathit{A}}^{\ast }$ must be satisfied. The antecedent of that implication is trivially satisfied. This implies that $\mathit{b}\in {\mathit{A}}^{\ast }$ for any $\mathit{b}\in \mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}\mathrm{)}$ . Equality of item 2 then holds because we assume ${\mathit{A}}^{\ast }\subseteq \mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}$ . Assume that $\mathit{a}\mathrm{,}\mathit{b}\in {\mathit{A}}^{\ast }$ holds. If $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{att}\mathrm{(}\mathit{B}\mathrm{)}$ holds, then by constraint (4) we get $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{R}}^{\ast }$ . If $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{R}}^{\ast }$ holds, then $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{att}\mathrm{(}\mathit{B}\mathrm{)}$ follows due to constraints (1) and (2). □

We close this section with some remarks on the structured enforcement operator. First, we note that there are cases when an AF corresponding to the whole knowledge base does not achieve that a desired set of arguments is part of an extension, but a subframework might. That is, when interpreting the structured enforcement as “disclosing” information, in form of AF expansion for part of a knowledge base, an agent may withhold information in its own knowledge base, but still achieve the enforcement goal. We exemplify this behavior in a simple example.

Example 20.

Assume a knowledge base B with the corresponding AF $\mathit{F}=\mathrm{(}\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}$ with $\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\mathrm{,}\mathit{d}\}$ and $\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}=\{\mathrm{(}\mathit{d}\mathrm{,}\mathit{c}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{c}\mathrm{,}\mathit{b}\mathrm{)}\mathrm{,}\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}\}$ , i.e., the AF is a simple chain of attacks. Say the current AF ${\mathit{F}}_1$ consists only of arguments a and b, and the attack $\mathrm{(}\mathit{b}\mathrm{,}\mathit{a}\mathrm{)}$ , say via base ${\mathit{B}}_1\subset \mathit{B}$ . It holds that a is not part of an admissible set for either F or ${\mathit{F}}_1$ , i.e., is not acceptable, under admissible semantics, when considering the current state and the full knowledge of base B. However, say, for ${\mathit{B}}^{\prime }$ , with ${\mathit{B}}_1\subset {\mathit{B}}^{\prime }\subset \mathit{B}$ we have ${\mathit{F}}^{\prime }=\mathrm{(}\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}\mathrm{)}$ with $\mathit{args}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}=\{\mathit{a}\mathrm{,}\mathit{b}\mathrm{,}\mathit{c}\}$ . In this AF ${\mathit{F}}^{\prime }$ there is an admissible set containing a, namely $\{\mathit{a}\mathrm{,}\mathit{c}\}$ , with c defending a against b. Since d is not part of ${\mathit{F}}^{\prime }$ , the attack from d to c is neglected.

Regarding the optimization statement, we have chosen to use the same optimization statement as for the (standard) AF enforcement operator, i.e., the number of modified attacks has to be minimum. Alternatives to that can also be considered, e.g., minimizing the number of added arguments, or the size of the underlying knowledge base, also possibly with weights attached to elements in the base. The latter optimization can be interpreted as minimizing what parts of a knowledge base one has to “expose” (if the setting is a multi-agent setting, for instance), in order to be equipped with the right arguments to utter in a debate and achieve an enforcement goal.

Further, constraint (3) is arguably not well suited in all cases, particularly when considering computational properties (there can be exponentially many such constraints). We discuss computational aspects in Section 7, including a more efficient representation of this constraint.

As a final remark, when the $\mathit{att}$ function is not ⊆-monotone, a constraint of type (4) is not adequate anymore, since an attack $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$ has to be present iff this attack is prescribed by $\mathit{att}\mathrm{(}{\mathit{B}}^{\ast }\mathrm{)}$ for the knowledge base underlying the solution AF ${\mathit{F}}^{\ast }$ . Yet, as is the case with preferences in structured argumentation (see also the discussion at the beginning of this section), it does not hold that $\mathit{B}\subseteq {\mathit{B}}^{\prime }$ implies $\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}\subseteq \mathit{att}\mathrm{(}{\mathit{B}}^{\prime }\mathrm{)}$ if a preference not present in B, but in ${\mathit{B}}^{\prime }$ , prevents an attack. On a meta-level, one can define an associated constraint: if $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in \mathit{att}\mathrm{(}\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}\mathrm{)}$ then $\mathrm{(}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}\in {\mathit{R}}^{\ast }$ . This constraint is not directly defined on arguments and attacks, but on the underlying knowledge base.

7. Computational aspects

In this section we show complexity results for the considered constraints from Section 4, the support enforcement operator on ADFs from Section 5, and the structured enforcement operator from Section 6.

We make use of standard complexity classes for decision problems, which are problems that are answered either positively or negatively. Concretely, we use the classes P, $\mathit{NP}$ , and $\mathit{coNP}$ . The first class contains all decision problems that can be decided in deterministic polynomial time and $\mathit{NP}$ contains all decision problems solvable in non-deterministic polynomial time. The third class, $\mathit{coNP}$ , contains all complementary problems to problems in $\mathit{NP}$ (i.e., the answers are switched).

7.1. Complexity of satisfaction of the structural constraints

In this section we investigate the feasibility of the constraints. More concretely, we show the complexity of the task of verifying whether a given ADF satisfies certain constraints. This insight is important for developing dynamic operators that use such constraints. For instance, if we know that a certain constraint c can be checked in polynomial time, then a dynamic operator that constructs a candidate solution ADF can verify the constraint in polynomial time. If this algorithm is non-deterministic, then the complexity of the overall algorithm is likely to stay the same even if constraint c has to be considered, since a non-deterministic algorithm that runs in polynomial time can check a polynomial number of constraints that can be checked in polynomial time for a non-deterministically guessed object. In Fig. 8, we see a high-level view of such an algorithm: after parsing the input, a framework, e.g., an AF or ADF, is constructed. After that the constructed framework is verified, i.e., checked whether all semantical, structural, and syntactical constraints are met. If the framework is deemed sufficient, then it is returned in the last step. If we assume that the framework construction is done non-deterministically, then if all constraints can be checked in polynomial time, we arrive at an “ $\mathit{NP}$ -algorithm”.

Fig. 8.

High-level view on dynamic algorithms.

There is evidence that dynamic operators in abstract argumentation are likely to be $\mathit{NP}$ hard, e.g. extension enforcement on AFs is in many cases $\mathit{NP}$ hard [44,102]. That is, for these kind of operators augmentation with any of the polynomial-time decidable constraints comes at no additional cost complexity-wise, in case the algorithm follows the workflow shown in Fig. 8. In Section 8, we consider also experimentally effects on the runtime.

A further benefit of having polynomial-time decidable constraints is that they can, usually, be incorporated more easily in implementations that make direct use of constraint languages, such as Boolean logic. In fact, many modern implementations of AF reasoning (dynamic or static) make use of solvers on Boolean logic, or variants thereof [37,38].

We begin analyzing the basic constraints, where polynomial-time decidability is immediate. For constraints of type (L4), the following results holds when the graph class is verifiable in polynomial time. We consider here directed acyclic graphs and bipartite graphs, as examples.

Proposition 5.

Verifying whether a given ADF satisfies constraints of type

(G1) , (G2) ,

(A1) ,

(L1) , (L4) ,

(C1) , or (C3)

is decidable in polynomial time.

Proof.

Complexity of these constraints follows directly: checking constraints (G1), (G2), (A1), (L1) amount to check membership in a given set, checking constraint (L4) requires verifying whether the graph structure of the ADF is acyclic or bipartite (both can be decided in polynomial time), checking constraint (C1) amounts to evaluating a Boolean formula under a two-valued interpretation, and checking constraint (C3) requires checking equal syntax of two Boolean formulas. □

We proceed to more sophisticated constraints. By (C2) we refer to cases where we ask for satisfiability (refutability) and by (C2)′ to the cases asking for tautology (unsatisfiability).

Proposition 6.

Verifying whether a given ADF satisfies

a constraint of type (C2) is $\mathit{NP}$ -complete,

and a constraint of type (L2) , (L3) , (C2) ′, (C4) , or (Char) is $\mathit{coNP}$ -complete.

Proof.

We show each constraint separately.

(C2): for membership note that checking whether a (partially evaluated) formula is satisfiable/refutable is in $\mathit{NP}$ ; Hardness follows from considering $\mathit{\phi }[{\mathit{I}}_{\mathbf{u}}]=\mathit{\phi }$ by a reduction from checking satisfiability (refutability) of a Boolean formula φ.

(L2) and (L3): follows from [61,99] (checking whether a link is attacking/supporting is $\mathit{coNP}$ -complete);

(C2)′: analogously as for (C2), but for tautological or unsatisfiable formulas;

(C4): immediate, since checking equivalence of (partially evaluated) formulas is an archetypical $\mathit{coNP}$ -complete problem;

(Char): let ${\mathit{D}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{L}}^{\ast }\mathrm{,}{\mathit{C}}^{\ast }\mathrm{)}$ , ${\mathit{\phi }}_{\mathit{a}}\mathrm{,}{\mathit{\phi }}_{\mathit{b}}\in {\mathit{C}}^{\ast }$ , and $\mathit{v}\mathrm{,}{\mathit{v}}^{\prime }\in \{\mathbf{t}\mathrm{,}\mathbf{f}\mathrm{,}\mathbf{u}\}$ be an arbitrary instance of this problem. Consider the complementary problem, i.e., checking whether there is an I s.t. ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{v}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne {\mathit{v}}^{\prime }$ . We look at the sub cases individually for the truth values, and argue that in each sub case a constant number of witnesses (interpretations) are sufficient to witness that the instance is a yes instance, and that they can be checked in polynomial time (implying that the complementary problem is in $\mathit{coNP}$ ).

$\mathit{v}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ and ${\mathit{v}}^{\prime }\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ : consider the case that both are equal to t (analogous for other combinations of t and f). Assume that there is an I s.t. ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{t}$ . Then, for all completions J of I we have $\mathit{J}\vDash {\mathit{\phi }}_{\mathit{a}}$ . Further, there is a completion ${\mathit{J}}^{\prime }$ of I s.t. ${\mathit{J}}^{\prime }⊭{\mathit{\phi }}_{\mathit{b}}$ (since ${\mathit{\phi }}_{\mathit{b}}[\mathit{I}]$ is not tautological). Then ${\mathit{J}}^{\prime }$ is a witness for ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{J}}^{\prime }\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{J}}^{\prime }\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{t}$ , since $\mathit{I}{⩽}_{\mathit{i}}{\mathit{J}}^{\prime }$ . Concretely, ${\mathit{J}}^{\prime }$ is two-valued and ${\mathit{J}}^{\prime }\vDash {\mathit{\phi }}_{\mathit{a}}$ and ${\mathit{J}}^{\prime }⊭{\mathit{\phi }}_{\mathit{b}}$ ;

$\mathit{v}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ and ${\mathit{v}}^{\prime }=\mathbf{u}$ : assume that there is an I s.t. ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{u}$ . Then, ${\mathit{\phi }}_{\mathit{b}}[\mathit{I}]$ is either tautological or unsatisfiable. Any completion J of I can be used as a witness for ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{u}$ ;

$\mathit{v}=\mathbf{u}$ and ${\mathit{v}}^{\prime }\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ : assume that there is an I s.t. ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{t}$ . Then this is witnessed by three completions of I: one that satisfies ${\mathit{\phi }}_{\mathit{a}}$ one that refutes ${\mathit{\phi }}_{\mathit{a}}$ and one that refutes  ${\mathit{\phi }}_{\mathit{b}}$ .

$\mathit{v}=\mathbf{u}$ and ${\mathit{v}}^{\prime }=\mathbf{u}$ : assume that there is an I s.t. ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{u}$ . Then, ${\mathit{\phi }}_{\mathit{b}}[\mathit{I}]$ is either tautological or unsatisfiable. There are two witnesses for ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ : J and ${\mathit{J}}^{\prime }$ , with the former satisfying ${\mathit{\phi }}_{\mathit{a}}$ and the latter refuting ${\mathit{\phi }}_{\mathit{a}}$ . There exist such witnesses that differ only in assignment to one variable (otherwise the formula ${\mathit{\phi }}_{\mathit{a}}[\mathit{I}]$ would be tautological or unsatisfiable). Now take ${\mathit{I}}^{\prime }$ instead of I that assigns all variables as J and ${\mathit{J}}^{\prime }$ , except where they differ. We claim that ${\mathit{I}}^{\prime }$ is also a witness, i.e., that ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{I}}^{\prime }\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{u}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}{\mathit{I}}^{\prime }\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{u}$ holds. It holds that there are still two witnesses for the first statement (via J and ${\mathit{J}}^{\prime }$ ), and ${\mathit{\phi }}_{\mathit{b}}[{\mathit{I}}^{\prime }]$ is also tautological or unsatisfiable (one just needs to check two completions of ${\mathit{I}}^{\prime }$ for ${\mathit{\phi }}_{\mathit{b}}$ ).

Thus, one can always find a constant number of interpretations that witness the property. This means the problem is in $\mathit{NP}$ , and the original problem for (Char) in $\mathit{coNP}$ .

For hardness: consider the problem of checking whether a formula φ is tautological. Then ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{a}\mathrm{)}=\mathbf{t}$ and ${\mathrm{\Gamma }}_{\mathit{D}}\mathrm{(}\mathit{I}\mathrm{)}\mathrm{(}\mathit{b}\mathrm{)}\ne \mathbf{t}$ checks this property if ${\mathit{\phi }}_{\mathit{a}}=\mathit{\phi }$ , ${\mathit{\phi }}_{\mathit{b}}=\perp$ , and $\mathit{I}={\mathit{I}}_{\mathbf{u}}$ .

 □

While some of these useful constraints have relatively high complexity, if we restrict an output ADF ${\mathit{D}}^{\ast }$ to be a bipolar ADF with known link types, we can infer the following.

Proposition 7.

Verifying whether a BADF with known link types satisfies

a constraint of type (L2) , (L3) , or (C2) is decidable in P, and

a constraint of type (C4) is $\mathit{coNP}$ -complete.

Proof.

For (L2) and (L3) the claim is immediate (the link types are given). For (C2), the claim follows directly from [99]. For (C4), hardness follows from taking ${\mathit{\phi }}_{\mathit{s}}=\perp \wedge \mathit{\psi }$ for some ψ containing all variables from a given φ; then checking whether ${\mathit{I}}_{\mathbf{u}}\mathrm{(}{\mathit{\phi }}_{\mathit{s}}\mathrm{)}\equiv \mathit{\phi }$ directly corresponds to checking whether φ is unsatisfiable. □

If one imposes the condition that each argument has at most k parents, for a given and fixed k (i.e. k is a constant), we can infer that all constraints can be checked in polynomial time, except for the optimization constraints.

Proposition 8.

Let k be a constant integer. Satisfaction of any constraint defined in Section  4 , except (O1) and (O2) , for a given ADF where each argument has at most k parents, is decidable in polynomial time.

Proof.

Membership follows, since under the restrictions it holds that one can construct the whole truth table in polynomial time (since we have a bounded number of variables in the conditions). Then one can check each property in polynomial time. □

7.2. Complexity of support enforcement under admissible semantics

We now show that the novel enforcement operator defined in Section 5 has the same complexity as the non-strict extension enforcement operator on AFs, under certain restrictions. We investigate the decision problem of the new enforcement operator, where we ask whether there exists a solution ADF such that its cost is at most a given integer (which is a standard way to investigate complexity of optimization problems). As a further condition we require the number of parents and ${\mathit{A}}^{\prime }$ to be bounded by a constant.

Proposition 9.

Support enforcement under admissible semantics on ADFs is $\mathit{NP}$ -complete, if both the number of parents of each argument and the set of expanded arguments are bounded by a constant.

Proof.

Membership follows from constructing the truth table for each argument’s acceptance condition, guessing new links from the expanded arguments, and guessing new entries in expanded truth tables. That is, for an argument a, construct the whole truth table for the original acceptance condition ${\mathit{\phi }}_{\mathit{a}}$ , which is exponential in the number of variables of a. If a new link is guessed as an incoming link to a, expand the truth table by the new incoming links as new variables. For each new entry in the expanded truth table, assign the guessed truth value. Since both the number of original parents of a and the expanded arguments are bounded by a constant, say k, the overall size of the expanded truth table is bounded from above by $2^{2·\mathit{k}}$ .

Finally, non-deterministically construct a three-valued interpretation I and check whether I is admissible in the expanded ADF, and whether the given interpretation J is less informative, i.e., that $\mathit{J}{⩽}_{\mathit{i}}\mathit{I}$ . Checking admissibility can be done in polynomial time if the truth tables are computed. To see this consider Definition 5. Checking whether ${\mathit{\phi }}_{\mathit{a}}[\mathit{I}]$ is tautological or unsatisfiable amounts to consulting rows in the truth table.

For hardness, we show hardness holds already for AFs. Concretely, we adapt an existing proof for checking whether an argument is part of an admissible set of a given AF, which is an $\mathit{NP}$ -complete problem. Let $\mathit{\phi }={\mathit{c}}_1\wedge \cdots \wedge {\mathit{c}}_{\mathit{n}}$ be a Boolean formula in conjunctive normal form with at most three literals per clause over vocabulary X and clauses $\mathit{C}=\{{\mathit{c}}_1\mathrm{,}\dots \mathrm{,}{\mathit{c}}_{\mathit{n}}\}$ . Construct AF $\mathit{F}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{R}\mathrm{)}$ with $$\begin{array}{ll}\hfill & \mathit{A}=\mathit{X}\cup \{\bar{\mathit{x}}\mid \mathit{x}\in \mathit{X}\}\cup \mathit{C}\cup \{{\mathit{c}}^{\prime }\mid \mathit{c}\in \mathit{C}\}\\ \hfill & \mathit{R}=\{\mathrm{(}\mathit{x}\mathrm{,}\bar{\mathit{x}}\mathrm{)}\mathrm{,}\mathrm{(}\bar{\mathit{x}}\mathrm{,}\mathit{x}\mathrm{)}\mid \mathit{x}\in \mathit{X}\}\\ \hfill & \phantom{\mathit{R}=}\cup \{\mathrm{(}\mathit{x}\mathrm{,}\mathit{c}\mathrm{)}\mid \mathit{c}\in \mathit{C}\mathrm{,}\mathit{x}\in \mathit{c}\}\\ \hfill & \phantom{\mathit{R}=}\cup \{\mathrm{(}\bar{\mathit{x}}\mathrm{,}\mathit{c}\mathrm{)}\mid \mathit{c}\in \mathit{C}\mathrm{,}\neg \mathit{x}\in \mathit{c}\}\\ \hfill & \phantom{\mathit{R}=}\cup \{\mathrm{(}\mathit{c}\mathrm{,}{\mathit{c}}^{\prime }\mid \mathit{c}\in \mathit{C}\}\end{array}$$ Note that each argument has at most three parents: arguments x, $\bar{\mathit{x}}$ , and ${\mathit{c}}^{\prime }$ have exactly one parent, and since each clause $\mathit{c}={\mathit{l}}_1\vee {\mathit{l}}_2\vee {\mathit{l}}_3$ has at most three literals per assumption, also each c has at most three parents.

We claim that $\mathit{E}=\{{\mathit{c}}^{\prime }\mid \mathit{c}\in \mathit{C}\}$ is part of an admissible set of F iff φ is satisfiable. It holds that $$\begin{array}{ll}\hfill & \mathit{\phi }\text{ is satisfiable}\\ \hfill & \text{iff }\exists \mathit{I}\mathrm{,}\mathit{I}\vDash \mathit{\phi }\\ \hfill & \text{iff }\exists \mathit{I}\mathrm{,}\mathit{I}\vDash \mathit{c}\forall \mathit{c}\in \mathit{C}\\ \hfill & \text{iff }\exists \mathit{I}\text{ and there is an }\mathit{l}\in \mathit{c}\text{ s.t. }\mathit{I}\mathrm{(}\mathit{l}\mathrm{)}=\mathbf{t}\forall \mathit{c}\in \mathit{C}\\ \hfill & \text{iff }\exists \mathit{S}\subseteq \mathit{X}\cup \{\bar{\mathit{x}}\mid \mathit{x}\in \mathit{X}\}\text{ s.t. }\nexists \mathrm{(}\mathit{y}\mathrm{,}{\mathit{y}}^{\prime }\mathrm{)}\in \mathit{R}\text{ for each }\{\mathit{y}\mathrm{,}{\mathit{y}}^{\prime }\}\subseteq \mathit{S}\text{ and }\exists \mathit{z}\in \mathit{S}\\ \hfill & \text{with }\mathrm{(}\mathit{z}\mathrm{,}\mathit{c}\mathrm{)}\in \mathit{R}\forall \mathit{c}\in \mathit{C}\\ \hfill & \text{iff }\exists {\mathit{E}}^{\prime }\in \mathit{\text{adm}}\mathrm{(}\mathit{F}\mathrm{)}\text{ s.t. }\mathit{E}\subseteq {\mathit{E}}^{\prime }.\end{array}$$ We complete the hardness proof by φ is satisfiable iff one can enforce, for the support enforcement operator, E with 0 changes and arguments to expand $\{\mathit{d}\}$ (a dummy argument). □

We note that any constraint defined in Section 4, except for optimization statements, can be added to the support enforcement operator, with the mentioned restrictions, without increased complexity. On the other hand, our proofs for these results exhibit exponentiality in running times w.r.t. the number of parents and expanded arguments. The same observation holds for our implementation presented in Section 8.1. Coping with large values for these parameters requires further work.

7.3. Complexity of structured enforcement under admissible semantics

Before looking at the complexity of the structured enforcement operator, we first consider the sizes of the knowledge base B, the “full” AF $\mathit{F}=\mathrm{(}\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}$ , and the number of constraints K described in Section 6.

Regarding the AF, we remark that many current approaches to AF instantiation in structured argumentation may produce large AFs, i.e., AFs whose number of arguments is not polynomially bounded by the size of the knowledge base. Studying approaches to more efficient AF generation is a current topic of research [76,103]. In this paper we make no concrete assumption on the size, but we do assume that both the knowledge base B and the full AF $\mathit{F}=\mathrm{(}\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}$ are given, and, further, based on these two given structures that one can in polynomial time check whether an argument (attack) is part of the function $\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}$ or $\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}$ , and similarly for $\mathit{kb}$ . We note that, if the knowledge base and the full instantiated AF are given, then poly-time decidable functions $\mathit{args}$ , $\mathit{att}$ , and $\mathit{kb}$ are plausible: this can amount to checking already instantiated arguments and attacks. Nevertheless, a concrete algorithm’s performance for structured enforcement hinges on the size metrics of the partial AF given as the current state and the full AF, since, in the worst case, all arguments and attacks have to be added to achieve an enforcement goal.

The structural constraints we utilized to define the structured enforcement operator are in number polynomial to the size of the AF F, except for (3). However, these constraints can be represented differently. Let ${\mathit{F}}^{\ast }=\mathrm{(}{\mathit{A}}^{\ast }\mathrm{,}{\mathit{R}}^{\ast }\mathrm{)}$ be a candidate AF to be checked. Define the following constraint: $$\begin{array}{c}\mathit{a}\in \mathit{args}\mathrm{\left(}\mathit{kb}\mathrm{\right(}{\mathit{A}}^{\ast }\mathrm{\left)}\mathrm{\right)}\to \mathit{a}\in {\mathit{A}}^{\ast }\text{for each }\mathit{a}\in \mathit{args}\mathrm{(}\mathit{B}\mathrm{)}.\end{array}$$ This constraint does not fall into the constraints we have defined in Section 4, since $\mathit{a}\in \mathit{args}\mathrm{(}\mathit{kb}\mathrm{(}{\mathit{A}}^{\ast }\mathrm{)}\mathrm{)}$ does not refer directly to components of an AF/ADF, however representing the set of constraints of (3) in this way saves space. Concretely, there are at most $|\mathit{A}|$ many such constraints. Similarly as before, these constraints can be checked solely based on the given input: the base B and a candidate AF ${\mathit{F}}^{\ast }$ .

We now investigate the complexity of the structured enforcement operator that is given as input a knowledge base B, represented as a set, an initial AF ${\mathit{F}}_0=\mathrm{(}\mathit{args}\mathrm{(}{\mathit{B}}_0\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}{\mathit{B}}_0\mathrm{)}\mathrm{)}$ , corresponding to some ${\mathit{B}}_0\subseteq \mathit{B}$ , the full AF $\mathit{F}=\mathrm{(}\mathit{args}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{,}\mathit{att}\mathrm{(}\mathit{B}\mathrm{)}\mathrm{)}$ , and a set of arguments $\mathit{S}\subseteq \mathit{args}\mathrm{(}{\mathit{B}}_0\mathrm{)}$ . For the semantics, we again consider the admissible semantics. We again consider the optimization variant and its decision problem, i.e., we ask whether enforcement is possible with at most k changes to the attacks.

Proposition 10.

The structured enforcement operator under admissible semantics is $\mathit{NP}$ -complete, if functions $\mathit{args}$ , $\mathit{att}$ , and $\mathit{kb}$ can be computed in polynomial time.

Proof.

For membership, consider a non-deterministic guess of an expanded AF. Checking each constraint can be done, under the stated assumptions, in polynomial time. Hardness, as before for support enforcement, follows from checking whether an AF without any changes has an admissible set containing a particular argument (this problem is $\mathit{NP}$ -complete). For a given arbitrary AF, construct a knowledge base B such that its instantiated AF is exactly the given AF. □

8. Empirical evaluation of an answer set programming approach to support enforcement

In this section we give details to an answer set programming implementation of support enforcement (see Section 5), and an experimental evaluation of the resulting prototype.

8.1. Implementing support enforcement in ASP for admissible semantics

We have implemented support enforcement in answer set programming (ASP), based on goDiamond [62,63,98] v0.6.6, a solver for ADF reasoning tasks via ASP. In light of Proposition 3, we fixed, in our implementation, the set of expanded arguments to be a singleton set (since an enforcement using several expanded arguments can be straightforwardly transformed to using only one). We have applied all constraints we have defined Section 5, i.e., we have implemented the operation we call support enforcement.

High-level description. We begin with a high-level view on the operation we implemented, and a high-level view on how we implemented this operation. We have implemented support enforcement, as defined in Section 5, including all constraints defined for that operation, yet allowing only for one expanded argument. That is, our implementation takes as input an ADF and a three-valued interpretation (with the format specified below). The output is a modified ADF, including an expanded argument e, such that there is an admissible interpretation that is more informative than the given one (thereby enforcing the given interpretation). Further, only the following modifications are permitted: new links only from the expanded argument onto original arguments, all new links supporting, for each original argument a with original acceptance condition ${\mathit{\phi }}_{\mathit{a}}$ it holds that the modified acceptance condition satisfies ${\mathit{\phi }}_{\mathit{a}}^{\prime }[{\mathit{I}}_{\mathbf{u}}{|}_{\mathbf{f}}^{\mathit{e}}]\equiv {\mathit{\phi }}_{\mathit{a}}$ (when the expanded argument is false the modified acceptance condition is equivalent to the original one). Finally, ${\mathit{\phi }}_{\mathit{e}}\equiv \top$ .

Our implementation approach, from a high-level viewpoint, works as follows. Let the input be the given ADF D, a three-valued interpretation I, and expanded argument e. Assume that the existing arguments are $\mathit{A}=\{{\mathit{a}}_1\mathrm{,}\dots \mathrm{,}{\mathit{a}}_{\mathit{n}}\}$ . We non-deterministically guess whether a new link is to be added or not, i.e., for each ${\mathit{a}}_{\mathit{i}}$ whether to add $\mathrm{(}\mathit{e}\mathrm{,}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ or not (other links are not allowed in strong expansions). In case no link was added onto ${\mathit{a}}_{\mathit{i}}$ , that argument’s acceptance condition ${\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}$ remains unmodified. Otherwise, in case $\mathrm{(}\mathit{e}\mathrm{,}{\mathit{a}}_{\mathit{i}}\mathrm{)}$ was added, condition ${\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}$ is modified. Due to the constraints, we can infer that the new condition can be represented by $\mathrm{(}{\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}\wedge \neg \mathit{e}\mathrm{)}\vee \mathrm{(}{\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}^{\prime }\wedge \mathit{e}\mathrm{)}$ , i.e., whenever e is assigned false no modification must have been taken place, otherwise the condition can be modified ( ${\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}^{\prime }$ may not be logically equivalent to ${\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}$ ). In order to find ${\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}^{\prime }$ , we expand the formula to a full truth table. Say the parents of ${\mathit{a}}_{\mathit{i}}$ are ${\mathit{par}}_{\mathit{D}}\mathrm{(}{\mathit{a}}_{\mathit{i}}\mathrm{)}=\{{\mathit{p}}_1\mathrm{,}\dots \mathrm{,}{\mathit{p}}_{\mathit{l}}\}$ . An illustration of the truth table is shown in Fig. 9. For each truth value combination of the parents we have an entry for a resulting truth value. For instance, under the interpretation assigning all arguments to false, ${\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}$ evaluates to ${\mathit{v}}_1\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}$ . We construct a modified truth table (corresponding to ${\mathit{\phi }}_{{\mathit{a}}_{\mathit{i}}}^{\prime }$ ) by adding a new parent e, copying values ${\mathit{v}}_1$ to ${\mathit{v}}_{\mathit{m}}$ from the original truth table to the cases where e is false, and assigning guessed entries ${\mathit{g}}_1\mathrm{,}\dots \mathrm{,}{\mathit{g}}_{\mathit{m}}$ to the remaining rows. Since the new link must be supporting, we ensure that, for all i with $1⩽\mathit{i}⩽\mathit{m}$ , we have ${\mathit{v}}_{\mathit{i}}=\mathbf{t}$ implies ${\mathit{g}}_{\mathit{i}}=\mathbf{t}$ (otherwise the link would not be supporting). Finally, under the modified acceptance condition, we non-deterministically construct a three-valued interpretation and verify that there is an admissible interpretation J such that $\mathit{I}{⩽}_{\mathit{i}}\mathit{J}$ (i.e., the enforcement is successful).

Fig. 9.

Constructing a truth table with guessed entries.

ASP background. We recall briefly ASP background [29,71,88]. We fix a countable set U of constants. An atom is an expression $\mathit{p}\mathrm{(}{\mathit{t}}_1\mathrm{,}\dots \mathrm{,}{\mathit{t}}_{\mathit{n}}\mathrm{)}$ , where p is a predicate of arity $\mathit{n}⩾0$ and each term ${\mathit{t}}_{\mathit{i}}$ is either a variable or an element from U. An atom is ground if it is free of variables. $\mathit{B}\mathit{U}$ denotes the set of all ground atoms over U. A rule r is of the form $$\begin{array}{c}\mathit{a}\leftarrow {\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{k}}\mathrm{,}\mathit{not}{\mathit{b}}_{\mathit{k}+1}\mathrm{,}\dots \mathrm{,}\mathit{not}{\mathit{b}}_{\mathit{m}}\end{array}$$ with $\mathit{m}⩾\mathit{k}⩾0$ , where $\mathit{a}\mathrm{,}{\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{m}}$ are atoms, and “ $\mathit{not}$ ” stands for default negation. The head of r is the set $\mathit{head}\mathrm{(}\mathit{r}\mathrm{)}=\{\mathit{a}\}$ and the body of r is $\mathit{body}\mathrm{(}\mathit{r}\mathrm{)}=\{{\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{k}}\mathrm{,}\mathit{not}{\mathit{b}}_{\mathit{k}+1}\mathrm{,}\dots \mathrm{,}\mathit{not}{\mathit{b}}_{\mathit{m}}\}$ . Furthermore, ${\mathit{body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}=\{{\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{k}}\}$ and ${\mathit{body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}=\{{\mathit{b}}_{\mathit{k}+1}\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{m}}\}$ . A rule r is ground if r does not contain variables. A program is a finite set of rules. If each rule in a program is ground, we call the program ground.

For any program π, let $\mathit{UP}$ be the set of all constants appearing in π. Define $\mathit{GP}$ as the set of rules $\mathit{r}\mathit{\sigma }$ obtained by applying, to each rule $\mathit{r}\in \mathit{\pi }$ , all possible substitutions σ from the variables in r to elements of $\mathit{UP}$ . An interpretation $\mathit{I}\subseteq \mathit{B}\mathit{U}$ satisfies a ground rule r iff $\mathit{head}\mathrm{(}\mathit{r}\mathrm{)}\cap \mathit{I}\ne \varnothing$ whenever ${\mathit{body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}\subseteq \mathit{I}$ and ${\mathit{body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}\cap \mathit{I}=\varnothing$ . I satisfies a ground program π, if each $\mathit{r}\in \mathit{\pi }$ is satisfied by I. A non-ground rule r (resp., a program π) is satisfied by an interpretation I iff I satisfies all groundings of r (resp., $\mathit{GP}$ ). An interpretation $\mathit{I}\subseteq \mathit{B}\mathit{U}$ is an answer set of π if it is a subset-minimal set satisfying the Gelfond–Lifschitz reduct ${\mathit{\pi }}^{\mathit{I}}=\{\mathit{head}\mathrm{(}\mathit{r}\mathrm{)}\leftarrow {\mathit{body}}^{+}\mathrm{(}\mathit{r}\mathrm{)}\mid \mathit{I}\cap {\mathit{body}}^{-}\mathrm{(}\mathit{r}\mathrm{)}=\varnothing \mathrm{,}\mathit{r}\in \mathit{GP}\}$ .

In this work we also consider optimization programs (following definitions from [33]), in particular programs with weak constraints of the form $$\begin{array}{c}⇝{\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}.[\mathit{w}\mathrm{,}{\mathit{t}}_1\mathrm{,}\dots \mathrm{,}{\mathit{t}}_{\mathit{m}}]\mathrm{,}\end{array}$$ with each ${\mathit{b}}_{\mathit{i}}$ an atom, each ${\mathit{t}}_{\mathit{j}}$ a term, and w an integer. Towards optimal answer sets we define $\mathit{weak}\mathrm{(}\mathit{\pi }\mathrm{,}\mathit{I}\mathrm{)}=\{\mathrm{(}\mathit{w}\mathrm{,}{\mathit{t}}_1\mathrm{,}\dots \mathrm{,}{\mathit{t}}_{\mathit{m}}\mathrm{)}\mid ⇝{\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}.[\mathit{w}\mathrm{,}{\mathit{t}}_1\mathrm{,}\dots \mathrm{,}{\mathit{t}}_{\mathit{m}}]\in \mathit{GP}\text{ and }\{{\mathit{b}}_1\mathrm{,}\dots \mathrm{,}{\mathit{b}}_{\mathit{n}}\}\subseteq \mathit{I}\}$ , for an answer set I. In words, in $\mathit{weak}\mathrm{(}\mathit{\pi }\mathrm{,}\mathit{I}\mathrm{)}$ we collect all weak constraints satisfied by I (terms ${\mathit{t}}_{\mathit{i}}$ can be used to distinguish different sources with the same weight in the set $\mathit{weak}\mathrm{(}\mathit{\pi }\mathrm{,}\mathit{I}\mathrm{)}$ ). The cost of I is then ${\sum }_{\mathrm{(}\mathit{w}\mathrm{,}{\mathit{t}}_1\mathrm{,}\dots \mathrm{,}{\mathit{t}}_{\mathit{m}}\mathrm{)}\in \mathit{weak}\mathrm{(}\mathit{\pi }\mathrm{,}\mathit{I}\mathrm{)}}\mathit{w}$ , i.e., the sum of weights of each satisfied weak constraint. An answer set I is optimal if there is no answer set J that has strictly lower cost than I.

Notation 1.

By convention, constants in ASP are written with a beginning lower case letter and variables are written with a beginning upper case letter. That is, “a” is a constant and “A” is a variable. In the subsequent encoding, we denote by A variables intended for arguments, by V we denote variables intended for valuations (interpretations in the terminology of the ASP modules we make use of), and F for variables that refer to identifiers for (Boolean) formulas.

Implementing support enforcement in diamond. In (go)Diamond, an ADF is represented via ASP facts, as follows. Let $\mathit{D}=\mathrm{(}\mathit{A}\mathrm{,}\mathit{L}\mathrm{,}\mathit{C}\mathrm{)}$ be an ADF, its representation as ASP facts is defined as $$\begin{array}{ll}\hfill {\mathit{\pi }}_{\mathit{ADF}}\mathrm{(}\mathit{D}\mathrm{)}=& \{\mathbf{s}\mathrm{(}\mathit{a}\mathrm{)}.\mid \mathit{a}\in \mathit{A}\}\\ \hfill & \cup \left\{\mathbf{ac}\mathrm{\right(}\mathit{a}\mathrm{,}\mathit{t}\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\mathrm{)}\mathrm{)}.\mid {\mathit{\phi }}_{\mathit{a}}\in \mathit{C}\}\}\mathrm{,}\end{array}$$ with $\mathit{t}\mathrm{(}\mathit{\phi }\mathrm{)}$ a straightforward prefix notation of φ. For instance, $\mathit{\phi }=\mathit{a}\wedge \mathrm{(}\mathit{b}\vee \neg \mathit{c}\mathrm{)}$ is translated to $\mathit{t}\mathrm{(}\mathit{\phi }\mathrm{)}=\mathit{and}\mathrm{(}\mathit{a}\mathrm{,}\mathit{or}\mathrm{(}\mathit{b}\mathrm{,}\mathit{neg}\mathrm{(}\mathit{c}\mathrm{)}\mathrm{)}\mathrm{)}$ . A three-valued interpretation I (on A) to be enforced is represented by $$\begin{array}{ll}\hfill {\mathit{\pi }}_{\mathit{enf}}\mathrm{(}\mathit{I}\mathrm{)}=& \{\mathbf{enf}\mathrm{(}\mathit{a}\mathrm{,}\mathit{v}\mathrm{)}.\mid \mathit{I}\mathrm{(}\mathit{a}\mathrm{)}=\mathit{v}\in \{\mathbf{t}\mathrm{,}\mathbf{f}\}\}.\end{array}$$ That is, we represent all arguments enforced to be true or false as ASP facts (arguments assigned undecided are not constrained in an enforcement).

In (go)Diamond, several derived predicates are then provided, in particular for several ADF semantics. We utilize the encodings for admissible semantics. We only recall predicates relevant for our approach, for details we refer to the original references and the code. In (go)Diamond, for each argument a, the acceptance condition ${\mathit{\phi }}_{\mathit{a}}$ is expanded to a truth table. Each entry in the truth table is assigned a number, represented by $\mathbf{n}\text{\_}\mathbf{v}\mathrm{(}\mathit{A}\mathrm{,}\mathit{V}\mathrm{)}$ , which indicates that, for argument A, the two-valued interpretation (truth table entry) with number V. For instance, if ${\mathit{\phi }}_{\mathit{a}}$ has 3 variables, there are $2^3=8$ such entries. With the auxiliary predicate $\mathbf{true}\mathrm{(}\mathit{A}\mathrm{,}\mathit{V}\mathrm{,}\mathit{F}\mathrm{)}$ it is derived whether entry V evaluates (sub)formula F to be true, or not, for argument A (i.e., F is a subformula of ${\mathit{\phi }}_{\mathit{a}}$ ). Building upon $\mathbf{true}$ , the two predicates $\mathbf{model}\mathrm{(}\mathit{A}\mathrm{,}\mathit{V}\mathrm{)}$ and $\mathbf{nomodel}\mathrm{(}\mathit{A}\mathrm{,}\mathit{V}\mathrm{)}$ state that V is a model or not a model of ${\mathit{\phi }}_{\mathit{a}}$ . Finally, regarding predicates of importance for us, there are $\mathbf{t}\mathrm{(}\mathit{A}\mathrm{)}$ , $\mathbf{f}\mathrm{(}\mathit{A}\mathrm{)}$ , and $\mathbf{u}\mathrm{(}\mathit{A}\mathrm{)}$ , stating that an argument A is assigned t, f, or u, respectively.

Listing 1.

Partial ASP encoding for support enforcement

We adapted goDiamond’s encoding, as follows, see also Listing 1. The first two lines represent a (standard) guess in ASP whether a link is to be added onto argument A (note that the origin is clear: the link comes from a distinguished expanded argument). Next, as illustrated in Fig. 9, we construct an expanded truth table. Since we are “copying” the entries when the expanded argument is false, and also can assume (see Proposition 3) that the new argument is assigned true, we only need to represent the guessed values $\mathrm{(}{\mathit{g}}_1\mathrm{,}\dots \mathrm{,}{\mathit{g}}_{\mathit{m}}\mathrm{)}$ for a number of interpretations equal to the number of the original truth table. In the ASP encoding, we represent this via guessing either $\mathbf{model}\mathrm{(}\mathit{A}\mathrm{,}\mathit{V}\mathrm{)}$ or $\mathbf{nomodel}\mathrm{(}\mathit{A}\mathrm{,}\mathit{V}\mathrm{)}$ for each $\mathbf{n}\text{\_}\mathbf{v}\mathrm{(}\mathit{A}\mathrm{,}\mathit{V}\mathrm{)}$ , whenever a link was actually added onto A. Since the new link has to be supporting, we apply the next constraint that ensures that when originally we evaluated to true ( $\mathbf{true}$ holds) we are not allowed to guess $\mathbf{nomodel}$ . The next four constraints specify that the enforcement goals are to be met: e.g., if A is an argument, it was assigned true ( $\mathbf{t}\mathrm{(}\mathit{A}\mathrm{)}$ ), then the enforcement goal cannot be false ( $\mathbf{enf}\mathrm{(}\mathit{A}\mathrm{,}\mathbf{f}\mathrm{)}$ ). The weak constraint specifies unit weight (cost) to each added link. Finally, in order to be able to compute the modified acceptance condition, we derive each change of entries in a truth table. That is, $\mathbf{changedmodel}\mathrm{(}\mathit{a}\mathrm{,}\mathit{i}\mathrm{)}$ indicates that ${\mathit{v}}_{\mathit{i}}\ne {\mathit{g}}_{\mathit{i}}$ . In this way, the full truth table can be inferred for the modified ${\mathit{\phi }}_{\mathit{a}}^{\ast }=\mathrm{(}{\mathit{\phi }}_{\mathit{a}}\wedge \neg \mathit{e}\mathrm{)}\vee \mathrm{(}{\mathit{\phi }}_{\mathit{a}}^{\prime }\wedge \mathit{e}\mathrm{)}$ , i.e., ${\mathit{\phi }}_{\mathit{a}}^{\prime }$ is fully specified in this way.

The full ASP encodings are available at https://www.dbai.tuwien.ac.at/research/project/embarg/supp-enf/

which, derived from (go)Diamond, are distributed under the GPL license.

Example 21.

We show an example of support enforcement, which is taken from a part, and simplified form, of an instance ADF that has 216 arguments that was used in the experiments shown in the next section. For our illustration, nine arguments are relevant, which have the following unmodified acceptance conditions: $$\begin{array}{ll}\hfill & {\mathit{\phi }}_{{\mathit{a}}_1}=\neg {\mathit{a}}_2\vee {\mathit{a}}_3\\ \hfill & {\mathit{\phi }}_{{\mathit{a}}_2}=\neg {\mathit{a}}_1\\ \hfill & {\mathit{\phi }}_{{\mathit{a}}_3}=\neg {\mathit{a}}_4\wedge \neg {\mathit{a}}_1\\ \hfill & {\mathit{\phi }}_{{\mathit{a}}_4}={\mathit{a}}_5\vee {\mathit{a}}_3\\ \hfill & {\mathit{\phi }}_{{\mathit{a}}_5}=\neg {\mathit{a}}_6\\ \hfill & {\mathit{\phi }}_{{\mathit{a}}_6}=\mathit{\psi }\\ \hfill & {\mathit{\phi }}_{{\mathit{a}}_7}=\mathrm{(}{\mathit{a}}_8\leftrightarrow {\mathit{a}}_2\mathrm{)}\\ \hfill & {\mathit{\phi }}_{{\mathit{a}}_8}=\top \end{array}$$ with ψ a formula with at least one variable (for our example the exact form of this condition is not relevant). Say we want to enforce ${\mathit{a}}_7$ to be true (other arguments are not constrained). When using the ASP encoding above (together with the Diamond encodings), we extracted a solution as follows. Consider the three-valued interpretation $\mathit{I}=\{{\mathit{a}}_1\mapsto \mathbf{f}\mathrm{,}{\mathit{a}}_2\mapsto \mathbf{t}\mathrm{,}{\mathit{a}}_3\mapsto \mathbf{f}\mathrm{,}{\mathit{a}}_4\mapsto \mathbf{t}\mathrm{,}{\mathit{a}}_5\mapsto \mathbf{t}\mathrm{,}{\mathit{a}}_6\mapsto \mathbf{u}\mathrm{,}{\mathit{a}}_7\mapsto \mathbf{t}\mathrm{,}{\mathit{a}}_8\mapsto \mathbf{t}\}$ . The interpretation I is not admissible in the unmodified ADF: ${\mathit{\phi }}_{{\mathit{a}}_5}[\mathit{I}]={\mathit{\phi }}_{{\mathit{a}}_5}=\neg {\mathit{a}}_6$ , but $\mathit{I}\mathrm{(}{\mathit{a}}_5\mathrm{)}=\mathbf{t}$ . We now expand the ADF with argument e and add link $\mathrm{(}\mathit{e}\mathrm{,}{\mathit{a}}_5\mathrm{)}$ and adapt the acceptance condition to ${\mathit{\phi }}_{{\mathit{a}}_5}^{\ast }=\mathrm{(}\neg {\mathit{a}}_6\wedge \neg \mathit{e}\mathrm{)}\vee \mathrm{(}\top \wedge \mathit{e}\mathrm{)}$ . This corresponds to having $\mathbf{changedmodel}\mathrm{(}{\mathit{a}}_5\mathrm{,}1\mathrm{)}$ in an answer set: there are two entries in the truth table of ${\mathit{\phi }}_{{\mathit{a}}_5}$ , with the one identified with 0 being the one where ${\mathit{a}}_6$ is assigned false and the one with ID 1 the one where ${\mathit{a}}_6$ is true. Then, $\mathbf{changedmodel}\mathrm{(}{\mathit{a}}_5\mathrm{,}1\mathrm{)}$ indicates that the new acceptance condition, with e true, has still a model where ${\mathit{a}}_6$ is false, but the previous non-model where ${\mathit{a}}_6$ is true shall become a model. Then, under ${\mathit{\phi }}_{{\mathit{a}}_5}^{\ast }$ , it holds that I is admissible, when expanded with $\mathit{e}\mapsto \mathbf{t}$ , and ${\mathit{a}}_7$ is true in I, thus, ${\mathit{a}}_7$ is enforced to be true in the expansion. In other words, support enforcement identified that a link from e to ${\mathit{a}}_5$ that states that acceptance of e is sufficient to accept ${\mathit{a}}_5$ leads to acceptance of ${\mathit{a}}_7$ , since this leads to a chain of changes of acceptance: due to acceptance of ${\mathit{a}}_5$ , we can accept ${\mathit{a}}_4$ , which, in turn, leads to rejection of ${\mathit{a}}_3$ if ${\mathit{a}}_1$ is likewise rejected. The argument ${\mathit{a}}_1$ can be rejected if ${\mathit{a}}_2$ is accepted and ${\mathit{a}}_3$ is rejected. By accepting ${\mathit{a}}_2$ we arrive at the situation that both ${\mathit{a}}_2$ and ${\mathit{a}}_8$ are accepted, implying that ${\mathit{a}}_8\leftrightarrow {\mathit{a}}_2$ evaluates to true, and ${\mathit{a}}_7$ can be accepted.

8.2. Experiments

We report on an experimental evaluation of the support enforcement operator implemented in ASP.

Instances and experimental setup. We performed experiments using instances from www.dbai.tuwien.ac.at/proj/adf/yadf/, which are ADFs that were generated from the AFs of domains ABA2AF, Planning2AF, and Traffic from ICCMA 2017 [66,67]. The generation procedure is described in [49, Section 5]. Briefly put, the generator transforms an undirected graph (from the AF competition) into cyclic or acyclic ADFs, by inheriting the graph structure (for acyclic ADFs, by a topological ordering, inducing an acyclic directed graph). Acceptance conditions are constructed by considering the parents (as given by the graph generation), and grouping parents into five classes: attack, group-attack, support, group-support, or XOR, which represent different types of generated Boolean subformulas, which are then connected via logical conjunction and disjunction.

We analyzed characteristics of the ADF instances. We list statistics of each domain in Table 3. Overall, the benchmark set contains 600 ADFs, which vary in several statistics. For instance, the maximum number of parents of arguments (i.e., the maximum in-degree of the graph) varies from at most 2 to at most 131. For the calculation of (number of) parents we excluded self-loops. We computed polarity of each ADF, and found that, from the whole set, 48 are bipolar, 547 are not bipolar, and 5 instances could not be checked (note that it is coNP-complete to check whether a link is supporting or attacking [61]). All bipolar ADFs have at most 12 parents for each argument.

Table 3

Statistics of ADFs used in the experimentation. For each group of instances we list the total number of ADFs, the average number of arguments in the ADFs, the interval of maximum number of parents in the ADFs (excluding self-loops), the number of cyclic ADFs, and the number of bipolar ADFs

Planning	Number of ADFs	200
	Average number of arguments	202.64
	Interval of maximum number of parents	6–19
	Number of ADFs with cyclic dependency graph	100
	Number of bipolar ADFs	0
Traffic	Number of ADFs	200
	Average number of arguments	111.81
	Interval of maximum number of parents	2–19
	Number of ADFs with cyclic dependency graph	100
	Number of bipolar ADFs	35
ABA2AF	Number of ADFs	200
	Average number of arguments	43.83
	Interval of maximum number of parents	3–131
	Number of ADFs with cyclic dependency graph	100
	Number of bipolar ADFs	13
Overall	Number of ADFs	600
	Average number of arguments	119.427
	Interval of maximum number of parents	2–131
	Number of ADFs with cyclic dependency graph	300
	Number of bipolar ADFs	48

For each ADF we created three enforcement requests, i.e., interpretations to enforce, as follows. We selected, at random, a subset of the arguments in the ADF with probability $\mathit{p}\in \{\frac{1}{5}\mathrm{,}\frac{1}{10}\mathrm{,}\frac{1}{20}\}$ to include an argument. For each such subset, we selected, again randomly, which argument shall be enforced to be true and which to be false, with a probability of $\frac{1}{5}$ that an argument is false. Thus having more arguments to be enforced to be true, since arguments enforced to be false can lead to a no solution instance in contrast to arguments enforced to be true, which motivates this choice. This was also observed empirically, see below. This resulted in 600 enforcements per domain, and 1800 enforcements overall.

All experiments were run on a machine with two AMD Opteron Processors 6308, 12 × 16 GB RAM, and Debian 8. We used a timeout of 900 seconds on each individual instance (query), i.e., for each pair of ADF and enforcement. Furthermore, we restricted memory consumption (virtual memory) to at most 8 GB. In order to enforce these limits, and to have more logging information, we utilized the runsolver v3.4.0 tool3

³

http://www.cril.univ-artois.fr/~roussel/

by Olivier Roussel, which was also used in several competitions. For the ASP solver, we used clingo v5.3.0 [70].

Results and interpretations. The results are summarized in Table 4. The rows show the instances grouped by domain, number of queries, number of successful computations (i.e., where clingo terminated with the result within the limits), number of instances where an optima was found, number of instances with optimum cost 0, number of instances where clingo reported unsatisfiability, number of timeouts, and the median runtimes in seconds. In the following, we interpret the results in more detail.

Table 4

Summary of experimental results

Domain	#	#successful	Opt. found	0-cost	Unsat.	Timeout	Median time (sec) of succ. runs
Planning	600	586	211	4	375	8	2.442
Traffic	600	591	341	49	250	0	0.188
ABA2AF	600	267	220	57	47	0	0.612
All	1800	1444	772	110	672	8	0.862

We first discuss successful and not successful runs. A run is deemed successful when clingo returned either with an optimal solution or reported unsatisfiability. In our experiments, we encountered four reasons for clingo not reporting successfully. The first is that the time limit was reached, which occurred rarely: only 8 runs timed out. In its current version, clingo does not support very high integers. Since in the ASP encoding used by us (and by Diamond), a truth table is constructed, and each entry is assigned an integer (an ID), we naturally have to deal with large integers. For instance, if the maximum number of parents is n, then an integer $2^{\mathit{n}}$ is required by the ASP encoding. We noted that 6 runs failed due to such high integers. The third reason is that the memory limit of 8 GB was reached, which happened for 63 runs. Finally, we encountered 279 runs where clingo could not solve the instance, but stayed with the limits and did not report an issue with large integers. We inspected these runs, and found that in all cases a large portion of memory was used: at least 6 GB, but in most cases almost 8 GB. While, strictly speaking, the memory limit was not reached, we interpret all these instances as failing due to the high memory consumption. Overall, out of 1800 runs, 1444 were successful and 356 were not. We looked at the maximum number of parents of the failed runs, and, except for the timed out runs, all failed runs had to cope with ADFs with a maximum number of parents of at least 15 and up to 131. In contrast, the successful runs had maximum number of parents between 2 and 16. We hypothesize that this is inherent to our method of transforming Boolean formulas by truth table expansion: the method was able to cope with instances up to 16 parents, but not more. Nevertheless, all instances with at most 14 parents (except for the 8 time outs) were solved successfully by clingo.

We move on to running time behavior of the successful runs. Table 4 summarizes that the median of these runs was (quite) low. Since, as observed above, the maximum number of parents seems to be a crucial parameter for difficulty, we detail running times for this parameter in Fig. 10. In the figure, the successfully solved instances are grouped by maximum number of parents (with the sample size in brackets) shown along the horizontal axis. As can be seen, there is a clear increase in running times when increasing the maximum number of parents, as expected. Nevertheless, even for a maximum number of parents of 16, running times were reasonable, e.g., below 200 seconds for most runs. We also looked at running time differences when considering cyclicity. As observed theoretically [77], acyclic ADFs have milder complexity. Within the successful runs, 726 were on acyclic ADFs and 718 were on cyclic ADFs. The cumulative running time (i.e., summing up all running times) were 5391.5 and 18112.7, respectively. While ADFs and enforcement requests are different for acyclic and cyclic instances, this result suggests that the difference in complexity was also observed empirically, in our experiments. Regarding bipolarity, the picture is not clear, since (recall description above) all bipolar ADFs have a low number of maximum number of parents (up to 12). Looking at the corresponding running times in Fig. 10 reveals that those runs were all solved quickly, independent of polarity. Such low running times do not give clear results of divergence of running times on bipolar or non-bipolar ADFs.

Fig. 10.

Whisker plot for all successful runs of support enforcement. In the vertical axis running times (sec) are shown, and in the horizontal axis instances are grouped by maximum number of parents (with size of the group in parentheses). The box shows the lower quartile and upper quartile (the 25th and 75th percentiles), the median in bold, and the lines denote the “whiskers“, i.e., these extend from the quartiles to the farthest points up to 1.5 times the interquartile range (range from lower and upper quartile) from upper/lower quartiles. Outliers are denoted as circles. Instances with a maximum number of parents less than seven are omitted (both their minimum and maximum running times are close to zero).

We now consider the three parameters for enforcement generation. When looking at those runs with the lowest number of arguments to be enforced to false ( $\mathit{p}=\frac{1}{20}$ ), we have 335 runs where clingo reported an optimal solution and 145 runs which were deemed unsatisfiable. For $\mathit{p}=\frac{1}{10}$ , we have 261 optimal solutions and 219 unsatisfiable queries. For $\mathit{p}=\frac{1}{5}$ , we encountered 176 optimal solutions and 308 unsatisfiable queries. This is in line with Proposition 2, i.e., that arguments enforced to be true always have a solution, while arguments enforced to be false may not have a solution. Further, we noticed an increase of costs for the three groups: the average costs were 2.8, 4.1, and 5.1, respectively, which reflects the increasing number of arguments enforced. Regarding costs, in, overall, 110 runs an optimal solution had 0 costs. This indicates that the enforcement request was already met without any change (i.e., when enforcing I to be admissible, there already is an admissible J with $\mathit{I}{⩽}_{\mathit{i}}\mathit{J}$ ). Compared to 1444 successful runs, the number of trivial instances (w.r.t. costs) is low.

Summarizing our results, with the ASP approach, we could solve 1444 out of 1800 instances, most of these within (rather) low running times. Non-solvability was mostly due to high memory consumption, which is to be expected as a natural barrier for our approach. Nevertheless, ADFs with at most 16 maximum number of parents were solved regularly.

9. Constraints for further operations

In this section we give a brief overview on further operators that fit into our three-layered approach, and for which structural constraints can be applied. Concretely, we look at revision of AFs, merging (aggregation) of AFs, and synthesis (learning) of AFs. Each of these operations result in a (modified) AF that has to satisfy certain semantical constraints. In addition some of these operators allow for structural constraints. These operators can be augmented with structural constraints we looked at in Section 4. For instance, in any of these operations one can fix certain parts of the AF, or impose implications (e.g. presence of one attack implies further attacks), or add further optimizations.

Revision of argumentation frameworks. Revision of knowledge has a long tradition in AI [1,69,74], and revision of semantics of AFs [42,43,48] and ADFs [79] has been studied recently. From a high-level perspective, these operators revise a given framework and return a modified framework. Many of these revision operators specify the semantics of the modified framework, and some, but not all, give constraints on the structure. In this regard, in our three-layered point of view, these operators specify semantical constraints, in the form of exact semantics a modified AF shall have, and sometimes further constraints such as optimizations. Our structural constraints can support further development of such revision operators by stating how an AF may evolve structurally, in addition to the semantics or existing structural constraints.

Merging of argumentation frameworks. Similar to revision, merging or aggregation of (logical) structures has received interest in the AI community [75]. Aggregation, or merging, of AFs has recently found attention in the argumentation community [26,41]. As an example for a semantical merging operator, consider an operator studied in [47], which, given a tuple of AFs, merges the tuple into an AF, or a set of AFs. For simplicity we look at those operators returning a single AF.4

⁴

The assumption that the merging operators of [47] return a single AF does not hold in general for all input tuples of AFs; in fact they show that when considering operators satisfying certain properties there is none that always returns a single AF. Nevertheless, our structural constraints can be straightforwardly applied to a tuple (set) of AFs.

Operators from this family specify the semantics of the output (i.e., specify a semantical constraint), and structural constraints that optimize the modifications of attacks. To such operators, similarly as for the revision operators, structural constraints can be added to further constrain the candidate solutions, e.g., to respect more interconnections between arguments and attacks.

Synthesis of argumentation frameworks. Broadly speaking, generation of structures from given information, also sometimes called learning, acquisition, or synthesis, has initiated several research directions within AI [20,24,46,100]. Focusing on the construction of argumentative structures [89,96,97], we recall the synthesis operation from [89], where our structural constraints can be applied. Simply put, the task in AF synthesis is to find an AF such that certain given examples of sets of arguments are (or are not) σ-extensions. An additional optimization criterion specifies that as many such examples as possible are satisfied. In its current form, AF synthesis incorporates structural constraints specifying that certain attacks have to part of the returned AF, or must be omitted. In addition, our structural constraints can specify, e.g., implications that specify that sets of attacks may be added as whole, or not at all.

10. Related work

A recent survey [52] gives an interesting overview over many approaches to dynamics of argumentation, constraints, and changes. In the following, we discuss relations of our work to several related works (including, but not restricting, to content of the survey).

Logical languages for dynamics and constraints. Several works considered constraints (in argumentation dynamics) specified in a logical language, which naturally relate to our work. In [50] control argumentation frameworks were proposed, where one can specify known, unknown, and controllable arguments by an agent, the last category being those arguments the agent can use in a debate. In [51,58] logical languages are proposed and used, in order to specify allowed changes to an argumentation framework. In contrast, we look ADFs (AFs in their works) and at particular families of constraints, consider their use cases, properties, computational aspects, and applied them in two case studies. Some of our constraints are already present in earlier works: limits of arguments and attacks, and mandatory (non-) presence of certain arguments and attacks is discussed, e.g., in [44,89,102]; similarly in enforcement and revision [42,43] optimization of modified attacks is part of the problem definition. We consider more general families of constraints. Constraints on presence of attacks is also, although in a quite different form, part of incorporation of preferences in structured argumentation, e.g., in [84], where a preference relation can make certain attacks not applicable. That is, a preference relation can be seen as a constraint on attacks.

Realizability and expressivity of argumentation frameworks. While our work focuses on structural constraints, semantical constraints are likewise important. A recent research direction is to study the signature of AFs, also called realizability [12,57,78]. That is, these studies reveal which sets of arguments can be, e.g., a part of the preferred semantics of an AF. In this way, limits to semantical constraints are given. Such constraints are also useful for incorporation of structural constraints, as seen by Example 10: when restricting an ADF structurally to be part of a particular sub family of ADFs (e.g., bipolar ADFs) the signature of the semantics changes and can directly lead to unsatisfiability of semantical constraints. Further, similar to this work, in [57] complexity results were shown for checking whether a semantical structure is part of the signature. While the realizability problem requires that an AF has exactly a certain semantics, in the synthesis problem [89] this is generalized to allow also for partial semantics specifications. Similarly, insights from AF synthesis can help to understand which constraints (semantical and structural) lead to a set of constraints that is satisfiable.

Dialogues, strategic argumentation, and incomplete AFs. Enforcement under structural constraints, as studied in this work, relates to some approaches in the literature. Incomplete AFs [13–17] are AFs where some attacks or arguments are fixed, while others can be modified. A task is then to see whether a set of arguments is an extension in all completions of the incomplete AFs. Bounds such as these, can be represented by the constraints considered in this work. In strategic argumentation, e.g., in [80–82], one can desire to look for an AF among many choices of AFs that satisfy a certain strategic goal (such as acceptance of an argument when adding arguments/attacks). Enforcement naturally shares this goal. Also, our structural constraints can be utilized to specify which AFs one may choose from. For our structured enforcement operator, dialogues, as studied in [64], have a similar motivation. In their work, a goal is to “reveal” (through a dialogue) parts of a knowledge base, in order to have parts revealed that make up a framework satisfying certain (strategic) goals. Similarly, structured enforcement aims to find an expansion satisfying an enforcement goal that also reflects contents of a knowledge base. Furthermore, different to the three directions, we work with general ADFs, consider several families of constraints, look at complexity of such families, and allow for rather fine-grained constraints (e.g., not allowing all completions). Further, our structured enforcement operator differs from the dialogue approach by working on expansion of AFs that reflect (general) structured formalisms in contrast to engaging in a dialogue that utters parts of a knowledge base, and include optimizations on such AFs.

11. Conclusions

In this article we have proposed to extend current (and future) dynamic operators on frameworks in argumentation in AI with constraints that, e.g., suit conditions “abstracted away” during instantiation, or ensure other desirable properties. More concretely, we proposed a set of constraints to be used for such operators, exemplified several use cases, and properties, of such constraints, investigated in more detail two concrete case studies developing an enforcement operator for ADFs based on supports and an enforcement operator for structured argumentation. The two case studies witness that our constraints can be utilized to extend operators, such as enforcement, in two ways: adapt them to more general abstract frameworks (e.g., ADFs), and adapt them to respect structural information from instantiation. Furthermore, we looked at the computational properties of constraints and the two novel enforcement operators. We implemented support enforcement in ASP, and presented an empirical evaluation of the resulting prototype. Our findings, from the case studies, are that several constraints can be applied to diverse scenarios, and our prototype implementation shows reasonable performance even when faced with complex optimization problems.

Directions for future work include, in particular, extending work on enforcement to complex contexts. For instance, our case study for a structural enforcement operator can be extended to one of the formalisms available in the field of structured argumentation (such as ABA and ASPIC+). However, such an endeavor requires care when instantiating: a large number of arguments (relations) should be avoided. We think that more efficient ways of instantiation, for which we already have seen early work [76,103], is a fruitful direction, since both dynamic operators we studied here, and static operators in argumentation can benefit from such efficiency gains.