Realizability of Three-Valued Semantics for Abstract Dialectical Frameworks

1 Introduction

Abstract dialectical frameworks (ADFs) [Brewka and Woltran, 2010] have been introduced as a generalization of Dung's argumentation frameworks (AFs) [Dung, 1995]. In contrast to AFs, where relations between arguments are restricted to bilateral attacks, the acceptance of a statement in an ADF may depend on an arbitrary function of the acceptance of other statements. This way, it allows for expressing more complex dependencies between arguments. Traditionally, the semantics of AFs is based on so-called extensions, i.e., sets of arguments that are in some sense compatible with each other. Extensions can also be seen as dedicated (twovalued) interpretations of propositional logic where each argument stands for a propositional variable. Caminada and Gabbay [2009] introduced a labeling based semantics for AFs, where every argument is assigned one of the labels in, out, or undec with respect to a labeling. Thus, a labeling can be seen as a three-valued interpretation. When an argument is in or out it means that it is accepted or rejected, respectively. The third label undec allows for expressing a point of view without an explicit judgment on the acceptance or rejection of the argument. Brewka et al. [2013] introduced various three-valued semantics also for ADFs that generalize corresponding labeling semantics for AFs. In this work, our aim is to characterize these semantics. In particular, we deal with the question whether a given set V of threevalued interpretations is realizable by an ADF, i.e., whether there is an ADF that has V as its set of admissible, complete, grounded, respectively, preferred interpretations. We address the problem by providing necessary and sufficient conditions that hold for V whenever there is an ADF realizing V under these semantics. In doing so, we continue a series of works on signatures of argumentation semantics [Dunne et al., 2014; Baumann et al., 2014; Dyrkolbotn, 2014; Strass, 2015]. This important line of research fosters the understanding of argumentation formalisms and is a prerequisite for studying diverse aspects of their expressiveness (cf. [Gogic et al., 1995; Dunne et al., 2014; Baumann et al., 2014; Strass, 2015; Eiter et al., 2013]). With suitable realizability characterizations at hand we can, e.g., compare what different formalisms (or one formalism under different semantics) can express, show whether a language is suitable to capture a given problem, or identify expressive subclasses of a formalism.

∗The German Research Foundation (DFG) supported this work under grant BR-1817/7-1.

While other previous works deal with AFs, Strass [2015] also addressed ADFs, investigating realizability under twovalued semantics, in particular stable and model semantics [Brewka et al., 2013]. We close a gap by characterizing the three-valued semantics introduced by Brewka et al. For admissible semantics we identify interpretations that must be admissible if all interpretations in a given set V are considered admissible. It turns out that V is realizable exactly when it already contains these induced interpretations. In the case of grounded and preferred semantics the characterization depends on simple syntactic conditions on V . For complete semantics, we reduce the existence of a realizing ADF to the existence of a characterization function and provide a complexity argument in favor of this solution. In addition, we provide a couple of simpler conditions that are necessary but not sufficient for complete realizability. Our results are based on constructive proofs and we discuss how to obtain an ADF realizing a set V whenever V is realizable.

As a first application of our characterizations we analyze whether there can be a join operator for ADFs that adheres to a certain desired requirement. Here, we get different results for different semantics, e.g., while the answer is positive for admissible semantics, we show that no such operator can exist for complete semantics.

2 Preliminaries

Unless stated otherwise, we assume that S is a fixed nonempty and finite set of statements. Intuitively, a statement can be seen as a position in a conversation and corresponds to an argument in the context of AFs. Following Brewka and Woltran [2010], an ADF is a tuple 〈S,L,C〉, where S is the set of statements and L ⊆ S2 is a set of links between statements. The idea is that the relation L determines for each statement s on which other statements its acceptance might depend. We call such a statement a parent of s and denote the set of parents of s by par(s) = {s′ | 〈s′ , s〉 ∈ L}. The final component C = {Cs | s ∈ S} of an ADF is a set of total functions Cs : 2par(s) → {t, f}, one for each statement s. Cs is called acceptance condition of s and if it maps some R ⊆ par(s) to t that means that s is accepted if all statements in R are accepted and all statements in par(s) \ R are rejected. We denote the set of all ADFs by D.

