A Study of Unrestricted Abstract Argumentation Frameworks

1 Introduction

In the last two decades formal argumentation has become one major research area in Artificial Intelligence. The main reason for its popularity is its numerous fields of application ranging from nonmonotonic reasoning over multi-agent systems as well as aspects of knowledge representation to analysis tool for debates or dialogues (cf. [Bench-Capon and Dunne, 2007; Rahwan and Simari, 2009] for excellent overviews). Dung's abstract argumentation frameworks (AFs) [Dung, 1995], which are essentially directed graphs, play a dominant role in this field since they are frequently used as an evaluation component in deductive approaches to argumentation and as common basis for more complex abstract argumentation formalisms. It is therefore not surprising that many fundamental properties typically considered for nonmonotonic formalisms have been studied in recent years. Among others, central issues like replaceability [Oikarinen and Woltran, 2011], expressibility [Dunne et al., 2015] intertranslatability [Dvoˇr´ak and Woltran, 2011] as well as general modularity and locality properties were studied [Baroni and Giacomin, 2007; Baumann, 2011; Baroni et al., 2014]. As a matter of fact, almost all existing research on abstract argumentation is restricted to finite AFs, and thus there is no systematic analysis of abstract properties in the unrestricted case. Studying infinite AFs is far from being an academic exercise since it is motivated by the following observations/facts:

• actual infinity: The semantics of rule-based argumentation formalisms (like ASPIC [Prakken, 2010]) is usually

Christof Spanring

University of Liverpool, United Kingdom TU Wien, Austria christof.spanring@tuwien.ac.at

• given via the evaluation of induced Dung-style AFs. It was already observed that even a finite set of rules may lead to an infinite set of arguments (cf. [Caminada and Oren, 2014; Strass, 2015]). Consequently, after clarifying whether some argumentation semantics always provides one with a formal meaning one may ask for sound and complete procedures evaluating even infinite AFs.
• potential infinity: Allowing an infinite number of arguments is essential in applications where upper bounds on the number of available arguments cannot be established a priori. For instance, this applies to multi-agent dialogues [Belardinelli et al., 2015] as well as modeling approaches including time or action sequences [Baumann and Strass, 2012]. A central issue regarding dynamics is whether, and if so how, one may simplify a current framework in a semantically neutral way even if an unbounded number of arguments may arise in future.
• theoretical foundations: The first theoretical results as well as applications regarding infinite AFs can be traced back to Dung himself [Dung, 1995]. For instance, he showed how to model (possibly infinitely many) solutions of n-person games with the help of AFs. Surprisingly, this research direction was somehow neglected for nearly 20 years. In recent times infinite AFs are gaining attention [Baroni et al., 2013; Baumann and Spanring, 2015]. Besides the deeper understanding of how the nonmonotonic theory of abstract argumentation works, we believe that a profound analysis will be of great benefit for the argumentation community as well as other research fields using Dung-style AFs as modeling tool.

The paper is organized as follows. Sect. 2 provides the necessary background on AFs. Sect. 3 contains our main contributions, namely an analysis of unrestricted AFs w.r.t. computational aspects including the characteristic function as well as SCC-recursiveness, subset relations between semantics, replaceability, expressibility and intertranslatability. Moreover, for each considered topic we contrast our general results with former ones restricted to finite AFs. Due to the limited space we omit all proofs. Nevertheless, in almost all cases we included some short comments indicating how to prove the statement in question. Finally, in Sect. 4 we discuss our results and give some pointers for future work.

2 Background

More often than not the assumption of a certain reference set U, say universe of arguments is implicitly assumed and not explicitly stated in argumentation papers. For any AF F = (A, R) we require that A ⊆ U as well as R ⊆ A×A. In order to deal with AFs possessing infinitely many arguments we have to request that |U| ≥ ℵ0 = |N|. No further conditions are imposed. An AF F = (A,R) is called finite if |A| ∈ N, otherwise it is called infinite. Moreover, an AF F is called finitary if each of its arguments has only finitely many attackers. We use F as an abbreviation for the class of unrestricted frameworks, i.e. F contains all AFs w.r.t. U.

