=Paper=
{{Paper
|id=None
|storemode=property
|title=The Scaffolding of a Formal Context
|pdfUrl=https://ceur-ws.org/Vol-672/paper25.pdf
|volume=Vol-672
|dblpUrl=https://dblp.org/rec/conf/cla/Doerfel10
}}
==The Scaffolding of a Formal Context==
https://ceur-ws.org/Vol-672/paper25.pdf
The Scaffolding of a Formal Context
Stephan Doerfel1,2
1
Knowledge & Data Engineering Group,
Department of Mathematics and Computer Science,
University of Kassel, Wilhelmshöher Allee 73, 34121 Kassel, Germany
http://www.kde.cs.uni-kassel.de/, doerfel@cs.uni-kassel.de
2
Department of Mathematics, Institute of Algebra,
Technical University of Dresden, 01062 Dresden, Germany
Abstract. The scaffolding of a complete lattice L of finite length was
introduced by Rudolf Wille in 1976 as a relative subsemilattice of L that
can be constructed using subdirect decomposition. The lattice is uniquely
defined by its scaffolding and can be reconstructed from it. Using bonds,
we demonstrate how the scaffolding can be constructed from a given
formal context and thereby extend the notion of the scaffolding to doubly
founded lattices. Further, we explain the creation of a suitable graphical
representation of the scaffolding from the context.
Key words: scaffolding, subcontext, bond, subirreducible
1 Introduction
The notion of the scaffolding was introduced by Rudolf Wille in [5]. There, the
scaffolding of a complete lattice L of finite length is constructed as a supremum-
dense subset of L. The subset together with a partial supremum operation allows
the reconstruction of the lattice L. In fact, any complete lattice of finite length
is uniquely determined by its scaffolding up to isomorphism. The construction
of the scaffolding is closely related to subdirect decomposition. If a lattice is
decomposable into small factors, its scaffolding will contain significantly fewer
elements than the lattice itself. Like lattices, their scaffoldings can also be visu-
alized by diagrams. The scaffolding diagrams are an extension of the usual line
diagrams. Although they require more interpretation effort, they can increase
readibility a lot, especially when the scaffolding is much smaller than its lattice.
An impressive example is given in [5], pp. 64-67, with a lattice of 99 elements
that has a scaffolding consisting of only 15 elements. In this paper we explain
the construction of the scaffolding and its diagram from a given formal context
without constructing the corresponding concept lattice first. Further, we extend
the definition of the scaffolding to doubly founded complete lattices. In the next
section we will recall the scaffolding as it was constructed in [5]. Other definitions
or properties of contexts and lattices will be recalled when used.
284 Stephan Doerfel
2 The Scaffolding of a complete lattice of finite length
A relative sup-subsemilattice of a complete lattice L is a subset S ⊆ L together
with a partial operation supS such that supS A = s ⇐⇒ sup A = s holds
for A ⊆ S and s ∈ S. The partial operation supS induces an order ≤S on S
by x ≤S y : ⇐⇒ supS {x, y} = y that is consistent with the order on L. The
scaffolding of a complete lattice L is constructed as a relative sup-subsemilattice
of L using a specific set of separating complete homomorphisms αt : L → Lt
(t ∈ T where T is a suitable index set) and their residual maps αt : Lt → L :
x 7→ inf αt−1 x. Here, separating means that for any two elements x, y ∈ L there
is an element t ∈ T with αt (x) 6= αt (y). Theorem 1 summarizes two important
results of [5]:
Theorem 1. For an arbitrary index set T , complete lattices L and Lt (t ∈ T )
and separating complete homomorphisms αt : L → Lt
S(αt | t ∈ T ) := {αt αt x | x ∈ L, t ∈ T } \ {0}
is a supremum-dense subset of L and L is isomorphic to the complete lattice of
complete ideals of the relative sup-subsemilattice S(αt | t ∈ T ).
The latter part of the theorem points out a method to reconstruct L from
S(αt | t ∈ T ) as an isomorphic copy of the complete lattice of ideals of the
scaffolding. An ideal of a relative sup-subsemilattice S is a subset I ⊆ S that is
closed against the partial supremum-operation supS and that with each element
x ∈ I also contains all elements of S that are smaller than x w.r.t. ≤S . Note
that a similar approach is taken in [2], where with the core of a finite lattice L
a minimal subset of L is constructed such that its lattice of filters is isomorphic
to L.
For the next step of the construction we need to distinguish between the two
properties of being subdirectly irreducible as a lattice and as a complete lattice.
A (complete) lattice L is called (completely) subdirectly irreducible, if there is
no set of (complete) lattices Lt (t ∈ T ), such that L is a (complete) subdirect
product of the Lt while none of the Lt is isomorphic to L. A lattice that is
complete and subdirectly irreducible is also completely subdirectly irreducible.
In the case of finite length, the two properties are the same. Note that when
it is clear that only complete lattices are discussed (as in [4] or [5]), usually
subdirectly irreducible stands for completely subdirectly irreducible.
To get a one-to-one relationship between lattices and their scaffoldings, one
fixes the choice of the Lt and αt in the construction of Theorem 1. Considered are
all completely subdirectly irreducible factors Lt of the lattice L and all surjective
complete homomorphisms αt : L → Lt . For lattices of finite length (thus the Lt
are also subdirectly irreducible) these αt are separating (cf. [5] or [1], p. 193)
and therefore one can define the scaffolding of L as S(L) := S(αt | t ∈ T ).
An element x ∈ L is called subirreducible if it is an element of S(L), i. e., if
a complete homomorphism α from L onto a subdirectly irreducible factor of L
exists with ααx = x.
The Scaffolding of a Formal Context 285
An example of the scaffolding of a lattice is shown in Figure 1 (the last
diagram). The subirreducible elements of the lattice are colored in gray. The
diagram above to the right of the lattice is that of its scaffolding as it is described
in [5]. Construction and interpretation of such diagrams are explained in Sect. 4.
In the following, K always denotes a context (G, M, I), and Kx a context
(Gx , Mx , Ix ). By γg we denote the object concept of an object g and by µm the
attribute concept of an attribute m. T will always be an index set. In the next
section we present a construction of the scaffolding from a formal context.
3 The Scaffolding of a Formal Context
For our construction we employ the theory of bonds and therefore shortly recall
some results about them (for details see [4], Sect. 7.2). A bond from Ks to Kt
is a relation Rst ⊆ Gs × Mt , such that g Rst is an intent of Kt for every object
g ∈ Gs and mRst is an extent of Ks for every attribute m ∈ Mt . For bonds Rrs
from Kr to Ks and Rst from Ks to Kt the bond product, defined by
Rrs ◦ Rst := {(g, m) ∈ Gr × Mt | g Rrs Is ⊆ mRst } ,
is itself a bond from Kr to Kt . The significance of the bond notion stems from
the fact that bonds from Ks to Kt correspond one-to-one to the sup-morphisms
from B(Ks ) to B(Kt ) and the bonds from Kt to Ks correspond one-to-one to
the inf-morphisms from B(Ks ) to B(Kt ). For example, a bond R from Ks to Kt
yields a sup-morphism from B(Ks ) to B(Kt ) via
(A, B) 7→ (ARIt , AR ) .
Each complete homomorphism from B(Ks ) to B(Kt ) is thus defined via
(A, B) 7→ (B S , AR )
by a pair (R, S) of bonds (R from Ks to Kt , S from Kt to Ks ) where ARIt = B S
holds for every (A, B) ∈ B(Ks ) (equiv. B SIt = AR ). In this paper, such pairs
shall be called hom-bonds. We also introduce the notion of being separating for
hom-bonds: A set of hom-bonds (Rt , St ) from K to Kt (t ∈ T ) is called separating,
if for any two extents A 6= C of K an index t ∈ T exists such that ARt 6= C Rt .
The following proposition presents some useful rules for bond arithmetics.
Proposition 1. Let Rrs , Rst and Rrt be bonds from Kr to Ks , Ks to Kt and
Kr to Kt resp. and A ⊆ Gr , B ⊆ Mt . The following hold:
1. AIr Ir Rrs = ARrs and B It It Rst = B Rst ,
2. ARrs ◦Rst = ARrs Is Rst and B Rrs ◦Rst = B Rst Is Rrs ,
3. AR◦S ⊇ AIs and A(R◦S)Is R = AR for hom-bonds (R, S) from Kr to Ks .
Proof. 1 simply follows from the bond properties and 2 follows from Proposi-
tion 83 in [4]. 3: According to 2 we have AR◦S = ARIs S = B SS ⊇ B = AIs
and A(R◦S)Is R = (ARIs S )Is R = (B SS )SIs = B SIs = ARIs Is = AR using the
hom-bond property twice.
286 Stephan Doerfel
a b c d e f g a b c b c d
1 ××. %× × × × 1 ××. % 1 ×.%×
2 .
% × %× × × × 2 .
%× % 3 .%× .
3 .%.× . × 3 .%. × 4 × %%.
4 × × %%.× × e f g
5 ××××××. % 5 ××. %
6 ××××. %× % 6 .
%× %
7 × × .% .× 7 .%.×
f
bd
c g
7
3
b b f e ae a
2 c 4 c 6 g 2 4 6
a 3 d 3 e 7
1 1 5 5
1
f b
d
a e
c g
3 7
4
6 2
5 1
Fig. 1. A context K, three covering subcontexts h2iK , h4iK and h6iK , diagrams of the
three corresponding components, the diagram of the scaffolding and that of the concept
lattice
The Scaffolding of a Formal Context 287
We are now ready to begin our construction.
Theorem 2. For separating hom-bonds (Rt , St ) between K and Kt (t ∈ T )
S(Rt , St )t∈T := {(ARt ◦St I , ARt ◦St ) | (A, B) ∈ B(K), t ∈ T } \ {(M I , M )}
is a supremum-dense subset of B(K).
Proof. For (A,TB) ∈ B(K) we show (A, B) = sup{(ARt ◦St I , ARt ◦St ) | t ∈ T } by
proving A = ( t∈T ARt ◦St )I . For an arbitrary index u ∈ T holds
\ \ [ [
( ARt ◦St )IRu = ( ARt ◦St II )IRu = ( ARt ◦St I )IIRu = ( ARt ◦St I )Ru
t∈T t∈T t∈T t∈T
by Proposition 1.1. From Proposition 1.3 we get:
[ [
ARt ◦St I ⊆ AII = A =⇒ ARt ◦St I ⊆ A =⇒ ( ARt ◦St I )Ru ⊇ ARu
t∈T t∈T
and
\ \
ARt ◦St ⊆ ARu ◦Su ⇒ ( ARt ◦St )I ⊇ ARu ◦Su I
t∈T t∈T
\
⇒( ARt ◦St )IRu ⊆ ARu ◦Su IRu = ARu .
t∈T
Rt ◦St IRu
= ( t∈T ARt ◦St I )Ru = ARu for all u ∈ T and
T S
Thus we have ( T t∈T A )
therefore A = ( t∈T ARt ◦St )I , since the bonds are separating. The smallest
concept (M I , M ) of K can be removed from the set, since it is the supremum of
the empty set.
To continue our construction we require the concept lattices to be doubly
founded. A complete lattice L is called doubly founded, if for any two elements
x, y ∈ L there always are elements s, t ∈ L with s being minimal w.r.t. s ≤ y
and s x and t being maximal w.r.t. t ≥ x and t y (cf. [4], Definition 26).
Note that every finite lattice is a doubly founded complete lattice. Further, every
doubly founded complete lattice is isomorphic to the concept lattice of a reduced
context. It is also possible to define doubly founded contexts. In fact, the context
of a doubly founded lattice is always doubly founded. The definition can be found
in [4], but the details are not important in this work. In the following we will
also make use of the arrow relations in a context K (cf. [4], Definition 25), i.e.
– g . m ⇐⇒ γg ∧ µm = sup{(A, B) ∈ B(K) | (A, B) < γg} =
6 γg
– g % m ⇐⇒ γg ∨ µm = inf{(A, B) ∈ B(K) | (A, B) > µm} =6 µm
– g%. m ⇐⇒ g . m and g % m
where g is an object and m is an attribute of K. In a reduced context of a doubly
founded lattice for every object g exists at least one attribute m with g % . m.
The analogue holds for every attribute. A subcontext of (H, N, J) of a reduced
context (G, M, I) is called arrow-closed, if for g ∈ G and m ∈ M it always holds
that
288 Stephan Doerfel
– from g ∈ H and g % m follows m ∈ N and
– from m ∈ N and g . m follows g ∈ H.
For an object g ∈ G there always exists a smallest arrow-closed subcontext
hgiK = (Gg , Mg , Ig ) containing g, called the 1-generated subcontext of g in
(G, M, I) (cf. [4], Sect. 4.1). An example of those subcontexts is given in Figure 1,
where the three small contexts are 1-generated subcontexts of the larger one. A
subcontext (H, N, J) of a context (G, M, I) is called compatible, if for each con-
cept (A, B) of (G, M, I) the pair (A ∩ H, B ∩ N ) is a concept of (H, N, J). In the
reduced context K of a doubly founded concept lattice the compatible subcon-
texts are exactly the arrow-closed subcontexts. For proof see [4], Propositions 15
and 36. Moreover, in this case, the 1-generated subcontexts yield the subdirectly
irreducible factors of B(K) (cf. [4], Propositions
S 61 and 62).
S Finally, subcontexts
Kt of K (t ∈ T ) are said to cover K, if t∈T Gt = G and t∈T Mt = M .
The scaffolding of a reduced context of a doubly founded concept lattice is
now defined using the construction of Theorem 2 by fixing specific subcontexts
and bonds.
Proposition 2. If K is a reduced context of a doubly founded concept lattice and
hgiK = (Gg , Mg , Ig ), then (Rg , Sg ) with Rg := I∩(G×Mg ) and Sg := I∩(Gg ×M )
(g ∈ G) are separating hom-bonds.
Proof. From [4], Theorem 18 follows that, because B(K) is doubly founded, it
has a subdirect decomposition into subdirectly irreducible factors. By [4], Propo-
sition 61 such a decomposition corresponds to a family of arrow-closed subcon-
texts covering K and by [4], Proposition 62 those subcontexts are 1-generated
and thus form a subset of the hgiK (g ∈ G). The bond properties of Rg and Sg
(g ∈ G) and the hom-bond condition follow easily from the fact that the subcon-
texts hgiK are arrow-closed and thus compatible (cf. [4], Proposition 36). Left to
prove is that (Rg , Sg ) (g ∈ G) are also separating. Suppose for two extents A, C
of K holds ARg = C Rg for all g ∈ G. By the definintion of the bonds this means
AI ∩ Mg = C I ∩ Mg for all g ∈ G and since the subcontexts hgiK (g ∈ G) cover
K, we have AI = C I and thus A = AII = C II = C.
Definition 1. If B(K) is the doubly founded concept lattice of a reduced context
K and (Rg , Sg ) are as above, then the relative sup-semilattice
S(Rg , Sg )g∈G = {(ARg ◦Sg I , ARg ◦Sg ) | (A, B) ∈ B(K), g ∈ G} \ {(M I , M )}
is called the scaffolding of K and will be denoted by S(K).
By the above proposition the scaffolding is well-defined. If one constructed
the scaffolding according to the definition above, one would need B(K) first.
This is an obvious drawback considering that one of the goals of the scaffolding
idea is to have a small representation of the lattice from which the lattice can be
reconstructed. We therefore simplify the construction such that one only needs
to construct smaller lattices – namely the concept lattices of the 1-generated sub-
contexts. We then also reduce the set of subcontexts needed for the construction
The Scaffolding of a Formal Context 289
in Proposition 4. But first we have to prove that our definition is consistent with
the construction in [5] described in the previous section.
Theorem 3. For a reduced context K of a lattice of finite length the scaffolding
of the context S(K) is equal to the scaffolding of the lattice S(B(K)).
Proof. By (A, B) 7→ (AS , AR ) hom-bonds (R, S) from K to a context L define a
complete homomorphism B(K) → B(L). From this it is easy to see that sepa-
rating hom-bonds define separating complete homomorphisms and vice versa.
Claim: S(αt | t ∈ T ) = S(Rt , St )t∈T if αt : B(K) → B(Kt ) are the complete
homomorphisms defined by (Rt , St ) (t ∈ T ).
As αt is residual to αt , Corollary 112 in [4] states that the bond from Kt
to K defining the sup-morphism αt is in fact St . Since α is a sup-morphism too
(defined by the bond Rt ), we can use the dual of [4], Proposition 113 (stating that
the composition of sup-morphisms corresponds to the product of their bonds)
and obtain αt αt (A, B) = (ARt ◦St I , ARt ◦St ).
In order to construct the scaffolding, surjective complete homomorphisms
onto subdirectly irreducible lattices are used. Considering isomorphism, it is ob-
vious that one can narrow these choices down to the projections onto subdirectly
irreducible factors of B(K). The subdirectly irreducible factors of a lattice of fi-
nite length (in fact of all doubly founded lattices) correspond to the 1-generated
subcontexts Kg (g ∈ G) (cf. [4], Propositions 61 and 62) and the associated
projections are given by B(K) → B(Kg ) : (A, B) 7→ (A ∩ Gg , B ∩ Mg ) (cf. [4],
Proposition 34). It is easy to see that the hom-bonds to these complete homo-
morphisms are (Rg , Sg ) as defined above. Thus S(K) and S(B(K)) meet the
requirements of the claim and are therefore equal.
Analogously to [5] it is also possible to define the scaffolding by subirre-
ducible elements. We restate this in the next corollary, which presents a first
simplification of the scaffolding construction: it allows to compute S(K) with-
out computing B(K) first.
Corollary 1. In a reduced context K of a doubly founded concept lattice a con-
cept (A, B) with B 6= M is subirreducible, iff there is a 1-generated subcontext
(H, N, J) such that (A, B) = ((A∩H)II , (A∩H)I ). The scaffolding S(K) consists
of all subirreducible elements of B(K), i.e.
[
S(K) = {(C II , C I ) | (C, C Ig ) ∈ B(hgiK ), C Ig 6= Mg } .
g∈G
Proof. Similarly to the proof above follows that a concept (A, B) is subirre-
ducible iff K has a 1-generated subcontext (H, N, J) such that the equation
(A, B) = (AR◦SI , AR◦S ) holds with R = I ∩ (G × N ) and S = I ∩ (H × N ). The
claimed equivalence follows (using Proposition 34 from [4] and Proposition 1.2)
from:
AR◦S = ARJS = (AI ∩ N )JS = (B I ∩ H)S = (A ∩ H)I .
Considering that the composed operator R ◦ S is idempotent (Proposition 1.3),
it follows immediately from Definition 1 that S(K) is the set of all subirreducible
290 Stephan Doerfel
elements. Since the map (A, B) 7→ (A∩Gg , (A∩Gg )Ig ) defined by the hom-bonds
(Rg , Sg ) is surjective onto B(hgiK ) (again [4], Proposition 34), we obtain
[
S(K) ∪ {(M I , M )} = {(C II , C I ) | (C, C Ig ) ∈ B(hgiK )} .
g∈G
Left to prove for the claimed equation is
(C II , C I ) = (M I , M ) ⇐⇒ C Ig = Mg for (C, C Ig ) ∈ B(hgiK ).
For (C II , C I ) = (M I , M ) we obtain C Ig = Mg . Conversely, for C Ig = Mg the
concept (C II , C I ) is the smallest concept of B(K) such that its intent contains
Mg . (M I , M ) is the smallest concept of B(K) and it is Mg ⊆ M . Hence we have
(C II , C I ) = (M I , M ).
As promised above, we will now show that one can construct the scaffolding
with any set of 1-generated subcontexts that is covering K.
Theorem 4. For a reduced context K of a doubly founded concept lattice with
1-generated subcontexts Kt (t ∈ T ) covering K and Rt := I ∩ (G × Mt ) and
St := I ∩ (Gt × M ) (t ∈ T ) holds
[
S(K) = S(Rt , St )t∈T = {(C II , C I ) | (C, C It ) ∈ B(Kt ), C It 6= Mt } .
t∈T
Proof. The second equality follows like in the proof above. From Definition 1
follows S(Rt , St )t∈T ⊆ S(K). For the proof of the converse inclusion let (A, B)
be an element of S(K). Hence B 6= M and therefore by Corollary 1 (A, B)
equals ((A ∩ Gg )II , (A ∩ Gg )I ) for some object g ∈ G. Since K is covered by the
subcontexts Kt (t ∈ T ), an index s ∈ T exists with g ∈ Gs . As Ks is arrow-closed,
hgiK is a subcontext of Ks (esp. Gg ⊆ Gs ⊆ G) and we have:
A = (A ∩ Gg )II ⊆ (A ∩ Gs )II ⊆ AII = A
which (using Proposition 1) yields
A = (A ∩ Gs )II = (AI ∩ Ms )Is II = ARs Is II = ARs Is Ss I = ARs ◦Ss I
and therefore (A, B) ∈ S(Rt , St )t∈T following the definition in Theorem 2.
The above theorem implies for finite contexts that, if a 1-generated subcon-
text Ks of K is strictly contained in a 1-generated subcontext Kt of K, then Ks
does not have to be used for the construction. Note that in an infinite context an
infinite chain without maximal element of 1-generated subcontexts could exist,
where each subcontext contains its predecessor. However, it is unclear whether
such a situation can occur in a doubly founded context.
In Theorem 4 the scaffolding is composed as a union of sets. This motivates
the interpretation of these sets as the components of the scaffolding (similar
to [3]). However, these components depend on the choice of the subcontexts.
The Scaffolding of a Formal Context 291
Also, in general neither the components nor the corresponding subcontexts need
to be disjoint. It has been noted in [5], Sect. 6, that this disjointness can be
achieved in the modular case.
Figure 1 shows an example for the scaffolding construction. In the given con-
text, three 1-generated subcontexts are chosen. For each subcontext its concept
lattice is constructed, with the smallest element removed. In the lattice diagram,
the nine gray colored elements are those, that belong to the scaffolding.
The better a context can be decomposed into 1-generated subcontexts, the
smaller will its scaffolding be. Power set lattices can be regarded as the extreme
case for this. A context for a power set lattice of a set S of size n is L = (S, S, I)
with (g, m) ∈ I ⇐⇒ g 6= m for g, m ∈ S. In this context we have g % . m ⇐⇒
g = m and thus hgiL = ({g}, {g}, ∅) for all g ∈ S. While the concept lattice grows
exponentially with the size of the set n (i. e., has 2n concepts) the cardinality
of the scaffolding grows only linearly (i. e., the scaffolding consists of n disjoint
components, each containing only one element – the object concept γg where g
is the object generating the subcontext).
To construct the scaffolding of a formal context one has to find a set of 1-
generated covering subcontexts and then compute the concept lattices to those
subcontexts. It is clear that if a context is 1-generated itself, one will have to
construct the whole concept lattice of that context and the scaffolding will con-
tain all elements of the lattice but its smallest. Thus in this (worst) case the
complexity of the construction is equal to the complexity of constructing the
concept lattice from its context. However, if the the context can be decomposed
into many small 1-generated subcontexts (like in the example of the power set
lattice), only the lattices of the small contexts have to be computed. Then the
time for computing the scaffolding will be significantly shorter than the time for
computing the whole lattice.
4 The diagram of a scaffolding
Wille describes a graphical representation of the scaffolding (cf. [5]) based on the
usual line diagrams of lattices. In this section we will adapt that visualization
scheme for our context based scaffolding. Let K be a reduced context of a doubly
founded complete lattice and Kt (t ∈ T ) be 1-generated subcontexts covering K.
For (C1 , C1It ), (C2 , C2It ) ∈ B(Kt ) we have
(C1II , C1I ) ≤ (C2II , C2I ) ⇐⇒ (C1 , C1It ) ≤ (C2 , C2It ) ,
because C1 ⊆ C2 implies C1II ⊆ C2II and C2I ⊆ C1I implies C2It ⊆ C1It . Therefore
within one component we can calculate the supremum of elements (AII I
x , Ax )
It
(x ∈ X where X is an index set) with (Ax , Ax ) ∈ B(Kt ) via
sup{(AII I II I It It
x , Ax ) | x ∈ X} = (C , C ) , where (C, C ) = supt {(Ax , Ax ) | x ∈ X}
(here, supt is the supremum operation in B(Kt )). Next, we take a look at the
relations between elements of different components. Let (A, B) ∈ B(Ks ) and
292 Stephan Doerfel
(C, D) ∈ B(Kt ) be concepts of two of the chosen subcontexts. We have
(AII , AI ) ≤ (C II , C I ) ⇐⇒ AII ⊆ C II ⇐⇒ A ⊆ C II .
This order relation can be described using the relations Ist := I ∩ (Gs × Mt )
and Its := I ∩ (Gt × Ms ). Ist and Its are bond products (Ist = Ss ◦ Rt and
Its = St ◦ Rs , with (Rs , Ss ) and (Rt , St ) defined as before). Therefore, they are
bonds themselves – Ist from Ks to Kt and Its from Kt to Ks . From A ⊆ Gs and
B ⊆ Ms follows
A ⊆ C II ⇐⇒ A ⊆ C II ∩Gs ⇐⇒ (A, B) ≤ (C II ∩Gs , C I ∩Ms ) ⇐⇒ B ⊇ C Its
and thus:
(AII , AI ) ≤ (C II , C I ) ⇐⇒ C Its ⊆ B. (∗)
Since we can determine the order in the scaffolding from the elements of the lat-
tices of the subcontexts and the bonds between them, we will use these elements
to construct a diagram. However, elements of the scaffolding can belong to more
than one component. When drawing the scaffolding we will have to identify such
two elements and therefore factor the set D of all the concepts of the lattices
B(Kt ) (t ∈ T ) by the equivalence relation
θ := {((A, B), (C, D)) ∈ D2 | (AII , AI ) = (C II , C I )} .
By the rule (∗) concepts (A, B) ∈ B(Ks ) and (C, D) ∈ B(Kt ) are equivalent
iff C Its ⊆ AIs and AIst ⊆ C It . Note, that the two inclusions together imply
C Its = AIs and AIst = C It . The order on D/θ given by
[(A, B)]θ ≤ [(C, D)]θ : ⇐⇒ C Its ⊆ B
is well-defined and consistent with the order of the corresponding scaffolding
elements. Particularly, (A, B) = (C Its Is , C Its ) is the largest concept of B(Ks )
whose equivalence class is smaller than the one of (C, C It ). We are now ready
to draw a diagram of the scaffolding in four steps:
1. We draw the line diagrams for B(Kt ) (t ∈ T ) omitting each lattice’s smallest
element. Objects and attributes are annotated as usual.
2. We calculate the relations between the elements of different components
using the bonds Ist (s, t ∈ T ). If two elements are equivalent according to D,
we enclose them with a circle. The order relation will be visualized by dashed
lines. If C Its = B for (A, B) ∈ B(Ks ) and (C, D) ∈ B(Kt ), then (A, B) is
the largest concept of B(Ks ) with an equivalence class smaller than that of
(C, D). In the diagram we move (A, B) below (C, D) and connect them by a
dashed line. The structure of the line diagram of B(Ks ) \ {(MsIs , Ms )} must
hereby be retained.
3. We erase any dashed line between two elements, if there already exists an-
other path of upward lines. This deletion realizes the transitive reduction
that is also conducted drawing regular line diagrams.
The Scaffolding of a Formal Context 293
4. Since the contexts Kt are not necessarily disjoint, annotations of the same
object/attribute can occur more than once. Since the context is reduced,
all object concepts are supremum-irreducible and thus contained in the
(supremum-dense) scaffolding. Hence, there is one smallest element for each
g ∈ G in the diagram annotated with g. We erase all other object annota-
tions. The same consideration does not apply for attributes. We determine
the maximal elements annotated with m in the diagram and delete m on all
others.
The resulting diagram with dashed and regular lines is the line diagram of the
ordered set S(K). All objects below some node form the extent and all attributes
above the node form the intent of that node’s concept. Other than in the line
diagram of a lattice the suprema and infima can not simply be read from the
lines. Only within a component the regular lines indicate suprema. Fig. 1 shows
the diagram of the scaffolding of a given context (below the three small contexts).
5 Conclusion
In this paper, we have translated the notion of the scaffolding into the language
of Formal Concept Analysis and we have extended the class of lattices for that
it is defined. We have presented a construction of the scaffolding from a given
reduced context (of a doubly founded lattice) without constructing the concept
lattice first. Further, we have described a method to draw and interpret the
corresponding diagrams.
References
1. Birkhoff, G.: Lattice theory. In: Colloquium Publications, vol. 25. Amer. Math. Soc.,
3. edn. (1967)
2. Duquenne, V.: The core of finite lattices. Discrete Math. 87(2-3), 133–147 (1991)
3. Ganter, B., Poguntke, W., Wille, R.: Finite sublattices of four-generated modular
lattices. Algebra Univ. 12, 160–171 (1981)
4. Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.
Springer-Verlag, Berlin/Heidelberg (1999)
5. Wille, R.: Subdirekte Produkte vollständiger Verbände. J. reine angew. Math.
283/284, 53–70 (1976)