For convenience, we will use a more compact notation for ADFs, in which the parent relation L is implicit and acceptance conditions are represented by propositional formulas (acceptance formulas): We represent an ADF as above as a set D that contains one pair 〈s, ϕ〉 for each s ∈ S where ϕ is a propositional formula over S such that for each R ⊆ S, Cs(R) = t iff R |= ϕ (where R is viewed as a two-valued propositional interpretation and |= is defined as usual).

We define semantics for ADFs as in Brewka et al. [2013] using a slightly different notation. A (three-valued) interpretation v is a function v : S → {t, f, u}, assigning every statement one of the truth values true (t), false (f), or undefined (u). Next, we introduce some notation that helps us to work with interpretations. For an interpretation v we use the sets Tv = {s ∈ S | v(s) = t}, Fv = {s ∈ S | v(s) = f}, and Uv = {s ∈ S | v(s) = u} to collect the statements with the same truth values under v. TFv = Tv ∪ Fv is the set of defined statements under v and V denotes the set of all interpretations. We sometimes represent interpretations by listing their defined statements, where statements mapped to f are barred, e.g., the interpretation v with Tv = {a}, Fv = {b}, Uv = {c} is denoted by a¯b. Furthermore, the interpretation that maps all statements to u is denoted by vu. The information ordering ≤i between interpretations is defined as ≤i= {〈v, v′ 〉 ∈ V 2 | Tv ⊆ Tv′ , Fv ⊆ Fv′}. Thus, for two different interpretations v and v′ , v ≤i v′ means that v′ extends v by assigning more statements a classical truth value. We write v <i v′ if v ≤i v′ and v ̸= v′ . The semantics for ADFs we are interested in are defined via twovalued extensions of three-valued interpretations with respect to the information ordering. Hence, we identify three-valued interpretations that do not assign u to any statement with its corresponding two-valued interpretation. Such an interpretation assigns a truth value to a propositional formula in the standard way. By V2 = {v ∈ V | Uv = ∅} we denote the set of two-valued interpretations. Given an interpretation v, the set [v]2 = {v2 ∈ V2 | v ≤i v2} collects the two-valued extensions of v.

The central device for defining three-valued semantics for ADFs is the consensus operator that maps an interpretation v to another interpretation v′ , where, intuitively, v′ maps statements to truth values of their acceptance formulas on which the two-valued extensions of v agree: Given an ADF D, the consensus for an interpretation v is the interpretation ΓD(v), where TΓD(v) = {s | 〈s, ϕ〉 ∈ D, v′ (ϕ) = t for every v′ ∈ [v]2} and FΓD(v) = {s | 〈s, ϕ〉 ∈ D, v′ (ϕ) = f for every v′ ∈ [v]2}.

Definition 1 ([Brewka et al., 2013]) Let D be an ADF. An interpretation v is

• admissible for D if v ≤i ΓD(v);
• complete for D if v = ΓD(v);
• grounded for D if v is complete for D and every v′ ∈ V with v′ <i v is not complete for D;
• preferred for D if v is admissible for D and every v′ ∈ V with v <i v′ is not admissible for D.

By adm(D), com(D), grd(D), respectively, pre(D), we denote the set of admissible, complete, grounded, respectively, preferred interpretations for D.

It is known that every grounded and every preferred interpretation for a given ADF D is complete for D and that every complete interpretation is admissible for D [Brewka et al., 2013]. For intuition on the different types of semantics we refer to Baroni et al. [2011] who discuss them for AFs. Due to space limitations we present only selected proofs.

3 Characterizing Three-Valued Semantics

Before analyzing concrete semantics, we want to start with a general observation about the nature of three-valued semantics for ADFs. That is, there is no three-valued semantics under which every set of interpretations can be realized. More precisely, there is no function σ : D → 2V assigning a set of interpretations to an ADF such that for every V ⊆ V there is some ADF D ∈ D with σ(F) = V . This is due to a simple cardinality argument: there are more sets of three-valued interpretations than ADFs. There are 22n Boolean functions in n variables and, in order to build an ADF, one of these functions is required for each statement. As a consequence, the number of ADFs with n statements is 2n2n . On the other hand, for n statements, there are 3n three-valued interpretations. Therefore, 23n sets of interpretations exist. The claim holds as for every natural number n we have 2n2n < 23n .

