Initial Models and Serialisability in Abstract Dialectical Frameworks

1 Introduction

Ever since its introduction by Dung [1995], abstract argumentation has been an important and growing field in artificial intelligence in general and within the area of knowledge representation and reasoning in particular. Specifically, in the context of explainable artificial intelligence, argumentation represents a promising approach with numerous recent developments [Leofante et al., 2024]. An abstract argumentation framework (AF) is a directed graph, where the nodes represent abstract arguments and the edges represent attacks among them. Various extensions of AFs have been proposed in the literature [Brewka et al., 2014], but abstract dialectical frameworks (ADF) have emerged as a particularly powerful generalisation of AFs [Brewka et al., 2013]. In an ADF, the relations between the arguments are represented by acceptance conditions, i. e., (propositional) logical formulae that specify the conditions under which arguments may be accepted. This enables the representation of more complex relationships between arguments than simple attacks, such as collective attacks or support relations.

Formal semantics for both AFs and ADFs are given through functions that determine admissible sets of arguments, called extensions [Baroni et al., 2018], or, in the case of ADFs, three-valued models [Brewka et al., 2017]. In particular, the classical admissibility-based semantics of Dung have been generalised to ADFs [Brewka et al., 2013].

As the name suggests, ADFs are inspired by dialectics [Brewka et al., 2013]. An important element of dialectics is procedurality, i. e., the fact that arguments are put forward and are then followed by counter-arguments [Hage, 2000; Rescher, 1977]. While this aspect is modelled well on the syntactic level in ADFs, on the semantical side this aspect is somewhat lost, just like in the case of AFs [Verheij, 1996]. Consider, for instance, the ADF in Figure 1, where acceptance conditions of arguments are placed right above them (we will provide formal definitions in Section 2). We have that a and b can only be accepted if the other is rejected, meaning they form a sort of atomic conflict that must be resolved. Only after resolving this conflict, for example by accepting a and rejecting b, can we turn to the remaining arguments and evaluate them properly. Now, rejecting b directly implies that c must also be rejected and in turn that we shall accept d afterwards. On the other hand, if we accept b and reject a in the initial conflict, that implies that we accept c and subsequently reject d. If we only consider the resulting admissible model that assigns the respective truth values, we disregard this information about the reasoning process of the argumentation performed to arrive at the conclusion.

An approach to address the above-described problem is the notion of serialisability for AFs [Thimm, 2022]. It provides a non-deterministic construction scheme for extensions, where initial sets of the AF are selected iteratively. An initial set [Xu and Cayrol, 2018] is thereby defined as a non-empty, minimal admissible set, essentially representing a solution to an atomic conflict of the AF. An extension can then be represented by serialisation sequences, i. e., sequences of initial sets that represent an order in which the corresponding extension can be build. The serialisation sequences thus lend themselves well to build explanations for the extension that they represent inside the AF [Bengel, 2022]. Even more so, they also induce a very expressive semantical equivalence notion for AFs [Bengel et al., 2024].

In this work, we characterise initial models for ADFs and generalise the notion of serialisability to ADFs. In particular, we define initial models as the minimal, non-empty admissible models with respect to characteristic operator of [Brewka et al., 2013]. Based on that, we show that initial models coincide with the initial sets for those ADFs that correspond directly to AFs. Furthermore, we generalise the notion of serialisation sequences from AFs to ADFs and characterise admissibility as well as the preferred, complete, grounded and twovalued semantics of [Brewka et al., 2013] in terms of serialisation sequences for ADFs in general. Due to the higher expressiveness of the three-valued models of ADFs (compared to extensions), this yields fine-grained serialisation sequences that make explicit the process of both accepted and rejected arguments within acceptable models. That means, with our approach we incorporate the procedural aspect of dialectic argumentation directly into the semantics of ADFs. Finally, we also analyse the computational complexity of tasks related to initial models, which surprisingly turns out to be harder than the respective tasks for admissible models.

To summarise, the main contributions of this work are:

1. We define the notion of initial models for ADFs and show that they are a generalisation of initial sets in AFs (Section 3).
2. We define serialisability and serialisation sequences for ADFs, and analyse their properties (Section 4).
3. We characterise most admissibility-based semantics for ADFs via serialisation sequences (Section 5).
4. We provide complexity results for various tasks related to initial models in ADFs (Section 6).

