The distinction between explicit and implicit information is essential in knowledge representation. In case of argumentation frameworks (AFs) the latter comes to light if dynamics are considered. The study of dynamic involvements is one of the most active fields in argumentation theory in recent years. In this paper, we further contribute to this topic via introducing two new orderings between AFs motivated by their carried implicit information. The orderings, called information and reachability order, are analyzed under lattice theoretical aspects.
representative of AFs sharing the same implicit information [
We fix a non-finite background set U , so-called universe. An argumentation framework (AF)
[
A semantics is a function σ : F → 22U with F ↦→ σ (F) ¦ 2A. This means, given an AF
F = (A, R) a semantics returns a set of subsets of A. These subsets are called σ -extensions. In
this paper we consider so-called stable, admissible, complete, grounded and preferred semantics
(abbr. stb, ad, co, gr, pr) already introduced by Phan Minh Dung in 1995 [
1. E ∈ stb(F) iff E ∈ cf (A) and E attacks any a ∈/ A \ E. 2. E ∈ ad(F) iff E defends all its elements, 3. E ∈ co(F) iff E ∈ ad(F) and for any a defended by E we have, a ∈ E, 4. E ∈ gr(F) iff E is ¦ -minimal in co(F) and 5. E ∈ pr(F) iff E is ¦ -maximal in co(F).
In this section we recall some basic notions from lattice theory [
A partial order f on a set M is a binary relation which is reflexive, antisymmetric and transitive. The pair (M, f ) is called partially ordered set. Finite partial ordered sets can be represented via so-called Hasse-diagrams, i.e. a drawing of its transitive reduction.
Definition 2. Given a partial ordered set (M, f ) and a subset X ¦ M. An element m ∈ M is called • upper bound of X iff x f m for all x ∈ X , and • supremum/join of X (sup(X )) iff it is the f -least upper bound of X , • lower bound of X iff m f x for all x ∈ X , and • infimum/meet of X (inf(X )) iff it is the f -greatest lower bound of X .
Remember that joins and meets need not to exist in general. There might be no upper/lower bounds at all, or no greatest/lowest bounds among them.
Definition 3. A partial order (M, f ) is called a lattice iff joins and meets exist for any twoelement sets {m1, m2} ¦ M. If only one of those is guarenteed we call it join-semilattice or meet-semilattice, respectively.
In case of propositional logic we have that sharing the same models guarantees intersubstitutability
in any logical context without loss of information. This property does not transfer to mainstream
non-monotonic logics [
Note that strong equivalence is indeed an equivalence relation, i.e. a binary relation being
reflexive, symmetric and transitive. In view of the fact that strong equivalence is defined
semantically it was a quite surprising result that it can be decided by looking at the syntax only [
Definition 5. Let σ ∈ {stb, ad, co, gr}. For any AF F = (A, R) we define the σ -kernel Fk(σ) = A, Rk(σ) as: 1. Rk(stb) = R \ {(a, b) | a ̸= b, (a, a) ∈ R}, 2. Rk(ad) = R \ {(a, b) | a ̸= b, (a, a) ∈ R, {(b, a), (b, b)} ∩ R ̸= 0/}, 3. Rk(co) = R \ {(a, b) | a ̸= b, (a, a), (b, b) ∈ R}, 4. Rk(gr) = R \ {(a, b) | a ̸= b, (b, b) ∈ R, {(a, a), (b, a)} ∩ R ̸= 0/}.
The following characterization results for finite AFs are taken from [
1. F ≡sσ G iff Fk(σ) = Gk(σ) for any σ ∈ {stb, co, gr}, 2. F ≡sτ G iff Fk(ad) = Gk(ad) for any τ ∈ {ad, pr}.
Example 1. Consider F as depicted below. According to Definition 5 we obtain the stable kernel Fk(stb) as well as the admissible kernel Fk(ad) as graphically presented. Note that redundancy regarding admissible semantics implies redundancy w.r.t. stable semantics. 3. R(Fk) ¦ R(F) and 4. Fk k = Fk. (node-preserving) (loop-preserving) (no further attacks) (idempotency)
We start with some basic properties which will be frequently used throughout the paper.
We proceed with the following two useful properties stating that subgraphs of kernels as well as intersections of kernels are already free of redundancy. Due to the limited space we will from now on present proofs for stable semantics only.
G ³ Fk, then Gk = G.
Proof. First, Gk ³ G is given by Proposition 2. Suppose towards a contradiction that G ̸³ Gk. Since arguments and loops are preserved we deduce an attack (a, b) ∈ R(G) \ R(Gk). Consider k = k(stb). Since (a, b) ∈/ R(Gk) we infer (a, a) ∈ R(G). The assumption G ³ Fk yields (a, b), (a, a) ∈ R(Fk) which is impossible in case of stable kernel. The other kernels can be handled in a similar way.
Proposition 4. For AFs F, G and k ∈ {k(stb), k(ad), k(co), k(gr)}, Fk ⊓ Gk = Fk ⊓ Gk k . Proof. Since Fk ⊓ Gk ³ Fk we apply Proposition 3 and obtain Fk ⊓ Gk k = Fk ⊓ Gk.
In the following we want to compare AFs with regard to their carried implicit semantical information. This means, we want to consider semantically relevant syntactical material only. Thus, the standard ordering ³ is not appropriate as it compares syntactical information without checking its meaningfulness. A suitable candidate is instead to compare the associated kernels of two AFs since kernels do not contain semantical redundant information. Hence, we will define the information order directly on the level of equivalence classes |F|σ = {G | F ≡sσ G} since all elements possess the same kernel.
Definition 6. Given a semantics σ ∈ {stb, ad, co, gr} and two AFs F and G. The information order f iσ on the associated equivalence classes is defined as: |F|σ f iσ |G|σ iff
Fk(σ) ³ Gk(σ).
Example 2. Consider again AF F from Example 1 as well as the AF G as depicted below. We observe that neither F ³ G, nor G ³ F.
However, if considering the associated stable kernels we are able to compare their carried information. More precisely, we have Fk(stb) ³ Gk(stb) implying that their corresponding equivalence classes are ordered as |F|stb f istb |G|stb.
Before continuing we have to show that f iσ does not depend on the particular choice of representatives.
Proposition 5. For any σ ∈ {stb, co, gr, ad}, f iσ is well-defined.
Proof. Given σ ∈ {stb, co, gr, ad} and |F|σ f iσ |G|σ for some AFs F, G. Assume now F′ ∈ |F|σ as well as G′ ∈ |G|σ . We have to show |F′|σ f iσ |G′|σ .
By Definition 6 we have Fk(σ) ³ Gk(σ). Since F′ ∈ |F|σ as well as G′ ∈ |G|σ we obtain F′ ≡sσ F and G′ ≡sσ G. According to Theorem 1 we derive F′k(σ) = Fk(σ) and G′k(σ) = Gk(σ). Hence F′k(σ) ³ G′k(σ) is implied showing |F′|σ f iσ |G′|σ as required.
The next proposition states that the induced information order is indeed a partial order as claimed.
Proposition 6. For any σ ∈ {stb, ad, co, gr}, f iσ is a partial order.
1. reflexive: For any AF F we have, Fk(σ) = Fk(σ). Hence, Fk(σ) ³ Fk(σ) is implied justifying |F|σ f iσ |F|σ . 2. antisymmetric: Consider two AFs F and G, s.t. |F|σ f iσ |G|σ as well as |G|σ f iσ |F|σ . For antisymmetry we have to prove |F|σ = |G|σ .
The given ordering entails Fk(σ) ³ Gk(σ) as well as Gk(σ) ³ Fk(σ). Thus, Fk(σ) = Gk(σ).
Consequently, F ≡sσ G and thus, F ∈ |G|σ proving |F|σ = |G|σ . 3. transitive: Consider three AFs F, G and H s.t. |F|σ f iσ |G|σ and |G|σ f iσ |H|σ . By definition we obtain Fk(σ) ³ Gk(σ) and Gk(σ) ³ Hk(σ). Since ³ is itself a partial order we derive Fk(σ) ³ Hk(σ) proving |F|σ f iσ |H|σ .
For illustration purpose we present the Hasse diagram for the information order regarding stable semantics. We restrict ourselves to AFs containing the arguments a and b only. Note that there are 24 = 16 syntactically different AFs. However, regarding strong equivalence we obtain 9 different equivalence classes only. Some equivalence classes consist of one element, e.g. |F|stb for F = ({a, b}, {(a, b)}). In contrast, the AF G = ({a, b}, {(a, a), (b, b)}) induces an equivalence class with 4 elements.
a a b b
a a b b a Let us turn now to another reasonable ordering. Consider a debate where the current state is represented by the AF F. One interesting question is whether a certain scenario G (and hence a certain output σ (G)) is reachable, or even more telling, not reachable in future. This means, is it possible to reach G from F via adding further information encoded by H. Clearly, semantical redundant information of F and G does not matter. Consequently, we will define the so-called reachability order on the level of strong equivalence classes. a b b b a a b b Definition 7. Given a semantics σ ∈ {stb, ad, co, gr} and two AFs F and G. The reachability order f rσ on the associated equivalence classes is defined as: |F|σ f rσ |G|σ iff ∃H : Fk(σ) ⊔ H k(σ) = Gk(σ).
Example 3. Let us reconsider Example 2. Regarding the information order we found |F|stb f istb |G|stb since Fk(stb) ³ Gk(stb). The following AF H justifies the same relation w.r.t. reachability, i.e. |F|stb f rstb |G|stb. Note that Fk(stb) ⊔ H k(stb) = Gk(stb) k(stb) = Gk(stb).
Proposition 8. For any σ ∈ {stb, ad, co, gr}, f rσ is a partial order.
Proof. Given σ ∈ {stb, ad, co, gr}.
1. reflexive: For any AF F, Fk(σ) = Fk(σ). Consequently, the empty AF H = ( 0/, 0/) serves as a witness for |F|σ f rσ |F|σ as Fk(σ) ⊔ H k(σ) = Fk(σ) k(σ) = Fk(σ). 2. antisymmetric: Consider two AFs F and G, s.t. |F|σ f rσ |G|σ as well as |G|σ f rσ |F|σ .
For antisymmetry we have to prove |F|σ = |G|σ , i.e. Fk(σ) = Gk(σ).
The given ordering entails the existence of two AFs H1 and H2, s.t.
Fk(σ) ⊔ H1 k(σ) = Gk(σ) (1) and Gk(σ) ⊔ H2 k(σ) = Fk(σ) (2). Both equations immediately entail A(F) ¦ A(G), L(F) ¦ L(G) as well as A(G) ¦ A(F), L(G) ¦ L(F). Thus, the initial frameworks and their associated kernels share the same arguments as well as loops.
Towards a contradiction we suppose (a, b) ∈ R Fk(σ) \ R Gk(σ) . First of all, we derive a ∈/ L(F). However, according to (1) (a, b) must be deleted in Fk(σ) ⊔ H1 if kernelized. This means, a ∈ L(H1) has to hold. However, this would imply a ∈ L(G) contradicting L(F) = L(G).
The case (a, b) ∈ R Gk(σ) \ R Fk(σ) can be shown in a similar way. Just use equation (2) instead of (1). 3. transitive: Consider three AFs F, G and H s.t. |F|σ f rσ |G|σ and |G|σ f rσ |H|σ . By definition we obtain the existence of two AFs I1 and I2, s.t. Fk(σ) ⊔ I1 k(σ) = Gk(σ) and Gk(σ) ⊔ I2 k(σ) = Hk(σ). We have to show |F|σ f rσ |H|σ , i.e. the existence of a witness I3, s.t. Fk(σ) ⊔ I3 k(σ) = Hk(σ).
Due to Proposition 2 we have A
Fk(σ) ⊔ I1 ⊔ I2 k(σ) = L Hk(σ) .
Fk(σ) ⊔ I1 ⊔ I2 k(σ)
=
We will show now = R Hk(σ) .
Consider I3 = I1 ⊔ I2.
A Hk(σ) R
as well as L
Fk(σ) ⊔ I1 ⊔ I2 k(σ) Consider σ = stb.
a) Let (a, b) ∈ R
Fk(σ) ⊔ I1 ⊔ I2 k(σ) . We infer (a, a) ̸∈ R Fk(σ) , R (I1) , R (I2) and hence, (a, a) ̸∈ R
Fk(σ) ⊔ I1 k(σ)
= R Gk(σ) . i. Let (a, b) ∈ R Fk(σ) ⊔ I1 : Since (a, a) ̸∈ R Fk(σ) ⊔ I1 we deduce (a, b) ∈ R Fk(σ) ⊔ I1 k(σ) = R Gk(σ) . Since further (a, a) ̸∈ R (I2) we have (a, b) ∈ R
Gk(σ) ⊔ I2 k(σ)
justifying (a, b) ∈ R Hk(σ) . ii. Let (a, b) ∈ R (I2): Since (a, a) ̸∈ R Gk(σ) , R (I2) we deduce (a, b) ∈
R Gk(σ) ⊔ I2 k(σ) hence (a, b) ∈ R Hk(σ) . b) Consider now (a, b) ∈ R Hk(σ) = R
Gk(σ) ⊔ I2 k(σ) .
This entails again that (a, a) ̸∈ R Gk(σ) , (I2). Since Gk(σ) = Fk(σ) ⊔ I1 derive (a, a) ̸∈ R Fk(σ) , R (I1) as well.
i. Let (a, b) ∈ R Gk(σ) = R
Fk(σ) ⊔ I1 k(σ)
: Due to Proposition 2 we have R (a, b) ∈ R
Fk(σ) ⊔ I1 . Since (a, a) ̸∈ R Fk(σ) , R (I1) , R (I2) we infer (a, b) ∈
Fk(σ) ⊔ I1 ⊔ I2 k(σ) . ii. Let (a, b) ∈ R (I2): Since (a, a) ̸∈ R Fk(σ) , R (I1) , R (I2) we immediately infer (a, b) ∈ R Fk(σ) ⊔ I1 ⊔ I2 k(σ) . k(σ) we
Let us consider the Hasse diagram for reachability regarding stable semantics (Figure 2). Again, we restrict ourselves to AFs containing the arguments a and b only. We observe that the reachability order looks quite different compared to information order. In particular, we have much less incomparable classes. However, a closer look reveals that the information order is part of the reachability order. In the following we will formally prove this observation. Proposition 9. For any two AFs F and G and any semantics σ ∈ {stb, ad, co, gr} we have: If |F|σ f iσ |G|σ , then |F|σ f rσ |G|σ . Proof. Given |F|σ f iσ |G|σ . Consequently, Fk(σ) ³ Gk(σ). In order to show |F|σ f rσ |G|σ we have to present a witnessing AF H, s.t. Fk(σ) ⊔ H k(σ) = Gk(σ). Consider H = Gk(σ). Since Fk(σ) ³ Gk(σ) we deduce Fk(σ) ⊔ Gk(σ) k(σ) = Gk(σ) k(σ) = Gk(σ) concluding the proof.
We now consider the question whether there exist bounds, meets and joins w.r.t. the introduced orders.
4.1.1. Lower Bounds and Meets The following proposition shows that lower bounds as well as meets always exist. A lower bound contains information which is shared by both frameworks. The meet can thus be understood as the maximum of shared information.
a b a
b
a
a
b
b
infiσ (|F|σ , |G|σ ) = Fk(σ) ⊓ Gk(σ)
σ
2. lower bound: Consider two AFs F, G and H = Fk(σ) ⊓ Gk(σ). Since H ³ Fk(σ) and H ³
Gk(σ) we deduce Hk(σ) ³ Fk(σ) as well as Hk(σ) ³ Gk(σ) (Prop. 3). Hence |H|σ f iσ |F|σ
and |H|σ f iσ |G|σ is implied.
3. meet: Assume towards contradiction that H is not the greatest lower bound. Then there
has to exist H′, s.t. |H|σ ¯iσ |H′|σ f iσ |F|σ , |G|σ . This means, Fk(σ) ⊓ Gk(σ) k(σ) ❘³
H′k(σ) ³ Fk(σ) ⊓ Gk(σ) ³ Fk(σ). Applying Prop. 3 again we obtain Fk(σ) ⊓ Gk(σ) k(σ) =
Fk(σ) ⊓ Gk(σ). Thus, H′k(σ) can not exist proving that H is indeed the greatest lower bound.
4.1.2. Upper Bounds and Joins
In contrast to lower bounds as well as meets we may show the conditional existence of upper
bounds as well as joins only. More precisely, a join exists whenever there is at least one upper
bound. Interestingly, upper bounds regarding the information order coincide with so-called
models in Dung-logics firstly considered in [
Proposition 11. For two AFs F, G and semantics σ ∈ {stb, ad, co, gr} we have: {|H|σ | |F|σ , |G|σ f iσ |H|σ } ̸= 0/ iff
Fk(σ) ⊔ Gk(σ) k(σ) = Fk(σ) ⊔ Gk(σ)
Proof. Combine Theorem 5 and Lemma 6 from [
Proposition 12. For two AFs F, G and semantics σ ∈ {stb, ad, co, gr} we have:
supiσ (|F|σ , |G|σ ) = Fk(σ) ⊔ Gk(σ)
σ
iff
{|H|σ | |F|σ , |G|σ f iσ |H|σ } ̸= 0/
Proof. It is easy to see that supiσ is well-defined as it uses the kernelized versions only. The claim
follows directly if combing Theorem 5 and Lemma 6 from [
Example 4. Consider the following three AFs which can also be found in Figure 1. We observe that F = Fk(stb), G = Gk(stb) and H = Hk(stb). First, the join of F and H exists as Fk(stb) ⊔ Hk(stb) k(stb) = Fk(stb) k(stb) = Fk(stb) = Fk(stb) ⊔ Hk(stb). Calculating the join reveals supistb (|F|stb, |H|stb) = Fk(stb) ⊔ Hk(stb) stb = Fk(stb) stb = |F|stb. However, in case of F and G there are no upper bounds as (a, b) ∈ R Fk(stb) ⊔ Gk(stb) \ R Fk(stb) ⊔ Gk(stb) k(stb) .
4.2.1. Lower Bounds and Meet The following Example shows that the intersection of classical kernels does not serve for finding the meet.
Example 5. Consider the following three AFs also depicted in Figure 2.
F : a b
G : a b
H : a b We have F = Fk(stb), G = Gk(stb) and H = Hk(stb). Moreover, Fk(stb) ⊓ Gk(stb) = ({a, b}, 0/) = H′. Clearly |H′|stb is a lower bound for |F|stb and |G|stb (confer Figure 2). However, |H′|stb is not the meet as |H′|stb ¯rstb |H|stb and |H|stb f rstb |F|stb, |G|stb holds.
For the considered semantics we have that the defined kernels represent ³-least elements within
one equivalence class. However, any equivalence class even possesses a ³-greatest element (for
more details we refer to the Handbook of Formal Argumentation [
Proposition 13. For two AFs F, G and semantics σ ∈ {stb, ad, co, gr} we have: infrσ (|F|σ , |G|σ ) = Fk+(σ) ⊓ Gk+(σ) σ 4.2.2. Upper Bounds and Join Example 6. Considering again the AFs F and G depicted in Example 4. We observed that for those two AFs no join under information order exists, because R Fk(stb) ⊔ Gk(stb) ̸= R Fk(stb) ⊔ Gk(stb) k(stb) . However, inspecting Figure 2 reveals that there is candidate for a join w.r.t. reachability, namely
Fk(stb) ⊔ Gk(stb) k(stb) stb .
The following proposition shows that our guess happens to be the join in general. Proposition 14. For two AFs F, G and semantics σ ∈ {stb, ad, co, gr} we have: suprσ (|F|σ , |G|σ ) =
Fk(σ) ⊔ Gk(σ) k(σ) σ
We introduced two orderings on equivalence classes of AFs, namely the information and
reachability order. We showed that AFs under f iσ form a semi-lattice as a join does not always exist.
However, AFs under f rσ form a full-lattice. The topic of comparing frameworks has received
some attention in recent years. In the report by Skiba [
Regarding future work there is one quite interesting question, namely the relation between our
information order and the Dung logics considered in [
This work was supported by the German Federal Ministry of Education and Research (BMBF, 01/S18026A-F) by funding the competence center for Big Data and AI “ScaDS.AI” Dresden/Leipzig and by the German Research Foundation (DFG, BA 6170/3-1) through Heisenberg project PEAR.