Approaching from this negative result we now turn our attention to the question which sets can be realized under different semantics and how. As a teaser, we want to provide some numbers for ADFs with three statements on a side note: There are 16,777,216 ADFs with three statements and 134,217,728 corresponding sets of interpretations. From the latter, only 77,712 can be realized under admissible semantics, 16,618 under complete semantics, 2088 under preferred semantics, and, finally, only 27 under grounded semantics.

3.1 Admissible Semantics

In this section, we want to characterize sets V of interpretations that constitute the admissible interpretations of an ADF. We start with the observation that the admissibility of interpretations of an ADF require other interpretations to be admissible as well. For identifying them, we introduce the following notion that depends on a set of interpretations.

Definition 2 Let V ⊆ V be a set of interpretations and v ∈ V an interpretation. We call v adm-induced by V if for every s ∈ TFv and every v2 ∈ [v]2 there is some v′ ∈ V such that v′ ≤i v2 and v′ (s) = v(s).

V ind adm denotes the set of interpretations adm-induced by V .

Note that the definition implies that V ⊆ V ind adm; hence every element of V is adm-induced by V , but the converse does not hold for arbitrary sets of interpretations. If it does we call V adm-closed:

Definition 3 Let V ⊆ V be a set of interpretations. V is adm-closed if V ind adm ⊆ V .

It turns out that adm-closedness is a necessary condition for realizability under admissible semantics.

Proposition 1 For every ADF D, adm(D) is adm-closed.

Proof. Consider some interpretation v ∈ adm(D)ind adm. It suffices to show that v ∈ adm(D), i.e. that for all 〈s, ϕ〉 ∈ D where s ∈ TFv and all v2 ∈ [v]2 it holds that v2(ϕ) = v(s). Consider some arbitrary 〈s, ϕ〉 ∈ D where s ∈ TFv and some v2 ∈ [v]2. From v ∈ adm(D)ind adm, we get that there is some v′ ∈ adm(D) with v′ (s) = v(s) and v′ ≤i v2. But then, from v′ ∈ adm(D) and v2 ∈ [v′ ]2, we get that v2(ϕ) = v′ (s). Thus, also v2(ϕ) = v(s). □

Next, we show constructively that adm-closedness is also a sufficient condition for realizability. As we will see, if V is realizable under admissible semantics, only a particular subset of V is sufficient to determine all admissible interpretations. This subset is formed by the adm-defining interpretations of each statement as defined next.

Definition 4 Given V ⊆ V and s ∈ S, the set of admdefining interpretations of s in V is

As depicted in Figure 1, this set consists of the ≤i-minimal interpretations in which a Boolean value is assigned to s. Based on that notion, we can define acceptance formulas for statements that allow us to construct a canonical ADF for a given set of interpretations.

Definition 5 Let V ⊆ V be a set of interpretations. The canonical acceptance formula of a statement s ∈ S in V is given by ψV (s) = ψ+ V (s) ∨ ψV (s) where

The canonical ADF of V is given by

Note that CAN(V ) is a well-defined ADF.

Proposition 2 Let V be an adm-closed set of interpretations. Then, V = adm(CAN(V )).

Proof. (⊆) Towards a contradiction, consider some interpretation v ∈ V such that v ̸∈ adm(CAN(V )). From the latter we conclude that there is some s ∈ TFv and some v2 ∈ [v]2 such that v2(ψV (s)) ̸= v(s). Moreover, as v ∈ V and s ∈ TFv there must be some v′ ∈ V def adm(s) with v′ ≤i v ≤i v2 with v′ (s) = v(s). Consider the case that s ∈ Tv. Then, from v2(ψV (s)) ̸= v(s) follows that v2(ψ+ V (s)) = f . Consequently, also

Hence, there is some s′ ∈ TFv′ such that v′ (s′ ) ̸= v2(s′ ), being a contradiction to v′ ≤i v2. For the case that s ∈ Fv, we have v2(ψV (s)) = t and, in particular,

Again, there must be some s′ ∈ TFv′ such that v′ (s′ ) ̸= v2(s′ ) which contradicts v′ ≤i v2.

