JOINT PROCEEDINGS OF THE ECSQARU 2025
WORKSHOPS AND TUTORIALS

CO-LOCATED WITH THE 18TH EUROPEAN CONFERENCE ON SYMBOLIC AND
QUANTITATIVE APPROACHES TO REASONING WITH UNCERTAINTY (ECSQARU 2025)

EDITED BY

CARL COREA

JÉRÔME DELOBELLE

JOHN GRANT

JEAN-GUY MAILLY

JULIEN ROSSIT

KENNETH SKIBA

Universität Koblenz

Université Paris Cité

University of Maryland

Université Toulouse Capitole

FernUniversität in Hagen
# Preface

The biennial ECSQARU conferences<fnref n="1" /> constitute a major forum for advances in the theory and practice of reasoning under uncertainty, with a focus on bringing symbolic and quantitative aspects together. In the context of ECSQARU 2025², several events have been organized before the main part of the conference: the *First European Workshop on Argumentation and Uncertainty* (ArgU 2025³ - Organized by Jérôme Delobelle, Jean-Guy Mailly, Julien Rossit and Kenneth Skiba), the *First International Workshop on Inconsistency Measurement* (IM'25⁴ - Organized by Carl Corea and John Grant), and the tutorial *StaRAI: From a Probabilistic Propositional Model to a Highly Compressed Probabilistic Relational Model*<fnref n="5" /> given by Marcel Gehrke and Malte Luttermann.

Formal models of argumentation are approaches that deal with the representation and interaction of arguments and counterarguments. These models can be applied in all areas that benefit from automatic decision-support such as medicine, accounting, chemistry, and law. Links between formal argumentation and uncertainty have been emphasized in many ways, since argumentation-based formalisms can be used to provide reasoning methods in presence of uncertainty, and they are also subject to the presence of uncertainty (for instance regarding the evolution of a debate, or the strength of arguments). The workshop ArgU 2025 aims at discussing the most recent advances in the relation between argumentation and uncertainty. We have received 3 submissions that were all accepted for the workshop, which also consists of an invited talk given by Prof. Bart Verheij.

IM'25 is focused on the topic of Inconsistency measurement (IM). IM is a critical area in knowledge representation, data management, and automated reasoning, addressing the challenges posed by contradictory information within data and knowledge representation formalisms. The goal of this workshop is to provide a dedicated platform for researchers and practitioners alike to discuss recent advances in inconsistency measurement, explore novel ideas, and present practical applications across diverse domains. The workshop invited contributions focusing on (but not limited to): Inconsistency Measurement, Culpability Measurement, Disagreement Measurement. We are happy to have received 3 submissions, all of which could be accepted for the workshop.

September 2025

Carl Corea

Jérôme Delobelle

John Grant

Jean-Guy Mailly

Julien Rossit

Kenneth Skiba

<footnote n="1">¹www.ecsqaru.org</footnote>

<footnote n="2">²https://ecsqaru2025.krportal.org</footnote>

<footnote n="3">³https://argu2025.krportal.org</footnote>

<footnote n="4">⁴https://sites.google.com/view/im25</footnote>

<footnote n="5">⁵https://www.philosophie.uni-hamburg.de/chai/forschung/tutorials/ecsqaru-25.html</footnote>
# Program Committee

## ArgU 2025

* Caren Al Anaissy, Sorbonne Université, France

* Gianvincenzo Alfano, D.I.M.E.S Department, University of Calabria, Italy

* Khaled Belahcène, MICS-CentraleSupélec, Université Paris-Saclay, France

* Lars Bengel, FernUniversität in Hagen, Germany

* Lydia Blümel, FernUniversität in Hagen, Germany

* Andrea Cohen, Universidad Nacional del Sur, Argentina

* Dennis Craandijk, Utrecht University, the Netherlands

* Victor David, INRIA, France

* Sébastien Destercke, CNRS - Heudiasyc, Compiègne, France

* Sylvie Doutre, University Toulouse Capitole - IRIT, France

* Bettina Fazzinga, DICES, University of Calabria, Italy

* Jesse Heyninck, Open Universiteit, the Netherlands

* Anthony Hunter, University College London, UK

* Isabelle Kuhlmann, FernUniversität in Hagen, Germany

* Marie-Christine Lagasquie-Schiex, IRIT - Université Paul Sabatier, France

* Yasir Mahmood, Paderborn University, Germany

* Yann Munro, Sorbonne Université, Paris, France

* Andreas Niskanen, University of Helsinki, Finland

* Daphne Odekerken, Utrecht University, the Netherlands

* Tjitze Rienstra, Maastricht University, the Netherlands

* Matthias Thimm, FernUniversität in Hagen, Germany

* Srdjan Vesic, CRIL, CNRS – Univ. Artois, France

* Bruno Yun, LIRIS - University of Lyon 1, France

* Antonio Yuste-Ginel, University of Malaga, Spain

## IM 2025

* Leopoldo Bertossi, SKEMA Business School Canada Inc., Canada

* Bryson Brown, University of Lethbridge, Canada

* Sylvie Doutre, University Toulouse Capitole - IRIT, France

* Hendrik Decker, LMU Munich, Germany

* Anthony Hunter, University College London, UK
* Isabelle Kuhlmann, FernUniversität in Hagen, Germany

* Maria Vanina Martinez, IIIA - CSIC, Spain

* Manuel A. Martins, University of Aveiro, Portugal

* Cristian Molinaro, Università della Calabria, Italy

* Kedian Mu, Peking University, China

* Sabine Nagel, Universität Koblenz, Germany

* Francesco Parisi, University of Calabria, Italy

* Matthias Thimm, FernUniversität in Hagen, Germany

* Johannes P. Wallner, TU Graz, Austria
# Contents

I The First European Workshop on Argumentation and Uncertainty (ArgU 2025) 5

1 Hybrid reasoning with evidence: arguments, scenarios, probabilities - Keynote (B. Verheij) 6

2 Strong Admissibility for Infinite Argumentation Frameworks (M. Caminada) 7

3 Uncertainty in Quantitative Bipolar Argumentation Frameworks (J. Thieyre, C. Al Anaissy, A. Beynier, S. Destercke, N. Maudet, S. Vesic) 21

4 On Uncertainty in Collective Attacks in Abstract Argumentation (D. Lewin, K. Skiba) 25

II The First International Workshop on Inconsistency Measurement (IM 2025) 39

5 Germane Conflicts: Desirable Properties for Localising Inconsistency - Keynote (A. Hunter) 40

6 Measuring Inconsistency in a Fragment of Hybrid Logic (J. Grant, M. A. Martins) 41

7 Towards Measuring Minimal Inconsistencies in Declarative Process Models (S. Nagel, P. Delfmann) 53

8 A MaxSAT-Based Approach for Computing Inconsistency Degrees in Linear Temporal Logic on Fixed Traces (I. Kuhlmann) 59

III Tutorials 70

9 StaRAI: From a Probabilistic Propositional Model to a Highly Compressed Probabilistic Relational Model - Extended Abstract (Marcel Gehrke, Malte Luttermann) 71
# Part I

## The First European Workshop on
Argumentation and Uncertainty
(ArgU 2025)
# Hybrid reasoning with evidence: arguments, scenarios, probabilities

Bart Verheij

University of Groningen

The reliable use of AI in high-stakes domains, such as criminal justice or healthcare, demands more than just data and algorithms. In particular, systems must be able to reason with contradictory evidence, generating and evaluating alternative interpretations under uncertainty.

This talk focuses on hybrid reasoning with evidence, a dual perspective on augmentative human-machine collaboration and the integration of arguments, scenarios and probabilities. Humans excel at understanding context and values, and machines at processing data. Arguments handle exceptions, scenarios explore alternatives, and probabilities quantify uncertainty.

Our collaborative research points to a critical insight: the reliable, trustworthy use of AI requires a new theoretical foundation that properly integrates argumentative, narrative and probabilistic thinking.

I will discuss the limitations of current AI, recent advances in hybrid reasoning with evidence, and the path forward, illustrated with examples about crime cases.

## References

[1] B. Verheij, Arguments for Good Artificial Intelligence, University of Groningen, Groningen, 2018.

[2] M. Di Bello, B. Verheij, Evidential reasoning, in: G. Bongiovanni, G. Postema, A. Rotolo, G. Sartor, C. Valentini, D. N. Walton (Eds.), Handbook of Legal Reasoning and Argumentation, Springer, Dordrecht, 2018, pp. 447–493.

[3] C. Steging, S. Renooij, B. Verheij, Parameterized argumentation-based reasoning tasks for benchmarking generative language models, in: Proceedings of the 20th International Conference on Artificial Intelligence and Law (ICAIL 2025), ACM, New York (New York), 2025, pp. 443–447.

[4] L. van Leeuwen, B. Verheij, R. Verbrugge, S. Renooij, Evaluating methods for scenario reasoning using bayesian networks in exhaustive and non-exhaustive settings, in: Proceedings of the 20th International Conference on Artificial Intelligence and Law (ICAIL 2025), ACM, New York (New York), 2025, pp. 443–447.

[5] W. Van Woerkom, D. Grossi, H. Prakken, B. Verheij, A fortiori case-based reasoning: from theory to data, Journal of Artificial Intelligence Research 81 (2024) 401–441.

[6] G. Zamprogno, I. Tiddi, B. Verheij, Hypothesis updating by combining knowledge graphs and argumentation, in: F. Lorig, J. Tucker, A. Lindstrom, F. Dignum, P. Murukannaiah, A. Theodorou, P. Yolum (Eds.), HHAI 2024: Hybrid Human AI Systems for the Social Good, IOS Press, Netherlands, 2024, pp. 441–448.

[7] W. Fungwacharakorn, K. Satoh, B. Verheij, Constructing and explaining case models: A case-based argumentation perspective, in: M. Bono, K. Satoh, Y. Takama, L. Nguyen, S. Kurahashi (Eds.), New Frontiers in Artificial Intelligence (JSAI-isAI 2023), Springer, 2023, pp. 100–114.

<figure><img src="image_1.png" /></figure>
# Strong Admissibility for Infinite Argumentation Frameworks

Martin Caminada¹

¹Cardiff University, Abacws building, Senghennydd Road, Cardiff, CF24 4AG

**Abstract**

Strong admissibility plays an important role in formal argumentation under the grounded semantics, especially when explaining the acceptance of an argument. However, strong admissibility has so far only been defined in the context of finite argumentation frameworks. In the current paper, we examine the case of infinite argumentation frameworks. In particular, we assess what the challenges are when moving from finite to infinite argumentation frameworks and we show that despite these challenges, strong admissibility can be meaningfully defined and applied in the context of infinite argumentation frameworks.

**Keywords**

Abstract Argumentation, Strong Admissibility, Infinite Argumentation Frameworks

## 1. Introduction

Formal argumentation has become one of the key approaches for symbolic reasoning under uncertainty [1]. Within formal argumentation, strong admissibility [2, 3, 4] plays a key role, especially in the context of grounded semantics. In essence, strong admissibility relates to grounded semantics in a similar way as admissibility relates to preferred semantics, especially when it comes to proof procedures. In order to show that an argument is in a preferred extension, it is not necessary to construct the entire preferred extension. Instead, it is sufficient to show that the argument is in an admissible set. Similarly, in order to show that an argument is in the grounded extension, it is not necessary to construct the entire grounded extension. Instead, it is sufficient to show that the argument is in a strongly admissible set [4]. Such a strongly admissible set can then either be presented in its original form, or be the basis for an interactive explanation in the form of a discussion game [5].

Strong admissibility was originally only defined for finite argumentation frameworks [2, 3, 4, 6, 7]. This can be a limitation, especially when applying strong admissibility in the context of instantiated argumentation. For instance, when applying ASPIC⁺ [8] with domain independent strict rules (that is, with strict rules based on classical logic entailment) the mere fact that there exist an infinite number of tautologies implies that there will be an infinite number of arguments. As such, it is worthwhile to explore how the concept of strong admissibility can be applied to infinite argumentation frameworks as well.

In the current paper, we examine the challenges when it comes to applying strong admissibility in the context of infinite argumentation frameworks. We provide a novel definition of strong admissibility that can be applied in a meaningful way for both finite and infinite argumentation frameworks. Moreover, we show that our new definition is backwards compatible with existing definitions of strong admissibility that were restricted to finite argumentation frameworks only. That is, we show that for finite argumentation frameworks, our new definition coincides with the existing definitions of strong admissibility. In addition, we show that (even in the context of infinite argumentation frameworks) our new definition satisfies properties very similar to what is satisfied by the existing definitions in the context of finite argumentation frameworks.

ArgU'25: First European Workshop on Argumentation and Uncertainty, September 23, 2025, Hagen, Germany

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

CaminadaM@cardiff.ac.uk (M. Caminada)

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

https://users.cs.cf.ac.uk/CaminadaM/ (M. Caminada)

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

0000-0002-7498-0238 (M. Caminada)

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

© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The current work is closely related to a paper that has recently been accepted to the ECSQARU 2025 conference [9]. However, where the ECSQARU paper restricts itself to finitary argumentation frameworks,<fnref n="1" /> the current work reports on subsequent research where we are able to lift this restriction and define strong admissibility for infinite argumentation frameworks in general (finitary or not).

The current paper is structured as follows. First, in Section 2, we provide some basic definitions and formal preliminaries. Then, in Section 3 we present some of the existing definitions of strong admissibility and examine why these are problematic in the context of infinite argumentation frameworks.<fnref n="2" /> Then, in Section 4 we introduce a new definition of strong admissibility, one that is well-defined for both finite and infinite argumentation frameworks, is backwards compatible with previous definitions of strong admissibility and satisfies similar properties. We round off in Section 5 with a discussion of the obtained results.

## 2. Preliminaries

In the current section, we briefly restate some of the key concepts of abstract argumentation theory, in its extension-based form.

**Definition 1.** An argumentation framework is a pair $(Ar, att)$ where $Ar$ is a set of entities, called arguments, whose internal structure can be left unspecified, and $att$ is a binary relation on $Ar$. For any $A, B \in Ar$ we say that $A$ attacks $B$ iff $(A, B) \in att$. An argumentation framework is called finite iff $Ar$ is finite, and is called finitary iff for each $A \in Ar$, the set $\{B \mid (B, A) \in att\}$ is finite.

**Definition 2.** Let $AF = (Ar, att)$ be an argumentation framework, $A \in Ar$ and $Args$ $\subseteq$ $Ar$. We define $A^+$ as $\{B \in Ar \mid A \text{ attacks } B\}$, $A^-$ as $\{B \in Ar \mid B \text{ attacks } A\}$, $Args^+$ as $\cup\{A^+ \mid A \in\}$, and $Args^-$ as $\cup\{A^- \mid A \in Arg\}$. $Args$ is said to be conflict-free iff $Args \cap $Args$^+ = \emptyset$. $Args$ is said to defend $A$ iff $A^- \subseteq $Args$^+$. The characteristic function $F_{AF} : 2^{Ar} \to 2^{Ar}$ is defined as $F_{AF}(Args) = \{A \mid Arg \text{ defends } A\}$.

**Definition 3.** Let $AF = (Ar, att)$ be an argumentation framework. $Args \subseteq Ar$ is said to be:

* an admissible set of $AF$ iff $Args$ is conflict-free and $Args \subseteq F_{AF}(Args)$

* a complete extension of $AF$ iff $Args$ is conflict-free and $Args = F_{AF}(Args)$

* a grounded extension of $AF$ iff $Args$ is the (unique) smallest (w.r.t. $\subseteq$) complete extension

* a preferred extension of $AF$ iff $Args$ is a maximal (w.r.t. $\subseteq$) complete extension

## 3. Strong Admissibility and Infinite Argumentation Frameworks

In the current section, we provide a brief overview of strong admissibility in its different forms,<fnref n="3" /> as well as of the challenges one encounters when trying to apply this concept in the context of infinite argumentation frameworks. Due to space limitations, we are unable to provide a general discussion of how strong admissibility is applied for finite argumentation frameworks. For this, we refer the reader to [4].

The concept of strong admissibility was first introduced by Baroni and Giacomin [2], using the notion of strong defence.

**Definition 4** ([2]). Let $(Ar, att)$ be an argumentation framework, $A \in Ar$ and $Args$ $\subseteq$ $Ar$. $A$ is strongly defended by $Args$ iff each attacker $B \in Ar$ of $A$ is attacked by some $C \in $Args $\setminus$ $\{A\}$ such that $C$ is strongly defended by $Args$ $\setminus$ $\{A\}$.

<footnote n="1">¹An argumentation framework is finitary iff each argument has a finite number of attackers [10].</footnote>

<footnote n="2">²Most of the contents of Section 3 is also contained in [9]. The reason for including it here as well is to make the paper self-contained.</footnote>

<footnote n="3">³Please notice that we restrict ourselves to set-based (instead of labelling-based) definitions of strong admissibility.</footnote>
Baroni and Giacomin say that a set *Args* satisfies the strong admissibility property iff it strongly defends each of its arguments [2]. However, it is also possible to define strong admissibility in an equivalent way without having to refer to strong defence [4].

**Definition 5** ([4]). Let (Ar, att) be an argumentation framework. *Args* ⊆ Ar is strongly admissible iff every A ∈ *Args* is defended by some *Args*' ⊆ *Args* \ {A} which in its turn is again strongly admissible.

It is important to note that Definition 4 and Definition 5 have so far only been applied in the context of finite argumentation frameworks (that is, argumentation frameworks in which the number of arguments is finite). Unfortunately, these definitions cannot easily be applied in the context where the argumentation framework is infinite. To see why, consider the infinite argumentation framework *AF*₁ = (*Ar*, *att*) where *Ar* = {*A*₁, *A*₂, *A*₃, ...} and *att* = {(*A*ᵢ₊₁, *A*ᵢ) | i ≥ 1}. This argumentation framework is shown in Figure 1.

<figure><img src="image_6.png" /><figcaption>**Figure 1:** *AF*₁: each argument is attacked by its successor</figcaption></figure>

In argumentation framework *AF*₁ there exist precisely three admissible sets: ∅, {*A*ᵢ | i is odd} and {*A*ᵢ | i is even}. The first set is the grounded extension. The second and third set are the preferred extensions. However, when trying to apply either Definition 4 or Definition 5 to assess whether the latter two sets are strongly admissible, one stumbles upon a problem. Take for instance the set {*A*ᵢ | i is odd}. When applying Definition 4 to assess whether *A*₁ is strongly defended by {*A*ᵢ | i is odd}, we observe that *A*₁'s attacker *A*₂ is attacked by *A*₃ ∈ {*A*ᵢ | i is odd} \ {*A*₁}. So we need to assess whether *A*₃ is strongly defended by {*A*ᵢ | i is odd} \ {*A*₁}. For this, we need to assess whether *A*₅ is strongly defended by {*A*ᵢ | i is odd} \ {*A*₁, *A*₃}, etc. The point here is that Definition 4 has a recursive nature, and for the argumentation framework *AF*₁ the recursion does not end. As such, one could either assume that for each odd *j*, *A*ᵢ is strongly defended by {*A*ᵢ | i is odd} \ {*A*ₖ | *k* is odd and *k* < *j*}, or that for each odd *j*, *A*ᵢ is not strongly defended by {*A*ᵢ | i is odd} \ {*A*ₖ | *k* is odd and *k* < *j*}. Both assumptions are consistent with Definition 4, yet only one of them can hold.

A similar problem occurs in the context of Definition 5. Here, in order to determine whether {*A*ᵢ | i is odd} is a strongly admissible set, we have to determine whether *A*₁ is defended by some subset of {*A*ᵢ | i is odd} \ {*A*₁} which in its turn is strongly admissible. In essence, Definition 5 is another example of a recursive definition of which the recursion does not end for argumentation framework *AF*₁.

A third definition of strong admissibility was provided in [4, Lemma 2, Theorem 1].<fnref n="4" />

**Definition 6.** Let *AF* = (*Ar*, *att*) be an argumentation framework and let *Args* ⊆ *Ar*. Let $H_{*Args}^0 = \emptyset$ and $H_{*Args}^{i+1} = F_{*AF} (H_{*Args}^i) \cap *Args$ ($i \ge 0$). *Args* is strongly admissible iff $\bigcup_{i=0}^\infty H_{*Args}^i = *Args$.

Definition 6 is not recursive. As such, it avoids the problem of potential infinite recursion. In particular, for *AF*₁ it can be observed that for any set *Args*, $H_{*Args}^0 = \emptyset$, $H_{*Args}^1 = F(H_{*Args}^0) \cap *Args = \emptyset$, $H_{*Args}^2 = F(H_{*Args}^1) \cap *Args = \emptyset$, etc. As such, the only set that is strongly admissible is the empty set, which as we observed before, is also the grounded extension.

Although Definition 6 allows one to unambiguously assess, even for infinite argumentation frameworks, whether a particular set is strongly admissible or not, it still has some issues. Consider the argumentation framework *AF*₂ = (*Ar*, *att*) with *Ar* = {*A*ᵢ | i ≥ 1} ∪ {*B*} and *att* = {(*A*ᵢ, *A*ᵢ₊₁) | i ≥ 1} ∪ {(*A*ⱼ, *B*) | *j* is even}. This argumentation framework is shown in Figure 2.

*AF*₂ only has one complete extension: {*A*ⱼ | *j* is odd} ∪ {*B*}, which is also the grounded extension. Yet, this grounded extension is not strongly admissible, at least not according to Definition 6. This

<footnote n="4">⁴It has been shown that Definition 4, Definition 5 and Definition 6 are equivalent to each other in the context of finite argumentation frameworks [4].</footnote>
<figure><img src="image_7.png" /><figcaption>**Figure 2:** $AF_2$: an argumentation framework that is not finitary in the sense of [10]</figcaption></figure>

is because (when taking *Args* as {*A*<sub>j</sub> | *j* is odd} ∪ {*B*}) ∪<sub>*i*=0</sub><sup>∞</sup> *H*<sup>*i*</sup><sub>*Args*</sub> is {*A*<sub>j</sub> | *j* is odd} instead of {*A*<sub>j</sub> | *j* is odd} ∪ {*B*}.<fnref n="5" /> More seriously, even though *B* is in the grounded extension, there is no strongly admissible set that contains *B*, at least not according to Definition 6. This is a problem, as the whole idea of strong admissibility is to show that an argument is in the grounded extension by showing that it is in a strongly admissible set [6].<fnref n="6" /> For finite argumentation frameworks, this property actually holds; in particular, it also holds that the grounded extension is always strongly admissible. For infinite argumentation frameworks, the property unfortunately does not always hold, as shown by the counter example of $AF_2$.

In [9] the notion of strong admissibility is broadened from finite argumentation frameworks to finitary argumentation frameworks. It is shown that, when restricted to finitary argumentation frameworks, strong admissibility as defined by Definition 6 satisfies the following properties:<fnref n="7" />

* each strongly admissible set is an admissible set

* the empty set is the smallest strongly admissible set (w.r.t. ⊑)

* the grounded extension is the biggest strongly admissible set (w.r.t. ⊑)

* the strongly admissible sets form a lattice (w.r.t. ⊑)

# 4. A New Definition of Strong Admissibility

In the current section we introduce a new definition of strong admissibility and examine its properties. However, before doing so, we first need to formally define the restriction of an argumentation framework to a set of arguments.

**Definition 7.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework and let $Args$ ⊑ $Ar$. We define $AF|_{Args}$ as $(Args, att ∩ (Args ×Args))$.

Our new definition of strong admissibility is as follows.

**Definition 8.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework and let $Args$ ⊑ $Ar$. $Args$ is called a strongly admissible set iff $Args$ is the grounded extension of $AF|_{Args ∪Args^-}$.

It should be mentioned that Definition 8 is not in any way restricted to finite or even finitary argumentation frameworks. It is designed to be applied to *any* argumentation framework (finite or infinite, finitary or non-finitary).

As an example of how Definition 8 is applied, consider the argumentation framework $AF_3$, depicted in Figure 3. Here, the strongly admissible sets are $\emptyset$, {*A*}, {*A*, *C*}, {*A*, *C*, *F*}, {*D*}, {*A*, *D*}, {*A*, *C*, *D*}, {*D*, *F*}, {*A*, *D*, *F*} and {*A*, *C*, *D*, *F*}, the latter also being the grounded extension of $AF_3$. As an example, the set {*A*, *C*, *F*} is strongly admissible because it is the grounded extension of $AF_3|\{A,C,F\} \cup \{A,C,F\}^-$ = $AF_3|\{A,B,C,E,F\} = (\{A,B,C,E,F\}, \{(A,B), (B,C), (C,E), (E,F)\})$. As another example, the set {*F*}, although admissible, is *not* strongly admissible, because it is not the

<footnote n="5">⁵A similar problem was observed in [10] w.r.t. the inductive proof procedure for grounded semantics.</footnote>

<footnote n="6">⁶In a similar way, one shows that an argument is in a preferred extension by showing that it is in an admissible set.</footnote>

<footnote n="7">⁷The same properties have previously been proven in [4] in the more restricted context of finite (instead of finitary) argumentation frameworks.</footnote>
From the thus proved fact that for each $i \ge 0$, $F^i = H_{\mathcal{A}rgs}^i$, it follows that $\bigcup_{i=0}^{\infty} F^i = \bigcup_{i=0}^{\infty} H_{\mathcal{A}rgs}^i$, so from $\mathcal{A}rgs = \bigcup_{i=0}^{\infty} F^i$ it follows that $\mathcal{A}rgs = \bigcup_{i=0}^{\infty} H_{\mathcal{A}rgs}^i$.

"<=" Let $\mathcal{A}rgs$ be a strongly admissible set in the sense of Definition 6. That is, $\mathcal{A}rgs = \bigcup_{i=0}^{\infty} H_{\mathcal{A}rgs}^i$ with $H_{\mathcal{A}rgs}^0 = \emptyset$ and $H_{\mathcal{A}rgs}^{i+1} = F_{AF}(H_{\mathcal{A}rgs}^i) \cap \mathcal{A}rgs$. We need to prove that $\mathcal{A}rgs$ is the grounded extension of $AF' = AF|_{\mathcal{A}rgs \cup \mathcal{A}rgs^-}$. That is, we need to prove that $\mathcal{A}rgs = \bigcup_{i=0}^{\infty} F^i$ with $F^0 = \emptyset$ and $F^{i+1} = F_{AF'}(F^i)$. This follows from the induction proof above (at "⇒") where it was shown that for each $i \ge 0$, $F^i = H_{\mathcal{A}rgs}^i$.