In Section 2 we introduce the necessary background and Section 7 concludes the paper. Omitted proofs for all technical results can be found in an online appendix 1 .

2 Preliminaries

In the following, we introduce the necessary background on abstract argumentation frameworks [Dung, 1995] and abstract dialectical frameworks [Brewka et al., 2013].

2.1 Abstract Argumentation Frameworks

An abstract argumentation framework (AF) is a pair F = (A, R) where A is a finite set of arguments and R is a relation R ⊆ A×A. For two arguments a, b ∈ A, the relation aRb means that argument a attacks b. For a set S ⊆ A we may write SRa (resp. aRS) iff there is some c ∈ S with cRa (resp. aRc). We say that a set S ⊆ A is conflict-free iff for all a, b ∈ S it is not the case that aRb. A set S defends an argument b ∈ A iff for all a with aRb there is c ∈ S with cRa. Furthermore, a set S is called admissible (ad) iff it is conflict-free and S defends all a ∈ S. Let ad(F) denote the set of admissible sets of F.

Non-empty minimal admissible sets have been coined initial sets by Xu and Cayrol (2018).

Definition 1. For F = (A,R), a set S ⊆ A with S ̸= ∅ is called an initial set if S is admissible and there is no admissible S′ ⊊ S with S′ ̸= ∅.

With is(F) we denote the set of initial sets of the AF F.

1 https://doi.org/10.5281/zenodo.15357088

2.2 Abstract Dialectical Frameworks

Let At be a set of propositional atoms and LAt the propositional language over At closed under the usual connectives ¬, ∨, and ∧. An interpretation υ is a function that assigns to each atom in At a truth value true or false. Truth evaluation wrt. an interpretation is extended to arbitrary formulas in the usual way. If an interpretation υ satisfies a formula ϕ ∈ LAt, i. e., it assigns true to ϕ, we may also call υ a model of ϕ. If a formula ϕ has at least one model it is satisfiable. Furthermore, we denote with TAUTAt the set of tautologies and with UNSATAt the set of unsatisfiable formulae over At.

Definition 2. An abstract dialectical framework (ADF) is a pair D = (A, C) where A is a set of arguments and C is a set of propositional formulae {ϕa}a∈A over A, called acceptance conditions. 2

Reasoning in ADFs is performed via three-valued propositional interpretations that satisfy all acceptance conditions called models.

Definition 3. Let D be an ADF and υ : A → {t, f, u} is three-valued interpretation. For a propositional formula ϕ over A, we define υ(ϕ) inductively as follows

An interpretation υ is called a (three-valued) model of D, iff υ(a) = u or υ(a) = υ(ϕa) for all a ∈ A.

We denote with val3(D) the set of three-valued models of D and with υu the three-valued model that assigns u to all a ∈ A. We also define the set of all two-valued models of D as val2(D) = {υ ∈ val3(D) | ∀a ∈ A : υ(a) ̸= u}.

Furthermore, we also consider the inverse function υ-1 : {t, f, u} → 2A, meaning we denote with υ-1 (x) the set arguments assigned the truth value x by the interpretation υ for all x ∈ {t, f, u}. We will also write a ↦→ x instead of υ(a) = x for readability. a ↦ → x will be written in bold if x ̸= u to highlight ≤i-maximal assignments (see below).

We consider the following partial order ≤i according to information content: u <i t, u <i f and no other pair in <i. For a pair of three-valued interpretations υ1, υ2 : A → {t, f, u} we define

The consensus operator ⊓ combines two interpretations υ1 and υ2 into a new interpretation υ3, that coincides with υ1

2 Note that the original definition of ADFs [Brewka et al., 2013] includes the links between arguments explicitly, but here we assume them implicitly given by the acceptance conditions.

and υ2 wherever both interpretations coincide and assigns u otherwise. We define υ3 = υ1 ⊓ υ2 as

for all a ∈ A.

For some three-valued interpretation υ, we define the set of completions [υ]2 as

The set [υ]2 is then essentially the set of all two-valued interpretations that contain more information than υ.

For the semantic evaluation of an ADF D we then define the characteristic operator ΓD which computes for a model υ the consensus of all its completions for every argument.

Definition 4. Let D = (A, C) be an ADF and υ : A → {t, f, u} be a three-valued interpretation. We define the characteristic operator ΓD as

for all a ∈ A.

Analogous to the characteristic function of AFs, we utilise the characteristic operator to define the classical admissibility-based semantics for ADFs.