(⊇) Now assume v ∈ adm(CAN(V )) but v ̸∈ V . As V is adm-closed, v is not adm-induced by V . As a consequence, there is some s ∈ TFV and some v2 ∈ [v]2 such that (⋆) for each v′ ∈ V def adm(s) it cannot hold that v′ ≤i v2. From v ∈ adm(CAN(V )) we get that v2(ψV (s)) = v(s). Consider the case that s ∈ Tv. Then, from v2(ψV (s)) = t follows that v2(ψ+ V (s)) = t as we know that s ∈ Tv implies v2(ψV (s)) = f . Hence, by definition of ψ+ V (s), there is some v′ ∈ V def adm(s) such that v′ ≤i v2. This is a contradiction to (⋆). In case that s ∈ Fv it must hold that v2(ψV (s)) = f . Again, this means that there is some v′ ∈ V def adm(s) such that v′ ≤i v2, leading to a contradiction to (⋆). □

We are ready to characterize realizability for admissible semantics.

Theorem 1 Let V ⊆ V be a set of interpretations. There is an ADF D such that adm(D) = V iff V is adm-closed.

Proof. The 'if'-direction follows from Proposition 2 and the 'only if'-direction from Proposition 1. □

While adm-closedness characterizes sets of admissible interpretations, checking the property for a given set V is expensive: we need to check for every interpretation v that is not contained in V whether it is adm-induced by V . Following the definition of being adm-induced, this would require to find a v′ ∈ V with v′ ≤i v2 and v′ (s) = v(s) for every two-valued extension v2 of v and every s ∈ TFv.

In the remainder of the section, we show how we can narrow the search for such a v′ . To this end, we need the following notions.

Definition 6 Let v, v′ ∈ V be interpretations. Then,

• v and v′ are compatible if (Tv ∩Fv′)∪(Tv′ ∩Fv) = ∅;
• if v and v′ are compatible we denote the interpretation v′′ with Tv′′ = Tv ∪Tv′ and Fv′′ = Fv ∪Fv′ by v ⊔v′ .

Compatibility of two interpretations v and v′ means that they do not assign conflicting Boolean truth values to a statement. As a consequence, if v and v′ are compatible then they have a common successor with respect to the ≤i-relation. In particular, v ⊔ v′ is a well-defined interpretation that is such a successor. We can make the following observation.

Proposition 3 Let V ⊆ V be a set of interpretations and v′ , v′′ ∈ V such that v′ and v′′ are compatible. Then, v′ ⊔ v′′ ∈ V ind adm.

Proof. Consider some s ∈ TFv for v = v′ ⊔ v′′ and some v2 ∈ [v]2. We have v′ (s) = v(s) or v′′ (s) = v(s). Without loss of generality assume v′ (s) = v(s). The conjecture holds as v′ ≤i v2. □

We call a set V ⊆ V of interpretations upward-closed if v′ ⊔ v′′ ∈ V for all v′ , v′′ ∈ V that are compatible. The intuition behind the naming is that the property has an upward effect with respect to the information ordering in the sense that v′ and v′′ imply the presence of v′ ⊔v′′ which lies higher than v and v′ in the corresponding lattice (as in Figure 1).

The next result follows from Theorem 1 and Proposition 3.

Proposition 4 For every ADF D, adm(D) is upward-closed.

If we assume non-emptyness and upward-closedness for the given set of interpretations-properties that are easy to check, we only need to consider interpretations v′ with v ≤i v′ to determine whether an interpretation v is adm-induced.

Lemma 1 Let V ⊆ V be a non-empty upward-closed set of interpretations and v ∈ V. Then, v ∈ V ind adm iff for every v2 ∈ [v]2 there is an interpretation v′ ∈ V with v ≤i v′ ≤i v2.