□

It has previously been shown that for finite argumentation frameworks, Definition 4, Definition 5 and Definition 6 coincide with each other [4]. As such, it follows from Theorem 1 that Definition 8 is backwards compatible not just with Definition 6 but also with Definition 4 and Definition 5 in the context of finite argumentation frameworks.

Now that we have shown our new definition of strong admissibility (Definition 8) to be backwards compatible with the previous definitions of strong admissibility, the next step is to show that it satisfies similar properties. That is, we aim to show that strong admissibility in the sense of Definition 8 satisfies the following properties:

* each strongly admissible set is an admissible set

* the empty set is the smallest strongly admissible set (w.r.t. $\subseteq$)

* the grounded extension is the biggest strongly admissible set (w.r.t. $\subseteq$)

* the strongly admissible sets form a lattice (w.r.t. $\subseteq$)

These properties are to be shown for arbitrary argumentation frameworks (finite or infinite, finitary or non-finitary) instead of just for finite argumentation frameworks [4] or finitary argumentation frameworks [9].

We start with showing that under our new definition of strong admissibility (Definition 8), each strongly admissible set is also an admissible set.

**Theorem 2.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework and let $\mathcal{A}rgs \subseteq Ar$ be a strongly admissible set (in the sense of Definition 8). It holds that $\mathcal{A}rgs$ is also an admissible set of $AF$.

*Proof.* The fact that $\mathcal{A}rgs$ is a strongly admissible set in the sense of Definition 8 means that $\mathcal{A}rgs$ is the grounded extension of $AF' = AF|_{\mathcal{A}rgs \cup \mathcal{A}rgs^-}$. As the grounded extension is admissible, it follows that $\mathcal{A}rgs$ is an admissible set of $AF'$. As such, $\mathcal{A}rgs$ is conflict-free in $AF'$, from which it follows that $\mathcal{A}rgs$ is also conflict-free in $AF$. We proceed to show that $\mathcal{A}rgs$ also defends all its elements in $AF$. Let $A \in \mathcal{A}rgs$. Then for each $B$ that attacks $A$ in $AF'$, there exists a $C \in \mathcal{A}rgs$ that attacks $B$ in $AF'$. Let $B$ be an attacker of $A$ in $AF$. As $A \in \mathcal{A}rgs$, it follows that $B \in \mathcal{A}rgs^-$, so $B$ also attacks $A$ in $AF'$. It then follows that there is a $C \in \mathcal{A}rgs$ that attacks $B$ in $AF'$. The same $C$ also attacks $B$ in $AF$. That is, $\mathcal{A}rgs$ defends $A$ in $AF$. The thus derived facts that $\mathcal{A}rgs$ is conflict-free in $AF$ and defends all of its elements in $AF$ mean that $\mathcal{A}rgs$ is an admissible set in $AF$. □

The next thing to observe is that the empty set is always strongly admissible.

**Proposition 1.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework. It holds that the empty set ($\emptyset$) is strongly admissible in the sense of Definition 8.

*Proof.* It holds that $AF|_{\emptyset \cup \emptyset^-} = AF|_{\emptyset}$ is the empty argumentation framework, which has the empty set as its grounded extension. □

As no set can be smaller than the empty set, it trivially follows that the empty set is the *smallest* strongly admissible set in the sense of Definition 8.

We proceed to show that the grounded extension is the biggest strongly admissible set. For this, we first show that the grounded extension is strongly admissible.
**Theorem 3.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework. The grounded extension of $AF$ is strongly admissible (in the sense of Definition 8).

*Proof.* Let $GE$ be the grounded extension of $AF$. That is, $GE$ is the smallest fixpoint of $F_{AF}$. We have to prove that $GE$ is also the grounded extension of $AF|_{GE \cup GE^-}$. For this, we have to show that $GE$ is the smallest fixpoint of $F_{AF|_{GE \cup GE^-}}$ in $AF|_{GE \cup GE^-}$. We start with showing that $GE$ is a fixpoint of $F_{AF|_{GE \cup GE^-}}$.

1. $GE \subseteq F_{AF|_{GE \cup GE^-}}(GE)$

Let $A \in GE$. Then from the fact that $GE$ is a fixpoint of $F_{AF}$ it follows that $A \in F_{AF}(GE)$. That is, for each $B$ that attacks $A$ in $AF$, there is a $C \in GE$ that attacks $B$ in $AF$. Let $B$ be an argument that attacks $A$ in $AF|_{GE \cup GE^-}$. Then $B$ also attacks $A$ in $AF$ (because every attack in $AF|_{GE \cup GE^-}$ is also an attack in $AF$), so there is a $C \in GE$ that attacks $B$ in $AF$. The same $C$ also attacks $B$ in $AF|_{GE \cup GE^-}$ (this is because every attack in $AF$ between arguments in $GE \cup GE^-$ is also an attack in $AF|_{GE \cup GE^-}$, together with the fact that $A \in GE$ and $B \in GE^-$) so $A \in F_{AF|_{GE \cup GE^-}}(GE)$.

2. $F_{AF|_{GE \cup GE^-}}(GE) \subseteq GE$

Let $A \in F_{AF|_{GE \cup GE^-}}(GE)$. Then for each $B$ that attacks $A$ in $AF|_{GE \cup GE^-}$ there is a $C \in GE$ that attacks $B$ in $AF|_{GE \cup GE^-}$. Let $B$ be an argument that attacks $A$ in $AF$. Then $B$ also attacks $A$ in $AF|_{GE \cup GE^-}$ (this is because $B$ attacks $A \in GE$, so $B \in GE^-$, so both $A$ and $B$ are in $GE \cup GE^-$) so there exists a $C \in GE$ that attacks $B$ in $AF|_{GE \cup GE^-}$. The same $C$ also attacks $B$ in $AF$ (because every attack in $AF|_{GE \cup GE^-}$ is also an attack in $AF$) so $A \in F_{AF}(GE)$. From the fact that $GE$ is a fixpoint of $F_{AF}$ it follows that $A \in GE$.

Now that we have proved that $GE$ is a fixpoint of $AF|_{GE \cup GE^-}$, the next thing to prove is that $GE$ is also the smallest fixpoint of $AF|_{GE \cup GE^-}$. Let $GE' \subseteq GE$ be a fixpoint in $AF|_{GE \cup GE^-}$. That is, $GE' = F_{AF|_{GE \cup GE^-}}(GE')$. We proceed to show that $GE'$ is also a fixpoint in $AF$.

1. $GE' \subseteq F_{AF}(GE')$

Let $A \in GE'$. Then from $GE' = F_{AF|_{GE \cup GE^-}}(GE')$ it follows that each $B$ that attacks $A$ in $AF|_{GE \cup GE^-}$ there is a $C \in GE'$ that attacks $B$ in $AF|_{GE \cup GE^-}$. Let $B$ be an argument that attacks $A$ in $AF$. From the fact that $B$ attacks $A \in GE'$, it follows that $B \in GE'^-$. From the fact that $GE' \subseteq GE$ it follows that $GE'^- \subseteq GE^-$, so $B \in GE^-$. Similarly, from the fact that $A \in GE'$ and $GE' \subseteq GE$ it follows that $A \in GE$. So $A, B \in GE \cup GE^-$. This means that $B$ attacks $A$ not only in $AF$ but also in $AF|_{GE \cup GE^-}$. From the fact that $A \in F_{AF|_{GE \cup GE^-}}(GE)$ (as $A \in GE' = F_{AF|_{GE \cup GE^-}}(GE')$) it then follows that there is a $C \in GE'$ that attacks $B$ in $AF|_{GE \cup GE^-}$. The same $C$ also attacks $B$ in $AF$ (as every attack in $AF|_{GE \cup GE^-}$ is also an attack in $AF$). So $A \in F_{AF}(GE')$.

2. $F_{AF}(GE') \subseteq GE'$

Let $A \in F_{AF}(GE')$. We first observe that as $F_{AF}$ is a monotonic function, $GE' \subseteq GE$ implies that $F_{AF}(GE') \subseteq F_{AF}(GE)$. So the fact that $A \in F_{AF}(GE')$ implies that $A \in F_{AF}(GE)$, so $A \in GE$, which means that $A$ is an argument in $AF|_{GE \cup GE^-}$. The fact that $A \in F_{AF}(GE')$ implies that for every $B$ that attacks $A$ in $AF$ there exists a $C \in GE'$ that attacks $B$ in $AF$. Let $B$ be an argument that attacks $A$ in $AF|_{GE \cup GE^-}$. Then $B$ also attacks $A$ in $AF$ (as every attack in $AF|_{GE \cup GE^-}$ is also an attack in $AF$) so there is a $C \in GE'$ that attacks $B$ in $AF$. The same $C$ also attacks $B$ in $AF|_{GE \cup GE^-}$. So $A \in F_{AF|_{GE \cup GE^-}}(GE')$. As $GE' = F_{AF|_{GE \cup GE^-}}(GE')$ it follows that $A \in GE'$.

From the thus obtained fact that $GE'$ is a fixpoint of $F_{AF}$, together with the fact that $GE$ is the smallest fixpoint of $F_{AF}$ (as $GE$ is the grounded extension of $AF$) it follows that $GE \subseteq GE'$. This, together with our initial assumption that $GE' \subseteq GE$ implies that $GE = GE'$. Hence, $GE$ is the smallest fixpoint of $F_{AF|_{GE \cup GE^-}}$.

Now that we have established that the grounded extension is a strongly admissible set, we proceed to show that it is also the biggest strongly admissible set.
**Theorem 4.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework. The grounded extension of $AF$ is the biggest strongly admissible set of $AF$ in the sense of Definition 8.

*Proof.* Let $GE$ be the grounded extension of $AF$ and let $Args$ $\subseteq$ $Ar$ be a strongly admissible set of $AF$ (in the sense of Definition 8) such that $GE \subseteq Claims$. We need to prove that $Args$ $\subseteq$ $GE$. We start with proving that $GE$ is a complete extension of $AF|_{Claims \cup Claims}$. First of all, from the fact that $GE$ is conflict-free in $AF$, it follows that $GE$ is also conflict-free in $AF|_{Claims \cup Claims}$ (as each attack in $AF|_{Claims \cup Claims}$ is also an attack in $AF$). We proceed to prove that $GE = F_{AF}|_{Claims \cup Claims}$ ($GE$).

"**$\subseteq$**" Let $A \in GE$. From the fact that $GE \subseteq Claims$ it follows that $A \in Claims$, so $A$ is an argument in $AF|_{Claims \cup Claims}$. Let $B$ be an argument that attacks $A$ in $AF|_{Claims \cup Claims}$. Then $B$ also attacks $A$ in $AF$ (as every attack in $AF|_{Claims \cup Claims}$ is also an attack in $AF$). From the fact that $GE = F_{AF}(GE)$ it follows that there is a $C \in GE$ that attacks $B$ in $AF$. The same $C$ also attacks $B$ in $AF|_{Claims \cup Claims}$, as $C \in GE$ and $GE \subseteq Claims$, so $C \in Claims \cup Claims^-$. Therefore, $A \in F_{AF}|_{Claims \cup Claims^-}(GE)$.

"**$\supseteq$**" Let $A \in F_{AF}|_{Claims \cup Claims^-}(GE)$. From the fact that $F_{AF}|_{Claims \cup Claims^-}$ is a monotonic function, the fact that $GE \subseteq Claims$ implies $F_{AF}|_{Claims \cup Claims^-}(GE) \subseteq F_{AF}|_{Claims \cup Claims^-}(Claims)$, so $A \in F_{AF}|_{Claims \cup Claims^-}(Claims)$. As $Claims$ is a strongly admissible set of $AF$, it holds by definition that $Claims$ is the grounded extension of $AF|_{Claims \cup Claims^-}$, so $F_{AF}|_{Claims \cup Claims^-}(Claims) = Claims$, so $A \in Claims$. The fact that $A \in F_{AF}|_{Claims \cup Claims^-}(GE)$ means that for each $B$ that attacks $A$ in $AF|_{Claims \cup Claims^-}$ there is a $C \in GE$ that attacks $B$ in $AF|_{Claims \cup Claims^-}$. Let $B$ be an argument that attacks $A$ in $AF$. Then the fact that $A \in Claims$ implies that $B$ attacks $Claims$, so $B \in Claims^-$. Therefore, $B$ also attacks $A$ in $AF|_{Claims \cup Claims^-}$, so there exists a $C \in GE$ that attacks $B$ in $AF|_{Claims \cup Claims^-}$. The same $C$ also attacks $B$ in $AF$ (as every attack in $AF|_{Claims \cup Claims^-}$ is also an attack in $AF$). Therefore, $A \in F_{AF}(GE)$. As $F_{AF}(GE) = GE$, it directly follows that $A \in GE$.

Now that we obtained that $GE$ is a complete extension of $AF|_{Claims \cup Claims^-}$, we can infer that this is a superset of the grounded extension of $AF|_{Claims \cup Claims^-}$. That is, $GE \supseteq Claims$, which is precisely what we needed to prove. $\square$

The next step is to show that the union of two strongly admissible sets is strongly admissible. To do so, we need the following proposition.

**Proposition 2.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework and let $Args$ $\subseteq$ $Ar$. If $Args$ is conflict-free then $F_{AF}(Args)$ is also conflict-free.

*Proof.* Suppose $F_{AF}(Args)$ is not conflict-free. Then $F_{AF}(Args)$ contains arguments $A$ and $B$ such that $A$ attacks $B$. From the fact that $B$ is defended by $Args$ it follows that there must be a $C \in Claims$ that attacks $A$. From the fact that $A$ is defended by $Args$ it follows that there must be some $D \in Claims$ that attacks $C$. Hence, $Args$ is not conflict-free. $\square$

**Theorem 5.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework and let $Args_1$ and $Args_2$ be strongly admissible sets of $AF$ (in the sense of Definition 8). It holds that $Args_1 \cup Claims_2$ is also a strongly admissible set of $AF$ (in the sense of Definition 8).

*Proof.* The fact that $Args_1$ is a strongly admissible set of $AF$ means that $Args_1$ is the grounded extension of $AF|_{Args_1 \cup Claims_1^-}$. Similarly, the fact that $Args_2$ is a strongly admissible set of $AF$ means that $Args_2$ is the grounded extension of $AF|_{Args_2 \cup Claims_2^-}$. We need to show that $Args_1 \cup Claims_2$ is the grounded extension of $AF|_{Args_1 \cup Claims_2 \cup Claims_1^- \cup Claims_2^-}$. For this, we first show that $Args_1 \cup Claims_2$ is a fixpoint of $F_{AF}|_{Args_1 \cup Claims_2 \cup Claims_1^- \cup Claims_2^-}$. That is, we show that $Args_1 \cup Claims_2 = F_{AF}|_{Args_1 \cup Claims_2 \cup Claims_1^- \cup Claims_2^-}(Args_1 \cup Claims_2)$.
“⊆” Let $A \in \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$. Without loss of generality, assume that $A \in \mathcal{A}rgs_1$ (the case of $A \in \mathcal{A}rgs_2$ is similar). Let $B$ be an argument that attacks $A$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. Then by definition, $B \in \mathcal{A}rgs_1^-$. So the fact that $A \in \mathcal{A}rgs_1 = F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}}$ implies that there is a $C \in \mathcal{A}rgs_1$ that attacks $B$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$. The same $C \in \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ also attacks $B$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$ (this is because every attack in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$ is also an attack in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$). So $A$ is defended by $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. That is, $A \in F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2)$.

“⊆” Suppose $A \in F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2)$. That is, each $B$ that attacks $A$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$ is attacked by some $C \in \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$. We need to prove that $A \in \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$. From the fact that $A$ is an argument in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$ it follows that $A \in \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-$. We distinguish two cases:

1. $A \in \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$.

In that case, we're done.

2. $A \in \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-$.

Assume without loss of generality that $A \in \mathcal{A}rgs_1^-$ (the case of $A \in \mathcal{A}rgs_2^-$ is similar).

We first show that $\mathcal{A}rgs_1 \subseteq F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1)$. Let $A' \in \mathcal{A}rgs_1$.

Let $B$ be an attacker of $A'$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. As $A' \in \mathcal{A}rgs_1$, it follows that $B \in \mathcal{A}rgs_1^-$. Therefore, $B$ also attacks $A'$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$, so from $A' \in \mathcal{A}rgs_1 = F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}}(\mathcal{A}rgs_1)$ it follows that $A'$ is defended by $\mathcal{A}rgs_1$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$, so there is a $C \in \mathcal{A}rgs_1$ that attacks $B$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$. The same $C$ also attacks $B$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. Therefore, $A'$ is defended by $\mathcal{A}rgs_1$ in $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. That is, $A' \in F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1)$.

From the trivial fact that $\mathcal{A}rgs_1 \subseteq \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ and the fact that $F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}$ is a monotonic function, it follows that $F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1) \subseteq F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2)$.

This, together with the above derived fact that $\mathcal{A}rgs_1 \subseteq F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1)$ implies that $\mathcal{A}rgs_1 \subseteq F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2)$. The fact that $A \in \mathcal{A}rgs_1^-$ means $A$ attacks $\mathcal{A}rgs_1$. Hence, $F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}(\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2)$ is not conflict-free. From Lemma 2 it then follows that $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ is not conflict-free. However, as both $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$ are strongly admissible sets of $AF$, it follows that the grounded extension of $AF$ contains both $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$ (as it follows from Theorem 4 that the grounded extension is the biggest strongly admissible set of $AF$). That is, the grounded extension of $AF$ contains $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$. Therefore, the grounded extension of $AF$ is not conflict-free. Contradiction.

Now that we have proved that $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ is a fixpoint of $F_{AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}}$, we proceed to prove that it is also the smallest fixpoint. For this, we first observe that $(AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-})_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-} = AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$. Hence, the fact that $\mathcal{A}rgs_1$ is the grounded extension of $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$ (as it is an admissible set of $AF$) trivially implies that it is the grounded extension of $(AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-})_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-} = AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_1^-}$. Hence, $\mathcal{A}rgs_1$ is a strongly admissible set of $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. This implies that $\mathcal{A}rgs_1$ is a subset of the grounded extension of $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$ (Theorem 4). For similar reasons, $\mathcal{A}rgs_2$ is also a subset of the grounded extension of $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. So overall, we obtain that $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ is a subset of the grounded extension of $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$. The fact that the grounded extension of $AF_{|\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2 \cup \mathcal{A}rgs_1^- \cup \mathcal{A}rgs_2^-}$ contains $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ means that every fixpoint
of $F_{AF}|_{\mathcal{A}_{\mathcal{A}_1 \cup \mathcal{A}_2 \cup \mathcal{A}_3} \subseteq \mathcal{A}_2}$ contains $\mathcal{A}_{\mathcal{A}_1} \cup \mathcal{A}_{\mathcal{A}_2}$. Hence, there cannot be a smaller fixpoint of
$F_{AF}|_{\mathcal{A}_{\mathcal{A}_1 \cup \mathcal{A}_2 \cup \mathcal{A}_3} \subseteq \mathcal{A}_2}$ than $\mathcal{A}_{\mathcal{A}_1} \cup \mathcal{A}_{\mathcal{A}_2}$. $\square$

Theorem 5 allows us to infer that $\mathcal{A}_{\mathcal{A}_1} \cup \mathcal{A}_{\mathcal{A}_2}$ is a least upper bound of $\mathcal{A}_{\mathcal{A}_1}$ and $\mathcal{A}_{\mathcal{A}_2}$ as any upper bound of $\mathcal{A}_{\mathcal{A}_1}$ and $\mathcal{A}_{\mathcal{A}_2}$ has to be a superset of $\mathcal{A}_{\mathcal{A}_1} \cup \mathcal{A}_{\mathcal{A}_2}$.

Now that we established that any two strongly admissible sets have a least upper bound, we proceed
to examine whether they also have a greatest upper bound. For this, we need the following lemma.<fnref n="8" />

**Lemma 1.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework and let $ArgS \subseteq Ar$.
$ArgS$ has a unique biggest (w.r.t. $\subseteq$) strongly admissible subset (in the sense of Definition 8).

*Proof.* We first observe that there is always at least one strongly admissible subset of $\mathcal{A}rgs$ (the empty set). We also observe that every increasing sequence $\mathcal{A}rgs_1, \mathcal{A}rgs_2, \mathcal{A}rgs_3, \dots$ of strongly admissible subsets of $\mathcal{A}rgs$ has an upper bound ($\cup_{i=1}^{\infty} \mathcal{A}rgs_i$ which is again strongly admissible; this follows from Theorem 5; also, it is still a subset of $\mathcal{A}rgs$). This allows us to apply Zorn's lemma and obtain that there is at least one maximal strongly admissible subset of $\mathcal{A}rgs$.<fnref n="9" /> We now proceed to show that this maximal strongly admissible subset is unique. Let $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$ be maximal strongly admissible subsets of $\mathcal{A}rgs$. Now consider $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$. From Theorem 5 it follows that this is again a strongly admissible set. From the fact that $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$ are maximal strongly admissible subsets, it follows that if $\mathcal{A}rgs_1 \subseteq \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ then $\mathcal{A}rgs_1 = \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$, and that if $\mathcal{A}rgs_2 \subseteq \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ then $\mathcal{A}rgs_2 = \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$, so we obtain that $\mathcal{A}rgs_1 = \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ and $\mathcal{A}rgs_2 = \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ so $\mathcal{A}rgs_1 = \mathcal{A}rgs_2$. $\square$

We are now ready to introduce one of our main results: the fact that the strongly admissible sets (in
the sense of Definition 8) form a lattice.<fnref n="10" />

**Theorem 6.** Let $AF = (Ar, att)$ be a (possibly non-finitary) argumentation framework. The strongly admissible sets of $AF$ (in the sense of Definition 8) form a lattice (w.r.t. $\subseteq$).

*Proof.* We need to prove that each two strongly admissible sets have a supremum (a least upper bound) and a infimum (a greatest lower bound).

**supremum** Let $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$ be strongly admissible sets. From Theorem 5 it follows that $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ is also a strongly admissible set. Since, by definition, $\mathcal{A}rgs_1 \subseteq \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ and $\mathcal{A}rgs_2 \subseteq \mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$, it follows that $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ is an upper bound. Moreover, it is also a least upper bound, since any proper subset of $\mathcal{A}rgs_1 \cup \mathcal{A}rgs_2$ will not be a superset of $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$.