Definition 5. Let D = (A, C) be an ADF. We define υ0 = υu and υi = ΓD(υi-1) for all i ∈ N. Let k ∈ N be the smallest number with υk = υk-1. Then υk is called the grounded model of D.

Definition 6. Let D = (A, C) be an ADF. An interpretation υ : A → {t, f, u} is called

• an admissible model of D, iff υ ≤i ΓD(υ),
• a complete model of D, iff υ = ΓD(υ),
• a preferred model of D, iff υ is complete and there is no complete model υ′ with υ ≤i υ′ .

The stable semantics has been revised in [Brewka et al., 2013] compared to its original proposal in [Brewka and Woltran, 2010] and is defined as follows.

Definition 7. Let D = (A, C) be an ADF. A two-valued model υ of D is a stable model of D, iff υ-1 (t) equals υ-1 gr (t) of the grounded model υgr of the reduced ADF D↓υ = (υ-1 (t), C ′ ) such that for all a ∈ υ-1 (t) we set ϕ′a = ϕ[b/f : υ(b)=f] a .

With σ(D) we denote the set of σ-models of D for σ ∈ {ad, gr, co, pr, val2, st}.

Example 1. Consider the ADF D1 in Figure 2. The ADF has the grounded model

and two preferred models

All three models are complete and the latter two are also twovalued models. However, only υ2 is a stable model.

For a given argumentation framework F = (A,R), we define the corresponding ADF DF as follows.

Definition 8. Let F = (A, R) be an AF. Then, we define the ADF DF = (A, C), where A is the same set of arguments and C is defined as {ϕa = ∧ b∈a¬b}a∈A.

Furthermore, for some ADF DF = (A, C) and a given interpretation υ of DF, we define the unique extension Eυ corresponding to υ as

3 Characterising Initial Models in ADFs

To characterise initial models and serialisability for ADFs we build on the characteristic operator-based approach to admissibility in ADFs as reviewed in Section 2.2. It should be noted however that there exist other approaches to admissibility in ADFs, for instance the decisive outing formulation of [Polberg et al., 2013]. The concept of serialisability for semantics of AFs is closely related to the characteristic function [Thimm, 2022], i. e., it can be understood as a generalisation of the construction scheme of the grounded extension via applying the characteristic function iteratively. In other words, it generalises from iteratively adding unattacked arguments to iteratively adding initial sets as the atomic units. For that reason, we consider the characteristic operator-based approach to be the most suitable for defining serialisability.

Before characterising initial models for ADFs, consider again the translation from a model υ of an ADF DF to an extension Eυ of the corresponding AF F as defined in Equation (3). Notably, there are cases where multiple models υ of DF correspond to the same extension Eυ of F, as shown by the following example.

Example 2. Consider the ADF D2 in Figure 3. D2 has the following three admissible models:

Both υ2 and υ3 correspond to the preferred extension {a} of the corresponding AF F = ({a, b}, {(a, b)}). However, υ2 is not a complete model of D2 while υ3 is complete and ≤imaximal in DF and thus a preferred model.

To obtain a unique correspondence between extensions and models we define the reverse direction as follows. For some conflict-free set of arguments S ⊆ A of F we define the corresponding interpretation υS of DF via

Note that, according to Equation (4) the truth value f is assigned only if a attacks S. With that, we deviate, for good reason, from previous literature where f is assigned to an argument a if SRa, cf. [Brewka et al., 2017]. Note first that our translation is well-defined and indeed constructs an admissible model υS iff S is an admissible set of F.

Proposition 1. Let F = (A,R) be an AF and DF is the corresponding ADF. S ⊆ A is an admissible set of F, if and only if υS is an admissible model of DF.

Now, the reason for introducing the new translation from an admissible set to a three-valued model is rooted in the fundamental idea of initial sets, i. e., the fact that they represent a minimal resolution to an atomic conflict [Thimm, 2022]. Equation (4) ensures exactly that, i. e., the corresponding model υS will be ≤i-minimal, as we will show in the proof of Theorem 1 below.

Example 3. We continue Example 2. According to Equation (4), only the extension {a} corresponds to the unique admissible model

which is a ≤i-minimal admissible model of D2 (excluding the trivial model υu).

With that, we now define the initial models of an ADF as those models that are admissible and minimal wrt. the information ordering ≤i, excluding the model υu that assigns u to all arguments.