We say a attacks b in F = (A,R) whenever (a, b) ∈ R. An argument a ∈ A is defended by a set A′ ⊆ A in F if for each b ∈ A with (b, a) ∈ R, b is attacked by some a′ ∈ A′ in F. For a set E ⊆ A we use E + F or simply, E + for E ∪ {b | (a, b) ∈ R, a ∈ E}. If G = (B, S), we use A(G) as well as R(G) to refer to the first or second component of G, i.e. B or S, respectively. The set L(G) = {a ∈ A(G) | (a, a) ∈ R(G)} contains all self-attacking arguments. Finally, the union of two AFs as well as the restriction to a certain set C ⊆ U is defined as expected, i.e. F ∪G = (A(F)∪A(G), R(F)∪ R(G)) and F |C = (A(F ) ∩ C, R(F ) ∩ (C × C)).

An extension-based semantics σ : F → 22U is a function which assigns to any AF F a set of sets of arguments σ(F) ⊆ 2A(F) . Each one of them, a so-called σ-extension E, is considered to be acceptable with respect to F. For two semantics σ and τ we write σ ⊆ τ, if for any AF F, σ(F) ⊆ τ(F). Besides conflict-free and admissible sets (abbreviated by cf and ad) we consider a large number of mature semantics, namely naive, stage, stable, semi-stable, complete, preferred, grounded, ideal and eager semantics (abbreviated by na, stg, stb, ss, co, pr , gr , il and eg respectively). A recent overview can be found in [Baroni et al., 2011].

Definition 1 Let F = (A, R) be an AF and E ⊆ A.

• 1.E ∈ cf (F) iff for no a, b ∈ E, (a, b) ∈ R,
• 2.E ∈ na(F) iff E ∈ cf (F) and for no I ∈ cf (F), E ⊂ I ,
• 3.E ∈ stg(F) iff E ∈ cf (F) and for no I ∈ cf (F), E + ⊂I +
• 4.E ∈ stb(F) iff E ∈ cf (F) and E+ = A,

5.E ∈ ad(F) iff E ∈ cf (F) and E defends all its elements,

• 6.E ∈ ss(F) iff E ∈ ad(F) and for no I ∈ ad(F), E + ⊂I +

7.E ∈ co(F) iff E ∈ ad(F) and for any a ∈ A defended by E in F, a ∈ E,

8.E ∈ pr(F) iff E ∈ co(F) and for no I ∈ co(F), E ⊂ I ,

• 9.E ∈ gr(F) iff E ∈ co(F) and for no I ∈ co(F), I ⊂ E,

10. E ∈ σ(F) iff E ∈ ad(F), E ⊆ ⋂ τ(F) (for σ/τ ∈ {il/pr, eg/ss}) and there is no I ∈ ad(F) satisfying E ⊂ I ⊆ ⋂ τ(F). ♦

3 FromFinite to Unrestricted Frameworks

A priori it is unclear whether certain abstract properties satisfied for finite AFs carry over to unrestricted ones. To the best of our knowledge, the only properties which were already analyzed outside the realm of finiteness are universal and unique definedness of semantics (cf. [Baumann and Spanring, 2015] for an overview). These results vividly show that it makes an important difference whether we restrict ourselves to finite AFs. After a brief review of these results we will tackle a bunch of well-known and important issues in the theory of abstract argumentation.

3.1 Existence and Uniqueness

Already Dung considered the question of existence and uniqueness of extensions for unrestricted frameworks. For instance, he showed that preferred semantics guarantees at least one extension for any AF [Dung, 1995, Corollary 12]. Later on further results were achieved showing that existence and uniqueness of extensions may depend on the structure of the considered AFs [Weydert, 2011; Baumann and Spanring, 2015]. Table 1 provides a compact overview. An empty entry indicates a possible collapse of the semantics σ, i.e. for some AFs F we observe σ(F) = ∅. The entries "∃" or "∃!" indicate that for any AF F, |σ(F)| ≥ 1 or |σ(F)| = 1, respectively.

3.2 Computing the Grounded Extension