**infimum** Let $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$ be strongly admissible sets. Let $\mathcal{A}rgs_3$ be $\mathcal{A}rgs_1 \cap \mathcal{A}rgs_2$. $\mathcal{A}rgs_3$ has (unique) biggest strongly admissible subset (Lemma 1) which we will refer to as $\mathcal{A}rgs'_3$. We proceed to show that $\mathcal{A}rgs'_3$ is the infimum of $\mathcal{A}rgs_1$ and $\mathcal{A}rgs_2$.

**lower bound** From the fact that $\mathcal{A}rgs'_3 \subseteq \mathcal{A}rgs_3 = \mathcal{A}rgs_1 \cap \mathcal{A}rgs_2 \subseteq \mathcal{A}rgs_1$ and the fact that $\mathcal{A}rgs'_3 \subseteq \mathcal{A}rgs_3 = \mathcal{A}rgs_1 \cap \mathcal{A}rgs_2 \subseteq \mathcal{A}rgs_2$ it follows that $\mathcal{A}rgs'_3 \subseteq \mathcal{A}rgs_1$ and $\mathcal{A}rgs'_3 \subseteq \mathcal{A}rgs_2$.

**greatest lower bound** Let $\mathcal{A}rgs''_3$ be a strongly admissible set such that $\mathcal{A}rgs''_3 \subseteq \mathcal{A}rgs_1$ and $\mathcal{A}rgs''_3 \subseteq \mathcal{A}rgs_2$. This implies that $\mathcal{A}rgs''_3 \subseteq \mathcal{A}rgs_1 \cap \mathcal{A}rgs_2 = \mathcal{A}rgs_3$. As $\mathcal{A}rgs'_3$ is the biggest strongly admissible subset of $\mathcal{A}rgs_3$, it follows that $\mathcal{A}rgs''_3 \subseteq \mathcal{A}rgs'_3$. $\square$

<footnote n="8">⁸Lemma 1 uses a similar structure as Lemma 2 of [9]. The main difference is that it uses Theorem 5, which is based on Definition 8.</footnote>

<footnote n="9">⁹Although not explicitly mentioned in [10], a similar form of reasoning is needed to prove that maximal admissible sets (i.e. preferred extensions) always exist, even for an infinite argumentation framework with an infinite sequences of ever increasing admissible sets.</footnote>

<footnote n="10">¹⁰Theorem 6 uses a similar structure as Theorem 5 of [4]. The main difference is that it uses Theorem 5 and Lemma 1, which are based on Definition 8.</footnote>
# 5. Discussion

Grounded semantics plays an important role in computational argumentation because it is one of the few mainstream semantics that is computationally tractable<fnref n="11" /> [11].

However, in many cases, the aim is not just to compute whether an argument is accepted, but also to *show* or *explain* why it is accepted. For preferred semantics, there is a well-known concept (that of an admissible set) that can be used to show that an argument is in a preferred extension. For grounded semantics, the concept of a strongly admissible set plays a similar role. Instead of having to construct (and show) the entire grounded extension, it suffices to show that the argument in question is in a strongly admissible set. As such, strong admissibility provides a local property that can be used to explain membership of the grounded extension.<fnref n="12" /> Also, unlike an admissible set, a strongly admissible set can be constructed in polynomial time [6, 7].

Traditionally, an important limitation of strong admissibility was its restricted scope. Whereas the notion of an admissible set was applicable to each argumentation framework (finite or infinite) right from the start [10], the notion of a strongly admissible set was originally only defined for finite argumentation frameworks [2, 4]. The contribution of the current paper is that it breaks with this limitation, making the notion of strong admissibility applicable to all argumentation frameworks.

The road towards the current result can be seen as consisting of three steps. The first step was defining strong admissibility in the context of finite argumentation frameworks [2, 4]. This resulted in Definition 4 [2], Definition 5 [4] and Definition 6 [4]. It was proved that in the context of finite argumentation frameworks, these three definitions are equivalent to each other and satisfy the following properties:

1. each strongly admissible set is an admissible set

2. the empty set is the smallest strongly admissible set (w.r.t. $\subseteq$)

3. the grounded extension is the biggest strongly admissible set (w.r.t. $\subseteq$)

4. the strongly admissible sets form a lattice (w.r.t. $\subseteq$)

The second step was to observe that the scope of Definition 6 can be broadened from finite argumentation frameworks to finitary argumentation frameworks, while still satisfying the above four properties. The third step, as presented in the current paper, was to come up with a new definition of strong admissibility (Definition 8) that satisfies the above four properties for any argumentation framework (finite or infinite). Moreover, we observed that the new definition is backwards compatible with the previous definitions in their respective domains. That is, for finite argumentation frameworks Definition 8 coincides with Definition 4, Definition 5 and Definition 6, and for finitary argumentation frameworks Definition 8 coincides with 6.

## On the Relevance of Infinite Argumentation Frameworks

Infinite argumentation frameworks play an important role in the context of instantiated argumentation, where the argumentation framework is constructed using an underlying knowledge base.<fnref n="13" /> As an example of how such construction works, consider the case of logic programming based argumentation [14, 15, 16]. Let $P_1$ be the following logic program [15].

$$ 
\begin{array}{l@{\quad}l@{\quad}l}
b & \leftarrow & c, \text{not } a & a \leftarrow \text{not } b \\
p & \leftarrow & c, d, \text{not } p & p \leftarrow \text{not } a \\
c & \leftarrow & d & d \leftarrow
\end{array}
 $$

$P_1$ would yield the argumentation framework $AF_{P_1}$ depicted in Figure 4 [15].

The basic idea of argument construction in [14, 15, 16] is that the logic programming rules are used to form what can be described as an “derivation tree”. Each rule in such a derivation tree that contains

<footnote n="11">¹¹together with conflict-free semantics and native semantics</footnote>

<footnote n="12">¹²See [12] for an example of what such an explanation can look like.</footnote>

<footnote n="13">¹³Such instantiated argumentation formalisms can be applied for reasoning under incomplete or uncertain information [13].</footnote>
<figure><img src="image_8.png" /><figcaption>**Figure 4:** $AF_{P_1}$: the argumentation framework built using logic program $P_1$</figcaption></figure>

a strong literal (that is, a literal not preceded by not) in its body has to have a child rule that has this literal in its head. Weak negation is ignored when constructing the arguments and is only used when it comes to defining the attacks. That is, an argument A attacks an argument B iff the conclusion of A (that is, the consequent of its top rule) is contained as a weakly negated literal in the body of one of the rules in B. The intuition behind this is that “not c” means that c is not derivable. So if there actually is a derivation (argument) for c, then this argument attacks everything that contains “not c”.

Although in the example above, a finite logic program $P_1$ generates a finite argumentation framework $AF_{P_1}$, this is not always the case. Consider the following logic program $P_2$.

$$ \begin{array}{lclcl} a & \leftarrow & b & \leftarrow & a \\ a & \leftarrow & b & c & \leftarrow \text{not } b \end{array} $$

Using $P_2$, we can construct an argument for c (consisting of the single rule $c \leftarrow \text{not } b$). We can also construct an infinite number of arguments for b, as there is no limit on how often one can apply the sequence of rules $b \leftarrow a$ and $a \leftarrow b$ in the construction of an argument. This means that the argument for c has an infinite number of attackers, making the argumentation framework non-finitary.<fnref n="14" />

Even when defining a formalism in such a way to prevent the same rule from occurring more than once in a root-originated path of the derivation tree, there are instantiated argumentation formalisms for which this is not sufficient. An example of this would be ASPIC+ [17]. In ASPIC+ there are two types of rules: strict and defeasible. The idea is that strict rules represent inferences that can be made in an underlying classical logic (e.g. propositional logic). In this way, ASPIC+ is able to encapsulate classical logic, in a similar way as for instance Default Logic [18] is able to encapsulate classical logic.<fnref n="15" /> Argument construction is done in a comparable way as we showed above for logic programming, with an argument essentially consisting of a “derivation tree” of strict and defeasible rules.

ASPIC+ can lead to an infinite number of arguments because of the way it encapsulates classical logic. As an example, suppose there is an ASPIC+ argument (say A) of which the conclusion is $p \wedge q$. If we would apply the strict rule $p \wedge q \rightarrow p$ (as the strict rules are based on classical logic, and the fact that $p \wedge q \vdash p$ means there is a strict rule $p \wedge q \rightarrow p$) we obtain another argument that consists of A with the rule $p \wedge q \rightarrow p$ on top of it. The point, however, is that from $p \wedge q$ there is an infinite number of ways to derive q, especially if more than one rule is involved. For instance, instead of extending A with the single rule $p \wedge q \rightarrow p$, one could instead extend A with the pair of rules $p \wedge q \rightarrow p \wedge p$ and $p \wedge p \rightarrow p$, or with the pair of rules $p \wedge q \rightarrow p \wedge p \wedge p$ and $p \wedge p \wedge p \rightarrow p$, etc. As such, there is an infinite

<footnote n="14">¹⁴Although [14, 15, 16] prevent this situation by disallowing using a rule that has already been used further down the argument, other rule-based instantiated argumentation formalisms such as ASPIC+ [17] do not implement such preventive measures and can therefore generate an infinite argumentation framework even from a finite rule base.</footnote>

<footnote n="15">¹⁵As such, it should not come as a surprise that ASPIC+ is able to model (prioritised) default logic [19].</footnote>
number of arguments with conclusion *p*, even without any rules occurring more than once in any of these arguments. Moreover, if there is an argument (say *B*) that contains an assumption of which *p* is the contrary, such an argument will have an infinite number of attackers, making the argumentation framework non-finitary.

One last formalism that we would like to mention is Assumption-Based Argumentation (ABA) [20]. In ABA, a derivation is basically a tree-based structure, comparable to what is done in logic programming based argumentation [14, 15, 16] or ASPIC+ [17]. Arguments, however, abstract from the particular structure of such a derivation. This is done by representing arguments as pairs, written as *Asms* ⊢ *c*, where *Asms* is a set of assumptions such that there exists a derivation that uses these assumptions to infer conclusion *c*. As such, an ABA argument in essence represents an equivalence class of derivations, each of which uses the same assumptions and derives the same conclusion. Even if there is an infinite number of such derivations in the equivalence class, it will generate only one associated ABA argument. This allows ABA to deal with the kind of issues discussed above. However, in spite of this, ABA can still generate an infinite number of arguments when encapsulating classical logic. This is for instance the case because in classical logic a tautology can be inferred without needing any premises or assumptions, which leads to an ABA argument ∅ ⊢ *t* for each tautology *t*. As classical logic supports an infinite number of tautologies, this translates to an infinite number of ABA arguments.

The point we want to make is that the current formalisms for instantiated argumentation tends to generate infinite argumentation frameworks, even when applying a finite knowledge base. In order for any theory of abstract argumentation to be useful for instantiated argumentation, it will need to be applicable for such infinite argumentation frameworks. Theories that are only defined for finite argumentation frameworks are not going to cut it.

## Acknowledgments

This publication is supported in part by the Joint Research and Innovation Seed Grants Program between Cardiff University and the University of Illinois System.

## References

[1] P. Baroni, D. Gabbay, M. Giacomin, L. van der Torre, Handbook of Formal Argumentation, volume 1, College Publications, 2018.

[2] P. Baroni, M. Giacomin, On principle-based evaluation of extension-based argumentation semantics, Artificial Intelligence 171 (2007) 675-700.

[3] M. Caminada, Strong admissibility revisited, in: S. Parsons, N. Oren, C. Reed, F. Cerutti (Eds.), Computational Models of Argument; Proceedings of COMMA 2014, IOS Press, 2014, pp. 197–208.

[4] M. Caminada, P. Dunne, Strong admissibility revisited: theory and applications, Argument & Computation 10 (2019) 277–300.

[5] M. Caminada, Argumentation semantics as formal discussion, in: Handbook of Formal Argumentation, volume 1, College Publications, 2018, pp. 487–518.

[6] M. Caminada, S. Harikrishnan, Tractable algorithms for strong admissibility, Argument & Computation 16 (2025) 212–235.

[7] M. Caminada, S. Harikrishnan, An evaluation of algorithms for strong admissibility, in: Proceedings of SAFA 2024, 2024, pp. 69–82.

[8] S. Modgil, H. Prakken, The aspic+ framework for structured argumentation: a tutorial, Argument & Computation 5 (2014) 31–62. Special Issue: Tutorials on Structured Argumentation.

[9] M. Caminada, Strong admissibility and infinite argumentation frameworks, in: The 18th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty, 2025. In print.

[10] P. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and *n*-person games, Artificial Intelligence 77 (1995) 321–357.
[11] W. Dvořák, P. Dunne, Computational problems in formal argumentation and their complexity, in: Handbook of Formal Argumentation, volume 1, College Publications, 2018, pp. 631–687.

[12] M. Caminada, A discussion game for grounded semantics, in: E. Black, S. Modgil, N. Oren (Eds.), Theory and Applications of Formal Argumentation (proceedings TAFA 2015), Springer, 2015, pp. 59–73.

[13] D. Odekerken, T. Lehtonen, A. Borg, J. Wallner, M. Järvisalo, Argumentative reasoning in aspic+ under incomplete information, in: 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023), 2023, pp. 531–541.

[14] Y. Wu, M. Caminada, D. Gabbay, Complete extensions in argumentation coincide with 3-valued stable models in logic programming, Studia Logica 93 (2009) 383–403. Special issue: new ideas in argumentation theory.

[15] M. Caminada, S. Sá, J. Alcântara, W. Dvořák, On the equivalence between logic programming semantics and argumentation semantics, International Journal of Approximate Reasoning 58 (2015) 87–111.

[16] M. Caminada, S. Harikrishnan, S. Sá, Comparing logic programming and formal argumentation; the case of ideal and eager semantics, Argument & Computation 13 (2022) 91–120.

[17] S. Modgil, H. Prakken, Abstract rule-based argumentation, in: Handbook of Formal Argumentation, volume 1, College Publications, 2018, pp. 287–364.

[18] R. Reiter, A logic for default reasoning, Artificial Intelligence 13 (1980) 81–132.

[19] A. Young, S. Modgil, O. Rodrigues, Prioritised default logic as rational argumentation, in: Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), 2016, pp. 626–634.

[20] K. Čyras, X. Fan, C. Schulz, F. Toni, Assumption-based argumentation: Disputes, explanations, preferences, in: Handbook of Formal Argumentation, volume 1, College Publications, 2018, pp. 365–408.
# Uncertainty in Quantitative Bipolar Argumentation Frameworks*

Jordan Thieyre<fnref n="1" />*, Caren Al Anaissy<fnref n="1" />, Aurélie Beynier<fnref n="1" />, Sébastien Destercke<fnref n="2" />, Nicolas Maudet<fnref n="1" /> and Srdjan Vesic<fnref n="3" />

**Abstract**

Online deliberation platforms allow people to exchange their opinions around a specified issue and to vote on these opinions in order to reach a collective decision. Argumentation allows to structure and analyse user input for these platforms. A debate can be represented by a quantitative bipolar argumentation framework where votes on each argument of the debate are aggregated into an initial weight. One of the main challenges these platforms face is *sparse voting* i.e. participants vote on a few number of arguments, leading to an imbalance of the number of votes between the arguments. In this paper, we propose a methodology that handles *sparse voting* in online debates, by introducing imprecise quantitative bipolar argumentation frameworks that incorporate uncertainty on the initial weights. Specifically, we leverage votes on arguments to initialize weight intervals that represent the uncertainty on the initial weights, using the imprecise Dirichlet model. We use four state-of-the-art bipolar gradual semantics to generate a final acceptability interval on each argument and we introduce several properties to study the effect of these semantics on the uncertainty on each argument’s final evaluation. Our methodology allows for a more robust representation of argument strength in the presence of limited data.

**Keywords**

Quantitative bipolar argumentation frameworks, Bipolar gradual semantics, Uncertainty, Imprecise Dirichlet model, Online debate platforms

# 1. Introduction

Deliberation can be useful for reaching well-balanced and thoughtful collective decisions. Online debate platforms, such that Idebate's debatabase<fnref n="1" />, Kialo<fnref n="2" /> and Debategraph<fnref n="3" />, facilitate the deliberation process by allowing for users to argue for and against an issue by exchanging "PRO" and "CON" arguments respectively. Some of them also offer simple mechanisms for the users to vote on the relevance of the arguments.

With the rise of these tools in digital democratic practices, it is becoming crucial to understand how to evaluate arguments on a large scale, taking into account their interactions and, where available, the votes of participants. As it is generally unrealistic to read all the contributions to a debate, it makes sense to use automated methods of analysis.

Computational argumentation provides a formal framework for dealing with conflicting, incomplete or uncertain information. It models debates in the form of graphs of arguments linked by attack and support relations, and uses semantics to evaluate the strength of each argument according to these relations. These semantics abstract the content of the arguments, thus reducing potential biases in the evaluation.

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

<footnote n="1">¹LIP6, CNRS - Sorbonne Université, Paris, France</footnote>

<footnote n="2">²Université de technologie de Compiègne, CNRS, Heudiasyc, Compiègne, France</footnote>

<footnote n="3">³CRIL, CNRS - Univ. Artois, Lens, France</footnote>

<footnote>ArgU'25: First European Workshop on Argumentation and Uncertainty, September 23, 2025, Hagen, Germany</footnote>

<footnote>* The paper was accepted in ECAI 2025 main track.</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>jordan.thieyre@lip6.fr (J. Thieyre)</footnote>

<footnote>0009-0006-8975-8169 (J. Thieyre); 0000-0002-8750-1849 (C. A. Anaissy); 0000-0002-3812-6755 (A. Beynier); 0000-0003-2026-468X (S. Destercke); 0000-0002-4232-069X (N. Maudet); 0000-0002-4382-0928 (S. Vesic)</footnote>

<footnote>© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).</footnote>

<footnote n="1">¹https://idebate.net/resources/dedatabase</footnote>

<footnote n="2">²https://www.kialo.com/</footnote>

<footnote n="3">³http://debategraph.org</footnote>
Among the many frameworks available, *Quantitative Bipolar Argumentation Frameworks* (QBAFs) are particularly well suited to online debates. They incorporate both attack and support relationships between arguments and initial weights, often derived from votes. The *bipolar gradual semantics* [1, 2, 3, 4] are then used to calculate a final degree of acceptability for each argument.

**Research problem.** A major challenge in online debates is the *sparse voting*: most users vote on only a small proportion of arguments citegoldberg2024aifuturedigitalpublic. This phenomenon limits the reliability of evaluations based on votes alone. Rather than attempting to predict missing votes or further solicit users, a prudent approach is to recognise this uncertainty and ensure that it is properly accounted for in the results displayed.

**Our approach.** We generalise the quantitative bipolar argumentation framework in order to take into account uncertainty about the initial weights of arguments. To do this, each argument is associated with an interval of possible weights, reflecting the variability and rarity of the votes cast. These intervals are initialized from the observed votes using the imprecise Dirichlet model, which quantifies the uncertainty while avoiding premature inferences.

Our contributions are as follows:

* Introduction of the imprecise quantitative bipolar argumentation framework (IQBAF) to model initial weights as intervals;

* Use of the imprecise Dirichlet model to estimate these weights from partially observed voting data;

* Proposal of a method for applying a family of bipolar gradual semantics to these IQBAFs;

* Experimental validation on a real corpus from the Kialo platform.

## 2. Imprecise Quantitative Bipolar Argumentation Frameworks

When an argument has limited information—particularly in the case of sparse voting—it becomes difficult to assign it a precise initial weight that reflects users’ opinions. To address this, we draw inspiration from the theory of imprecise probabilities and propose a framework in which the initial weight of an argument is no longer represented by a single value, but by an *interval of possible values*. The lower (resp. upper) bound indicates the minimum (resp. maximum) value this weight can take. This formalism leads to the definition of *Imprecise Quantitative Bipolar Argumentation Frameworks* (IQBAFs) as follows:

**Definition 1.** Let $\mathcal{I}_{[0;1]}$ be the set of intervals included in or equal to $[0; 1]$. An *Imprecise Quantitative Bipolar Argumentation Framework* (IQBAF) is a quadruple $(\mathcal{A}, \mathcal{R}^{-}, \mathcal{R}^{+}, i^{i})$ where:

* $\mathcal{A}$ is a finite set of arguments,

* $\mathcal{R}^{-} \subseteq \mathcal{A} \times \mathcal{A}$ represents an acyclic binary attack relation,

* $\mathcal{R}^{+} \subseteq \mathcal{A} \times \mathcal{A}$ represents an acyclic binary support relation,

* $i^{i}: \mathcal{A} \to \mathcal{I}_{[0;1]}$ maps each argument $a$ to an interval of initial weights $i^{i}(a) = [\underline{i}^{i}(a), \overline{i}^{i}(a)]$.

## 3. Computing final acceptability intervals

Rather than introducing a new dedicated gradual bipolar semantics for IQBAFs, we propose a method to adapt existing semantics in order to compute the final acceptability intervals $i^f$. For each argument $a$, $i^f(a) = [\underline{i^f}(a), \overline{i^f}(a)]$ is defined based on the bounds of its attackers and supporters:

$$ \underline{i^f}(a) = \min_{\substack{x \in i^i(a) \\ Y \in \{y \in i^f(b) | b \in \mathcal{R}^{-}(a)\} \\ Z \in \{z \in i^f(c) | c \in \mathcal{R}^{+}(a)\}}} s^f(x, Y, Z) $$
and

$$ \bar{i^f}(a) = \max_{\substack{x \in i^i(a) \\ Y \in \{y \in i^f(b) | b \in \mathcal{R}^-(a)\} \\ Z \in \{z \in i^f(c) | c \in \mathcal{R}^+(a)\}}} s^f(x, Y, Z) $$

We show that if the semantics satisfies a set of mild properties, then the bounds of $i^f(a)$ can be obtained by combining: the minimal (resp. maximal) initial weight, the final acceptability degree of the maximal (resp. minimal) attackers, and those of the minimal (resp. maximal) supporters. The final acceptability interval of an argument a can then be computed directly from the lower and upper bounds of its attackers and supporters as follows:

$$ \underline{i^f}(a) = \sigma(\underline{i^i}(a), \{\bar{i^f}(b) | b \in \mathcal{R}^-(a)\}, \{\underline{i^f}(c) | c \in \mathcal{R}^+(a)\}) $$

and

$$ \bar{i^f}(a) = \sigma(\bar{i^i}(a), \{\underline{i^f}(b) | b \in \mathcal{R}^-(a)\}, \{\bar{i^f}(c) | c \in \mathcal{R}^+(a)\}) $$

We also show that adding information (particularly in the form of new votes) does not necessarily reduce the uncertainty intervals. We therefore conducted an experiment on a dataset of nearly 3000 debates from the Kialo platform.

# 4. Properties

We investigate properties of IQBAFs. We examine how uncertainty propagates through such frameworks when using various gradual bipolar semantics. First, we introduce the notion of Full Ignorance (FI), ensuring that final acceptability interval [0; 1] can only be reached when initial weight intervals equal [0; 1]. We show that semantics such as QuAD and DF-QuAD satisfy only a weak version of this property, while Exb and QuEM satisfy a stronger form due to their resilience to saturation.

We then define and analyze principles of Uncertainty Reduction, distinguishing between three variants: via semantics computation (UR-SC), via general information gain (UR-IG), and via coherent information gain (UR-CIG). While none of the studied semantics satisfy UR-SC or UR-IG, all satisfy UR-CIG, meaning that more precise and consistent input data reduces the uncertainty in final acceptability intervals. These results underline the non-trivial effects of information gain in uncertainty-aware argumentation.

# 5. Experimental results

For each argument, we applied the *IDM* method to estimate an interval of initial weights from the votes, then used the *QuEM* semantics to compute the final interval. Only a few debates show a clear reduction in uncertainty, often linked to a sufficient number of votes or to a structure dominated by one type of relation (attack or support). Regarding acceptability, a global bias is observed toward lower final acceptance of theses. Some debates show a marked shift, where the final interval does not overlap with the initial one. In general, although the central thesis gathers many votes, taking into account the “PRO” and “CON” arguments broadens the range of possible conclusions.

# Acknowledgments