Proof. (⇒) Consider some v2 ∈ [v]2 and the set V ′ = {v′ ∈ V | v′ ≤i v2, s ∈ TFv, v(s) = v′ (s)}. As elements of V ′ are mutually compatible, there is an interpretation v′2 such that Tv′2 = ⋃v′∈V ′ Tv′ and Fv′2 = ⋃v′∈V ′ Fv′ . Note that v′2 is the result of iteratively joining the elements of V ′ using the ⊔-operator. Hence, as V is upward-closed and V ′ ⊆ V we have by Proposition 3 that v′2 ∈ V . Clearly, v′2 ≤i v2. Consider some s ∈ TFv. As v ∈ V ind adm, there must be some v′ ∈ V with v′ ≤i v2 and v(s) = v′ (s). From that we get that v′ ∈ V ′ and, consequently, v′2 (s) = v(s). It follows that v′2 is the interpretation we are looking for because also v′2 ≤i v2 holds. (⇐) The conjecture follows immediately from Definition 2. □

In this light, we can reformulate the realizability result for admissible semantics as follows.

Theorem 2 Let V ⊆ V be a set of interpretations. There is an ADF D such that adm(D) = V iff

• (i) V is non-empty,
• (ii) upward-closed, and
• (iii) for every v ∈ V such that for every v2 ∈ [v]2 there is some v′ ∈ V with v ≤i v′ ≤i v2 we have v ∈ V .

The first condition makes explicit that every ADF has an admissible interpretation. In particular, it is easy to see that vu is admissible for every ADF. In contrast to upward-closedness, condition (iii) has an effect that is downward-directed with respect to the information ordering, i.e., the membership of the interpretations v′ in V enforces the membership of v that lies on a lower level of the corresponding lattice.

3.2 Complete Semantics

For complete semantics we start with a couple of necessary conditions for sets com(D), where D is an ADF. The first condition is downward-oriented. We will need the following counterpart of the ⊔-operator.

Definition 7 Let v, v′ ∈ V be interpretations. We denote the interpretation v′′ with Tv′′ = Tv ∩ Tv′ and Fv′′ = Fv ∩ Fv′ by v ⊓ v′ .

Proposition 5 Let D be an ADF and v′ , v′′ ∈ com(D). Then, there is some v ∈ com(D) with v ≤i v′ and v ≤i v′′ .

Note that v ≤i v′ and v ≤i v′′ means that v ≤i v′ ⊓ v′′ .

Example 1 Assume S = {a, b, c} and consider the ADF

D has three complete interpretations, vu, abc, and a¯b. Regarding Proposition 5, vu is the interpretation with vu ≤i abc ⊓ a¯b that has to be complete because abc and a¯b are. However, the interpretation abc ⊓ a¯b = a, is not complete.

The example shows that, unlike conditions (ii) and (iii) of Theorem 2 that fully determine the interpretations implied to be admissible, in Proposition 5, v′ and v′′ being complete implies only that one from a class of interpretations is complete.

The next proposition can be considered as an upwarddirected counterpart of Proposition 5.

Proposition 6 Let D be an ADF and v′ , v′′ ∈ com(D) compatible interpretations. Then, there is some v ∈ com(D) with v′ ⊔ v′′ ≤i v.

The difference to upward-closedness is that, similar as in Proposition 5, the implied complete interpretation v is not uniquely determined by v′ and v′′ .

The next three results, however, allow to infer concrete interpretations to be complete under special circumstances. If we consider two complete interpretation that share a direct successor with respect to the information ordering, then the latter is also complete.

Proposition 7 Let D be an ADF and v′ , v′′ ∈ com(D) such that Tv′ = Tv′′∪{s} and Fv′′ = Fv′∪{s} for some statement s ∈ S. Then, v′ ⊓ v′′ ∈ com(D).

Intuitively, in contrast to the general case (cf. Proposition 5), for the common direct successor of v′ and v′′ there is no further statement whose truth value under one of the two-valued extensions of v′ ⊓v′′ can spoil completeness. A similar argument justifies the following result.

Proposition 8 Let D be an ADF, v′2 , v′′ 2 ∈ V2 such that Tv′ = Tv′′ ∪ {s} or Tv′′ = Tv′ ∪ {s} for some statement s ∈ S, and v′2 , v′2 ⊓ v′′ 2 ∈ com(D). Then, v′′ 2 ∈ com(D).

The next necessary condition is upward-directed and infers a two-valued interpretation to be complete if there are ≤i-predecessors that are complete and jointly assign all statements a Boolean truth value. Note that the result is not an immediate consequence of Proposition 6.