Definition 9. Let D = (A, C) be an ADF. An interpretation υ : A → {t, f, u} is called an initial model of D, iff υ is admissible with υ ̸= υu and there is no admissible model υ′ ̸= υu with υ′ <i υ.

We denote with is(D) the initial models of D. It follows then from Proposition 1 and the fact that Equation (4) indeed induces a ≤i-minimal model that the initial sets of any argumentation framework F correspond exactly to the initial models of the corresponding ADF DF .

Theorem 1. Let F = (A,R) be an AF and DF is the corresponding ADF. Then S ⊆ A is an initial set of F if and only if υS is an initial model of DF.

Example 4. Consider the ADF D3 in Figure 4. The initial models of D3 are

They correspond directly to the initial sets {a}, {c}, {d} and {e} of the associated AF, respectively.

As we can observe in the following example, if we do not restrict the acceptance conditions to simple attack relations, the initial models of an ADF can be quite different than the initial sets in AFs. In particular, we can have initial models in which only f and u are assigned, i. e., no argument is accepted, either because of an unsatisfiable acceptance condition or because of cyclic support relations. In fact, the latter case always leads to two initial models (assuming no further influences): one where the arguments in the support-cycle are assigned t and one where they are assigned f.

Example 5. Consider the ADF D4 in Figure 5. The initial models of D4 are:

To better investigate the relation between different models of an ADF, we introduce a notion of conflict between models. For two models υ1, υ2 of an ADF D = (A, C), we say that they are conflicting iff there exists an argument a ∈ A such that υ1(a) ̸= υ2(a) with υ1(a) ̸= u and υ2(a) ̸= u. With this notion of conflict we can now distinguish between three types of initial models for ADFs, similar to how it is done for AFs [Thimm, 2022].

Definition 10. For D = (A, C) and some initial model υ of D, we say that

1. υ is unattacked iff for all a ∈ A if υ(a)̸=u, then ϕa ∈ TAUTA ∪ UNSATA,
2. υ is unchallenged iff υ is not unattacked and there is no initial model υ′ that is conflicting with υ,
3. υ is challenged iff there is some model υ′ that is conflicting with υ and υ′ is an initial model.

We denote with is̸←(D), is̸↔(D), and is↔(D) the set of unattacked, unchallenged, and challenged initial models, respectively. Intuitively, unattacked initial models are not involved in any conflict while (un)challenged initial models are and the latter even conflicts with some other initial model.

Example 6. We continue Example 4 with the ADF D3 in Figure 4. We have that υ1 is an unattacked initial model. The models υ2 and υ3 are challenged initial models, both conflicting with each other. Finally, υ4 is an unchallenged initial model of D3.

Example 7. We continue Example 5 with the ADF D4 in Figure 5. The models υ1 and υ2 are challenged initial models, conflicting both on c and f. υ3 is unattacked initial and υ4 is the only unchallenged initial model of D4.

Analogously to the initial sets in AFs, we have that an unattacked initial model is always a singleton. There is however an important difference, while for AFs this singleton set obviously contains only one accepted argument, in the unattacked initial models for ADFs we can have that the single argument is evaluated to either t or f.

Corollary 1. Let D = (A, C) be an ADF and υ is an unattacked initial model of D. Then, we have that |{a ∈ A | υ(a) ̸= u}| = 1.

4 Serialisability in ADFs

We now characterise admissibility for ADFs in terms of serialisation sequences, i. e. sequences of initial models. Before we consider the notion of a serialisation sequence we generalise the notion of the reduct in the sense of [Baumann et al., 2020b] to ADFs. For some model υ, we define the υ-reduct Dυ of D as the ADF where all arguments that are evaluated to t or f by υ are removed and their occurrence in the acceptance condition of some other argument is replaced by ⊤ or ⊥ respectively. The intuition being that the reduct of an ADF D wrt. some model υ represents the part of the ADF that is unresolved by υ.

Definition 11. Let D = (A, C) be an ADF and υ : A → {t, f, u} is a three-valued interpretation. Then we define the υ-reduct of D as the ADF Dυ = (A′ , {ϕ′a }a∈A′ ) where

with x ∈ {t, f} and ϕ′a = ϕ[b/x : υ(b)=x] a .

Example 8. Consider again the ADF D3 in Figure 4 and the model

Then, the reduct wrt. υ is the ADF Dυ 3 = ({b, e}, C ′ ) with