In contrast to Definition 1 Dung defined the grounded extension of an AF F as the ⊆-least fixpoint of the so-called characteristic function ΓF : 2A(F) → 2A(F) with E ↦→ {a ∈ A(F) | a is defended by E}. Moreover, he showed that this definition coincides with the ⊆-least complete extension [Dung, 1995, Theorem 25]. In case of finite (and even finitary) AFs the characteristic function is ω-continuous, implying that the least fixpoint equals ⋃i<ω ΓiF (∅) [Gabbay and Grossi, 2014]. However, in case of non-finitary AFs ΓF might not be ω-continuous but still remains monotonic. Consequently, ω-iteration might not be sufficient (cf. Example 1). Nevertheless, even in case of unrestricted AFs we may ensure the stepwise "computation" of the grounded extension by using ordinals beyond ω. The assertion can be shown with results from lattice theory.

Theorem 1 For any unrestricted AF F = (A,R) exists an ordinal α of size at most |A(F )|, s.t. gr (F ) = {⋃i<α ΓiF (∅)}. Example 1 (ω·2-iteration) Consider the following nonfinitary AF F = (A,R) where A = {ai, bi | i ∈ N} and

R = {(ai, ai+1), (bi, bi+1), (a2i, b1) | i ∈ N}.

Clearly, gr(F) = {{ai, bi | i ∈ N, i is odd}}. Let us compute some iterations. For finite ordinals n we have ⋃ni=1 ΓiF (∅) = {a1, ..., a2n-1}. Then, the first limit ordinal ω yields ⋃i<ω ΓiF (∅) = {ai | i ∈ N, i is odd} which does not coincide with the grounded extension. Pursuing with successor ordinals results in ⋃ω+n i=1 ΓiF (∅) = {ai | i ∈ N, i is odd}∪{b1, ..., b2n-1} and finally, after ω+ω, i.e. ω·2 - iterations we end up with a fixpoint coinciding with the grounded extension. Please observe that the cardinality of ω·2 equals ℵ0 = |A(F)| as promised by Theorem 1.

3.3 SCC-recursiveness

The concept of SCC-recursiveness plays a decisive role in the study of argumentation semantics. We mention two important facts: firstly, it guarantees desirable properties like directionality and secondly, it already gave rise for new semantics definitions like cf2 and stg2 which are able to overcome certain questionable results of former semantics (cf. [Baroni et al., 2005; Baroni and Giacomin, 2007; Dvoˇr´ak and Gaggl, 2012] for more details). Semantics satisfying SCC-recursiveness can be incrementally computed via a recursive schema which is based on the decomposition of AFs along their strongly connected components (SCCs). More precisely, the schema takes a base semantics σ, proceeds along the induced partial ordering and evaluates the SCCs according to σ while propagating relevant results to subsequent SCCs. This procedure defines a σ2 semantics. We say that a semantics τ is SCC-recursive if there is a base function σ, s.t. for any AF F, τ(F) = σ2(F). In case of finite AFs a bunch of semantics have been identified to be SCC-recursive (cf. [Baroni et al., 2005; Gaggl and Strass, 2014], Table 2 gives an overview).

In case of unrestricted frameworks we are faced with some difficulties in drawing conclusions. Firstly, infinite AFs need not possess initial SCCs which is granted for finite AFs. This makes checking whether a certain set is a σ2 -extension more complicated and due to the recursive definitions not that easy to handle. Secondly, even worse, even if initial SCCs are available there is no guarantee that the recursion will stop in finitely many steps.

Example 2 (Non-SCC-recursiveness) Consider the following finitary AF F = (A,R) where A = {ai, bi | i ∈ N} and R = {(bi, ai), (ai+1, ai), (ai, bi+1) | i ∈ N}.

Obviously, B = {bi | i ∈ N} ∈ τ(F) for any semantics τ ∈ {stb, ss, stg, pr, ad, co, na, cf , gr, il , eg}. Striving for a contradiction, suppose that there is base semantics σ, s.t.

τ(F) = σ2(F). Observe that the AF F possesses two SCCs, namely C1 = {b1} and C2 = A \ {b1}. For C1 we end up with the base case returning {b1} ∈ σ(F|C1 ). For C2 we have to consider the AF F ′ = F|C2\{a1} (since a1 is attacked by the SCC C1). Now, we have to determine whether B′ = {bi | i ∈ N, i ≥ 2} is a σ2-extension of F ′ . Note that this is equivalent to deciding whether B is a σ2 -extension of F . This means, the candidate set B leads to infinite recursion, i.e. the base case will never be considered although B ∈ τ (F ).♦