Proposition 9 Let D be an ADF and V ⊆ com(D) such that v2 ∈ V2, Tv2 = ⋃v∈V Tv and Fv2 = ⋃v∈V Fv. Then, we have v2 ∈ com(D).

The following example shows that the necessary conditions expressed in Propositions 5-9 are not sufficient to guarantee realizability under complete semantics.

Example 2 Assume S = {a, b, c} and consider the set V = {vu, ¯a, b, ¯ c, ¯ab¯ c}. V fullfills the properties stated for com(D) in Propositions 5-9, nevertheless it can be shown (using the notion of a com-characterization we introduce below) that there is no ADF that has V as its complete interpretations.

Intuitively, the complete semantics is difficult to capture because there are many possible reasons why an interpretation is or is not complete. For example, in case an interpretation v is complete, for each statement s ∈ Uv, there must be one two-valued extension v′2 of v under which s is true and another v′′ 2 under which s is false. However, these v′2 and v′′ 2 are not necessarily complete and thus we do not know to which truth values they map s. Therefore, we cannot identify v′2 and v′′ 2 without knowing the ADF. Conversely, if v is an interpretation that is not complete, we do in general not know which statements are the culprit for that. We can, however, formulate necessary and sufficient conditions for a set V to be realizable that are not based on simple pattern-based checking of the presence or absence of interpretations in V . Completeness of an interpretation in an ADF depends on the truth values that its two-valued extensions assign to the acceptance formulas of each statement. We use the notion of a com-characterization, defined next, for providing such truth values (encoded as two-valued interpretation) without reference to an ADF.

Definition 8 Let V ⊆ V be a set of interpretations. A function f : V2 → V2 is a com-characterization of V if for each v ∈ V we have v ∈ V exactly when for every s ∈ S

• v(s) ̸= u implies f(v2)(s) = v(s) for all v2 ∈ [v]2 and
• v(s) = u implies s ∈ Tf(v′2 ) and s ∈ Ff(v′′ 2 ) for some v′2 , v′′ 2 ∈ [v]2.

Given a com-characterization for V we can construct an ADF that has V as its set of complete interpretations.

Proposition 10 Let V ⊆ V be a set of interpretations, f a com-characterization for V , and Df the ADF where the acceptance formula for each statement s is given by

Then, com(Df ) = V .

Proof. First, observe that for every two-valued interpretation v2 and every s ∈ S we have f(v2)(s) = v2(ϕs).

(⊆) Let v ∈ com(Df) be an interpretation and s ∈ S a statement. Consider the case that s ∈ Uv. Since v = ΓDf (v), by definition of ΓDf , there must be two two-valued interpretations v2, v′2 ∈ [v]2 such that v2(ϕs) = t and v′2 (ϕs) = f . By our initial observation, we get s ∈ Tf(v2) and s ∈ Ff(v′2 ). Now, consider the case that s ∈ TFv. Let v2 be a two-valued interpretation with v2 ∈ [v]2. Since v = ΓDf (v) we have v(s) = v2(ϕs). Therefore, by our observation it must also hold that f(v2)(s) = v(s). Thus we have v ∈ V as for every s ∈ S, v meets the respective condition of Definition 8.

(⊇) Consider an interpretation v such that v ̸∈ com(Df). We will show that v ̸∈ V . As v ̸∈ com(Df) we have v ̸= ΓDf (v). Let s ∈ S be a statement such that v(s) ̸= ΓDf (v)(s). Consider the case that s ∈ TFv. As v ̸= ΓDf (v), there must be some v2 ∈ [v]2 with v2(ϕs) ̸= v(s) and consequently f(v2)(s) ̸= v(s). Thus, by Definition 8 we have v ̸∈ V . Now consider the case that s ∈ Uv(s). As then ΓDf (v)(s) ̸= u we have that for some x ∈ {t, f} we have v2(ϕs) = x for each v2 ∈ [v]2. But then it must also hold that f(v2)(s) = x for each v2 ∈ [v]2. Again, by Definition 8 we have v ̸∈ V . □

Note that, unlike the canonical ADF for a set V that we defined for admissible semantics, the ADF Df is not unique for V but depends on a concrete f.

Example 3 Let D be the ADF from Example 1. A comcharacterization of com(D) is given by f:

Note that D corresponds to Df as obtained in Proposition 10.

The existence of a com-characterization is not only a sufficient but also a necessary condition for realizability.

Theorem 3 Let V ⊆ V be a set of interpretations. There is an ADF D such that com(D) = V iff there is a comcharacterization for V .

Proof. (Sketch) The 'if'-direction follows from Proposition 10. It remains to show that for any ADF D there is a com-characterization for com(D). In particular, we define the function fD as fD(v2)(s) = v2(ϕs) for every v2 ∈ V2 and s ∈ S with 〈s, ϕs〉 ∈ D. The remainder of the proof shows com(D) = V along the lines as com(Df) = V was shown in the proof of Proposition 10, but now the argument of the initial observation of the former proof (that is based on the structure of Df ) is provided by the definition of fD. □

One could ask whether checking the existence of a comcharacterization for checking whether V is realizable has advantages over directly checking the definition of realizability

.

itself, i.e., enumerating all ADFs and checking com(D) = V . In order to answer this question, we next give a complexity result. For the theorem we assume that the set S of all statements is not predefined.

Theorem 4 Given a finite, non-empty set S as the set of all statements and a set V ′ ⊆ V of interpretations, the problem of deciding whether there is an ADF D such that com(D) = V ′ is in NEXPTIME.

The proof of Theorem 4 is based on guessing a candidate for a com-characterization and checking whether it fulfills the conditions of Definition 8. The result shows that we do much better than in a na¨ıve approach where first an ADF D is guessed and then V = com(D) is tested by checking v ∈ com(D) for every interpretation. Remember that there are 3n many interpretations where n is the cardinality of S and note that checking whether a given interpretation is complete is hard for the complexity class DP (as shown by Strass and Wallner [2014]) which necessitates an NP-oracle call for each interpretation.

3.3 Grounded Semantics

As shown by Brewka et al. [2013], every ADF has a single grounded interpretation, in particular that is the minimal complete interpretation with respect to the information ordering. The existence of a unique minimal complete interpretation is also reflected by Proposition 5.

Lemma 2 For every v ∈ V, f s v is a com-characterization for {v}, where

The lemma implies that every singleton set of statements can be realized under complete semantics. For each ADF realizing such a set, grounded and complete semantics coincide. Therefore, also constructing such an ADF is similar as under complete semantics. We get the following realizability result for grounded semantics.

Theorem 5 Let V ⊆ V be a set of interpretations. There is an ADF D such that grd(D) = V iff V has cardinality 1.

Note that singleton sets of interpretations can be realized under all four semantics we consider.

3.4 Preferred Semantics

While the grounded interpretation is the minimal complete interpretation of an ADF, the preferred interpretations are those complete interpretations that are maximal with respect to the information order. At the same time they are the maximal admissible interpretations [Brewka et al., 2013]. From this we get that the set of preferred interpretations must be incomparable as defined next, since the set of admissible interpretations is upward-closed.

Definition 9 A set V ⊆ V of interpretations is incomparable if all two v′ , v′′ ∈ V with v′ ̸= v′′ are not compatible.

For selecting the ≤i-maximal interpretations from a set V ⊆ V of interpretations, we introduce the notation V ⊤ = {v ∈ V | v ≤i v′ for v′ ∈ V implies v = v′}.

The realizability result for preferred semantics can then be given as follows.

Theorem 6 Let V ⊆ V be a set of interpretations. There is an ADF D such that pre(D) = V iff V is non-empty, incomparable, and V = V ⊤.

For constructing an ADF for a given V that satisfies the conditions of Theorem 6, the idea is to create an adm-closed set V ′ with V = V ′⊤. Then, the canonical ADF CAN(V ′ ) for V ′ has V as its set of preferred interpretations. In order to obtain V ′ it suffices to start with V and iteratively add adminduced interpretations. In this process, whenever, the intermediate set V ′′ of interpretations is upward-closed, an arbitrary adm-induced interpretation can be added without changing the ≤i-maximal interpretations by Lemma 1. Whenever V ′′ is not upward-closed, there is some v′ , v′′ ∈ V ′′ with v′ ⊔ v′′ ̸∈ V ′′ . Then, one can safely add v′ ⊔ v′′ which is admissible induced by V ′′ and can be shown not to influence the ≤i-maximal interpretations either.