Notably, while D3 correspond to an AF, the reduct Dυ 3 does not, because ϕ′b ∈ UNSATA′ .

It should be noted that this new definition of a reduct wrt. a three-valued model υ is different from the reduct used in the definition of the stable models in Definition 7. That definition is used for two-valued models, as the ADF where only arguments evaluated to t are retained and in the acceptance conditions all arguments that are evaluated to f are replaced by their truth value. The intention behind that approach is to verify whether a two-valued model υ is the grounded model of this reduct. In contrast to that, in our approach, where the intent is to obtain the unresolved part of the framework to iteratively compute a model for the original ADF. Meaning, using the reduct from Definition 11 with a two-valued model υ ∈ val2(D) will always yield the empty ADF Dυ = (∅, ∅).

Dual to the consensus operator ⊓, we define the union operator ⊔, which combines two non-conflicting interpretations υ1 and υ2 into an interpretation υ3 by unifying their value assignments. So in case there is no a with {υ1(a), υ2(a)} = {t, f}, we define υ3 = υ1 ⊔ υ2 as

for all a ∈ A. If υ1 and υ2 are in conflict (so there is a with {υ1(a), υ2(a)} = {t, f}) we leave υ1 ⊔ υ2 undefined.

We now define the concept of the serialisation sequence for ADFs as a series of initial models of the respective reducts.

Definition 12. A serialisation sequence for D = (A, C) is a sequence Y = (υ1, . . . υn) with υ1 ∈ is(D) and for each 2 ≤ i ≤ n we have that υi ∈ is(Dυ1⊔···⊔υi-1 ).

As an intermediary result we formulate a generalisation of Dung's fundamental lemma for AFs [Dung, 1995], stating that given non-conflicting admissible models υ1, υ2 of an ADF D, the union υ1 ⊔υ2 is itself an admissible model of D.

Lemma 1. Let D = (A, C) be an ADF and υ1, υ2 are admissible models of D. If υ1 and υ2 are not in conflict with each other, then υ1 ⊔ υ2 is an admissible model of D.

If υ2 is an admissible model of the reduct Dυ1 then υ1 and υ2 are non-conflicting and we can infer in that case that υ1 ⊔υ2 is an admissible model of D. The following corollary formalises this statement and is a generalisation of the modularisation property for AFs from [Baumann et al., 2020a].

Corollary 2. Let D = (A, C) be an ADF and υ1, υ2 are three-valued models. If υ1 ∈ ad(D) and υ2 ∈ ad(Dυ1 ) then υ1 ⊔ υ2 ∈ ad(D).

Note that serialisability is generally more expressive than (iterative) modularisation, since the former considers initial sets (resp. models), independently of the semantics [Bengel and Thimm, 2022]. Based on the above results, we can then show that the union of all initial models υi in some serialisation sequence Y = (υ1, . . . υn) corresponds directly to an admissible model. In particular, we can characterise the admissible models for ADFs in this way.

Theorem 2. A serialisation sequence Y = (υ1, . . . υn) induces an admissible model υ = υ1 ⊔ · · · ⊔ υn and for every admissible model there is at least one such sequence.

Note that, every serialisation sequence corresponds to exactly one admissible model, but an admissible model may have multiple corresponding serialisation sequences, each representing one particular order in which the admissible model can be constructed.

Interestingly, the serialisation sequences for ADFs provide an even more fine-grained sequence than we can obtain for AFs. Recall that ADFs enable us to have unattacked initial models that assign f to one argument and u to all others. In addition to that, the reduct for ADFs is more cautious and may contain arguments with an unsatisfiable acceptance condition. Thus, a serialisation sequence of an ADF not only provides a sequence of accepted arguments within some model (like in the case of AFs), but rather a sequence of both accepted and rejected arguments. This ties in nicely with the procedural aspect of dialectical argumentation and means that we bring this aspect to the semantical level of ADFs with our approach.

Example 9. Consider the ADF D5 in Figure 6. We have for instance the initial model

Now, in the reduct Dυ1 5 , we have ϕ′b ∈ UNSATA′ and thus the unattacked initial model

Note that, in the corresponding AF F b would be removed in the reduct F {a} since b ∈ a+ and thus the information that b can be rejected after accepting a would not be explicitly encoded in the serialisation sequence for the AF.

In the reduct Dυ1⊔υ2 5 we have two initial models