In contrast to all other semantics available in the literature, cf2 and stg2 were originally defined in terms of the recursive schema with naive and stage semantics as base functions. This means, SCC-recursiveness is given by definition but Example 2 shows that both semantics are not well-defined (in the sense of a function) in the general unrestricted case since we cannot determine whether B ∈ cf2 (F) or B ∈ stg2 (F), respectively.

Theorem 2 For unrestricted frameworks we have,

1. for any σ ∈ {stb, ss, stg, pr, ad, co, na, cf , gr, il , eg}, semantics σ is not SCC-recursive and
2. cf2 and stg2 are SCC-recursive.

Table 2 summarizes all results. The entries "SW", "S" and "W" in row certain AFs and column σ mean that for certain AFs the semantics σ is SCC-recursive and well-defined, SCCrecursive but not well-defined and well-defined but not SCCrecursive.

3.4 Subset Relations between Semantics

Note that the shorthand σ ⊆ τ requires that both semantics are total functions since a framework to which one of these semantics is undefined renders the subset shorthand undefined itself. Consequently, stb ⊆ stg2 ⊆ cf2 ⊆ na does not hold in general (Example 2) but it does in case of finite AFs as shown in [Dvoˇr´ak and Gaggl, 2012]. All other subset relations already known from finite AFs carry over to unrestricted AFs which can be shown with reasonable effort. The following figure summarizes the results in a compact way. For two semantics σ and τ , σ ⊆ τ iff there is a path from σ to τ in Figure 1. A red-highlighted arrow indicates that the corresponding subset relation is guaranteed for finite frameworks only.

3.5 Expansion Equivalence

In contrast to classical (monotone) logics ordinary equivalence is not sufficient to capture replaceability without loss of information (cf. [Baumann and Strass, 2016] for more detailed information on this issue). This means, analogously to other non-monotonic logics one may easily find two AFs F and G which possess the same σ-extensions but differ semantically if augmented by a further AF H . We say that both frameworks are expansion (or strong) equivalent if the latter is impossible.

Definition 2 Given a semantics σ. Two AFs F and G are

It was the main result in [Oikarinen and Woltran, 2011] that expansion equivalence can be decided by looking at the syntax only. More precisely, they introduced the notion of a kernel of an AF F which is (informally speaking) a graph where redundant attacks w.r.t. F are deleted or added and showed that syntactical identity of suitably chosen kernels characterizes expansion equivalence w.r.t. the considered semantics.

Definition 3 Let σ ∈ {stb, ad, gr, co}. For any AF F = (A, R) we define the σ-kernel F k(σ) = (A, Rk(σ) ) of F as:

Please note that all introduced kernels k are node- and looppreserving. This means, for any AF F, A(F)=A(F k ) and L(F)=L(F k ). We say thatk characterizes an equivalence notion ≡ if for any two AFs F and G, F ≡G iff F k =G k .

Theorem 3 [Oikarinen and Woltran, 2011; Baumann et al., 2016b; Gaggl and Woltran, 2013] For finite AFs, we have:

1. k(stb) characterizes ≡σE for any σ ∈ {stb, stg},
2. k(ad) characterizes ≡σE for any σ ∈ {ss, eg, ad, pr, il},
3. k(σ) characterizes ≡σE for any σ ∈ {gr, co} and
4. k(na) characterizes ≡σE for any σ ∈ {na, cf }.

We mention that all semantics considered in the literature satisfy regularity given that finite AFs are considered. Regularity means that expansion equivalent AFs have to share the same arguments [Baumann, 2012]. This is obvious for the semantics considered in Theorem 3 since all characterizing kernels are node-preserving. Moreover, since the background universe U contains infinitely many arguments it is always possible to expand finite AFs F and G by "fresh" arguments, i.e. arguments which do not occur in A(F) ∪ A(G). Clearly, dropping the finite assumption may rule out this possibility.

Example 3 (Non-regularity) Given c ∈ U, F = (U \ {c}, {(a, a) | a ∈ U \ {c}}) and G = (U, {(a, a) | a ∈ U \ {c}}). For any H we observe stb(F∪H)=stb(G∪H). In particular,