4 Semantical Consideration on Joining ADFs

Having characterizations for the realizability of a semantics is a starting point for studying the expressiveness of a formalism. For example, Strass [2015] uses realizability results to compare the expressiveness of ADFs, AFs, and logic programs under two-valued semantics. An application in answer-set programming is to decide whether a given program can be replaced by another from a syntactically simpler class and to construct the latter if possible [Eiter et al., 2013]. Our results are targeted towards similar applications, e.g., deciding whether a given ADF can be replaced by a bipolar ADF [Brewka and Woltran, 2010] with the same semantics or an AF under the corresponding labeling semantics [Caminada and Gabbay, 2009].

In this section we deal with another interesting problem that can be addressed using the new characterizations and is related to composing ADFs. In particular, we deal with the question whether for a given semantics σ, there can be a join operator ⊗ : D2 → D on ADFs such that for every two ADFs D1 and D2 we have σ(D1 ⊗ D2) = σ(D1) ∩ σ(D2). One could argue that this property, i.e., that the result of a join accepts exactly those interpretations that are accepted by both operands, is a reasonable requirement for a join operation in specific settings. As an example, consider cases where the two operand ADFs represent two separate discussions and the join should give a cautious summary on common conclusions. 1 The following result shows that there is such a desired ⊗-operator for admissible semantics.

Theorem 7 Let D1 and D2 be ADFs. Then, there is an ADF D such that adm(D) = adm(D1) ∩ adm(D2).

The proof is based on showing that the intersection of two adm-closed sets is adm-closed.

For complete semantics, on the other hand, we get a negative result. That is, given two ADFs D1 and D2, there might be no third ADF D such that com(D) = com(D1) ∩ com(D2). The following ADFs with three statements provide a counterexample for the general case:

1 Note that different operators for composing ADFs are appropriate for different purposes as argued by Gaggl and Strass [2014].

We have that com(D1) = {vu, ¯a,¯b, ¯a¯b¯ c} and com(D2) = {vu, ¯a, ¯b, ¯a¯b}. However, there is no ADF D with com(D) = {vu, ¯a, ¯b} because by Proposition 6, a common ≤i-successor of ¯a and ¯b would be missing.

As a side node, if S is restricted to at most two statements, there exists an ADF D with com(D) = com(D1)∩com(D2) whenever com(D1) ∩ com(D2) is non-empty.

For grounded semantics, given Theorem 5, it is easy to see that there is only an ADF that realizes grd(D1) ∩ grd(D2) if grd(D1) and grd(D2) coincide.

Finally, for preferred semantics, a join fulfilling the desired requirement is possible under the condition that the intersection of preferred interpretations is non-empty.

Theorem 8 Let D1 and D2 be ADFs. Then, there is an ADF D such that pre(D) = pre(D1) ∩ pre(D2) iff pre(D1) ∩ pre(D2) ̸= ∅.

5 Discussion and Conclusion

In this paper we addressed the question whether for a given set of three-valued interpretations, there is an ADF that realizes it. Our results lay the ground for investigating the expressiveness of ADFs under the four semantics we considered. Interestingly, works on realizability for AFs [Dunne et al., 2014; Baumann et al., 2014; Dyrkolbotn, 2014] do not cover complete semantics that turned out to be the hardest to characterize in our setting. For AFs, two variants of realizability have been considered: strict realizability [Dunne et al., 2014] that corresponds to the problems we studied, where the arguments that may be used in the realizing AF are pre-determined, and weaker forms [Baumann et al., 2014; Dyrkolbotn, 2014] where auxiliary arguments may be used. Considering auxiliary statements is also an interesting topic for further work on realizability for ADFs. A natural next step is investigating realizability for important subclasses of ADFs such as bipolar ADFs or AFs under labeling semantics. Together with our current results this would allow us to determine under what circumstances ADFs can be replaced by syntactically simpler ones.

Acknowledgments

The author wishes to thank Stefan Woltran, Thomas Linsbichler, Hannes Strass, and Stefan Ellmauthaler for informative discussions and useful pointers to related work.