Then, we have that in the reduct Dυ1⊔υ2⊔υ3 5 only the argument c is left with ϕ′c = ⊤ and thus the initial model υ5 = {c ↦ → t}.

It follows then that (υ1, υ2, υ3, υ5) is an admissible serialisation sequence corresponding to the admissible model

Intuitively, the sequence then tells us the following. We can accept a unconditionally and after that rejecting b follows logically, but not necessarily. On the other hand, when accepting e we must necessarily reject d in the same step (as evidenced by υ3). Finally, after rejecting d the argument c can now be accepted.

With slight abuse of notation, we also have the serialisation sequence (υ1, υ2, υ4, υ6) with υ6 = {c ↦ → f} corresponding to the admissible model

Clearly there are many more admissible serialisation sequences of D5, for instance (υ3, υ1, υ2), (υ4, υ6) or (υ4).

Notably, this example shows that even for ADFs corresponding to AFs, the serialisation sequences of the ADF are more expressive than those of the corresponding AF.

5 Characterising Serialisable Semantics

Besides characterising admissible models through serialisation sequences, we can also characterise other admissibilitybased semantics for ADFs. For that, we utilise the distinction between initial models introduced in Definition 10. First, we consider the preferred semantics which can be characterised by the maximal serialisation sequences, i. e., the serialisation sequences (υ1, . . . υn) where the final reduct Dυ1⊔···⊔υn possesses no further initial models.

Theorem 3. Let D = (A, C) be an ADF and υ : A → {t, f, u} is an interpretation. We have that υ ∈ pr(D) if and only if there is a serialisation sequence (υ1, . . . υn) of D with υ = υ1 ⊔ · · · ⊔ υn and it holds that is(Dυ1⊔···⊔υn ) = ∅.

Example 10. We continue Example 5 with the ADF D4 in Figure 5. There is, for instance, the preferred serialisation sequence (υ3, υ5, υ6, υ7) with

With slight abuse of notation, we also have the preferred serialisation sequences (υ6, υ5, υ3, υ7) and (υ6, υ5, υ7, υ3), all corresponding to the same preferred model of D4. We obtain a serialisation sequence for a different preferred model if we, for example, include the initial model υ8 ∈ Dυ3⊔υ5 4 , with υ8 = {d ↦ → t, e ↦ → f}, i. e., the serialisation sequences (υ3, υ5, υ8, υ6) or (υ3, υ5, υ6, υ8). Finally, if we consider the initial model υ9 = {c ↦ → t, f ↦ → t} (instead of υ6) of D4 and the reduct wrt. different models, we can construct similar sequences for the two other preferred models of D4, e. g., (υ9, υ3, υ5, υ7) or (υ3, υ9, υ5, υ8).

We continue with the complete semantics, which can be characterised by the serialisation sequences that maximise only the unattacked initial models. Meaning, a serialisation sequence (υ1, . . . υn) is only complete iff there does not exist an unattacked initial model in the final reduct Dυ1⊔···⊔υn . This nicely generalises the intuition behind the complete semantics that a complete extension should contain every argument defended by it. So, for ADFs, a complete model should contain all of the information (in the sense of truth value assignments) that is implied by it.

Theorem 4. Let D = (A, C) be an ADF and υ : A → {t, f, u} is an interpretation. We have that υ ∈ co(D) if and only if there is a serialisation sequence (υ1, . . . υn) of D with υ = υ1 ⊔ · · · ⊔ υn and is̸←(Dυ1⊔···⊔υn ) = ∅.

For the grounded semantics, a serialisation sequence is then comprised only of unattacked initial models and there must be no further unattacked initial model left. As already mentioned, there may be multiple serialisation sequences corresponding to the unique grounded model of an ADF.

Theorem 5. Let D = (A, C) be an ADF and υ : A → {t, f, u} is an interpretation. We have that υ ∈ gr(D) if and only if there is a serialisation sequence (υ1, . . . υn) of D with υ = υ1 ⊔ · · · ⊔ υn and for all υi, i = 1, . . . , n, it holds that υi ∈ is̸←(Dυ1⊔···⊔υi-1 ) and is̸←(Dυ1⊔···⊔υn ) = ∅.

Example 11. We continue Example 10 with the ADF D4 in Figure 5. Besides the preferred serialisation sequences, which are obviously also complete, there are, for instance, the complete serialisation sequences (υ3, υ5, υ7) and (υ3, υ5, υ8). Note that, we have is̸←(Dυ3⊔υ5⊔υ7 4 ) = ∅ since υ6 and υ9 are challenged initial models. The same holds for Dυ3⊔υ5⊔υ8 4 .