This work has been supported by ANR (french National Research Agency) project AGGREEY (ANR-22-CE23-0005), and by a French government grant managed by the Agence Nationale de la Recherche as part of the France 2030 program, reference ANR-22-EXEN-0004 (PEPR eNSEMBLE / PC3 MATCHING).

# Declaration on Generative AI

The author(s) have not employed any Generative AI tools.
References

[1] P. Baroni, M. Romano, F. Toni, M. Aurisicchio, G. Bertanza, Automatic evaluation of design alternatives with quantitative argumentation, Argument & Computation 6 (2015) 24–49.

[2] A. Rago, F. Toni, M. Aurisicchio, P. Baroni, et al., Discontinuity-free decision support with quantitative argumentation debates., Fifteenth International Conference on Principles of Knowledge Representation and Reasoning 16 (2016) 63–73.

[3] L. Amgoud, J. Ben-Naim, Evaluation of arguments in weighted bipolar graphs, International Journal of Approximate Reasoning 99 (2018) 39–55.

[4] N. Potyka, Continuous Dynamical Systems for Weighted Bipolar Argumentation, in: Proceedings of the Sixteenth International Conference, KR 2018, Tempe, Arizona, 2018.
# On Uncertainty in Collective Attacks in Abstract Argumentation

Dominik Lewin¹,†, Kenneth Skiba¹,†

¹Artificial Intelligence Group, University in Hagen, Germany

**Abstract**

We introduce *incomplete argumentation frameworks with set attacks* (ISETAFs), a novel generalisation of abstract argumentation frameworks that integrates set-based attacks and incomplete information. This unified model subsumes both *argumentation frameworks with set attacks* (SETAFs) and *incomplete argumentation frameworks* (IAFs) and is designed to better capture uncertainty in real-world argumentative reasoning. We explore two complementary approaches: a completion-based semantics that evaluates all possible completions, and an extension-based semantics that defines new acceptance conditions directly over ISETAFs. We show that key reasoning problems for ISETAFs are no harder than for IAFs, and we analyse which desirable properties (e.g., I-maximality, conflict-sensitivity, directionality) are preserved. Our results demonstrate that ISETAFs maintain the expressiveness and semantic rigour of existing frameworks, while significantly enhancing their modelling capabilities.

**Keywords**

Abstract Argumentation Frameworks, Incomplete Argumentation Frameworks, Set Argumentation Frameworks

## 1. Introduction

*Formal argumentation* [1] is concerned with models of rational decision-making based on representations of arguments and their relations. A particularly important and simple approach is that of abstract argumentation frameworks (AF) [2], which represent argumentative scenarios as directed graphs. Here, *arguments* are identified by vertices, and an *attack* from one argument to another is represented as a directed edge. To reason over AFs *extension semantics* were proposed. These are functions that evaluate whether a set of arguments is accepted or not.

Due to the limited expressivity of abstract argumentation frameworks a number of extensions were proposed. One such extension are *incomplete argumentation frameworks* (IAFs) [3], which can model qualitative uncertainty about the existence of arguments and attacks. Such uncertainty can emerge if there is a disagreement between two agents about the validity of one argument. Another extension are *argumentation frameworks with set attacks* (SETAFs) [4], where an attack is not a binary relation between two arguments, but rather a set of arguments attacks an argument. With this attack notion collective attacks can be modelled, for example the statements “John has hay fever” and “It is hay fever season” are individually not a reason against going on a hike, however together these two statements are a reason against going on a hike.

Both IAFs and SETAFs have higher expressivity than AFs, however these two formalisms cannot model each other. An IAF cannot handle collective attacks and a SETAF cannot cope with uncertainty. In this paper, we combine these two formalisms into *incomplete argumentation frameworks with set attacks* (ISETAFs) to define a more expressive extension of AFs, which can handle both uncertainty and collective attacks. More precisely, the main contributions of this paper are as follows:

* We present *incomplete argumentation frameworks with set attacks* as an extension of abstract argumentation frameworks.

* We discuss two approaches to reason with ISETAFs.

ArgU'25: First European Workshop on Argumentation and Uncertainty, September 23, 2025, Hagen, Germany

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

kenneth.skiba@fernuni-hagen.de (K. Skiba)

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

© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).

<footnote>†These authors contributed equally.</footnote>
<figure><img src="image_12.png" /><figcaption>**Figure 1:** Abstract argumentation framework $F_1$ from Example 1.</figcaption></figure>

• We evaluate properties for ISEΤΑFs by modifying properties for AFs.

• We analyse the computational complexity of reasoning with ISEΤΑFs.

In Section 2, we recall all necessary background information on abstract argumentation frameworks, incomplete argumentation frameworks, and argumentation frameworks with set attacks. In Section 3, we introduce incomplete argumentation frameworks with set attacks as an extension of AFs. In addition, we discuss two reasoning approaches for this new framework. Properties of extension semantics of ISEΤΑFs are discussed in Section 4. The computational complexity of the corresponding acceptance problems are analysed in Section 5. Section 6 concludes this paper.

Due to space limitations, some proofs can be found in the appendix <fnref n="1" />.

## 2. Preliminaries

*Abstract argumentation frameworks* [2] are a formalism that allows the representation of conflicts between pieces of information using arguments and attacks between arguments.

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

For an AF $F = (A, R)$, an argument *a* is said to *attack* an argument *b* if $(a, b) \in R$. We say that, a set $E \subseteq A$ *defends* an argument *a* if every argument *b* $\in A$ that attacks *a* is attacked by some $c \in E$. For $a \in A$, we define $a_F^- = \{b \mid (b, a) \in R\}$ and $a_F^+ = \{b \mid (a, b) \in R\}$. In other words, $a_F^-$ is the set of attackers of *a* and $a_F^+$ is the set of arguments attacked by *a*. For a set of arguments $E \subseteq A$, we extend these definitions to $E_F^+$ and $E_F^-$ via $E_F^+ = \cup_{a \in E} a_F^+$ and $E_F^- = \cup_{a \in E} a_F^-$, respectively. If the AF is clear in the context, we omit the index. To reason with AFs, Dung [2] proposed *extension semantics*.

**Definition 2.** Given $F = (A, R)$, a set $E \subseteq A$ is a

• conflict-free (cf) set iff $\forall a, b \in E, (a, b) \notin R$;

• admissible (ad) set iff it is conflict-free and it defends its elements;

• complete extension (co) iff it contains every argument it defends;

• preferred extension (pr) iff it is a $\subseteq$-maximal admissible set;

• grounded extension (gr) iff it is the $\subseteq$-minimal complete extension;

• stable extension (st) iff E is conflict-free and $E \cup E_F^+ = A$.

We use cf(*F*) and ad(*F*) to denote the sets of conflict-free and admissible sets of an argumentation framework *F*, respectively, and co(*F*), pr(*F*), gr(*F*), and st(*F*) to denote the complete, preferred, grounded and stable extensions of *F*.

**Example 1.** Consider the AF $F_1 = (\{a, b, c\}, \{(a, c), (b, c)\})$ depicted as a directed graph in Figure 1. $F_1$ has four admissible sets $E_1 = \{a\}$, $E_2 = \{b\}$, $E_3 = \{a, b\}$, and $E_4 = \emptyset$. Since arguments *a* and *b* are unattacked, only set $E_3$ is the complete, preferred, grounded, and stable extension.

An argument *a* is *credulously accepted* in *F* with respect to the extension semantics $\sigma$ if there exists a set $a \in E$ such that $E \in \sigma(F)$, argument *a* is *skeptically accepted* if $a \in E$ for all $E \in \sigma(F)$.

Incomplete argumentation frameworks [5, 3, 6, 7] are an extension of AFs with qualitative uncertainty about the presence of arguments and attacks.

<footnote n="1">¹https://fernuni-hagen.sciebo.de/s/n3wsYP9yIpuUPVa</footnote>
<figure><img src="image_13.png" /><figcaption>**Figure 2:** IAF $\mathcal{I}_1$ from Example 2.</figcaption></figure>

**Definition 3.** An incomplete argumentation framework (IAF) is a tuple $\mathcal{I} = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$, where $\mathcal{A} \cap \mathcal{A}^? = \emptyset$ and $\mathcal{R}, \mathcal{R}^?$ the sets of attacks with $\mathcal{R}, \mathcal{R}^?$ $\subseteq (\mathcal{A} \cup \mathcal{A}^?) \times (\mathcal{A} \cup \mathcal{A}^?)$.

Elements from $\mathcal{A}$ and $\mathcal{R}$ are certain arguments and attacks (i.e. the agent is sure that they appear in the framework), while $\mathcal{A}^?$ and $\mathcal{R}^?$ are uncertain arguments and attacks (i.e. there is a doubt about their actual existence). To reason on IAFs we use completions. These were first defined for Partial AFs (i.e. IAFs with $\mathcal{A}^? = \emptyset$, see [5]) and then adapted to IAFs. Intuitively, a completion is a possible world consistent with the uncertainty encoded in the IAF.

**Definition 4.** Given $\mathcal{I} = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$, a completion of $\mathcal{I}$ is an AF $F = (A', R')$, such that:

$$ \mathcal{A} \subseteq A' \subseteq \mathcal{A} \cup \mathcal{A}^?; $$

$$ \mathcal{R} \cap (A' \times A') \subseteq R' \subseteq (\mathcal{R} \cup \mathcal{R}^?) \cap (A' \times A'); $$

The set of completions of an IAF $\mathcal{I}$ is denoted with $\text{comp}(\mathcal{I}, a) = \{F = (A', R') | F \in \text{comp}(\mathcal{I}) \text{ and } a \in A'\}$ the sets of completions where argument $a$ is present, with $a \in \mathcal{A} \cup \mathcal{A}^?$. Naturally, if $a \in \mathcal{A}$ then $\text{comp}(\mathcal{I}, a) = \text{comp}(\mathcal{I})$.

With these completions, we extend the reasoning process of AFs to IAFs. For an IAF $\mathcal{I}$, an certain or uncertain argument $a$ is possibly credulously accepted with respect to an extension semantics $\sigma$ in $\mathcal{I}$ if there is at least one completion $F \in \text{comp}(\mathcal{I})$ such that $a$ is credulously accepted with respect to $\sigma$. Argument $a$ is necessarily credulously accepted with respect to $\sigma$ in $\mathcal{I}$ if $a$ is credulously accepted with respect to $\sigma$ in every completion of $\mathcal{I}$. Possible skeptical acceptance and necessary skeptical acceptance are defined accordingly.

**Example 2.** Consider the IAF $\mathcal{I}_1 = (\{a, c\}, \{b\}, \{(b, c)\}, \{(a, c)\})$ depicted as a directed graph in Figure 2. The attack from $a$ to $c$ is uncertain and argument $b$ is uncertain. This IAF has four completions, one containing $b$ and $(a, c)$, one containing only $b$ and not $(a, c)$, one containing $(a, c)$ and not $b$, and one containing neither $b$ nor $(a, c)$. In each of these completions, we check whether an argument is accepted or not according to an extension semantics. For example, argument $a$ is necessary skeptically accepted w.r.t. preferred semantics, while arguments $b$ and $c$ are possible skeptically accepted w.r.t. preferred semantics.

A second approach to reasoning on IAFs is an extension-based approach. Given an IAF, sets of arguments can be evaluated from two perspectives: optimistic (weak, $w$) and pessimistic (strong, $s$), depending on the treatment of uncertainty.

**Definition 5.** Let $\mathcal{I} = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an IAF, $E \subseteq \mathcal{A} \cup \mathcal{A}^?$ and $x \in \{w, s\}$. A set $E$ $x$-defends an argument $a \in \mathcal{A} \cup \mathcal{A}^?$ if

* for $x = w$: for every $b \in \mathcal{A}$ with $(b, a) \in \mathcal{R}$, there exists $c \in E \cap \mathcal{A}$ with $(c, b) \in \mathcal{R}$;

* for $x = s$: for every $b \in \mathcal{A} \cup \mathcal{A}^?$ with $(b, a) \in \mathcal{R} \cup \mathcal{R}^?$, there exists $c \in E \cap \mathcal{A}$ with $(c, b) \in \mathcal{R}$.

The semantics are defined as follows:

**Definition 6 ([8, 9]).** Let $\mathcal{I} = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an IAF, $E \subseteq \mathcal{A} \cup \mathcal{A}^?$, and $x \in \{w, s\}$. Then:

* $E$ is $x$-conflict-free (cf$_x$) if

- for $x = w$: for all $a, b \in E \cap \mathcal{A}$, $(a, b) \notin \mathcal{R}$,

- for $x = s$: for all $a, b \in E$, $(a, b) \notin \mathcal{R} \cup \mathcal{R}^?.$
<figure><img src="image_14.png" /><figcaption>**Figure 3:** SETAF S₁ from Example 4.</figcaption></figure>

* E is x-admissible (adₓ) iff E is x-conflict-free and x-defends all a ∈ E.

* E is x-complete (coₓ) iff E is x-admissible and contains all arguments it x-defends.

* E is x-preferred (prₓ) iff E is a $\subseteq$-maximal x-complete set.

* E is x-grounded (grₓ) iff E is the $\subseteq$-minimal x-complete set.

* E is x-stable (stₓ) iff E is x-conflict-free and, for all a ∈ Aₓ \ E, a is certainly attacked by E, where $A_w = A$ and $A_s = A \cup A^?$.

This extension-based approach enables direct evaluation of argument acceptability in IAFs via generalised semantics, allowing for fine-grained reasoning under uncertainty by distinguishing between optimistic and pessimistic interpretations.

**Example 3.** Consider again $\mathcal{I}_1$ from Example 2. Since the attack from a to c is uncertain, the set $\{a, c\}$ is w-admissible. The set $\{a, b\}$ is s-complete, s-preferred, and s-grounded.

Another extension of abstract argumentation frameworks are *argumentation frameworks with set attacks* by Nielsen and Parsons [4], where a set of arguments collectively attack an argument.

**Definition 7.** An argumentation framework with set attacks (SETAF) is a tuple $S = (\mathbf{A}, \mathbf{R})$, where $\mathbf{A}$ is a finite set of arguments and $\mathbf{R} \subseteq (2^\mathbf{A} \setminus \emptyset) \times \mathbf{A}$.

For a SETAF $S = (\mathbf{A}, \mathbf{R})$, a set of arguments $E \subseteq \mathbf{A}$ attacks argument $a \in \mathbf{A}$ if and only if $(E, a) \in \mathbf{R}$. A set of arguments $E$ defends an argument $a$ if for every $G \subseteq \mathbf{A}$ such that $(G, a) \in \mathbf{R}$ there is an set $E' \subseteq E$ with $(E', b) \in \mathbf{R}$ where $b \in G$. With these attack and defence notions, we can define the extension semantics for SETAF similar to Definition 2.

**Example 4.** Consider the SETAF S₁ depicted as a directed hypergraph in Figure 3. Arguments a and b collectively attack argument c. Thus, the set $\{a, b, c\}$ is not conflict-free, however the two subsets $\{a, c\}$ and $\{b, c\}$ are conflict-free. The set $\{a, b\}$ is the only complete, preferred, grounded, and stable set in S₁.

### 3. Incomplete Set Argumentation Framework

Incomplete argumentation frameworks and argumentation frameworks with set attacks both extend the expressivity of argumentation frameworks. Although they extend an AF differently, IAFs can handle uncertainty and SETAFs can handle collective attacks, but they cannot handle the extension of the other. However, an uncertain collective attack is imaginable.

**Example 5.** A group of friends want to go on a hike, however John has hay fever, so he has to track the amount of pollen in the air. If there is too much pollen he cannot go hiking.

If we try to model this scenario with an argumentation framework, we get three arguments “John goes hiking”, “John has hay fever”, and “the pollen concentration is high”. The statements “John has hay fever” and “the pollen concentration is high” only attack “John goes hiking” together, since individually the two statements are no reason against going hiking. We could model this with a SETAF, however, if we consider that we cannot be sure whether the pollen concentration is high or not, we are unsure about the existence of the argument “the pollen concentration is high”. This uncertainty cannot be modelled with a SETAF. However, an IAF can model this uncertainty, but it cannot model the collective attack.
<figure><img src="image_15.png" /><figcaption>Figure 4: ISETAF $U_1$ from Example 6.</figcaption></figure>

Example 5 motivates the use of a combination of IAFs and SETAFs to handle uncertain collective attacks. Next, we define *incomplete argumentation frameworks with set attacks* as an extension of IAFs and SETAFs and present the corresponding attack notion.

**Definition 8.** An incomplete argumentation framework with set attacks (ISETAF) is a tuple $U = (A, A^?, R, R^?)$ where $A$ are the certain arguments, $A^?$ uncertain arguments and $R, R^?$ the sets of collective attacks with $A \cap A^? = \emptyset$ and $R, R^? \subseteq (2^{A \cup A^?} \setminus \emptyset) \times (A \cup A^?)$.

For an ISETAF $U = (A, A^?, R, R^?)$, a set of arguments $E \subseteq A \cup A^?$ attacks an argument $a \in A \cup A^?$ if $(E, a) \in R \cup R^?$. An attack $(E, a)$ can consist out of multiple uncertainty. One or multiple arguments of $E$ can be uncertain, the attack relation can be uncertain, or any combination of these two situation can occur. We call an attack $(E, a)$ with $E \subseteq A \cup A^?$ and $a \in A \cup A^?$ conditionally certain if $(E, a) \in R$ and certain if $(E, a) \in R$ and $E \subseteq A$. An attack $(E, a)$ is uncertain if $(E, a) \in R^?$ for $E \subseteq A \cup A^?$ and $a \in A \cup A^?$.

**Example 6.** Continuing Example 5, we can model our scenario with an ISETAF as follows:

$$U_1 = (\{h, f\}, \{p\}, \{(f, p), h\}, \emptyset)$$

The corresponding hypergraph is depicted in Figure 4, where:

* $h$ represents: John goes hiking

* $f$ represents: John has hay fever

* $p$ represents: the pollen concentration is high

The arguments $h$ and $f$ are certain arguments and $p$ is uncertain. The set $\{p, f\}$ are collectively attacking argument $h$, this attack $(\{f, p\}, h)$ is a conditionally certain attack, meaning that if argument $p$ exists the attack $(\{f, p\}, h)$ exists as well. If argument $p$ does not exists, then the attack $(\{f, p\}, h)$ has to be removed as well.

In the remainder of this section, we discuss two reasoning approaches, completion-based and extension-based, for ISETAFs.

### 3.1. Completion-based Approach

Similar to incomplete argumentation frameworks, uncertainty in an ISETAF can be resolved with an *completion-based approach*. Each uncertain element is either included in or excluded from the completion, resulting in a SETAF.

**Definition 9.** Let $U = (A, A^?, R, R^?)$ be an ISETAF, a completion of $U$ is a SETAF $S = (A^*, R^*)$, s.t.:

$$A \subseteq A^* \subseteq (A \cup A^?)$$

$$R \cap (2^{A^*} \times A^*) \subseteq R^* \subseteq (R \cup R^?) \cap (2^{A^*} \times A^*)$$

The set of completions of an ISETAF $U$ is denoted with $comp_{ISETAF}(U)$. Using the completions of an ISETAF, we extend the acceptability question to ISETAFs.

**Definition 10.** Let $U = (A, A^?, R, R^?)$ be an ISETAF, $a \in A \cup A^?$ and $\sigma$ an extension semantics.
• *a* is possibly credulously accepted with respect to σ in U if there is at least one completion of S ∈ comp<sub>ISETAF</sub>(U) such that *a* is credulously accepted with respect to σ in S.

• *a* is necessarily credulously accepted with respect to σ in U if *a* is credulously accepted with respect to σ in every completion of U.

• *a* is possible skeptically accepted with respect to σ in U if there is at least one completion of S ∈ comp<sub>ISETAF</sub>(U) such that *a* is skeptically accepted with respect to σ in S.

• *a* is necessary skeptically accepted with respect to σ in U if *a* is skeptically accepted with respect to σ in every completion of U.

The acceptance problems give us insight into the behaviour of the ISETAF. If an argument *a* is possibly credulously accepted, then there is one interpretation, where *a* can be accepted. If an argument *a* is necessary skeptically accepted, then *a* is always accepted and its acceptance cannot change.

**Example 7.** Continuing with Example 6, this ISETAF has two completions, one with *p* and one without *p*. We call the completion with *p* U<sub>1,p</sub> and the one without *p* U<sub>1,¯p</sub>. The set {f, h} is conflict-free in U<sub>1,p</sub>, while it is not conflict-free in U<sub>1,¯p</sub>. Thus, *h* is possibly credulously accepted with respect to admissibility in U<sub>1</sub>. Argument *f* is necessary skeptically accepted with respect to complete semantics in U<sub>1</sub>.

To construct a completion for an ISETAF, we have a number of options for a single collective attack. If the attack is certain, then we get a single completion, however if the attack is conditionally certain then we have multiple options. For any uncertain argument that is part of the attack, we can decide to either include it in the completion or leave it out. For uncertain attacks, an additional decision has to be done, to include the collective attack or not, thus the number of completions of an ISETAF scales exponentially to the number of uncertain arguments.

**Proposition 1.** Consider ISETAF U = (A, A?, R, R?) and r' ∈ R ∪ R? such that r' = (E, a) with E ⊆ A ∪ A? and a ∈ A. Let m = |E ∩ A?| be the number of uncertain arguments of E and p ∈ {0, 1} such that:

$$p := \begin{cases} 0 & \text{if } r' \in R \\ 1 & \text{if } r' \in R^? \end{cases}$$

Then the number of completions with respect to r' is 2^m + p.

*Proof.* We prove the proposition by complete induction. Consider a single collective attack of an ISETAF. Let *m* denote the number of uncertain arguments involved, and let *p* ∈ {0, 1} indicate whether the attack itself is uncertain (*p* = 1) or certain (*p* = 0). We show that the number of completions is *n* = 2^m + *p*.

• **Base case** (*m* = 0): If no uncertain arguments are involved, the number of completions depends only on whether the attack is certain or uncertain.

– If the attack is certain (*p* = 0): *n* = 2<sup>0</sup> + 0 = 1.

– If the attack is uncertain (*p* = 1): *n* = 2<sup>0</sup> + 1 = 2.

Thus, the base case holds.

• **Induction hypothesis:** Assume the formula holds for *k* uncertain arguments, i.e., *n* = 2<sup>*k*</sup> + *p*.

• **Induction step:** Consider *m* = *k* + 1, i.e., one additional uncertain argument.

– If *p* = 0: Adding another uncertain argument doubles the number of completions, as each previous completion can either include or exclude the new uncertain argument. Thus, *n* = 2 · 2<sup>*k*</sup> = 2<sup>*k*+1</sup>.

– If *p* = 1: For *k* uncertain arguments, we have 2<sup>*k*</sup> + 1 completions. Adding one more uncertain argument doubles the completions not including the attack and leaves the single completion with the attack, so *n* = 2 · 2<sup>*k*</sup> + 1 = 2<sup>*k*+1</sup> + 1.

In both cases, the formula *n* = 2<sup>*m*</sup> + *p* holds for *m* = *k* + 1. □

The total number of completions for an ISETAF can be determined by multiplying the number of completions for each attack, provided that all collective attacks are independent, i.e., no argument occurs in more than one collective attack. Thus, the number of completions of an ISETAF grow exponentially.
## 3.2. Extension-based Approach

To avoid the exponential amount of completions for an IAF, Mailly proposed an extension-based approach to reason with IAFs [8, 9, 10]. To handle uncertainty there are two point of views, optimistic and pessimistic. In the optimistic view uncertain arguments and attacks are considered not harmful, thus conflicts originating from uncertain attacks are tolerated. In the pessimistic view all attacks are harmful. We adapt these two view points for ISETFAs.

**Definition 11.** Let $U = (A, A^?, R, R^?)$ be an ISETF and $E \subseteq A \cup A^?$. The set $E$ is:

* weakly conflict-free *iff there is no attack* $(E', a) \in R$ *with* $E' \subseteq E \cap A$ *and* $a \in E$.

* strongly conflict-free *iff there is no attack* $(E', a) \in R \cup R^?$ *with* $E' \subseteq E \cap (A \cup A^?)$ *and* $a \in E$.

With $cf_w(U)$ and $cf_s(U)$ we denote the sets of weakly respectively strongly conflict-free sets of an ISETF $U$. The second fundamental concept of formal argumentation is *defence*.

**Definition 12.** Let $U = (A, A^?, R, R^?)$ be an ISETF, $E \subseteq A \cup A^?$ and $a \in A \cup A^?$. The set $E$:

* weakly defends $a$ *iff for every certain collective attack* $(E', a) \in R$ *with* $E' \subseteq A$, *there exists a nonempty subset* $G \subseteq E \cap A$ *such that* $(G, b) \in R$ *for at least one* $b \in E'$.

* strongly defends $a$ *iff for every collective attack* $(E', a) \in R \cup R^?$ *with* $E' \subseteq A \cup A^?$, *there exists a nonempty subset* $G \subseteq E \cap A$ *such that* $(G, b) \in R$ *for at least one* $b \in E'$.

Next, we combine both conflict-freeness and defence to extension semantics for ISETFAs similar to Definition 2. For every extension semantics, we get two variations, a *weak* and a *strong* one.

**Definition 13.** Let $U = (A, A^?, R, R^?)$ be an ISETF, $E \subseteq A \cup A^?$ and $x \in \{w, s\}$. Then:

* $E$ is $x$-admissible ($\mathrm{ad}_x$) *iff* $E$ is $cf_x$ and $E$ $x$-defends all its elements;

* $E$ is $x$-complete ($\mathrm{co}_x$) *iff* $E$ is $\mathrm{ad}_x$ and every $a \in A \cup A^?$ $x$-defended by $E$ is in $E$;

* $E$ is $x$-preferred ($\mathrm{pr}_x$) *iff* $E$ is a $\subseteq$-maximal $x$-complete set;

* $E$ is $x$-grounded ($\mathrm{gr}_x$) *iff* $E$ is the $\subseteq$-minimal $x$-complete set;

* $E$ is $x$-stable ($\mathrm{st}_x$) *iff* $E$ is $cf_x$ and for all $a \in A_x \setminus E$, $a$ is certainly attacked by $E$, where $A_w = A$, $A_s = A \cup A^?

**Example 8.** We modify the ISETF from Example 6 to $U_2 = (\{h, f\}, \{p\}, \emptyset, \{(\{f, p\}, h)\})$, thus the collective attack is uncertain. Since argument $h$ is only attacked by an uncertain collective attack, the set $\{f, h, p\}$ is $w$-complete, while the set $\{f, p\}$ is $s$-complete.

## 4. Properties

In this section, we investigate key properties for the extension-based approach for ISETF, thus we focus on the ISETF directly and avoid generating completions. The properties considered were originally introduced for standard AF [11], but are extended to fit the context of ISETFs with minor modifications.

We begin by discussing the relationship between ISETFs, AFs, IAFs, and SETAFs. By construction, ISETFs subsumes AFs, IAFs, and SETAFs as special cases: for AFs, all attacks are certain and every set-attack is a singleton; for IAFs, all set-attacks are singletons (which may be certain or uncertain); and for SETAFs, all set-attacks are certain (but may have arbitrary size). As a result, properties and results established for the classical frameworks are directly inherited or can be generalised for ISETFs. To make this correspondence precise, we formally state and prove the following proposition:

**Proposition 2.** Every AF, IAF, and SETAF can be represented as an ISETF.
**Proof.** Let $F = (A, R)$ be an AF with $R \subseteq A \times A$. The corresponding ISETAF is $U = (A, \emptyset, \{(\{a\}, b) \mid (a, b) \in R\}, \emptyset)$. Thus, for any AF, a corresponding ISETAF can be constructed.

Let $\mathcal{I} = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an IAF. The corresponding ISETAF is $U = (\mathcal{A}, \mathcal{A}^?, \{(\{a\}, b) \mid (a, b) \in \mathcal{R}\}, \{(\{a\}, b) \mid (a, b) \in \mathcal{R}^?\})$. Thus, for any IAF, a corresponding ISETAF can be constructed.

Let $\mathcal{S} = (\mathcal{A}, \mathcal{R})$ be a SETAF. The corresponding ISETAF is $U = (\mathcal{A}, \emptyset, \mathcal{R}, \emptyset)$. Thus, for any SETAF, a corresponding ISETAF can be constructed. $\square$

Properties originally considered for AFs can be meaningfully adapted to ISETAFs, taking into account the richer structure provided by uncertain arguments and collective attacks. For each property, we carefully reformulated the postulate in the ISETAF setting and examined its satisfaction for all extension-based semantics, distinguishing between their weak and strong variants. A comprehensive overview of all results is presented in tabular form at the end of the section.

To analyse the properties within ISETAFs, several technical notions must first be formally introduced. In particular, we require precise definitions of set of attack arguments, x-untouched sets, projection operator, cohesive subsets, and the x-reduct of an ISETAF. These concepts provide the formal basis for our property formulations and subsequent results. We proceed by outlining the required definitions before presenting and discussing the adapted properties in detail.

**Definition 14.** Let $U = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an ISETAF and $E \subseteq A \cup A^?$ a set of arguments. We define:

* $E^{+,w} := \{a \mid (E', a) \in \mathcal{R} \text{ s.t. } E' \subseteq E\}$ – the set of arguments certainly attacked by $E$;

* $E^{+,s} := \{a \mid (E', a) \in \mathcal{R} \cup \mathcal{R}^? \text{ s.t. } E' \subseteq E\}$ – the set of arguments certainly or uncertainly attacked by $E$.

A set of arguments $E$ is considered *untouched* if it is not attacked by any set of arguments.

**Definition 15.** Let $U = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an ISETAF and $E \subseteq A \cup A^?$ a set of arguments. $E$ is:

* w-untouched if there is no $b \in A \setminus E$ and no set $B \subseteq A$ with $b \in B$ such that $(B, a) \in \mathcal{R}$ for any $a \in E$.

* s-untouched if there is no $b \in (A \cup A^?) \setminus E$ and no set $B \subseteq A \cup A^?$ with $b \in B$ such that $(B, a) \in \mathcal{R} \cup \mathcal{R}^?$ for any $a \in E$.

A projection of an ISETAF with respect to a set of arguments $E$ is an ISETAF, where every argument not in $E$ is removed.

**Definition 16.** Let $U = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an ISETAF and $E \subseteq A \cup A^?$. The projection of $U$ onto $E$, denoted $U_{\downarrow E}$, is $U_{\downarrow E} = (A \cap E, A^? \cap E, R_{\downarrow E}, R^?_{\downarrow E})$, where $R_{\downarrow E} = \{(B, a) \in \mathcal{R} \mid B \subseteq E, a \in E\}$ and $R^?_{\downarrow E} = \{(B, a) \in \mathcal{R}^? \mid B \subseteq E, a \in E\}$.

We call a set *cohesive* if it represents exactly those arguments that collectively participate in a set-based attack. More formally, a singleton $\{a\}$ is cohesive if the argument $a$ alone forms a set attack, i.e., there exists a target $c$ such that $(\{a\}, c)$ is a set attack. In contrast, if $a$ does not attack any argument on its own, then $\{a\}$ is not cohesive. Furthermore, if a group of arguments, such as $a, b$, and $c$, jointly attack a common target, then the set $\{a, b, c\}$ is cohesive.

**Definition 17.** Let $U = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an ISETAF. A set $E \subseteq A \cup A^?$ is called a cohesive set if there exists $c \in A \cup A^?$ such that $(E, c) \in \mathcal{R} \cup \mathcal{R}^?$.

The reduct of an ISETAF U w.r.t. a set $E$ is an ISETAF, where all arguments of $E$ and arguments attacked by $E$ are removed. All attacks involving the removed arguments are removed as well.

**Definition 18.** Let $U = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an ISETAF and $E \subseteq A \cup A^?$. The weak or strong x-reduct of $U$ with respect to $E$, denoted $U^{E,x} = (A', A'^?, R', R'^?)$, is defined by:

$$A' = A \setminus (E \cup E^{+,x}),$$
$$
\begin{align*}
A'^{?} &= A^{?} \setminus (E \cup E^{+,x}), \\
R' &= \{(B \setminus E, a) \mid (B, a) \in R, B \subseteq A' \cup A'^{?}, a \in A' \cup A'^{?}, B \cap E^{+,x} = \emptyset\}, \\
R'^{?} &= \{(B \setminus E, a) \mid (B, a) \in R^{?}, B \subseteq A' \cup A'^{?}, a \in A' \cup A'^{?}, B \cap E^{+,x} = \emptyset\}.
\end{align*}
$$

With the necessary background cleared, we can define properties for ISETEAFs.

**Definition 19.** Let $\mathcal{U} = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ be an ISETEAF, let $\sigma_x$ be an extension-based semantics ($x \in \{w, s\}$), and $\sigma_x(\mathcal{U})$ the set of corresponding extensions.

We say that $\sigma_x$ satisfies the following property if and only if:

*   **Language independence:** For any two ISETEAFs $U, U'$ and any bijective renaming $\rho$ such that $U' = \rho(U)$ and $\rho$ preserves the type of each argument (certain or uncertain) and each attack (certain or uncertain), it holds that $\sigma_x(U') = \rho(\sigma_x(U))$.

*   **I-maximality:** For all $E, E' \in \sigma_x(\mathcal{U})$, if $E \subseteq E'$, then $E = E'$, i. e., no two extensions are in a proper subset relation.

*   **Allowing abstention:** For all $E, E' \in \sigma_x(\mathcal{U})$ and all $a \in \mathcal{A} \cup \mathcal{A}^?$: if $a \in E$ and $a \in E'^{+,x}$, then there exists $E'' \in \sigma_x(\mathcal{U})$ such that $a \notin E''$ and $a \notin E'^{+,x}$.

*   **Set-based directionality:** For every $x$-untouched set $E \subseteq \mathcal{A} \cup \mathcal{A}^?$ in $\mathcal{U}$, it holds that $\sigma_x(\mathcal{U}_{\downarrow E}) = \{E' \cap E \mid E' \in \sigma_x(\mathcal{U})\}$.

*   **Set-based tightness:** For any $E \in \sigma_x(\mathcal{U})$ and any $a \in (\mathcal{A} \cup \mathcal{A}^?) \setminus E$ with $E \cup \{a\} \notin \sigma_x(\mathcal{U})$, there exists a cohesive set $B \subseteq E$ such that for all $E' \in \sigma_x(\mathcal{U})$, $B \cup \{a\} \not\subseteq E'$.

*   **Set-based conflict sensitivity:** For all $E, E' \in \sigma_x(\mathcal{U})$ with $E \cup E' \notin \sigma_x(\mathcal{U})$, there exist cohesive sets $B \subseteq E$ and $B' \subseteq E'$ such that there is no extension $E'' \in \sigma_x(\mathcal{U})$ with $B \cup B' \subseteq E''$.

*   **Modularisation:** For any $E \in \sigma_x(\mathcal{U})$ and $E' \in \sigma_x(\mathcal{U}^{E,x})$, it holds that $E \cup E' \in \sigma_x(\mathcal{U})$.

The properties Language independence, I-maximality, Allowing abstention, and Modularisation are adapted from AFs to ISETEAFs to ensure that the extensions-based semantics for ISETEAFs behave inline with their corresponding AF variant. The properties Set-based directionality, Set-based tightness, and Set-based conflict sensitivity help to design algorithms suited for ISETEAFs.

Proposition 2 shows that ISETEAFs are generalisations of AFs, IAFs, and SETAFs, thus we can immediately observe that any negative result for a given semantics in the classical frameworks will also hold in ISETEAF semantics.

**Proposition 3.** If an extension semantics $\sigma$ for AFs, SETAFs, or IAFs violates a property $P$, then neither the ISETEAF semantics $\sigma_w$ nor $\sigma_s$ satisfies this property $P$.

*Proof.* Let $F$ be an AF, $S$ a SETAF, and $\mathcal{I}$ an IAF. Consider extension semantics $\sigma$ such that $\sigma$ violates property $P$ for $F$, $S$, or $\mathcal{I}$. Each of these frameworks can be transformed into an ISETEAF as seen in Proposition 2, thus $\sigma$ also violates $P$ in the corresponding ISETEAF, implying that this property cannot generally be satisfied. $\square$

**Example 9.** The complete semantics violates I-maximality for AFs and therefore this property is also violated by the weak and strong complete semantics ($\mathcal{C}_{w}, \mathcal{C}_{s}$) for ISETEAFs. Similarly, the property directionality is violated by the stable semantics $\mathcal{S}$ in AFs, and also by $\mathcal{S}_w$ and $\mathcal{S}_s$ in ISETEAFs.

The results of our analysis are summarised in Table 1. Each row corresponds to one of the adapted properties, while columns indicate for each ISETEAF semantics (both weak and strong variants) whether the property is satisfied (✓) or not (✗).

**Proposition 4.** The satisfied and violated by $\sigma_x$ for $\sigma \in \{\text{cf}, \text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$ and $x \in \{w, s\}$ are depicted in Table 1.
<table><caption>**Table 1**</caption><thead><tr><th></th><th>cf<sub>w</sub></th><th>cf<sub>s</sub></th><th>ad<sub>w</sub></th><th>ad<sub>s</sub></th><th>co<sub>w</sub></th><th>co<sub>s</sub></th><th>pr<sub>w</sub></th><th>pr<sub>s</sub></th><th>gr<sub>w</sub></th><th>gr<sub>s</sub></th><th>st<sub>w</sub></th><th>st<sub>s</sub></th></tr></thead><tbody><tr><td>Language independence</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>I-maximality</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td></tr><tr><td>Allowing abstention</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Set-based directionality</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Set-based tightness</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Set-based conflict sensitivity</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Modularization</td><td>✗</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td></tr></tbody></table>

Overview of property satisfaction for ISETAF-semantics.

The results demonstrate that ISETAFs inherit many desirable properties of classical argumentation frameworks when appropriately generalised. Most notably, properties such as *language independence*, *I-maximality*, *allowing abstention*, and *modularisation* are still satisfied by the considered semantics. In addition, the new properties specifically tailored to ISETAFs, such as *set-based directionality*, *set-based tightness*, and *set-based conflict sensitivity*, are also satisfied by the respective semantics whenever their analogues hold in the classical AF. Overall, the results show that ISETAFs maintain strong theoretical foundations while providing increased expressiveness for modelling argumentation under incomplete information.

## 5. Computational Complexity

We analysed ISETAFs based on their axiomatic properties, however beyond these principles, we can also investigate the computational complexity of reasoning with ISETAFs. In this paper, we focus on *decision problems*, i. e. problems consisting out of an instance and a question that has a YES or NO answer. We assume familiarity with the basic concepts of computational complexity, in particular the complexity classes P, NP, and coNP [12, 13] as well as $\Pi_2^P$ and $\Pi_3^P$, which are problems that can be recognised by a non-deterministic polynomial time algorithm with access to an NP respectively $\Pi_2^P$ oracle [14].

For abstract argumentation three decision problems are typically considered: *verification*, *credulous acceptance* and *skeptical acceptance* [15, 16]. The verification problem $VER_\sigma$ asks whether a set $E$ is a $\sigma$-extension of an AF or not. Formally:

$VER_\sigma$ **Input:** An AF $F = (A, R)$ and $E \subseteq A$
**Output:** Yes if $E \in \sigma(F)$, and No otherwise.

The two acceptance problems ask whether a given argument is credulously or skeptically accepted with respect to an extension semantics $\sigma$ in an AF.

$CRED_\sigma$ **Input:** An AF $F = (A, R)$ and $a \in A$
**Output:** Yes if $a$ is credulously accepted with respect to $\sigma$ in $F$, and No otherwise.

$SKEP_\sigma$ **Input:** An AF $F = (A, R)$ and $a \in A$
**Output:** Yes if $a$ is skeptically accepted with respect to $\sigma$ in $F$, and No otherwise.

The three decision problems can be extended for IAFs to incorporate the *possible* and *necessary* variations of these problems. For instance the possible verification problem $P-VER_\sigma$ asks whether a set $E$ is a $\sigma$-extension of at least one completion of an IAF.

$P-VER_\sigma$ **Input:** An IAF $\mathcal{I} = (\mathcal{A}, \mathcal{A}^2, \mathcal{R}, \mathcal{R}^2)$ and $E \subseteq \mathcal{A} \cup \mathcal{A}^2$
**Output:** Yes if there is a completion $F \in \text{comp}(\mathcal{I})$ such that $E \in \sigma(F)$, and No otherwise.

For the necessary variation of the verification problem a set $E$ has to be a $\sigma$-extension in every completion.
**N-VER<sub>σ</sub>**
**Input:** An IAF $\mathcal{I} = (\mathcal{A}, \mathcal{A}^?, \mathcal{R}, \mathcal{R}^?)$ and $E \subseteq \mathcal{A} \cup \mathcal{A}^?$
**Output:** Yes if for all completions $F \in \text{comp}(\mathcal{I})$ it holds that $E \in \sigma(F)$, and No otherwise.

The possible and necessary variants of the skeptical acceptance problems are defined accordingly [6].

We can extend the six problems (P-VER<sub>σ</sub>, N-VER<sub>σ</sub>, P-CRED<sub>σ</sub>, N-CRED<sub>σ</sub>, P-SKEP<sub>σ</sub>, and N-SKEP<sub>σ</sub>) to ISETAFs. Formally:

**P-SETVER<sub>σ</sub>**
**Input:** An ISETAF $U = (A, A^?, R, R^?)$ and $E \subseteq A \cup A^?$
**Output:** Yes if there is a completion $S \in \text{comp}_{\text{ISETAF}}(U)$ such that $E \in \sigma(S)$, and No otherwise.

**N-SETVER<sub>σ</sub>**
**Input:** An ISETAF $U = (A, A^?, R, R^?)$ and $E \subseteq A \cup A^?$
**Output:** Yes if for all completions $S \in \text{comp}_{\text{ISETAF}}(U)$ it holds that $E \in \sigma(S)$, and No otherwise.

The acceptance problems (P-SETCRED<sub>σ</sub>, N-SETCRED<sub>σ</sub>, P-SETSKEP<sub>σ</sub>, and N-SETSKEP<sub>σ</sub>) can be defined accordingly. In the following, we analyse the computational complexity of these six decision problems.

Every IAF can be represented as an ISETAF, as shown in Proposition 2. Therefore, reasoning problems for ISETAFs are at least as hard as for IAFs. To establish whether the converse also holds, that is, whether the complexity of ISETAFs is upper-bounded by that of IAFs, it suffices to show that any ISETAF can be translated into an equivalent IAF in polynomial time, while preserving semantic properties.

Inspired by Modgil and Bench-Capon [17], the idea is to simulate each set attack by introducing auxiliary arguments and appropriate attack relations, eliminating collective attacks in favour of standard ones. The following definition formalises this transformation.

**Definition 20.** Let $U = (A, A^?, R, R^?)$ be an ISETAF. The transformed IAF $\mathcal{I}_U = (\mathcal{A}_U, \mathcal{A}_U^?, \mathcal{R}_U, \mathcal{R}_U^?)$ is defined as follows:

* $\mathcal{A}_U = A \cup \{h_a \mid a \in E, (E, b) \in R \cup R^?\} \cup \{h_{(E,b)} \mid (E, b) \in R \cup R^?\}$

* $\mathcal{A}_U^? = A^?$

* $\mathcal{R}_U = \{(a, h_a) \mid a \in E, (E, b) \in R \cup R^?\} \cup \{(h_a, h_{(E,b)}) \mid a \in E, (E, b) \in R \cup R^?\} \cup \{(h_{(E,b)}, b) \mid (E, b) \in R\}$

* $\mathcal{R}_U^? = \{(h_{(E,b)}, b) \mid (E, b) \in R^?\}$

This transformation introduces two types of auxiliary arguments: for each attacker in a set attack, and for each set attack as a whole. As a result, all set attacks are simulated via standard attacks between these arguments. To show that the transformation induces the same σ-extensions, we need a few more notations. Besides transforming the ISETAF into an IAF, we also need to transform the corresponding completions.

**Definition 21.** Let $U = (A, A^?, R, R^?)$ be an ISETAF, $\mathcal{I}_U = (\mathcal{A}_U, \mathcal{A}_U^?, \mathcal{R}_U, \mathcal{R}_U^?)$ the transformed IAF with respect to $U$ and $U^* = (A^*, R^*)$ a completion of $U$ with $A \subseteq A^* \subseteq (A \cup A^?)$ and $R \cap (2^{A^*} \times A^*) \subseteq R^* \subseteq (R \cup R^?) \cap (2^{A^*} \times A^*)$. The corresponding transformed completion of $U^*$ is:

$$ 
\begin{aligned}
I_{\to U^*}^* &= (B, T) \\
B &= \{\mathcal{A}_U \cup (\mathcal{A}_U^? \cap A^?)\} \\
T &= \{(c, d) \mid c, d \in B, (c, d) \in \mathcal{R}_U\} \cup \{(h_{(E,a)}, a) \mid E \subseteq B, (E, a) \in \mathcal{R}^?\}
\end{aligned}
$$

The transformed completion contains all auxiliary arguments, contained in the completion, and therefore also all attacks. Furthermore, for all collective attacks $(E, a)$ of the completions of the ISETAF there is a corresponding attack $(h_{(E,a)}, a)$, from the auxiliary argument to argument $a$.

Next, we introduce the notion of *transformed sets*.
<figure><img src="image_16.png" /><figcaption>**Figure 5:** Transformed IAF $\mathcal{I}_{U_1}$ from Example 10, where $r = (\{f, p\}, h)$.</figcaption></figure>

**Definition 22.** Let $U = (A, A^?, R, R^?)$ be an ISETAF, $\mathcal{I}_U = (A_U, A_U^?, R_U, R_U^?)$ the transformed IAF with respect to $U$, $E \subseteq A \cup A^?$, $U^* = (A^*, R^*)$ a completion of $U$, and $I_{\to U^*}^* = (B, T)$ the corresponding transformed completion of $U^*$.

The transformed set with respect to $E$ is:

$$ E'_{\to E} = E \cup H_E \cup H'_E \quad \text{where:} \quad \begin{aligned} H_E &= \{h_{(C,a)} \mid C \subseteq E\} \\ H'_E &= \{h_a \mid h_{(C,a)} \in H_E \text{ or } a \in A_U^?, a \notin B\} \end{aligned} $$

**Example 10.** Consider $U_1$ from Example 6. For the collective attack $(\{f, p\}, h)$, we add three auxiliary arguments $h_f$, $h_p$, and $h_{(\{f,p\},h)}$. $h_f$ and $h_p$ are attacking $h_{(\{f,p\},h)}$ and are attacked by $f$ and $p$, respectively. $h_{(\{f,p\},h)}$ attacks $h$. The corresponding IAF is depicted in Figure 5.

The set $\{f, p\}$ is a complete extension in the completion where $p$ is contained. The corresponding transformed set is $\{f, p, h_{(\{f,p\},h)}\}$, this set is a complete extension. Thus, we find for a complete extension in the ISETAF, a corresponding complete extension in the IAF.

Example 10 demonstrates, that for every $\sigma$-extension of an ISETAF, we can find a corresponding $\sigma$-extension in the transformed IAF.

**Proposition 5.** Let $U = (A, A^?, R, R^?)$ be an ISETAF, $\mathcal{I}_U = (A_U, A_U^?, R_U, R_U^?)$ the transformed IAF with respect to $U$, $\sigma$ an extension semantics, $E \subseteq A \cup A^?$, and $E'_{\to E}$ the transformed set wrt. $E$. Then:

1. $E'_{\to E}$ is a possible $\sigma$-extension in $\mathcal{I}_U$ iff $E$ is a possible $\sigma$-extension in $U$.

2. $E'_{\to E}$ is a necessary $\sigma$-extension in $\mathcal{I}_U$ iff $E$ is a necessary $\sigma$-extension in $U$.

We can transform any IAF into an ISETAF and back, while inducing the same extensions, thus the computational complexity of $\text{P-SETVER}_\sigma$, $\text{N-SETVER}_\sigma$, $\text{P-SETCRED}_\sigma$, $\text{N-SETCRED}_\sigma$, $\text{P-SETSKEP}_\sigma$, and $\text{N-SETSKEP}_\sigma$ coincide with their IAFs counterparts. Table 2 summarises the results.

<table><thead><tr><th></th><th>P-SETCRED<sub>σ</sub></th><th>N-SETCRED<sub>σ</sub></th><th>P-SETSKEP<sub>σ</sub></th><th>N-SETSKEP<sub>σ</sub></th><th>P-SETVER<sub>σ</sub></th><th>N-SETVER<sub>σ</sub></th></tr></thead><tbody><tr><td>cf</td><td>in P</td><td>in P</td><td>trivial</td><td>trivial</td><td>in P</td><td>in P</td></tr><tr><td>ad</td><td>NP-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>trivial</td><td>trivial</td><td>in P</td><td>in P</td></tr><tr><td>co</td><td>NP-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>NP-c</td><td>coNP-c</td><td>in P</td><td>in P</td></tr><tr><td>pr</td><td>NP-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>Π<sub>3</sub><sup>P</sup>-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>coNP-c</td></tr><tr><td>gr</td><td>NP-c</td><td>coNP-c</td><td>NP-c</td><td>coNP-c</td><td>in P</td><td>in P</td></tr><tr><td>st</td><td>NP-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>Π<sub>2</sub><sup>P</sup>-c</td><td>coNP-c</td><td>in P</td><td>in P</td></tr></tbody></table>

**Table 2**

The complexity of reasoning problems for ISETAFs is derived from the complexity results for IAFs as established in the works by Baumeister et al., and Baumeister et al. [3, 18].

**Proposition 6.** The computation complexity of $\text{P-SETVER}_\sigma$, $\text{N-SETVER}_\sigma$, $\text{P-SETCRED}_\sigma$, $\text{N-SETCRED}_\sigma$, $\text{P-SETSKEP}_\sigma$, and $\text{N-SETSKEP}_\sigma$ for $\sigma \in \{\text{cf}, \text{ad}, \text{co}, \text{pr}, \text{gr}, \text{st}\}$ are as depicted in Table 2.
# 6. Conclusion

We introduced ISEΤΑFs, a novel extension of abstract argumentation frameworks that unifies reasoning with collective attacks and incomplete information within a single model addressing realistic scenarios previously not supported by existing frameworks.

We formally defined ISEΤΑFs and developed two reasoning approaches: a completion-based approach, which evaluates all possible scenarios, and an extension-based approach, which enables direct analysis of argument sets without generating completions. For the extension-based method, we devised weak and strong variants of standard Dung semantics, reflecting different attitudes towards uncertain information.

In addition, we looked at the computational complexity of the corresponding acceptance problems. Our complexity analysis showed that reasoning in ISEΤΑFs does not increase the computational complexity compared to established frameworks, since ISEΤΑF problems can be polynomially reduced to IAFs. At the same time, ISEΤΑFs strictly generalise AFs, SETAFs, and IAFs, preserving their expressiveness but also inheriting both positive and negative results regarding desirable semantic properties.

A systematic analysis of central properties demonstrated that satisfaction of these properties in ISEΤΑFs precisely mirrors their satisfaction in the respective base frameworks and semantics.

Overall, ISEΤΑFs provide a powerful and unifying framework for argumentation under both collective attacks and incomplete information. They enable more expressive and realistic modelling of decision-making scenarios while maintaining manageable reasoning complexity for standard tasks.

Dimopoulos et al. [19] introduced a framework also termed ISEΤΑF, which allows attacks from sets of arguments to sets of arguments and models uncertainty exclusively on attacks, while arguments remain strictly certain. In contrast, our notion of ISEΤΑFs permits uncertainty for both arguments and attacks, and restricts collective attacks to target single arguments. This distinction highlights two different approaches to extending classical argumentation frameworks towards handling incomplete information. In the literature we can find more works discussing the combination of uncertainty and other features. For instance Lagasquie-Schiex et al. [20] discuss the combination of support and uncertainty and Doutre et al. [21] investigates the combination of higher-order attacks and uncertainty. Uncertainty has not only been discussed in the abstract case, but also for structured approaches. Odekerken et al. [22] investigated uncertainty for ASPIC$^+$.

Future work could focus on incorporating probabilistic information into the modelling of uncertain arguments and attacks, following ideas from probabilistic argumentation frameworks [23]. Furthermore, alternative semantics and additional desirable properties, as recently explored for SETAFs [24], could be investigated within the context of incomplete information. Finally, practical implementations and evaluations in real-world settings would help to demonstrate the applicability and potential of the proposed framework.

# References

[1] K. Atkinson, P. Baroni, M. Giacomin, A. Hunter, H. Prakken, C. Reed, G. R. Simari, M. Thimm, S. Villata, Towards artificial argumentation, AI Mag. 38 (2017) 25–36.

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

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

[4] S. H. Nielsen, S. Parsons, A generalization of dung's abstract framework for argumentation: Arguing with sets of attacking arguments, in: Argumentation in Multi-Agent Systems, ArgMAS 2006, volume 4766 of Lecture Notes in Computer Science, Springer, 2006, pp. 54–73.

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

[6] D. Baumeister, M. Järvisalo, D. Neugebauer, A. Niskanen, J. Rothe, Acceptance in incomplete argumentation frameworks, Artif. Intell. 295 (2021) 103470.
[7] K. Skiba, D. Neugebauer, J. Rothe, Complexity of nonempty existence problems in incomplete argumentation frameworks, IEEE Intell. Syst. 36 (2021) 13–24.

[8] J. Mailly, Extension-based semantics for incomplete argumentation frameworks, in: Logic and Argumentation, CLAR 2021, volume 13040 of *Lecture Notes in Computer Science*, Springer, 2021, pp. 322–341.

[9] J. Mailly, Extension-based semantics for incomplete argumentation frameworks: Grounded semantics and principles, in: Symbolic and Quantitative Approaches to Reasoning with Uncertainty, ECSQARU 2023, volume 14294 of *Lecture Notes in Computer Science*, Springer, 2023, pp. 84–94.

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

[11] L. van der Torre, S. Vesic, The principle-based approach to abstract argumentation semantics, IfCoLog Journal of Logics and Their Applications 4 (2017).

[12] C. H. Papadimitriou, Computational complexity, Addison-Wesley, 1994.

[13] S. Arora, B. Barak, Computational Complexity - A Modern Approach, Cambridge University Press, 2009.

[14] L. J. Stockmeyer, The polynomial-time hierarchy, Theoretical Computer Science 3 (1976) 1–22.

[15] P. E. Dunne, M. J. Wooldridge, Complexity of abstract argumentation, in: G. R. Simari, I. Rahwan (Eds.), Argumentation in Artificial Intelligence, Springer, 2009, pp. 85–104.

[16] W. Dvorák, P. E. Dunne, Computational problems in formal argumentation and their complexity, Journal of Applied Logics 4 (2017) 2557–2622.

[17] S. Modgil, T. J. M. Bench-Capon, Metalevel argumentation, J. Log. Comput. 21 (2011) 959–1003.

[18] D. Baumeister, D. Neugebauer, J. Rothe, Credulous and skeptical acceptance in incomplete argumentation frameworks, in: Computational Models of Argument COMMA 2018, volume 305 of *Frontiers in Artificial Intelligence and Applications*, IOS Press, 2018, pp. 181–192.

[19] Y. Dimopoulos, W. Dvorák, M. König, A. Rapberger, M. Ulbricht, S. Woltran, Sets attacking sets in abstract argumentation, in: International Workshop on Non-Monotonic Reasoning NMR 2023, volume 3464 of *CEUR Workshop Proceedings*, CEUR-WS.org, 2023, pp. 22–31.

[20] M. Lagasquie-Schiex, J. Mailly, A. Yuste-Ginel, How to manage supports in incomplete argumentation, in: Foundations of Information and Knowledge Systems FoIKS 2024, volume 14589 of *Lecture Notes in Computer Science*, Springer, 2024, pp. 319–339.

[21] S. Doutre, M. Lagasquie-Schiex, J. Mailly, A. Yuste-Ginel, Incomplete higher-order abstract argumentation frameworks, in: Logic and Argumentation CLAR 2025, volume 15712 of *Lecture Notes in Computer Science*, Springer, 2025, pp. 34–52.

[22] D. Odekerken, T. Lehtonen, J. P. Wallner, M. Järvisalo, Argumentative reasoning in aspic+ under incomplete information, Journal of Artificial Intelligence Research 83 (2025).

[23] H. Li, N. Oren, T. J. Norman, Probabilistic argumentation frameworks, in: Theorie and Applications of Formal Argumentation TAFA 2011, volume 7132 of *Lecture Notes in Computer Science*, Springer, 2011, pp. 1–16.

[24] W. Dvorák, M. König, M. Ulbricht, S. Woltran, Principles and their computational consequences for argumentation frameworks with collective attacks, J. Artif. Intell. Res. 79 (2024) 69–136.
## Part II

# The First International Workshop on Inconsistency Measurement (IM 2025)
# Germane Conflicts: Desirable Properties for Localising Inconsistency (Keynote)

Anthony Hunter¹

¹University College London

Inconsistency is a common problem in knowledge, and so there is a need to analyse it. Inconsistency measures assess its severity, but there is a more basic question: “where is the inconsistency?”. Typically, not all subsets of a knowledgebase are causing the inconsistency, and minimal inconsistent sets have been the standard way to localise the germane ones, even though there are shortcomings in some scenarios. Recently, *-conflicts were proposed as a more suitable definition to localise inconsistency when considering a method to repair it [1]. But in general there is no way to tell what is a sensible definition to capture the germane conflicts. This work [2] provides a set of desirable properties to assess definitions for germane conflicts. Also, a new conflict definition, based on substitution, is presented and evaluated via the proposed properties, and the related computational complexity is analysed. In the talk, we will also consider how these ideas can be used in measuring inconsistency and in computational models of argument, and we will look at future work in extending the framework to a recent proposal for analysing inconsistency in three-valued logics [3].

## References

[1] G. D. Bona, A. Hunter, Localising iceberg inconsistencies, Artificial Intelligence 246 (2017) 118–151.

[2] G. D. Bona, A. Hunter, Germane conflicts: Desirable properties for localising inconsistency, in: Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI’25), AAAI Press, 2025, pp. 14840–14847.

[3] J. Grant, A. Hunter, Semantic inconsistency measures using 3-valued logics, International Journal of Approximate Reasoning 156 (2023) 38–60.

IM’25@ECSQARU: 1st International Workshop on Inconsistency Measurement, September 23, 2025, Hagen, Germany

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

anthony.hunter@ucl.ac.uk (A. Hunter)

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

© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
# Measuring Inconsistency in a Fragment of Hybrid Logic

John Grant¹, Manuel A. Martins²

¹Department of Computer Science and UMIACS, University of Maryland, College Park, MD, USA

²CIDMA& Mathematics Department, University of Aveiro, Aveiro, Portugal

**Abstract**

Hybrid logic extends modal logic by means of a satisfaction operator that is essentially a locator function. The purpose of this paper is to extend the work on inconsistency measures from the modal logic framework to a fragment of hybrid logic. We define both inconsistency measures directly taken from propositional logic as well as new inconsistency measures for hybrid logic. We also study properties of these measures, called rationality postulates.

**Keywords**

Inconsistency measures, Hybrid logic, Rationality postulates

## 1. Introduction

Hybrid logic is an extension of standard modal logic that increases its expressive power by allowing explicit reference to individual states (or possible worlds) within a model [Bla00; AC07]. While ordinary modal logic enables reasoning about necessity and possibility across possible worlds, it lacks the means to directly name or refer to specific worlds. Hybrid logic addresses this limitation through the introduction of nominals—special propositional symbols that are true at exactly one world—and the satisfaction operator (commonly denoted as @), which enables formulas to be evaluated at worlds named by these nominals. Using a nominal i, one can assert that a property holds at the unique world named by i. The formula @iϕ expresses that the statement ϕ is true at the world identified by i, regardless of the current evaluation point. Moreover, in hybrid logic we can specify the accessibility relation between named worlds, namely the world named by i accesses the world named by j if @i◇j holds.

Another important aspect is that hybrid logic retains the computational tractability of modal logic. The addition of nominals and the satisfaction operator does not increase the complexity of the satisfiability problem beyond that of standard modal logic; both remain PSPACE-complete. Furthermore, hybrid logic formulas can be translated into first-order logic by interpreting nominals as constants, further bridging the gap between modal and first-order expressiveness.

Hybrid logic has been applied to various domains where its ability to name and reason about specific states is useful. In knowledge representation, it enriches ontology languages and description logics ([AR00]), enabling precise reasoning for the Semantic Web, and has enhanced query languages such as XPath ([AF21]). In artificial intelligence and verification, hybrid logic facilitates model checking, temporal and epistemic reasoning, and the specification of distributed systems ([BT98]). The expressiveness of hybrid logic, namely its ability to explicitly name states and reason about their properties, has proved essential in the rigorous specification of reconfigurable and reactive systems. Thus, hybrid logic has been used in adaptive software architectures, reconfigurable hardware, and dynamic communication networks, which demand rigorous methods for their specification and verification to capture both the structural variability of configurations and the dynamic nature of reconfiguration processes. By associating system configurations with nominals and expressing reconfiguration rules through modal operators, hybrid logic enables a precise specification of system behavior across different configurations. This makes it possible to formally describe not only the properties that must hold within a given configuration, but also the constraints that govern safe and correct transitions between configurations

1st International Workshop on Inconsistency Measurement (IM'25) @ECSQARU 2025, Hagen, Germany, September 23rd, 2025

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

grant@cs.umd.edu (J. Grant); martins@ua.pt (M. A. Martins)

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

0000-0001-7503-7703 (J. Grant); 0000-0002-5109-8066 (M. A. Martins)

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

© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
([Mad+16; Mar+11]). Recently, D. Gaina introduced a hybrid-dynamic logic for quantum programming, capable of formally capturing measurements and unitary evolutions. He shows that this logic provides a basis for defining executable languages for specifying quantum programs ([Găi24]).

Our starting point will be [Gra21] which defined and discussed several inconsistency measures for logics with modal operators. The idea of an inconsistency measure is to assess the amount of inconsistency in a set of formulas. Our goal is to add the location function $@_i$ of hybrid logic to the modal operators. We will review previous work in steps where at each step we will show how to add $@_i$ and give examples of its use.

The plan of this paper is as follows. In Section 2 we write the basic definitions for several well-known inconsistency measures in propositional logic (PL) as well as desirable properties that inconsistency measures may possess, called rationality postulates. The main focus of the paper is Section 3 where we define a fragment of hybrid logic and study inconsistency measures for them as well as the satisfaction of various properties, called rationality postulates.

# 2. Propositional Logic (PL)

## 2.1. Notation

We assume a potentially countable infinite set of atoms $A = \{a_1, a_2, a_3, \dots\}$ (but we will usually write $a, b, c, \dots$), that can be combined by negation ($\neg$), conjunction ($\wedge$), disjunction ($\vee$) and parentheses in the usual way to create formulas. Capital letters: $A, B, C, \dots$ represent finite sets of formulas and $\mathcal{F}$ for the set of all formulas. An interpretation $i: A \to \{\text{false, true}\}$ assigns a truth value to every atom (of the set of formulas under consideration). Using this, each formula also obtains a truth value using the usual truth tables. Formulas are indicated by the lower case Greek letters, $\alpha$ and $\beta$. A set of formulas is consistent iff there is an interpretation in which all the formulas in the set get the truth value *true*. Otherwise it is inconsistent. For example, the set $A = \{a \wedge \neg a, b, \neg b \wedge c, c \vee d, \neg c, d \vee e, \neg d\}$ is inconsistent. We write $\mathcal{PL}$ for the set of possible formulas of PL.

## 2.2. Inconsistency Measures

In this subsection we define several inconsistency measures for PL. We note that this is just a small sample of the many inconsistency measures that have been proposed. A survey of 22 inconsistency measures is given in [Thi18]. We chose these because they have good intuitive justification and are easy to define.

**Definition 1.** An inconsistency measure is a function $I: \mathcal{P}_{fin}(\mathcal{F}) \to \mathbf{R}^+ \cup \{0\}$

Thus an inconsistency measure assigns to every finite subset of formulas a nonnegative real number. This number represents the inconsistency of the set according to the inconsistency measure $I$. An inconsistency measure is expected to assign every consistent set the value 0 and every inconsistent set a positive value. This is called the Consistency postulate.

One concept that occurs in several inconsistency measures is the notion of minimal inconsistent subset (MIS), i.e., the inconsistent subsets none of whose proper subsets is inconsistent. We may think of the MISs as the building blocks of the inconsistencies. We write $\text{MIS}(S)$ for the set of minimal inconsistent subsets of a set $S$. In particular, $\text{MIS}(A) = \{\{a \wedge \neg a\}, \{b, \neg b \wedge c\}, \{\neg b \wedge c, \neg c\}, \{c \vee d, \neg c, \neg d\}\}$. Formulas that appear in at least one MIS are called *problematic*. We write $\text{Prob}(S)$ for the set of problematic formulas of $S$. In particular, $\text{Prob}(A) = \{a \wedge \neg a, b, \neg b \wedge c, c \vee d, \neg c, \neg d\}$.

Some inconsistency measures look inside the formulas for the atoms in them. One such measure uses the concept of a weak interpretation. For a weak interpretation the truth value of each instance of each atom must be specified. We can think of this as rewriting the set of formulas by distinguishing each occurrence of each atom. The rewriting of $A$ above would give $A^r = \{a^1 \wedge \neg a^2, b^1, \neg b^2 \wedge c^1, c^2 \vee d^1, \neg c^3, d^2 \vee e^1, \neg d^3\}$. Then, the weak interpretation $i$ where $i(a^1) = i(b^1) = i(c^1) = i(c^2) = i(d^1) = i(d^2) = i(e_1) = \text{true}$ and $i(a_2) = i(b_2) = i(c_3) = i(d_3) = \text{false}$ makes $A$ consistent. In fact, a weak
interpretation can make every set consistent by assigning every instance of an atom the value *true* and every instance of a negated atom the value *false*. When a weak interpretation gives different truth values to different occurrences of an atom we say that that atom has a weak interpretation. However, it may not be necessary to have a weak interpretation for every atom to get consistency. For example, if an atom occurs only once then it does not have a weak interpretation.

We will use the following inconsistency measures in this paper.

**Definition 2.** *Inconsistency measures for a finite set of formulas, S, in propositional logic:*

• $I_M(S) = |\text{MIS}(S)|$.

• $I_P(S) = |\text{Prob}(S)|$.

• $I_R(S) = \min\{|S'| \text{ such that } S \setminus S' \text{ is consistent}\}$.

• $I_A(S) = |\text{Atoms}(\text{Prob}(S))|$.

• $I_C(S) = \min\{|X| \mid X \subseteq \text{Atoms}(S) \text{ whose weak interpretation restores consistency}\}$.

• $I_B(S) = 1$ if S is inconsistent and 0 otherwise.

$I_M$ is the number of MISs; $I_P$ is the number of problematic formulas; $I_R$ (the repair measure) is the minimal number of formulas whose deletion makes the set consistent; $I_A$ is the number of distinct atoms in the problematic formulas; $I_C$ is the minimal number of atoms that need to be weakly interpreted to get consistency; and $I_B$ (the baseline measure) assigns 1 to every inconsistent set. In our example, $I_M(A) = 4$, $I_P(A) = 6$, $I_R(A) = 3$; $I_A(A) = 4$; $I_C(A) = 3$; and $I_B(A) = 1$.

## 2.3. Rationality Postulates

The concept of inconsistency measure is very weak; many functions that satisfy it may have no intuitive justification to be called inconsistency measures. Hence researches have formulated various properties that a function that intuitively appears to measure inconsistency should satisfy. These are called rationality postulates. We list 6 such postulates below. There are many other proposed postulates; the reason for our choice is that these postulates have good intuitive justification and are easy to define. A survey of 18 postulates is given in [Thi18].

**Definition 3.** *Formal definitions of postulates for inconsistency measures:*

• *Consistency:* $I(S) = 0$ iff S is consistent.

• *Variant Equality:* If $g: A \to A$ is an injective function, and $g(S)$ is the transformation of S by $g$, then $I(g(S)) = I(T)$.

• *Monotony:* $I(S) \le I(S \cup S')$.

• *Penalty:* If $\alpha \in \text{Prob}(S)$ then $I(S \setminus \{\alpha\}) < I(S)$.

• *Free-Formula Independence:* If $\alpha \in \text{Free}(S)$ then $I(S \setminus \{\alpha\}) = I(S)$.

• *Super-Additivity:* If $S \cap S' = \emptyset$ then $I(S \cup S') \ge I(S) + I(S')$.

The Consistency postulate was mentioned after Definition 1. Variant Equality means that atoms have no intrinsic meaning or weight that would make an inconsistency involving one atom, say a, different from the same inconsistency involving a different atom, say b. Monotony deals with the addition of formulas to a set; Penalty (resp. Free-Formula Independence) deals with what happens when a problematic (resp. free) formula is deleted; and Super-Additivity is a result about the inconsistency of a union of 2 disjoint sets of formulas.

These and other postulates have been studied for a wide variety of inconsistency measures. The result for the ones we defined is shown in Table 1. There is no consensus among experts about which postulates are truly needed, except for Consistency and Variant Equality, and perhaps Monotony. Although all the inconsistency measures we defined have an intuitive justification, only two of them satisfy all the postulates in the list.
<table><caption>**Table 1**</caption><thead><tr><th rowspan="2"></th><th colspan="6">Postulate Satisfaction</th></tr><tr><th>I<sub>M</sub></th><th>I<sub>P</sub></th><th>I<sub>R</sub></th><th>I<sub>A</sub></th><th>I<sub>C</sub></th><th>I<sub>B</sub></th></tr></thead><tbody><tr><th>Consistency</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><th>Variant Equality</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><th>Monotony</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><th>Penalty</th><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><th>Free-Formula Independence</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td></tr><tr><th>Super-Additivity</th><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td></tr></tbody></table>

Postulate satisfaction of inconsistency measures for propositional logic: ✓ means satisfied; ✗ means not satisfied.

## 3. AHPL

As the computation of inconsistency measures for the full language of modal logic is complicated, in [Gra21] this was accomplished in several steps by starting with simpler languages. We will follow a similar process as we deal with hybrid logic. So first we define a simple version of hybrid logic, called AHPL, based on the AMPL of [Gra21].

In the standard modal logics there is a clear distinction between the syntax: the formulas allowed in the language, which is the expansion of propositional logic with the modal operators, □ (for necessarily) and ◇ (for possibly) and the semantics: Kripke structures consisting of worlds and an accessibility relation between them. Essentially, hybrid logic adds some of the semantics to the syntax by the use of a locator function (usually called the satisfaction operator) @. While the interest in modal and hybrid logic is in the formation and meaning of consistent sets of formulas, our interest is in inconsistent sets of formulas as we attempt to measure their amount of inconsistency. Therefore, our approach to the semantics differs from the Kripke model approach.

### 3.1. The Syntax of AHPL

The symbols of AHPL are as follows. We start with an arbitrarily large set of propositional atoms, *a*, *b*, *c*, etc. and the propositional connectives ∧, ∨, and ¬, thereby obtaining propositional logic (PL) using the standard rules. We write α, β, etc. for PL formulas. AHPL also contains a separate arbitrarily large finite set *N* of nominals representing names for worlds. We write *i*, *j*, *k*, etc. for the nominals. We write *O*<sub>*i*</sub> to refer to a modal operator, either □ or ◇. Furthermore, the language also includes a locator function @.

Next we define the AHPL formulas by placing them into three groups. The first group consists of formulas using the locator function whose purpose is to add to the accessibility relation for nominals. The second group consists of formulas that may apply modal operators to PL formulas. The third group consists of formulas like the second group but preceded by the locator function.

**Definition 4.** An AHPL formula is either

1. a formula of the form @<sub>*i*</sub>◇j where *i*, *j* ∈ *N*, or

2. a PL formula α or a PL formula preceded by a sequence of modal operators: *O*<sub>1</sub>...*O*<sub>*r*</sub>(*α*), or

3. any formula in 2. in parentheses preceded by @<sub>*i*</sub>.

We will use the Greek letters like η and θ for formulas of AHPL. We also define the *depth* of a formula as the number of □ and ◇ operators. Thus all formulas of type 1 have depth 1, while formulas of the other types may have any nonnegative integer depth. For example, @<sub>*i*</sub>(*a* ∧ (¬*b* ∨ *c*)), a formula of type 3, has depth 0 and □◇(*b* ∨ ¬*c*), a formula of type 2, has depth 2. Also, for every AHPL formula η, except for a formula of type 1, we write *PL*(*η*) for α, the *PL* portion of the formula.
## 3.2. The Models of an AHPL formula

A key concept for the semantics of AHPL is the notion of a frame that is independent of the formulas under consideration. Accessibility in modal logic is usually expressed as a relation, but for our purpose it will be convenient to write it as a function. First we define the concept of an initial frame.

**Definition 5.** An initial frame of AHPL is a triple $F = \langle W, v_0, f \rangle$ where $W = V \cup N$, $V$ is a finite set such that $V \cap N = \emptyset$, $v_0 \in V$, and $f : W \to \mathcal{P}(W)$ is such that $f(v_0) \neq \emptyset$ and $|f(v)| \neq 1$ for all $v \in V$.

The set $V$ is the set of unnamed worlds. We will usually write the elements of $V$ as $v_0, v_1, \dots$. It is convenient to include all the nominals in every frame. The world $v_0$ acts as a starting point for the unnamed worlds. The accessibility relation is defined here as the function $f$ associating a set of worlds with every world. We will represent $f$ as a graph where $W$ is the set of vertices and the edges from a vertex $w$ go to the vertices of $f(w)$.

At least two worlds must be accessible from $v_0$ and for the unnamed worlds having a single accessible world is not allowed. The reason for not allowing a single accessible world is to be able to differentiate between $\diamond$ and $\square$. This rule is needed only for unnamed worlds as formulas of type 1 can set accessibility between named worlds. When we deal with a set of formulas that includes formulas of type 1, the initial frame is modified. We will usually write $F'$ for the later frames and just write "frame" instead of "initial frame" when there is no confusion.

The concept of a structure is an essential component of the semantics for AHPL.

**Definition 6.** A structure $T$ for a set of worlds $W$ is a function $T : W \to \mathcal{P}_{finite}(\mathcal{PL})$.

Thus our concept of a structure, unlike a Kripke structure, assigns to every world a finite set of propositional logic formulas. In particular, this applies to a frame as a frame defines a set of worlds. Our interest will be in structures that are models of a set of formulas for a given (initial) frame. Later we will need the concept of a substructure.

**Definition 7.** Given two structures $T$ and $T'$ over the same set $W$ of worlds, $T$ is a substructure of $T'$, written as $T \subseteq T'$, iff for all $w \in W$, $T(w) \subseteq T'(w)$.

Our interest is in finding structures that are models for a finite set of AHPL formulas for a particular frame. Our assumption is that for any frame $F$ the starting point is the initial structure $T$ where $T(w) = \emptyset$ for all $w \in W$. In particular, that structure is the unique model for the empty set of formulas. As we are including all nominals in a frame, for all structures $T$ almost every world will have $T(w) = \emptyset$. Hence when describing a structure we will indicate only those worlds $w \in W$ for which $T(w) \neq \emptyset$.

Next we show how to obtain the models of a single formula. Afterwards, we will show how to find the models of a set of formulas.

**Definition 8.** Let $F$ be a frame with set of worlds $W$. We define the model for an AHPL formula $\phi$ as a structure $T$ defined as follows. Start by initializing $T : T(w) = \emptyset$ for all $w \in W$.

When we get to sets of formulas, we will call the processing of formulas of type 1 the preprocessing step because it is done first. The effect of a formula of type 1, i. e., a formula of the form $@_i\diamond j$, in conjunction with other formulas, will be to change the frame $F$ to $F' = \langle W, v_0, f' \rangle$, where $f' = f \cup \{(i, j)\}$ and use the new frame to calculate the models of the other formulas. But a type 1 formula by itself is not meaningful; we say that it has no models.

For a formula of type 2 that is simply a PL formula $\alpha$, we set $T(v_0) = \{\alpha\}$ and for a formula of type 3 that has the form $@_i(\alpha)$ we set $T(i) = \{\alpha\}$.

For the version of type 2 and type 3 formulas with at least one modal operator, we proceed by induction on the depth of the formula. We go through only the case of type 2 and explain the modification for type 3. At each step we temporarily insert place holding numbers into various worlds as follows. Strictly speaking these are not structures as they contain numbers instead of formulas in worlds, but we will ignore them later; we use a new function $H$ for this purpose. We initialize $H(w) = \emptyset$ for all $w \in W$. We start with $O_1$. If $O_1 = \square$ (resp. $O_1 = \diamond$) then set $H(w) = H(w) \cup \{1\}$ for all (resp. some) $w \in W$ such that $w \in f(v_0)$.
<figure><img src="image_22.png" /><figcaption>**Figure 1:** The models of Example 1.</figcaption></figure>

Note that for $\square$ there is only one way to do this but for $\diamond$ there are $|f(v_0)|$ possibilities. We will need to consider each such possibility separately later.

For $k \ge 2$, the procedure goes as follows. Suppose that the process has been done for the first $k$ operators, i.e., $O_1, \dots, O_k$. Next, we work with $O_{k+1}$. This means that there may be multiple temporary structures that contain some numbers between 1 and $k$ in some worlds. The following process has to be done for each such temporary structure.

Fix such a temporary structure. Let $W_k = \{w \in W | k \in H(w)\}$. The following process must be done for each $w \in W_k$, say $w'$. If $O_{k+1} = \square$ (resp. $O_{k+1} = \diamond$) then set $H(w) = H(w) \cup \{k+1\}$ for all (resp. some) $w \in W$ such that $w \in f(w')$. Again, for $\square$ there is only one way to do this (for $w'$) but for $\diamond$ there are $|f(w')|$ possibilities. We will need to consider each such possibility separately later.

We proceed with this construction until $k = r$. At the end of this process there may be multiple temporary structures for which at some worlds $w$, $H(w)$ contains some numbers between 1 and $r$. For each such temporary structure $T$, for all $w \in W$ such that $r \in H(w)$, set $T(w) = T(w) \cup \{\alpha\}$ and set $T(w) = \emptyset$ for all other $w \in W$. After this step the $H$ function is ignored. We obtain a set of structures this way. These structures are the models of the formula. The only difference for formulas of type 3 is that in the first step $v_0$ is replaced by $i$. We write $\text{Models}(\eta)$ for the set of these structures for the formula $\eta$.

A model may be a substructure (submodel) of another model. We say that a model is a *minimal model* iff no model is a proper substructure. It turns out that for the inconsistency measures we define it suffices to consider only minimal models.

### 3.3. Models on Different Frames

In this section, we present two examples of the set of models for an AHPL formula on different frames. We use the formula $\eta = \square\diamond(a \wedge \neg b)$.

**Example 1.** Let $F = \langle W, v_0, f \rangle$ where $V = \{v_0, \dots, v_4\}$, $f(v_0) = \{v_1, v_2\}$, $f(v_1) = \{v_3, v_4\}$, $f(v_2) = f(v_3) = f(v_4) = \emptyset$. We compute the models $M_i$ of $\eta$ given above. We initialize $H(w) = \emptyset$ for all $w \in W$.

As $\eta$ is a formula of type 2, we set $H(v_0) = \{0\}$ and as the depth is 2 we need to go through 2 steps. In the first step, for $O_1 = \square$, we set $H(v_1) = H(v_2) = \{1\}$. At the next step, for $O_2 = \diamond$, we have 2 choices: either set $H(v_3) = \{2\}$ or set $H(v_4) = \{2\}$. As $r = 2$ there are no additional steps for operators. Thus there will be 2 models; either set $T(v_3) = \{a \wedge \neg b\}$ or set $T(v_4) = \{a \wedge \neg b\}$.

The two models, $M_1, M_2 \in \text{Models}(\phi)$, are as follows. $M_1(v_3) = \{a \wedge \neg b\}$ and $M_2(v_4) = \{a \wedge \neg b\}$. This is illustrated in Figure 1.

Next we modify the previous example by changing the frame.

**Example 2.** Let $F = \langle W, v_0, f \rangle$ where $V = \{v_0, \dots, v_4\}$, $f(v_0) = \{v_0, v_1, v_2\}$, $f(v_1) = \{v_2, v_3, v_4\}$, $f(v_2) = f(v_3) = f(v_4) = \emptyset$. The difference between this example and the previous one is that the accessibility functions for $v_0$ and $v_1$ were both expanded by one extra world. Again, we initialize $H(w) = \emptyset$ for all $w \in W$ and set $H(v_0) = \{0\}$. Then, in the first step, for $O_1 = \square$, we set $H(v_0) = H(v_1) = H(v_2) = \{1\}$. At the next step, for $v_0$ there are 3 choices: set $H(v_0) = \{1, 2\}$ or set $H(v_1) = \{1, 2\}$, or set $H(v_2) = \{1, 2\}$. For $v_1$ there are also 3 choices: set $H(v_2) = \{1, 2\}$ or set $H(v_3) = \{2\}$, or set $H(v_3) = \{2\}$.
$H(v_4) = \{2\}$. So as we put the formula $a \wedge \neg b$ into the worlds $w$ where $2 \in H(w)$, altogether there are 9 models. Next we list these and for convenience we abbreviate them by writing only the worlds that contain $a \wedge \neg b$ (as all other worlds contain the empty set) and obtain:

$M_1 = \{v_0, v_2\}$, $M_2 = \{v_0, v_3\}$, $M_3 = \{v_0, v_4\}$, $M_4 = \{v_1, v_2\}$, $M_5 = \{v_1, v_3\}$, $M_6 = \{v_1, v_4\}$, $M_7 = \{v_2\}$, $M_8 = \{v_2, v_3\}$, $M_9 = \{v_2, v_4\}$. To obtain the minimal models we eliminate $M_1, M_4, M_8, M_9$, as $M_7$ is a substructure for them. That leaves 5 minimal models:

$$
\begin{align*}
M_1(v_0) &= M_1(v_3) = \{a \wedge \neg b\}, \\
M_2(v_0) &= M_2(v_4) = \{a \wedge \neg b\}, \\
M_3(v_1) &= M_3(v_3) = \{a \wedge \neg b\}, \\
M_4(v_1) &= M_4(v_4) = \{a \wedge \neg b\}, \\
M_5(v_2) &= \{a \wedge \neg b\}.
\end{align*}
$$

**3.4. The Models of a Set of AHPL Formulas**

In general we will be considering the inconsistency of a set of AHPL formulas. For this purpose we
define an operation that merges structures.

**Definition 9.** Let $T_1, \dots, T_k$ be structures with the same set of worlds $W$. Their merge is
$\text{Merge}(\{T_1, \dots, T_k\} = \bigcup_{i=1}^k T_i(w)$ for all $w \in W$.

Thus *Merge* is an operator on a set of structures with the same set of worlds where each world
contains the union of all the PL formulas in that world for all the structures. This is used to define the
set of models for a set of AHPL formulas.

**Definition 10.** Let $F = \langle W, v_0, f \rangle$ be an initial frame and $S = \{\eta_1, \dots, \eta_k\}$ a set of AHPL formulas. Let $S^1 \subseteq S$ be the set of formulas of type 1 in $S$. We also write $S^*$ for the set of formulas of types 2 and 3. In case $S \neq \emptyset$ and $S = S^1$, all the formulas have type 1; we say that such a set has no models. Otherwise, we use $S^1$ for the preprocessing step as explained in Definition 8. That is, for each formula of type 1, $@_i \diamond j \in S'$, we expand the frame $F$ by adding $j$ to $f(i)$. The new frame $F'$ is the result of all the expansions using $S^1$. For the rest of the processing the new frame is used. Next, we obtain the models for each formula of $S^*$, noting that a frame expansion does not affect the models of formulas of type 2 and the order of processing the formulas does not make a difference. For instance, suppose that $S^1 = \{\eta_1, \eta_2\}$. We obtain the sets: Models($\eta_3$), . . . , Models($\eta_k$) using the expanded frame, $F'$. Then, each model of $S$ over $F'$ is obtained as Merge($M_3$, . . . , $M_k$) where each $M_i \in$ Models($\eta_i$). All the models of all the formulas must be used to obtain Models($S$).

Next we illustrate this definition on a simple example.

**Example 3.** Let $F = \langle W, v_0, f \rangle$ where $V = \{v_0, \dots, v_4\}$, $f(v_0) = \{v_1, v_2\}$, $f(v_1) = \{v_3, v_4\}$, and $f(v_2) = f(v_3) = f(v_4) = \emptyset$. Let $S = \{\Box\diamond(a \wedge \neg b), \Box(\neg a), \Box\Box(b), @_i(b \wedge \neg b \wedge (a \vee \neg c)), @_i\diamond j\}$. $S$ contains one formula of type 1, namely, $@_i\diamond j$. The preprocessing extends the frame $F$ to $F' = \langle W, v_0, f' \rangle$, where $f' = f \cup \{(i, j)\}$ (as a graph).

We already computed Models(□◇(a ∧ ¬b)) in Example 1. These models do not change in the expansion
of the frame. The formula □(¬a} has a single model M, where M(v₁) = M(v₂) = {¬a}. The formula
□□(b) has a single model M where M(v₃) = M(v₄) = {b}. The formula @ᵢ(b ∧ ¬b ∧ (a ∨ ¬c)) has a
single model M where M(i) = {b ∧ ¬b ∧ (a ∨ ¬c)}. Note that in this example, with no formulas of type
3 that include modal operators, the frame expansion induced by @ᵢ◇j does not change the result. So we
get 2 models:

$$
\begin{align*}
M_1(v_1) &= M_1(v_2) = \{\neg a\}, M_1(v_3) = \{a \wedge \neg b, b\}, M_1(i) = \{b \wedge \neg b \wedge (a \vee \neg c)\} \text{ and} \\
M_2(v_1) &= M_2(v_2) = \{\neg a\}, M_2(v_4) = \{a \wedge \neg b, b\}, M_2(i) = \{b \wedge \neg b \wedge (a \vee \neg c)\}.
\end{align*}
$$

**3.5. Inconsistency in AHPL**

In AHPL all occurrences of negation are inside PL formulas. Recall that for a given frame, a set of AHPL
formulas has a set of models. Each model has a set of worlds (dependent on the frame) each of which
contains a set of PL formulas. The inconsistencies in AHPL arise from the inconsistent sets of formulas
in individual worlds.

**Definition 11.** A structure *T* is consistent iff *T*(w) is consistent for all w ∈ *W*. For a given frame *F*, a set *S* of AHPL formulas is consistent iff it has a consistent model for *F*.

Thus every model *M* for an inconsistent set of AHPL formulas is such that for some world *w* ∈ *W*, *M*(w) is inconsistent. We will try to minimize the amount of computation needed to calculate inconsistency measures. The following will be useful for this purpose. Consider the two models we obtained for Example 3. The only difference is that *v*₃ and *v*₄ are interchanged.

**Definition 12.** Let $T_1$ and $T_2$ be two structures for the same frame. We say that $T_1$ and $T_2$ are equivalent iff there is a permutation $p$ of $W$ such that for all worlds $w \in W$, $T_2(p(w)) = T_1(w)$.

As long as an inconsistency measure does not distinguish between worlds, any pair of equivalent
models has the same measure. All the inconsistency measures that we define will have this property.

**3.6. Nonmonotonicity and Same Frame Subsets**

Classical logics such as propositional and first-order logic are monotonic. In fact, we also used Monotony
as a postulate for inconsistency measures. The symbol $|=$ is used for logical implication, meaning that
the formula on the right side is a logical consequence of (or is logically implied by) the set of formulas
on the left side.

**Definition 13.** A logic is called monotonic iff for all formulas $\phi$ and sets of formulas $S_1$ and $S_2$ (in the logic) if $S_1 \models \phi$ then $S_1 \cup S_2 \models \phi$.

The monotonicity of a logic means that the consequence of a set of formulas in the logic, *S*, is included in the consequence of every superset of *S*. For our purpose in measuring inconsistency, this means that if a set formulas is inconsistent, and hence its consequence is the set of all formulas, then every superset is also inconsistent. So if there is an inconsistent set of formulas in the logic that has a consistent superset, the logic is nonmonotonic. This is what we next show for AHPL.

**Proposition 1.** *AHPL is a nonmonotonic logic.*

*Proof.* We give an example where a set of formulas is inconsistent but a superset is consistent. Let the initial frame be $F = \langle W, v_0, f \rangle$ where $V = \{v_0, v_1, v_2\}$, $f(v_0) = \{v_1, v_2\}$, and $f(w) = \emptyset$ for all other $w \in W$. Let $S = \{@_i \diamond j, @_i \diamond (a), @_i \diamond (\neg a)\}$. $S$ has a single model $M$ where $M(j) = \{a, \neg a\}$. Hence $S$ is inconsistent. Next, let $S' = S \cup \{@_i \diamond k\}$. $S'$ has four models depending on which world, $j$ or $k$, is assigned which formula(s). Two of the models are consistent: for example, $M_1(j) = \{a\}$ and $M_1(k) = \{\neg a\}$. Hence $S'$ is consistent. $\square$

Inconsistency measures for various nonmonotonic logics have been studied in several papers including [UTB20] and [GP2024]. The former uses a general formulation for nonmonotonic logics oriented towards logic programming; the latter deals with graph databases. The way to handle such a case is to define a special type of subset and then use those subsets instead of all the subsets. These definitions use inconsistency as the criterion. But in our version we use a more specific concept for hybrid logic based on the frame.

**Definition 14.** A subset *S* of a set of AHPL formulas *S*′ is called a same frame subset, written *S* ⊆<sub>*sf*</sub> *S*′ iff *S*<sup>1</sup> = *S*′<sup>1</sup>. We write MIFS(*S*) for the set of minimal same frame inconsistent subsets of *S*.

A same frame subset, as the name implies, has the same frame as the set because it contains all the type 1 formulas of the set. Then, $S_1 \in \text{MIFS}(S)$ iff $S_1$ is an inconsistent same frame subset of $S$ and no proper subset of $S_1$ is a same frame inconsistent subset of $S$. The following result connects the models of a set with the models of its same frame subsets.
**Proposition 2.** Let $S \subseteq_{sf} S'$ be sets of AHPL formulas on the same initial frame $F$. Then for every model $M$ of $S$ there is a model $M'$ of $S'$ such that $M \subseteq M'$ and for every model $M'$ of $S'$, there is a model $M$ of $S$ such that $M \subseteq M'$.

*Proof.* By the hypothesis we can ignore formulas of type 1 as they are the same for $S$ and $S'$. Let $S^* = \{\eta_1, \dots, \eta_k\}$ and $S'^* = \{\eta_1, \dots, \eta_k, \dots, \eta_{k+h}\}$. By Definitions 9 and 10, each model $M'$ of $S'$ is obtained by a Merge of $k+h$ models, where each model is the model of a different formula of $S'^*$, that is, $M' = \text{Merge}(M'_1, \dots, M'_k, \dots, M'_{k+h})$. Similarly, each model of $M$ of $S$ is obtained by using the Merge operation on the models of $k$ formulas of $S^*$, that is, $M = \text{Merge}(M_1, \dots, M_k)$. But the models of $\eta_i$ for $S^*$ and $S'^*$ are the same. Each Merge operation adds some PL formula to one or more worlds. So every model of $S$, $M$, is enlarged to obtain a model of $S'$, $M'$, and so $M \subseteq M'$. Going in the opposite direction, for a model $M'$ of $S'$ obtained by $k+h$ merges, the model $M$ obtained by doing only the $k$ merges is such that $M \subseteq M'$. $\square$

We will mainly be using corollaries of this result.

**Corollary 1.** Let $S \subseteq_{sf} S'$ be sets of AHPL formulas on the same initial frame $F$. If $S'$ is consistent then so is $S$.

*Proof.* If $S'$ is consistent then by Definition 11 it has a consistent model $M'$ (on the frame obtained by adding the effect of $S'^1$ to $F$). By Proposition 2 $S$ has a model $M$ on the same frame such that $M \subseteq M'$, that is, $M(w) \subseteq M'(w)$ for all $w \in W$. As each $M'(w)$ is consistent, as PL is a monotonic logic, each $M(w)$ must also be consistent. Hence $M$ is consistent. $\square$

**Corollary 2.** Let $S \subseteq_{sf} S'$ be sets of AHPL formulas on the same initial frame $F$. Then $\text{MIFS}(S) \subseteq \text{MIFS}(S')$.

*Proof.* Let $S_1 \in \text{MIFS}(S)$. Then every model of $S_1$ is inconsistent, that is, if $M_1$ is a model of $S_1$ then for some world $w \in W$, $M_1(w)$ is inconsistent. The models of $S_1$ are the same whether we consider $S_1$ as a subset of $S$ or $S'$ and minimality also does not change. Hence $S_1 \in \text{MIFS}(S')$. $\square$

Using the concept of equal frame subsets we now rewrite the inconsistency measures and rationality postulates. In Definition 14 we already defined $\text{MIFS}(S)$. In analogy with PL, the *same frame problematic* formulas are formulas that appear in at least one minimal inconsistent same frame subset. We write $\text{sfProb}(S)$ for the set of same frame problematic formulas and $\text{sfFree}(S)$ for the set of same frame free, that is, not problematic, formulas of $S$.

**Definition 15.** *Inconsistency measures for a finite set of formulas, S, in AHPL:*

* $I_{Msf}(S) = |\text{MIFS}(S)|$.

* $I_{Psf}(S) = |\text{sfProb}(S)|$.

* $I_{Rsf}(S) = \min\{|S'| \text{ such that } S \subseteq_{sf} S \text{ and } S \text{ is consistent}\}$.

* $I_{Asf}(S) = |\text{Atoms}(\text{sfProb}(S))|$.

* $I_C(S) = \min\{|X||X \subseteq \text{Atoms}(S) \text{ whose weak interpretation (over all worlds) restores consistency}\}$.

* $I_B(S) = 1$ if $S$ is inconsistent and 0 otherwise.

We calculate these inconsistency measures for a set of AHPL formulas introduced earlier.

**Example 4.** For Example 3 we found 2 models. By Definition 12 these models are equivalent. Hence, as explained after Definition 12, it suffices to deal with a single model, say $M_1$. That is, $I_x(S) = I_x(M_1)$ for all inconsistency measures $I_x$. For $M_1$, $\text{MIFS}(M_1) = \{\{\square\diamond(a \wedge \neg b), \square\square(b), @_i\diamond j\}, \{@_i(b \wedge \neg b \wedge (a \vee \neg c)), @_i\diamond j\}\}$. Thus $I_{Msf}(S) = 2$; $I_{Psf}(S) = 3$; $I_{Rsf}(S) = 2$, $I_{Asf}(S) = 3$; $I_C(S) = 1$; and $I_B(S) = 1$. It suffices to delete one formula from each minimal inconsistent same frame subset to restore consistency. The reason for the $I_{Csf}$ value is that it suffices to interpret only b weakly in order to restore consistency.
<table><caption>**Table 2**
Postulate satisfaction of inconsistency measures for AHPL: ✓ means satisfied; ✗ means not satisfied.</caption><thead><tr><th rowspan="2"></th><th colspan="6">Postulate Satisfaction</th></tr><tr><th>I<sub>Msf</sub></th><th>I<sub>Psf</sub></th><th>I<sub>Rsf</sub></th><th>I<sub>Asf</sub></th><th>I<sub>C</sub></th><th>I<sub>B</sub></th></tr></thead><tbody><tr><th>Consistency</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><th>Variant Equality</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><th>SF-Monotony</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><th>SF-Penalty</th><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✗</td></tr><tr><th>SF-Free-Formula Independence</th><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✓</td></tr><tr><th>SF-Super-Additivity</th><td>✓</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td></tr></tbody></table>

**Definition 16.** *Formal definitions of postulates for inconsistency measures in AHPL:*

*   **Consistency:** $I(S) = 0$ iff $S$ is consistent.

*   **Variant Equality:** If $g: A \to A$ is an injective function, and $g(S)$ is the transformation of $S$ by $g$, then $I(g(S)) = I(S)$.

*   **SF-Monotony:** If $S \subseteq_{sf} S \cup S'$ then $I(S) \le I(S \cup S')$.

*   **SF-Penalty:** If $\eta \in \text{sfProb}(S)$ and $S \setminus \eta \subseteq_{sf} S$ then $I(S \setminus \{\eta\}) < I(S)$.

*   **SF-Free-Formula Independence:** If $\eta \in \text{sfFree}(S)$ and $S \setminus \eta \subseteq_{sf} S$ then $I(S \setminus \{\eta\}) = I(S)$.

*   **SF-Super-Additivity:** If $S \subseteq_{sf} S \cup S'$, $S' \subseteq_{sf} S \cup S'$, and $S \cap S' = \emptyset$ then $I(S \cup S') \ge I(S) + I(S')$.

### 3.7. Postulate Satisfaction in AHPL

Now we are ready to obtain the satisfaction results for the postulates on the inconsistency measures defined in the previous subsection.

**Theorem 1.** *The satisfaction results of the 6 postulates for the 6 inconsistency measures for AHPL are as given in Table 2.*

*Proof.* We start by observing that PL is a sublogic of AHPL in the sense that a set of PL formulas is also a set of AHPL formulas. Hence every violation of a postulate by an inconsistency measure (by a counterexample) in PL carries over to AHPL where for all inconsistency measures and postulates the same frame concept is not used. As the check marks in Table 2 are in the same place as in Table 1 we must show that for every postulate satisfied by an inconsistency measure in PL the same frame version of the postulate is satisfied by the same frame version of the inconsistency measure in AHPL. We do so by going in the order of the postulates first.

**Consistency** Suppose that $S$ is consistent. By its definition, $I_B(S) = I_{Rsf}(S) = 0$ and no atom has to be interpreted weakly, hence $I_C(S) = 0$. For the other measures consider that by Corollary 1 every same frame subset of $S$ is consistent. Hence $\text{MIFS}(S) = \emptyset$. Therefore, $I_{Msf}(S) = I_{Psf}(S) = I_{Asf}(S) = 0$.

Suppose that $S$ is inconsistent. By its definition, $I_B(S) = 1$. At least one formula must be removed to restore consistency; hence $I_{Rsf}(S) \ge 1$. Also, at least one atom has to be interpreted weakly, hence $I_C(S) \ge 1$. For the other measures consider that there must be at least one minimal inconsistent same frame subset, either $S$ or some same frame subset of $S$ by Corollary 1. Hence, $I_{Msf}(S) \ge 1$ from which we obtain that $I_{Psf}(S) \ge 1$ and $I_{Asf}(S) \ge 1$ also.

**Variant Equality** Variant Equality holds for all the measures we defined as there is no distinction made between the atoms for the purpose of inconsistency measure calculation.

**SF-Monotony** The result is immediate for $I_B$ on account of the same frame concept. Corollary 2 proves SF-Monotony for $I_{Msf}$, $I_{Psf}$, and $I_{Asf}$. Also, By Corollary 1 if $(S \cup S') \setminus S_1$ is consistent
then so is $S \setminus S_1$ which proves SF-Monotony for $I_{Rsf}$. Similarly, if the weak interpretation of the set of atoms $A$ makes $S \cup S'$ consistent, then the weak interpretation of some subset of $A$ must make $S$ consistent as well. Hence $I_C$ satisfies SF- Monotony.

**SF-Penalty** As explained above this needs to be proved only for $I_{Msf}$ and $I_{Psf}$. Let $\eta$ be as given in the statement for SF-Penalty. This means that there must be some $S_1 \in \text{MIFS}(S)$ such that $S_1 \setminus \{\eta\}$ is consistent. Using also Corollary 2 this means that the removal of $\eta$ reduces the size of $\text{MIFS}(S)$. Similarly, it reduces the size of $\text{sfProb}(S)$.

**SF-Free-Formula Independence** Let $\eta$ be given as in the statement of SF-Free-Element Independence. The result for $I_B$ follows from Corollary 1 in case $S$ is consistent and from the definition of sfFree if $S$ is inconsistent. The removal of $\eta$ from $S$ does not affect MIFS. This gives the result for $I_{Msf}$, $I_{Psf}$, and $I_{Asf}$. Finally, for $I_{Rsf}$ using the definition of sfFree the removal of $\eta$ has no effect on what else has to be removed to restore consistency.

**Super-Additivity** By Corollary 2, $\text{MIFS}(S) \cup \text{MIFS}(S') \subseteq \text{MIFS}(S \cup S')$ and as $S \cap S' = \emptyset$ the result follows for $I_{Msf}$ and $I_{Psf}$. Also, if $S_1$ (resp. $S'_1$) is a set of minimal size whose removal makes $S$ (resp. $S'$) consistent then $S_1 \cup S'_1$ must be removed from $S \cup S'$ to make it consistent. The result for $I_{Rsf}$ follows from $S \cap S' = \emptyset$.

# 4. Future Work

As was noted in [Gra21] the inconsistency measures of PL applied to modal logic cannot handle the distinction between the modal operators. Hence we will define inconsistency measures specifically for hybrid logic and show the satisfaction of the postulates for them. AHPL constitutes only a fragment of hybrid logic; essentially, the hybrid atomic formulas. We intend to go further, by applying propositional connectives to the AHPL formulas. Negation, in particular, can be interpreted in multiple ways within this context but the issue is not trivial even for the restriction to positive formulas. In this paper we have dealt only with absolute inconsistency measures: these measure the total amount of inconsistency in a set of formulas. We will also study relative inconsistency measures: these measure the proportion of the inconsistency in a set of formulas. The general aim is to define inconsistency measures for full hybrid logic that have good properties and give insight into the inconsistency of a set of hybrid logic formulas.

# Acknowledgments

This work is supported by FCT – Fundação para a Ciência e a Tecnologia through projects UIDB/04106/2025 at CIDMA and by National and European Funds through SACCCT-IC&DT - Sistema de Apoio à Criação de Conhecimento Científico e Tecnológico, as part of COMPETE2030, within the project BANKSY with reference number 15253. We also wish to thank the reviewers for helpful comments.

# References

[AC07] Carlos Areces and Balder ten Cate. "Hybrid Logics". In: *Handbook of Modal Logic*. Ed. by Patrick Blackburn, Johan van Benthem, and Frank Wolter. INRIA Lorraine, Nancy, France and Informatics Institute, University of Amsterdam. Amsterdam: Elsevier, 2007, pp. 821–868.

[AF21] Carlos Areces and Ramiro Fervari. "Axiomatizing Hybrid XPath with Data". In: *Logical Methods in Computer Science* 17.5 (2021), pp. 1–37. doi: 10.46298/lmcs-17(5:1)2021.
[AR00] Carlos Areces and Maarten de Rijke. "From Description to Hybrid Logics, and Back". In: *Advances in Modal Logic 3, papers from the third conference on "Advances in Modal logic," held in Leipzig, Germany, 4-7 October 2000*. Ed. by Frank Wolter, Heinrich Wansing, Maarten de Rijke, and Michael Zakharyaschev. World Scientific, 2000, pp. 17-36. doi: 10.1142/9789812776471\_0002. url: https://doi.org/10.1142/9789812776471%5C_0002.

[Bla00] Patrick Blackburn. "Representation, reasoning, and relational structures: a hybrid logic manifesto". In: *Logic Journal of the IGPL* 8.3 (2000), pp. 339-365.

[BT98] Patrick Blackburn and Mihaila Tzakova. "Hybridizing Concept Languages". In: *Annals of Mathematics and Artificial Intelligence* 24 (1998), pp. 23-49. doi: 10.1023/A:1018997920951.

[Gäi24] Daniel Găină. *Foundations of Logic Programming in Hybrid-Dynamic Quantum Logic*. 2024. arXiv: 2406.02085 [cs.LO]. url: https://arxiv.org/abs/2406.02085.

[Gra21] John Grant. "Measuring inconsistency in some logics with modal operators". In: *Studia Logica* 109 (2021), pp. 581-605.

[Mad+16] Alexandre Madeira, Renato Neves, Luís S. Barbosa, and Manuel A. Martins. "A method for rigorous design of reconfigurable systems". In: *Science of Computer Programming* 132 (2016), pp. 50-76.

[Mar+11] Manuel A. Martins, Alexandre Madeira, Razvan Diaconescu, and Luís S. Barbosa. "Hybridization of Institutions". In: *Algebra and Coalgebra in Computer Science (CALCO 2011)*. Vol. 6859. LNCS. Springer, 2011, pp. 283-297.

[Thi18] Matthias Thimm. "On the evaluation of inconsistency measures". In: *Measuring Inconsistency in Information*. Ed. by John Grant and Maria Vanina Martinez. College Publications, 2018, pp. 19-60.
# Towards Measuring Minimal Inconsistencies in Declarative Process Models

Sabine Nagel¹*, Patrick Delfmann¹

¹University of Koblenz, Universitätsstr. 1, 56070, Koblenz, Germany

**Abstract**

Declarative process models (DPMs) are prone to inconsistencies due to their constraint-based semantics. While existing techniques detect and measure such inconsistencies, they typically treat all minimal inconsistent subsets (MISes) equally, without means to assess their severity. This research-in-progress paper takes a first step toward MIS-level inconsistency measurement by proposing three categories of measures that allow the quantification of inconsistency based on behavioral and structural properties of individual MISes. These examples are intended to demonstrate the feasibility and value of MIS-level evaluation and provide the foundation for a future framework that supports more interpretable and actionable inconsistency management in DPMs.

**Keywords**

Inconsistency Measurement, Minimal Inconsistent Subset, Declarative Process Model, Declare

## 1. Introduction

Declarative process models (DPMs) provide a flexible alternative to imperative process models by defining behavior implicitly through constraints [1]. However, their reliance on logical rules makes them particularly vulnerable to inconsistencies and even a single contradiction can make an entire model unsatisfiable [2]. For example, in the modeling language DECLARE, which is based on linear temporal logic over finite traces (LTL<sub>f</sub>), the constraint set $C_1 = \{\text{INIT}(a), \text{RESPONSE}(a, b), \text{NOTRESPONSE}(a, b)\}$ is inconsistent and allows no valid execution trace, as all traces must start with activity *a*, and activity *b* is required and prohibited to eventually follow *a*. DECLARE uses simple trace semantics, where each position in a trace contains exactly one activity [3]. While this is realistic for many business scenarios, this restriction can lead to additional inconsistencies, e.g., $C_2 = \{\text{INIT}(a), \text{INIT}(b)\}$, as both *a* and *b* cannot occupy the first position in a trace.

While numerous approaches for inconsistency measurement have been introduced [4], they typically treat all minimal inconsistent subsets (MISes) equally and do not allow comparing or ranking them in terms of severity or complexity. This limits the usefulness of current measures for inconsistency prioritization and (interactive) resolution [5]. For example, a previous study [6] has shown that different MIS patterns require very different levels of cognitive effort from humans when trying to understand both *that* a problem exists and *why* a given constraint combination accepts no valid traces, which can be taken advantage of when designing inconsistency handling approaches with a strong human-in-the-loop focus [5].

Therefore, this research-in-progress paper takes a first step toward addressing this gap by proposing several categories of MIS-level measures (i.e., temporal, language-based, and structural measures) to serve as the starting point for a general framework for measuring and reasoning about MISes.

Section 2 introduces background on DPMs and inconsistency measurement. Section 3 presents initial MIS measure categories and respective measures. We conclude in Section 4 with a discussion of limitations and future research.

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

snagel@uni-koblenz.de (S. Nagel); delfmann@uni-koblenz.de (P. Delfmann)

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

0000-0003-4838-8246 (S. Nagel); 0000-0003-4441-0311 (P. Delfmann)

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

© 2025 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
## 2. Preliminaries and Related Work

### 2.1. Declarative Process Models

**Definition 1** (Declarative Process Model [1]). A declarative process model is a tuple DPM = (T, A, C), where

* T is a finite, non-empty set of templates, where each template is a predicate $\rho(x_1, ..., x_m) \in T$ on variables $x_1, ..., x_m$ (with $m \in \mathbb{N}$ the arity of $\rho$),

* A is a finite, non-empty set of activities,

* C is a finite set of constraints, namely pairs $(\rho(x_1, ..., x_m), \kappa)$ where $\kappa(x_1, ..., x_m)$ is a template from T, and $\rho$ is a mapping that, for every $i \in \{1, ..., m\}$, assigns variable $x_i$ to an activity $\rho(x_i) = a_i \in A$. For simplicity, we denote such a constraint with $\rho(a_1, ..., a_m)$.

Furthermore, the language L of a DPM over an activity set A is defined as the set of all finite traces $t = \langle a_1, a_2, ..., a_n \rangle$ with each $a_i \in A$, such that $t$ satisfies<fnref n="1" /> every constraint $c \in C$. Similarly, for any subset $C' \subseteq C$, the language of $C'$ (with respect to A), denoted $L(C')$, is the set of all finite traces $t = \langle a_1, ..., a_n \rangle$ over A such that $t$ satisfies every constraint $c \in C'$.

This work focuses on the declarative process modeling language DECLARE, which offers a set of predefined existence (unary predicates) and relation templates (binary predicates). The templates used in this paper, their corresponding LTL<sub>f</sub> formula and natural language descriptions are listed in Table 1. We refer to [1] for a comprehensive overview and formal semantics of DECLARE.

<table><caption>**Table 1**</caption><thead><tr><td>Constraint</td><td>LTL<sub>f</sub> Expression</td><td>Description</td></tr></thead><tbody><tr><td>INIT(x)</td><td>x</td><td>Each trace must start with x.</td></tr><tr><td>ATLEASTONE(x)</td><td>Fx</td><td>Each trace must contain at least one x.</td></tr><tr><td>CHAINRESPONSE(x, y)</td><td>G(x → Xy)</td><td>If x occurs, it must immediately be followed by y.</td></tr><tr><td>RESPONSE(x, y)</td><td>G(x → Fy)</td><td>If x occurs, it must eventually be followed by y.</td></tr><tr><td>NOTCHAINRESPONSE(x, y)</td><td>G(x → ¬Xy)</td><td>If x occurs, it must never immediately be followed by y.</td></tr><tr><td>NOTRESPONSE(x, y)</td><td>G(x → ¬Fy)</td><td>If x occurs, it must never eventually be followed by y.</td></tr></tbody></table>

Selected DECLARE constraints, their corresponding LTL<sub>f</sub> formulas, and natural language descriptions

### 2.2. Inconsistencies and Inconsistency Measurement

Let C be a set of constraints and L be its language, i.e., the set of traces accepted by C (cf. Definition 1). C is inconsistent if L is empty, denoted as $C \models \bot$. Furthermore, C is a minimal inconsistent subset (MIS) if there is no $C' \subset C$ so that $C \models \bot$. Let C be the set of all constraint sets and MI(C) be the set of MISes in C. A constraint c is called a free formula if for all MIS $\in$ MI(C), $c \notin$ MIS.

To enable expressing the severity of an (inconsistent) constraint set, so-called inconsistency measures have been introduced [7, 8, 9], where a higher value intuitively implies a higher degree of inconsistency.

**Definition 2** (Inconsistency Measure). An inconsistency measure I is a function $I: C \to \mathbb{R}_{\ge 0}^{\infty}$ that assigns a non-negative real value to a set of (declarative) constraints.

Over the years, a variety of measures has been introduced [4]. This includes the drastic inconsistency measure $I_d$ that only differentiates between consistent (0) and inconsistent (1), the MI-inconsistency measure $I_{MI}$ that counts the number of MISes, the problematic measure $I_p$ that counts the number of formulas that are in at least one MIS, the repair measure $I_r$ that represents the smallest number of constraints that must be removed to restore consistency, and the contension measure $I_c$ that measures the minimal number of activities with conflicting truth values when defining a three-valued interpretation. For a formal definition of these measures, we refer to [4]. In addition, various postulates have been proposed to capture the common properties of inconsistency measures, with the following ones being used to describe a basic inconsistency measure [10].

<footnote n="1">¹Due to space limitations, we refer to [1] for a full definition of constraint satisfaction.</footnote>
**Definition 3 (Basic Inconsistency Measure).** An inconsistency measure *I* is called a basic inconsistency measure if it satisfies the following properties, $\forall C, C' \in C, \forall \alpha, \beta \in A$:

* $I(C) = 0$ iff C is consistent (Consistency)

* $I(C \cup C') \ge I(C)$ (Monotony)

* If $\alpha$ is a free formula of $C \cup \{\alpha\}$, then $I(C \cup \{\alpha\}) = I(C)$ (Free Formula Independence)

* If $\alpha \vdash \beta$ and $\alpha \not\vdash \beta$, then $I(C \cup \{\alpha\}) \ge I(C \cup \{\beta\})$ (Dominance)

### 3. Measuring Minimally Inconsistent Constraint Sets

As mentioned, most traditional inconsistency measures are unable to differentiate between different MISes. This generally applies to all measures that satisfy the MinInc postulate, which states that if $M \in MI(C)$ then $I(M) = 1$ [11]. Consider the MISes in Table 2 and the respective values assigned by basic inconsistency measures. The only measure able to distinguish between the MISes is $I_p$, which measures inconsistency based on the size of the constraint sets. However, all MISes of the same size can still not be distinguished any further, as interaction patterns or structural density of the constraints are not considered.

<table><caption>**Table 2**</caption><thead><tr><th>MIS</th><th>Constraints</th><th>$I_d$</th><th>$I_{MI}$</th><th>$I_p$</th><th>$I_r$</th><th>$I_c$</th></tr></thead><tbody><tr><td>$M_1$</td><td>INIT(a), RESPONSE(a,b), NOTRESPONSE(a,b)</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td></tr><tr><td>$M_2$</td><td>INIT(a), CHAINRESPONSE(a,b), NOTCHAINRESPONSE(a,b)</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td></tr><tr><td>$M_3$</td><td>ATLEASTONE(a), RESPONSE(a,b), NOTRESPONSE(a,b)</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td></tr><tr><td>$M_4$</td><td>ATLEASTONE(a), CHAINRESPONSE(a,b), NOTCHAINRESPONSE(a,b)</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td></tr><tr><td>$M_5$</td><td>INIT(a), CHAINRESPONSE(a,b), NOTRESPONSE(a,b)</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td></tr><tr><td>$M_6$</td><td>INIT(a), CHAINRESPONSE(a,b), CHAINRESPONSE(a,c)</td><td>1</td><td>1</td><td>3</td><td>1</td><td>1</td></tr><tr><td>$M_7$</td><td>INIT(a), INIT(b)</td><td>1</td><td>1</td><td>2</td><td>1</td><td>1</td></tr></tbody></table>

Example minimal inconsistent constraint sets and respective inconsistency measure results

To enable a more granular and meaningful comparison of MISes, we propose a novel class of inconsistency measures that operate directly on individual MISes rather than on entire constraint sets. Let MI be the universe of all MIS.

**Definition 4 (MIS Measure).** An MIS measure $I^{MIS}$ is a function $I^{MIS}: MI \to \mathbb{R}_{\ge 0}^{\infty}$ that assigns a non-negative real value to a minimal inconsistent subset of constraints, with a higher value indicating a higher degree of local inconsistency.

In contrast to global inconsistency measures, most of the basic rationality postulates (cf. Definition 3) do not apply to MIS-level measures. This is because MIS measures are not intended to evaluate entire constraint sets, but rather to assess the internal characteristics of individual MISes. Nonetheless, we require that all MIS measures satisfy the *Dominance* postulate, as it ensures consistency with the intuition that stricter constraints contribute at least as much to inconsistency as their weaker counterparts.

#### 3.1. Temporal MIS Measures

Corea et al. [8, 3] introduce a paraconsistent three-valued semantics for DPMs, where inconsistencies are captured by assigning the value B (both true and false) to certain activities in trace positions. However, their measures depend solely on the number of such conflicting assignments, which would classify, for instance, $M_1$ and $M_2$ (cf. Table 2) as equally inconsistent, despite differences in when the conflict manifests during execution. To address this, we propose a class of temporal MIS measures that consider *how early* a conflict is expected to occur in a trace. The underlying intuition is that earlier conflicts constrain behavior more immediately and are therefore more critical to detect and resolve.

Consider $M_1$ and $M_2$ that both contain conflicting information on the relation between a and b, but the inconsistency in $M_2$ (involving CHAINRESPONSE and NOTCHAINRESPONSE) manifests immediately
after a, i.e., at the second position in the trace. In contrast, the inconsistency in $M_1$ (based on RESPONSE and NOTRESPONSE) may only manifest at the end of the trace, depending on if and when b eventually follows a. A similar observation can be made when comparing $M_1$ and $M_2$ with $M_3$ and $M_4$, respectively. While the latter use the same conflicting pairs of constraints, they replace INIT with ATLEASTONE, meaning a can occur anywhere as opposed to just in the first position. As a result, the point of conflict becomes dependent on the (unknown) position of a in the trace, which delays when the contradiction can be detected.

We formalize this intuition using the three-valued semantics for LTL$_f$ over fixed-length traces, as introduced in [8, 3]. Let A be a set of activities, and let $T = \{t_0, ..., t_{n-1}\}$ denote the positions of a fixed-length trace of length n. A three-valued interpretation $\hat{v}$ for LTL$_f$ is a function $\hat{v} : T \times A \rightarrow \{0, 1, B\}$ that assigns to each activity at each trace position a truth value with B indicating a contradiction.

**Definition 5** (Inconsistency Manifestation Point). Let $M \in MI$ and let $\hat{v}$ be a three-valued interpretation such that $\hat{v} \models_3 M$. A conflict is said to manifest at position $t_i$ if:

$$ \exists a \in A \text{ such that } \hat{v}(t_i, a) = B \quad \text{and} \quad \forall j < i, \forall a \in A, \hat{v}(t_j, a) \neq B. $$

To reason probabilistically about where conflicts emerge in the trace, we define a probability distribution over manifestation points. For each position $t_i \in T \cup \{t_n\}$, let $P_M(t_i)$ denote the probability that a conflict in M manifests at position $t_i$, based on a probabilistic trace model. Existence constraints are treated as known facts, which enables determining activity occurrence with certainty (e.g., INIT(a) ensures that a occurs at position 0). In contrast, relation constraints are evaluated assuming random activity occurrences, where each activity has equal probability of appearing at a given position, subject to the fixed trace length<fnref n="2" />. The positions $t_0$ through $t_{n-1}$ correspond to the actual positions in the trace, while $t_n$ represents the moment after the trace has been completed to capture conflicts that become observable only once the entire trace is known. We then define a linear weight function $w(t_i) = \frac{n+1-i}{n+1}$ that favors earlier manifestation points with $t_i \in T \cup \{t_n\}$.

**Definition 6** (Temporal MIS Measure). Let $M \in MI$. The temporal MIS measure is defined as:

$$ I_{\text{temp}}^{\text{MIS}}(M) = \sum_{i=1}^{n+1} w(i) \cdot P_M(i). $$

This measure captures the expected temporal proximity of an inconsistency within traces and allows structurally similar MISes to be distinguished based on when their conflicts are likely to arise.

**Example 1.** Consider the set of activities $A = \{a, b\}$ and the trace length $n = 3$. Then, the temporal inconsistency measure for $M_1 - M_4$ can be calculated as follows:

$$ I_{\text{temp}}^{\text{MIS}}(M_1) = 0.75 \cdot \frac{2}{4} + 0.5 \cdot \frac{1}{4} + 0.25 \cdot \frac{1}{4} \approx 0.56 \qquad I_{\text{temp}}^{\text{MIS}}(M_3) = 0.75 \cdot \frac{2}{7} + 0.5 \cdot \frac{2}{7} + 0.25 \cdot \frac{3}{7} \approx 0.46 $$

$$ I_{\text{temp}}^{\text{MIS}}(M_2) = 0.75 \cdot \frac{4}{4} = 0.75 \qquad I_{\text{temp}}^{\text{MIS}}(M_4) = 0.75 \cdot \frac{3}{7} + 0.5 \cdot \frac{3}{7} + 0.25 \cdot \frac{1}{7} \approx 0.57 $$

## 3.2. Language-Based MIS Measures

While temporal measures evaluate when inconsistencies occur, they only partially capture how restrictive the involved constraints are. For instance, consider $M_2$ and $M_5$ (cf. Table 2). Both involve a conflict between CHAINRESPONSE(a, b) and a negating constraint, and both manifest early in the trace. However, the negation in $M_5$ is NOTRESPONSE(a, b), which is stricter than NOTCHAINRESPONSE(a, b) in $M_2$. Therefore, the constraints in $M_5$ restrict behavior more strongly, which reflects a more severe inconsistency in behavioral terms. To capture such differences, we define a class of language-based MIS measures that quantify restrictiveness based on trace language size. We distinguish two perspectives: (i) the strictness of individual constraints and (ii) the behavioral recovery after removing a constraint from the MIS.

Let $L(c) \subseteq A^n$ denote the set of traces of length n that satisfy constraint c. Constraints with smaller languages are considered more restrictive.

<footnote n="2">²Other possibilities include calculating the probabilities based on activity occurrences in an actual event log.</footnote>