Example 4 (Non-coincidence) Let F =(U,{(a, a) | a ∈ U}) and G = (U, {(a, b) | a, b ∈ U, a ̸= b). Applying the grounded kernel does not change anything for either framework, i.e. F k(gr) = F and G = G k(gr) . Due to the absence of unattacked arguments we deduce ΓF(∅) = ΓG(∅) = ∅ implying that gr (F ∪ H ) = gr (G ∪ H ) = {∅} for any AF H . Consequently, F ≡gr E G although F k(gr) ̸= G k(gr) . ♦

The examples show that neither regularity, nor Theorem 3 remain true in general. It turns out that for some semantics we do not observe any differences if sticking to unrestricted AFs. In particular, this is the case for all considered semantics characterizable by the admissible or naive kernel. For the remaining semantics Theorem 3 becomes false but we may restore the characterization theorems if guaranteeing the existence of fresh arguments. We say that two frameworks F and G are jointly expandable (w.r.t. U) if U \ (A(F) ∪A(G)) ̸= ∅.

Theorem 4 For unrestricted AFs we have,

1. k(ad) characterizes ≡σE for any σ ∈ {ss, eg, ad, pr, il},
2. k(na) characterizes ≡σE for any σ ∈ {na, cf }.

For jointly expandable AFs we have,

1. k(stb) characterizes ≡σE for any σ ∈ {stb, stg} and
2. k(σ) characterizes ≡σE for any σ ∈ {gr, co}.

The main proof strategies are straightforward extensions of those presented in [Oikarinen and Woltran, 2011]. However, one has to pay attention whenever properties of finite AFs like jointly expandability or finite computation of grounded semantics are used. Table 3 summarizes all results. The entry "k" in row certain AFs and column σ indicates that for certain AFs expansion equivalence w.r.t. semantics σ is characterizable through k. A question mark represents two different things. First, the characterization problem is unsolved and second, it can be checked that none of the introduced kernels serve as a characterization. As an aside, in consideration of Example 3 no node-preserving kernel may serve as a characterizing kernel for stable semantics in case of unrestricted AFs.

3.6 Realizability

Realizability is concerned with the expressive power of logical formalisms. It is well-known that in case of propositional logic any finite set of two-valued interpretations is realizable. Given such a finite set I, we always find a set of formulae T , s.t. Mod(T) = I. In abstract argumentation we are equipped with a high number of semantics and it was shown that representational limits highly depend on the chosen semantics [Dunne et al., 2015]. We will see that it is essential which class of frameworks we consider if we want to compare the expressiveness of two semantics. In case of finite AFs it does not make a difference whether we use semi-stable or preferred semantics but it does if sticking to unrestricted frameworks.

We proceed with the formal definition of different σsignatures which collect all σ-realizable extension-sets of a certain class of AFs. Note that members of the compact versions require a witnessing framework without rejected arguments, i.e. any argument is contained in at least one extension.

Definition 4 The unrestricted, finite, compact and finite compact σ-signatures of a semantics σ are defined as follows:

1. Σσ = {σ(F) | F is an AF},
2. Σfin σ = {σ(F) | F is a finite AF},
3. Σcσ = {σ(F) | F is an AF ,A(F) = ⋃ σ(F)} and
4. Σc,fin σ = Σfin σ ∩Σcσ .

♦

Clearly, for any semantics σ, Σc,fin σ ⊆ Σcσ ,Σfin σ ⊆ Σσ. For a detailed discussion on the relation between finite and finite compact signatures see [Baumann et al., 2016a]. For some semantics both concepts coincide. Since finite AFs may realize finite extensions only, for any considered semantics σ a strict subset relation between finite compact and compact as well as finite and unrestricted signatures. A detailed analysis is part of future work. Let us recall a comparison of the expressiveness of the semantics in the realm of finiteness.

Theorem 5 [Dunne et al., 2015] For finite signatures,

1. Σfin na ⊂ Σfin stg = Σfin stb \ {∅} ⊂ Σfin ss = Σfin pr ,
2. Σfin cf ⊂ Σfin ad ⊂ Σfin co and
3. {{E} | E ⊆ U, |E| ∈ N} = Σfin σ ⊂ Σfin τ where σ ∈ {gr , il , eg} and τ ∈ {na, stb, stg, pr , ss, co}.

Sticking to unrestricted AFs makes a comparison more complex and for a long time it was unclear how to systematically achieve comparison results regarding expressiveness. It is the main result of this section that the relation between finite compact signatures is intimately connected to their relation in case of unrestricted signatures. More precisely, non-empty relative complements in case of finite compact signatures between two semantics carry over to their unrestricted versions.

Theorem 6 Given two semantics σ, τ ∈ {na, stb, stg, ss, pr , co, gr , il , eg, cf , ad} we have:

1. If Σc,fin σ \ Σc,fin τ ̸= ∅, then Σcσ \ Σcτ ̸= ∅ as well as
2. If Σcσ \ Σcτ ̸= ∅, then Σσ \ Στ ̸= ∅.

Now we are prepared for a comparison in case of unrestricted frameworks.

Theorem 7 For unrestricted signatures the following hold:

1. {{E} | E ⊆ U} = Σσ ⊂ Σna ⊂ Στ for σ ∈ {gr, il} and τ ∈ {stb, stg, ss, pr},
2. Σeg ⊂ Σpr ,
3. Σstb ⊂ Σσ for σ ∈ {stg, ss},
4. Σpr \ (Σstb ∪Σss ∪Σstg) ̸= ∅,
5. Σstg \ (Σstb ∪Σpr ∪Σss) ̸= ∅,
6. Σstb \ Σpr ̸= ∅,

In order to highlight the tremendous change we additionally present the relations in Venn-diagrams for some selected semantics. The dashed areas represent particular intersections for which the question of non-emptiness has to be left open.

3.7 Intertranslatability

Intertranslatability revolves around the idea of mapping one semantics to another. A motivation from [Dvoˇr´ak and Woltran, 2011] is to reuse a solver for one semantics for another. The main tool for this endeavour are functions mapping AFs to AFs, so-called translations formally defined as follows.

Definition 5 [Dvoˇr´ak and Woltran, 2011] Given two semantics σ, τ . A function f : F → F is called an exact translation for σ → τ, if σ(F) = τ(f(F)) for any AF F. It is called a faithful translation if for any AF F first |σ(F)| = |τ(f(F))| and second σ(F) = {S ∩ A(F) | S ∈ τ(f(F))}. ♦

Please note that for some semantics there are no exact translations available due to reasons inherent to those semantics. For instance, preferred semantics satisfies I-maximality, i.e. for any AF F , pr(F) forms a ⊆-antichain [Baroni and Giacomin, 2007]. This implies that an exact translation ad → pr can not exist since for F = ({a}, ∅) we observe {∅, {a}} = ad(F). Sticking to faithful translations provides us with a positive answer if we consider finite AFs only [Spanring, 2012, Translation 3.1.85]. However, the considered translation does not serve in the general unrestricted case and interestingly, we will see that any search for a suitable translation will never succeed.

We proceed with some preliminary exact translation results.

Theorem 8 Given an unrestricted AF F . Define Tr cf ad (F ) = G with A(G) = {a ∈ A(F) | (a, a) ̸∈ R(F)} and R(G) = {(a, b), (b, a) | a, b ∈ A(G), (a, b) ∈ R(F)}. We have that cf (F)=ad(G) and na(F)=σ(F) for σ∈{pr,ss,stg,stb}.

According to Table 1 grounded and ideal semantics result in exactly one extension even in case of unrestricted AFs. Eager semantics in contrast additionally exhibits the possibility of infinitely many extensions. In this case eager and preferred semantics coincide [Baumann and Spanring, 2015, Theorem 15]. Both results give rise for the following exact translations.

Theorem 9 Given an unrestricted AF F and let σ ∈ {gr , il }, then Trστ (F) = (S, ∅) is an exact translation for σ → τ with τ ∈ {co, pr, stg, ss, stb, gr, il , eg} and σ(F) = {S}. For eg → pr use Tr eg τ (F) in case |eg(F)| = 1 and id otherwise.

Remember that stable semantics may collapse even for finite AFs. This means, there are frameworks which do not provide any stable extension. In order to provide exact translations for stb → τ we have to construct an AF G, s.t. τ(G)=∅.

Example 5 (Semantical Collapse) Consider the non-finitary AF G = (A, R1∪R2∪R3) as indicated below. Formally, A = {pi, qi, ri | i ∈ N}, R1 = {(pi, qi), (qi, pi), (pi, ri) | i ∈ N}, R2 = {(rk, rk+1), (rk+1, rk+2), (rk+2, rk) | 0 ≡ k mod 3} and R3 = {(pi, pj), (pj , ri) | i < j, i ≡ j mod 3}.

Due to lack of space we omit a detailed semantical analysis. However, it can be checked that A = ⋃ pr(F) and more importantly, stb(F) = stg(F) = ss(F) = ∅. Since ⋂ ∅ = U we further infer eg(F) = pr(F). ♦

Theorem 10 Let σ ∈ {stg, ss, stb}, F an unrestricted AF. For G from Example 5 we have σ(Tr stb σ (F)) = stb(F) with

So far, we gave concrete translations only. The following theorem generalizes the finite version from [Dvoˇr´ak and Spanring, 2016, Section 6.1]. It establishes a close relation between realizability and intertranslatability: if τ is not less expressive than σ, then σ can be exactly translated to τ and vice versa.

Theorem 11 Given semantics σ, τ , we have Σσ ⊆ Στ if and only if there is an exact translation for σ → τ .

Note that this theorem implies that translational impossibilities entail differences in the expressive power. For instance, the following example shows that (in contrast to finite AFs) there is no faithful translation for ad → pr yielding Σad \Σpr ̸= ∅. Example 6 (Translational Impossibility) The AF F = (U, ∅) prohibits a faithful (and thus exact) translation Tr for ad → pr. This is due to the fact that firstly, U ∈ ad(F) enforces Tr(F) = F because of the lack of fresh arguments and secondly, pr (F ) = {U} entails Tr (F ) ̸= F . ♦

Instead of listing all translational (im)possibilities we provide figures illustrating all results in an eye-catching way. Figure 3b summarizes known results regarding faithful translations in the finite case [Dvoˇr´ak and Woltran, 2011; Spanring, 2012; Dvoˇr´ak and Spanring, 2016], augmented with obvious insights for unique status semantics il and eg. For semantics σ, τ, encirclement in the same component indicates bidirectional translations. An arrow from σ to τ means directional translations. If there is no directed path (for instance for na to cf , or for cf to gr), then there is no translation. Figure 3a features the same visualization for unrestricted AFs. Dropping the restriction assumption has some further consequences for the considered semantics, namely exact and faithful intertranslatability coincide. It is a part of future work to study which basic requirements a semantics has to fulfill, s.t. both forms of translations are essentially the same. However, in consideration of Theorem 11 we may interpret Figure 3a as a comparison of the expressiveness of the considered semantics. That is, Σσ ⊂ Στ if and only if there is a directed path from σ to τ. This interpretation supplements the former illustration depicted in Venn-diagram 2b.

Figure 3: Intertranslatability.

4 Discussion

We provided a first extensive overview of abstract properties in case of unrestricted frameworks. In almost all cases we observed substantial differences if leaving the realm of finiteness. However, it is an important observation of this study that some differences can be overcome if considering AFs expandable by a certain number of "fresh" arguments. For instance, in case of expansion equivalence we have seen that being jointly expandable is sufficient for restoring former results (Theorem 4). Moreover, regarding translations, we observed that for slightly restricted AFs F = (A,R), s.t. |A| ≤ |U \A| we are able to provide exact and efficiently computable translations from preferred to semi-stable semantics via Tr pr ss (F ) = F ′ = (A′ , R′ ) with A′ = A∪{a′ | a ∈ A} and R′ = R ∪ {(a, a′ ), (a′ , a′ ) | a ∈ A}. It is part of future work to figure out whether this restriction allows for similar translational possibilities as in case of finite AFs (cf. Figure 3b).

Another promising issue related to the presented research are alternative characterizations of cf2 and stage2 semantics as presented in [Gaggl and Woltran, 2013; Dvoˇr´ak and Gaggl, 2012]. These definitions avoid the recursive computation of subframeworks and it is an interesting question whether such alternative characterizations may overcome problems of undefinedness as discussed in Section 3.4.

Finally, it is already known that AFs can be seen as a restricted class of logic programs (LPs). More precisely, there is a standard translation Tr from AFs to LPs, s.t. σ(F) and τ(Tr(F)) coincide for certain pairs of semantics σ and τ [Strass, 2013, Theorem 4.13]. Consequently, one interesting research question is to which extent results regarding infinite AFs may contribute to a better understanding of infinite LPs.

Acknowledgements

This research has been supported by the Austrian Science Fund (FWF) through project P25521.