Finally, we obtain the following characterisation for the two valued models of ADFs.

Theorem 6. Let D = (A, C) be an ADF and υ : A → {t, f, u} is an interpretation. We have that υ ∈ val2(D) if and only if there is a serialisation sequence (υ1, . . . υn) of D with υ = υ1 ⊔ · · · ⊔ υn and it holds that Dυ1⊔···⊔υn = (∅, ∅).

The following result for AF-like ADFs follows then directly from Theorem 6 and [Brewka et al., 2013].

Corollary 3. Let F = (A,R) be an AF and DF is the corresponding ADF. For any interpretation υ : A → {t, f, u} the following are equivalent:

1. There is a serialisation sequence (υ1, . . . υn) with υ = υ1 ⊔ · · · ⊔ υn and Dυ1⊔···⊔υn F = (∅, ∅),
2. Eυ ∈ st(F),
3. υ ∈ st(DF),
4. υ ∈ val2(DF).

It should be noted that, in the general case, Theorem 6 only characterises the two-valued models and not the stable semantics described in Definition 7. The difference lies in the handling of self-supporting arguments and it is an open question whether the stable semantics of [Brewka et al., 2013] can be characterised in terms of serialisation sequences.

6 Computational Complexity

We assume familiarity with the basic concepts of computational complexity, in particular with the basic complexity classes P, NP and coNP, cf. [Papadimitriou, 1994]. We also consider the classes ΣP2 and ΠP2 . The class ΣP2 = NP NP denotes decision problems that are solvable in polynomial time by a non-deterministic algorithm that has access to an NP-oracle and ΠP2 is the complementary class, i. e., ΠP2 = coNP NP . Furthermore, we consider the class P NP ∥ whose problems can be solved by a deterministic polynomial-time algorithm that can make polynomially many non-adaptive (or parallel) queries to an NP-oracle [Eiter and Gottlob, 1997]. Note that P NP ∥ is sometimes denoted as ΘP2 and is equivalent to P NP[log] [Papadimitriou, 1994].

We consider the following computational tasks, cf. [Strass and Wallner, 2015]:

Theorem 7 summarises the results of our analysis, with the exact complexity of VERis still an open problem. Table 1 gives an overview over the complexity results in comparison to related problems in AFs and ADFs.

Theorem 7.

1. VERis is in P NP ∥ and coNP-hard.
2. EXISTSis and EXISTS¬∅ is are ΣP2 -complete.
3. CREDis is ΣP2 -complete.
4. SKEPTis is ΠP2 -complete.

7 Conclusion

In this work, we defined initial models for ADFs as a notion of minimal acceptable models that resolve atomic conflicts. We showed that for ADFs that correspond to AFs the initial models coincide with the initial sets of the AF. Subsequently, we generalised the principle of serialisability of argumentation semantics to ADFs. Based on this principle we then characterised all of the characteristic operator-based semantics as well as the two-valued models for ADFs in terms of serialisation sequences, i. e., sequences of initial models of the respective reducts. These serialisation sequences then provide a fine-grained view into why the corresponding model is accepted. We concluded with some results on the computational complexity of task related to initial models.

In future work, we intend to study in more detail the relation of serialisability and the approximation fixpoint theorybased approach to ADF semantics [Strass, 2013; Strass and Wallner, 2015]. In that approach approximation operators for the characteristic operator ΓD are analysed, whose fixpoints correspond to admissible models. These operators then also allow for a step-by-step evaluation of an ADF. There also exist further semantics for ADFs that can be considered. A promising candidate is the strongly admissible semantics of [Keshavarzi Zafarghandi et al., 2022], which is serialisable for AFs. The stable semantics, as defined in [Brewka et al., 2013], is a relevant candidate, but its characterisation would require a new distinction for the initial models to identify and filter out models that require self-support. Completing the complexity results for the tasks related to initial sets is left for future work. For the development of algorithms for computing initial sets, the work on splitting ADFs [Linsbichler, 2014] is of particular interest, as it provides useful results on partitioning ADFs which helps to limit the search space.

Acknowledgements

We thank Johannes P. Wallner for some discussions related to the computational complexity of the problems discussed in this paper. The research reported here was partially supported by the Deutsche Forschungsgemeinschaft (grant 550735820).