=Paper=
{{Paper
|id=Vol-1624/paper20
|storemode=property
|title=A Fresh View on Fuzzy Formal Concept Analysis and Mathematical Morphology
|pdfUrl=https://ceur-ws.org/Vol-1624/paper20.pdf
|volume=Vol-1624
|authors=Tim B. Kaiser,Lars Lumpe,Stefan E. Schmidt
|dblpUrl=https://dblp.org/rec/conf/cla/KaiserLS16
}}
==A Fresh View on Fuzzy Formal Concept Analysis and Mathematical Morphology==
https://ceur-ws.org/Vol-1624/paper20.pdf
A Fresh View on Fuzzy FCA and Mathematical
Morphology
Tim B. Kaiser1 , Lars Lumpe2 , and Stefan E. Schmidt2
1
SAP AG, Walldorf
2
Institut für Algebra, Technische Universität Dresden
tbkaiser@gmx.de,larslumpe@gmail.com, midt1@msn.com
Abstract. In this paper we discuss how biresiduations provide a unify-
ing paradigm for fuzzy formal concept analysis and mathematical mor-
phology. In particular we provide constructions of morphological oper-
ators such as dilation and erosion within the framework of convolution
algebras of action networks (also known as small covariant categories)
over join complete semirings. This unifies and generalizes previous contri-
butions in mathematical morphology, such as the work of Isabelle Bloch.
Further we show how decomposition, factorization, and hedges naturally
align themselves in the framework of fuzzy formal concept analysis.
Keywords: biresiduation, fuzzy formal concept analysis, hedges, fac-
torization, decomposition, linear algebra, complete monoids
1 Introduction
In our paper we outline the fundamental role of biresiduation in combination with
biadditivity for a common view on fuzzy FCA and mathematical morphology.
While the concept of biresiduation is an important paradigm of algebraic logic,
the concept of biadditivity is rooted in linear algebra (over complete monoids and
complete semirings). The close relationship between both approaches is reflected
in the bijective correspondence of the residuated complete lattices and the join
complete semirings on a fixed set. Our considerations yield a major application
for a better understanding of mathematical morphology: We achieve this by
constructing and investigating convolution algebras of action networks over join
complete semirings. Finally, as a tool for information reduction, we also discuss
the role of hedges on residuated complete lattices and their relationship with
substructures of join complete semirings, and more generally within the category
of biadditive setups.
Important literature for (fuzzy) FCA is given by [1,2,3,4,5], regarding factor
analysis, especially by [6], regarding hedges [7]. Belohlávek gives an overview on
approaches to fuzzy concept analysis in [8] which is an update of [9].
We assume the reader to be familiar with ordered sets and formal concept anal-
ysis as exposed in [5] and [1]. Profound information on residuation theory can
be found, for instance, in [10].
Over the last two decades, major contributions to mathematical morphology go
back to Isabelle Bloch [11,12,13].
This paper is based on [14].
2 Biresiduation
One of the key concepts for accessing FCA and its generalizations is that of a
biresiduated map. We start by recalling the definition of a residuated map.
Definition 1 (residuated map, adjunction). Let P1 := (P1 , ≤) and P2 := (P2 , ≤)
be ordered sets. Then a map f : P1 → P2 is residuated from P1 to P2 if there
exists a map f + : P2 → P1 such that
f p1 ≤ p2 ⇐⇒ p1 ≤ f + (p2 ).
Here, the map f + is uniquely determined by f and is called the residual of f .
The pair (f, f + ) is called an adjunction w.r.t. (P1 , P2 ). In case P1 = P2 , we will
say that (f, f + ) forms an adjunction on P1 .
Remark 1. A map between complete lattices is residuated if and only if it is
completely join preserving, that is, f (sup X) = sup(f X) holds for all X ⊆ P1 in
the above setting.
The following definition is central for this paper.
Definition 2 (biresiduation). Let P1 := (P1 , ≤), P2 := (P2 , ≤), and P := (P, ≤)
be ordered sets. Then a map
⊗ : P1 × P2 → P
will be called a biresiduation w.r.t. P := (P1 , P2 , P) if there exist maps
⊗
→ : P1 × P → P2
⊗
← : P × P2 → P1
such that
⊗ ⊗
p1 ≤ (p ← p2 ) ⇐⇒ (p1 ⊗ p2 ) ≤ p ⇐⇒ p2 ≤ (p1 → p)
holds for all p1 ∈ P1 , p2 ∈ P2 , and p ∈ P .
In case P1 = P2 = P, we say that ⊗ forms a biresiduation w.r.t. P. If in addition
(P, ⊗, ε) is a monoid then (P, ⊗, ε) will be referred to as residuated ordered set. If
in particular P forms a complete lattice, (P, ⊗, ε) is a residuated complete lattice.
Remark 2. A biresiduation is characterized as a map ⊗ which is residuated in
both arguments. In particular a biresiduation is isotone in each argument.
Example 1. Any two sets G and M give rise to a biresiduation as follows: The
map
⊗ : 2G × 2M → 2G×M , (A, B) 7→ A × B
is a biresiduation w.r.t. (2G , 2M , 2G×M ), where 2G denotes the power set lattice
of G. This follows immediately since power set lattices are complete with the
supremum operation as set union. In particular for I ⊆ G × M we consider the
context (G, M, I): For all A ⊆ G and all B ⊆ M we have
⊗
(A × B) ⊆ α ⇐⇒ A ⊆ (B → α)
where
⊗
[
(B → α) = {H ⊆ G | H × B ⊆ α} = B 0 .
Dually, we get
⊗
[
(α ← A) = {N ⊆ M | A × N ⊆ α} = A0 .
We have recaptured the derivation operators of classical formal concept analysis
as residuals of a specific biresiduation, the cartesian product.
Now, it is worth noting the connection between cartesian product and dyadic
product as used in linear algebra. We recall the definition of a dyadic product.
Given two n-dimensional vectors u, v over a semiring S we can define the dyadic
product as
u ⊗ v := u · v T
where the second multiplication is simply matrix multiplication. If S is the well-
known boolean 2-element semiring, the dyadic product resembles exactly the
cartesian product. So, in a sense, the dyadic product generalizes the cartesian
product. From our point of view, this is key to understanding fuzzy concept
analysis in terms of biresiduations.
Example 2 (t-Norm). A binary operation ⊗ on the real unit interval [0, 1],
which is isotone in both arguments, is called t-Norm if for all a, b, c ∈ [0, 1] the
following hold:
(1) 1 ⊗ a = a
(2) a ⊗ b = b ⊗ a
(3) a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c
The t-norm ⊗ is left continuous if for all a ∈ [0, 1] and α ∈ [0, 1]I (where I is an
arbitrary index set) the following holds:
a ⊗ (sup αi) = sup(a ⊗ αi)
i∈I i∈I
From the terminology introduced above, a map ⊗ : [0, 1] × [0, 1] → [0, 1] is a
left continuous t-norm if and only if ([0, 1], ≤, ⊗, 1) forms a residuated complete
lattice. Among the various left continuous t-norms we point out the Gödel t-notm
⊗ : [0, 1] × [0, 1] → [0, 1],
(a, b) 7→ min(a, b)
and the Lukasiewicz t-norm
⊗ : [0, 1] × [0, 1] → [0, 1],
(a, b) 7→ max(a + b − 1, 0)
These t-norms will be used in our visualizations for mathematical morphology
in figure 1 and 2.
In the next section, we will highlight that residuals of a biresiduation play a
crucial role in FCA and its abstractions.
3 Abstract Concepts and Maximal Rectangles
Let P1 := (P1 , ≤), P2 := (P2 , ≤) and P = (P, ≤) be ordered sets and ⊗ a biresid-
uation w.r.t. (P1 , P2 , P). We define
f ⊗ := P1 × P2
to be its set of formal rectangles. If α ∈ P then
K := (⊗, α)
is called an abstract context w.r.t. (P1 , P2 , P). Given such an abstract context we
can define the set of formal rectangles w.r.t. K as
f K := {(u, w) ∈ f ⊗ | u ⊗ w ≤ α}.
On a formal rectangle, we can apply our biresiduation operation to yield an
(actual) rectangle. We define
K
:= {u ⊗ w | (u, w) ∈ f K }
to be the set of (actual) rectangles w.r.t. K and
mf K := max f K
to be the set of maximal rectangles regarding the product order on P1 × P2 . We
define the set of abstract concepts as
⊗ ⊗
BK := {(u, w) ∈ P1 × P2 | u → α = w & α ← w = u}.
We order the set of maximal rectangles of an abstract context. For b = (ub , wb ), c =
(uc , wc ) ∈ mf K we set
b ≤K c : ⇐⇒ ub ≤P1 uc ⇐⇒ wc ≤P2 wb .
Now we can define an abstract concept order as
BK := (BK, ≤K ).
In case (P1 , P2 , P) is a triple of complete lattices, BK forms a complete lattice,
called the abstract concept lattice of K.
⊗
As usual in FCA, let us abbreviate u → α as u0 , the derivation of u w.r.t. K :=
⊗
(⊗, α), and similarly, α ← w as w0 . We show that even in our rather abstract
setting we can talk about maximal rectangles being the abstract concepts.
Proposition 1. Let K := (⊗, α) be an abstract context w.r.t. (P1 , P2 , P) and
define γ : P1 → P, x 7→ (x00 , x0 ) and µ : P2 → P, x 7→ (x0 , x00 ). Then
1. BK = im(γ) = im(µ)
2. mf = BK
K
We call (p1 , p2 ) ∈ f K a decomposition of K if p1 ⊗ p2 = α. If additionally
(p1 , p2 ) ∈ mf K we call (p1 , p2 ) a conceptual decomposition of K.
Corollary 1. Let K = (⊗, α) be an abstract context w.r.t. (P1 , P2 , P). If (p1 , p2 )
is a decomposition of K there exists a conceptual decomposition (q1 , q2 ) of K with
p1 ≤ q1 and p2 ≤ q2 .
Proof. For instance, set (q1 , q2 ) := γ(p1 ).
4 Biadditivity
We complement the approach sketched above (where ordered sets are used as
basic structures) by using complete monoids [15] as basic structures.
Definition 3 (complete monoid). A quadruple A := (A, +, 0, Σ) is called a
complete monoid if (A, +, 0) is a commutative monoid and Σ assigns to every
α ∈ AI (for an arbitrary index set I) an element Σα =: Σi∈I αi of A such that
(1) Σα = 0 if αi = 0 for all i ∈ I
(2) Σα = αi if I = {i}
(3) Σα = αi + αj if I = {i, j} and i 6= j
(4) Σα = Σβ for every partition T of I and β given by T → A, T 7→ Σα|T
Definition 4 (join complete monoid). A join complete monoid is a complete
monoid AP := (A, +, 0, Σ) such that for every non-empty set I and every a ∈ A
it follows a = a.
i∈I
Remark 3. For every complete lattice L := (L, ≤) let A(L) := (L, +, 0, Σ)
be the join complete monoid, where x + y := supL {x, y} for all x, y ∈ L and
0 := supL ∅ and Σα := supL {α(i) | iP∈ I} for every index set I and all α ∈ LI .
If on the other hand, A := (A, +, 0, ) is a join complete monoid then L(A) :=
(A, ≤) is a complete lattice, provided x ≤ y :⇔ x + y = y for all x, y ∈ A. This
observation establishes for every set A a bijective correspondence between all
complete lattices on A and all join complete monoids on A.
L := (L1 , L2 , L) is a triple of complete lattices then A(L) := (A(L1 ), A(L2 ), A(L)).
We define the analogue of biresiduations for complete monoids.
Definition 5 (biadditive map). Let A := (A1 , A2 , A) be a triple of complete
monoids. Then a biadditive map w.r.t. A is defined as a map ⊗ : A1 × A2 → A
such that
Σβ ⊗ Σγ = Σ(i,j)∈I×J βi ⊗ γj
holds for all β ∈ AI1 and γ ∈ AJ2 for arbitrary index sets I, J.
The next definition will also be useful in the section concerning hedges.
Definition 6 (biadditive setup, morphism). Let A := (A1 , A2 , A) be a triple of
complete monoids and let ⊗ be a biadditive map on A. Then we call the pair
(A, ⊗) a biadditive setup. In case A1 = A2 = A, we say that ⊗ is a biadditive
operation on A, and (A, ⊗) forms a biadditive setup.
Given two biadditive setups (A, ⊗) and (U, ⊗) we call Φ := (ϕ1 , ϕ2 , ϕ) a mor-
phism from (U, ⊗) to (A, ⊗) if ϕ1 , ϕ2 , ϕ are morphisms from U1 , U2 , and U to
A1 , A2 , and A, respectively, and for all u1 ∈ U1 and u2 ∈ U2 we have
ϕ1 (u1 ) ⊗ ϕ2 (u2 ) = ϕ(u1 ⊗ u2 ).
Biadditive setups and their morphisms obviously form a category. In particular,
(U, ⊗) is a substructure of (A, ⊗) if U1 , U2 , and U are complete submonoids of
A1 , A2 , and A, respectively, and U1 ⊗ U2 ⊆ U . Clearly, The image of a morphism
induces a substructure.
P
Definition 7 (complete semiring). A tuple R := (R, +, ⊗, 0, 1, ) is a complete
semiring if the following properties are satisfied:
X
(1) Radd := (R, +, 0, ) is a complete monoid,
(2) Rmult := (R, ⊗, 1) is a monoid with 1 6= 0,
(3) the following distributive laws hold for all a ∈ R, α ∈ RI :
X X
a⊗( αi) = (a ⊗ αi)
i∈I i∈I
X X
( αi) ⊗ a = (αi ⊗ a).
i∈I i∈I
P
Remark 4. If R := (R, +, ⊗, 0, 1, ) is a complete semiring then (Radd , ⊗)
forms a biadditive setup.
Definition 8. A join complete semiring is a complete semiring R such that
Radd is a join complete monoid.
P
Remark 5. If R := (R, +, ⊗, 0, 1, ) is a given join complete semiring then
L(R) := (L(Radd ), ⊗, 1) forms a complete residuated lattice. If on the other
hand L := (L, ⊗, ε) with P L = (L, ≤) is aPgiven residuated complete lattice then
R(L) := (L, +, ⊗, 0, ε, ) with (L, +, 0, ) := A(L) is a join complete semiring.
This establishes a bijection between all join complete semirings on a set R and all
complete residuated lattices on R. In particular for every join complete semiring
P ⊗ ⊗
R := (R, +, ⊗, 0, 1, ) there exist maps → and ← from R × R to R such that
for all r, s, t ∈ R the following holds:
⊗ ⊗
r ≤ (t ← s) ⇐⇒ (r ⊗ s) ≤ t ⇐⇒ s ≤ (r → t)
A more extensive discussion of the interplay between biresiduation and biaddi-
tivity will be presented in section 6.
Proposition 2. Let (A, ⊗) be a biadditive setup where A := (A1 , A2 , A). For
sets G and M define : AG M
1 × A2 → A
G×M
where
(u w)(g, m) := u(g) ⊗ w(m).
Then forms a biadditive map w.r.t. (AG M
1 , A2 , A
G×M
) which is also known as
the dyadic product.
More generally, we have the following construction.
Proposition 3. Let (A, ⊗) be a biadditive setup where A := (A1 , A2 , A). For
sets G, H, and M define
∗ : AG×H
1 × A2H×M → AG×M
where
(β ∗ η)(g, m) := Σh∈H β(g, h) ⊗ η(h, m).
Then ∗ forms a biadditive map w.r.t. (A1G×H , A2H×M , AG×M ) – which, as a mat-
ter of fact, is the matrix product.
If (A, ⊗) is a biadditive setup where A := (A1 , A2 , A) and α ∈ A then a familiy
(uh , wh )h∈H ∈ (A1 × A2 )H will be called a sum-decomposition of (⊗, α) if
α = Σh∈H uh ⊗ wh .
An important observation is the following
Proposition 4. Let (A, ⊗) be a biadditive setup where A := (A1 , A2 , A). Then
for sets G, H, M and α ∈ AG×M the following holds
1. If (β, η) is a decomposition of (∗, α), that is, β ∈ A1G×H and η ∈ A2H×M
such that α = β ∗ η, then (uh , wh )h∈H is a sum-decomposition of (, α)
where uh := β(·, h) and wh := η(h, ·).
2. Conversely, if (uh , wh )h∈H is a sum-decomposition of (, α) then (β, η) is
a decomposition of (∗, α) where β : G × H → A1 , (g, h) 7→ uh g and η :
H × M → A2 , (h, m) 7→ wh m.
Remark 6. An important situation where this proposition can be applied occurs
when R = (R, +, ⊗, 0, 1, Σ) is a complete semiring, since then (Radd , ⊗) is a
biadditive setup as already mentioned in remark 4.
In mathematical morphology the concept of dilation is fundamental, and cru-
cially involves convolution in a general setting which will be layed out in the
following.
5 Construction of Convolution Algebras
The ingredients of our modelling approach for the construction of convolution
algebras are action networks and complete semirings. For this we still need to
introduce networks and action networks.
Definition 9 (network). A triple G := (V, E, %) will be called a network (directed
multigraph) if V and E are sets and % : E → V × V is a map. In this context
we interpret V as the set of nodes, E as the set of edges, and % as the structure
map of G.
Additional Remark: The structure map % of G induces two maps
σ : E → V, e 7→ σe and
e
τ : E → V, e 7→ τ e τe
σe
satisfying %e = (σe, τ e) for all e ∈ E; here we consider σe as source
node and τ e as target node of e.
A pair of edges (c, d) will be called sequential if the target node of c is equal to
the source node of d. The set of all sequential pairs of edges will be denoted by
E h2i . Similarly E h3i will denote the set of all triples of edges (c, d, e) such that
(c, d) and (d, e) are sequential pairs.
Next we consider networks with additional structure. In this situation, edges
will be interpreted as actions which allow concatenation of sequential pairs of
actions.
Definition 10 (action network). A triple G := (G, ∗, id) will be called an action
network (small covariant category) if G := (V, E, %) is a network and
∗ : E h2i → E, (c, d) 7→ c ∗ d and id : V → E
are maps satisfying:
%(c ∗ d) = (σc, τ d) for all (c, d) ∈ E h2i
(c ∗ d) ∗ e = c ∗ (d ∗ e) for all (c, d, e) ∈ E h3i
%(idp) = (p, p) for all p ∈ V
id(σc) ∗ c = c = c ∗ id(τ c) for all c ∈ E.
We interprete E as set of actions and ∗ as concatenation map, which maps
every sequential pair of actions (c, d) to its concatenation c ∗ d. Furthermore, idp
denotes the passive action at node p.
a
Example 3. Any monoid M := (M, ∗, ε) can be interpreted
as action network with {ε} as the singleton node set, M
b ε
as the set of edges, and ∗ as concatenation map as well as
id : {ε} → M , ε 7→ ε.
b
a+
Example 4. Any preordered set P := (P, R) can be interpreted as action net-
work which has (P, R, ρ) as underlying network, where ρ : R → V × V, (p, q) 7→
(p, q), and ∗ : Rh2i → R, ((p, t), (t, q)) 7→ (p, q) as concatenation map and fur-
thermore id : P → R, p 7→ (p, p) as passivity map.
P
Construction 1 (convolution algebra). Let R := (R, +, ·, 0, 1, ) be a complete
semiring and let G := (G, ∗, id) be an action network with underlying network
G := (V, E, %); then the convolution algebra of G over R is given by
X
R[G] := (RE , +, ∗, O, I, ),
where for every index set I for all i ∈ I and ui , u, w ∈ RE as well as e ∈ E the
following hold:
(u + w)e := ue + we
X X
( ui )e := (ui e)
i∈I i∈I
X
(u ∗ w)e := uc · wd
(c,d)∈SplitG (e)
with SplitG (e) := {(c, d) ∈ E h2i |c ∗ d = e} and
O : E → R, e 7→ 0
(
1 for e ∈ idV
I : E → R, e 7→
0 otherwise
Remark 7. If u and w are as above then the product u ∗ w will be called the
convolution of u with w.
Remark 8. In case M := (M, ∗, ε) is a monoid then R[M] is defined as R[G]
where G is the action network associated with M and R[M].
6 Combining Biresiduation and Biadditivity
The following fact will help us to combine biresiduation and biadditivity, which
will be relevant for fuzzy FCA and also for mathematical morphology:
Proposition 5. Let L := (L1 , L2 , L) be a triple of complete lattices and let
⊗ : L1 × L2 → L be a map. Then ⊗ is biresiduated w.r.t. L if and only if ⊗ is
biadditive w.r.t. A(L).
Theorem 1. Let L := (L1 , L2 , L) be a triple of complete lattices and let ⊗ be
a biresiduation w.r.t. L. Then for sets G, R, and M the following holds:
1. is a biresiduation w.r.t. (LG M
1 , L2 , L
G×M
).
Hence, for all u ∈ LG
1 and w ∈ L M
2 and α ∈ LG×M we have
u ≤ (α ← w) ⇐⇒ (u w) ≤ α ⇐⇒ w ≤ (u → α).
Also,
⊗
(α ← w)(g) = infL1 {α(g, m) ← w(m) | m ∈ M }
for all g ∈ G and
⊗
(u → α)(m) = infL2 {u(g) → α(g, m) | g ∈ G}
for all m ∈ M .
2. ∗ is a biresiduation w.r.t. (LG×H
1 , L2H×M , LG×M ).
G×H
Hence, for all β ∈ L1 and η ∈ L2H×M and α ∈ LG×M we have
∗ ∗
β ≤ α ← η ⇐⇒ β ∗ η ≤ α ⇐⇒ η ≤ β → α.
Also,
∗ ⊗
(α ← η)(g, h) = infL1 {α(g, m) ← η(h, m) | m ∈ M }
for all (g, h) ∈ G × H and
∗ ⊗
(β → α)(h, m) = infL2 {β(g, h) → α(g, m) | g ∈ G}
for all (h, m) ∈ H × M .
3. Let α ∈ LG×M and let (β0 , η0 ) be a decomposition of K = (∗, α). Then
there exists a conceptual decomposition (β, η) of K with β0 ≤ β and η0 ≤ η.
The corresponding sum-decomposition (β(·, h), η(h, ·))h∈H of K0 := (, α)
consists of abstract concepts of K0 . Such a sum-decomposition is called con-
ceptual sum-decomposition.
Conversely, if (xh , yh )h∈H is a sum-decomposition of K0 then there ex-
ists a conceptual sum-decomposition (uh , wh )h∈H of K0 with xh ≤ uh and
yh ≤ wh . The corresponding decomposition (β, η) of K defined via
β : G × H → L1 , (g, h) 7→ uh (g)
and
η : H × M → L2 , (h, m) 7→ wh (m)
is a conceptual decomposition of K. If (β, η) is a conceptual decomposition
of K then, by definition, β = α ← η and η = β → α.
Proof. Part 1 follows from Propositions 5 and 2. Part 2 follows from Propositions
5 and 3. Part 3 follows from Proposition 5 and 4 together with Corollary.
The above theorem extends Theorem 6 from [16]. Note that Part 3 of the above
theorem employs a well-known fact from linear algebra: matrix multiplication
can be rewritten as summing over the dyadic products of the respective column
and row vectors.
Remark 9. Referring to remark 6, the last theorem is connected with fuzzy
formal concept analysis in the following way: Let R := (R, +, ⊗, 0, 1, Σ) be a
join complete semiring. Then for sets G, M and α ∈ RG×M , the triple (G, M, α)
will be regarded as fuzzy context over R having the same concept lattice as
the abstract context (, α) w.r.t. (LG , LM , LG×M ) for L := L(Radd ). Also the
decomposition discussed in the third part of the above theorem applies to this
situation.
If we restrict ourselves to the situation of M being a singleton, Theorem 1.1
yields for all r ∈ R and u, v ∈ RG
⊗
u ⊗ r ≤ v ⇐⇒ r ≤ (u → v),
that is, u → v can be interpreted as the degree of u being a subset of v.
P
Theorem 2. For every complete semiring R := (R, +, ⊗, 0, 1, ) and every
action network G := (G, ∗, id) with G := (V, E, %) the convolution algebra R[G]
is a complete semiring.
In case R is join complete then so is R[G]; consequently (L(RE , +, O, ), ∗, I)
P
forms a residuated complete lattice, and for all u, w ∈ RE and all d ∈ E it
follows
∗ ⊗
(u → w)d = inf{uc → w(c ∗ d) | c ∈ E : (c, d) ∈ E h2i }.
Proof. Straightforward calculation yields that R[G] is a complete semiring, which
is join complete if R is join complete.
In the latter, it remains to show that for all u, v, w ∈ RE the following holds:
∗
∀d ∈ E : vd ≤ (u → w)d
∗
⇔v ≤ (u → w)
⇔(u ∗ v) ≤ w
X
⇔∀e ∈ E : uc ⊗ vd ≤ we
(c,d)∈Split(e)
⇔∀e ∈ E, ∀(c, d) ∈ Split(e) : uc ⊗ vd ≤ we
⇔∀(c, d) ∈ E h2i : uc ⊗ vd ≤ w(c ∗ d)
⊗
⇔∀(c, d) ∈ E h2i : vd ≤ uc → w(c ∗ d)
⊗
⇔∀d ∈ E : vd ≤ inf{uc → w(c ∗ d) | c ∈ E : (c, d) ∈ E h2i }
Indeed, the above equivalences immediately imply
⊗ ⊗
(u → w)d = inf{uc → w(c ∗ d) | c ∈ E : (c, d) ∈ E h2i } for all d ∈ E.
P
Construction 2 (dilation and erosion). Let R := (R, +, ⊗, 0, 1, ) be a join
complete semiring and G := (G, ∗, id) be an action network with G := (V, E, %).
Then an element ν ∈ RE will be considered as structuring element of G over R,
and the map
δν : RE → RE , µ 7→ (ν ∗ µ)
is called the dilation via the structuring element ν and the map
∗
εν : RE → RE , µ 7→ (ν → µ)
is the erosion via the structuring element ν. In this setting, µ ∈ RE often plays
the role of an image, the dilation of which via the structuring element ν is given
by
(δν )µ = (ν ∗ µ).
Similarly, the erosion via ν of the image µ is given by
∗
(εν )µ = (ν → µ).
Remark 10. Here, the pair (δν , εν ) is an adjunction on L(RE , +, O,
P
).
A significant application of mathematical morphology is photo editing. Here
we visualize dilation and erosion by using convolution algebras induced via the
t-norms introduced previously.
original Structuring element
dilation erosion
Fig. 1: Lukasiewicz t-norm
dilation erosion
Fig. 2: Gödel t-norm
P
Remark 11 (fuzzy FCA). Referring to construction 2, let R := (R, +, ⊗, 0, 1, )
be a given join complete semiring and G := (G, ∗, id) be an action network with
G := (V, E, %). In this situation, an element η ∈ RE will be considered as input
image and an element ν ∈ RE will be regarded as structuring element. Then
∗
µ := (ν → η) is the erosion of η via ν. From the viewpoint of fuzzy FCA, µ is
the derivation of ν in the abstract context K := (∗, η) w.r.t. (LE , LE , LE ) for
L := L(Radd ).
7 Integration of Isabelle Bloch’s Approach
Isabelle Bloch has been one of the key scientists in developing mathematical mor-
phology and its fuzzifications during the past 20 years (for example we mention
[11,17,18,19] and [20,12,13,21]). In her recent papers on the topic, she considered
as underlying structure a so-called space, which is given by a commutative group
S := (S, +, O).
Construction 3 (dilation and erosion after Bloch - cf. [11]).
Let S := (S, +, O) be a commutative group and ⊗ : [0, 1] × [0, 1] → [0, 1] a left
continuous t-norm. Then Isabelle Bloch defines the dilation via a structuring
element ν : S → [0, 1] as
δν : [0, 1]S → [0, 1]S ,
µ 7→ δν µ
where
(δν µ)x := sup{ν(x − y) ⊗ µy | y ∈ S} for all x ∈ S.
Similarly, the erosion via ν is defined as the map
εν : [0, 1]S → [0, 1]S ,
µ 7→ εν µ
where
⊗
(εν µ)x := inf{ν(y − x) → µy | y ∈ S} for all x ∈ S.
Here δν µ is the dilation of the image µ via the structuring element ν, and εν µ is
the erosion of the image µ via the structuring element ν. Indeed, Bloch proves
that the pair (δν , εν ) forms an adjunction on ([0, 1], ≤).
Remark 12. By theorem 2 it follows immediately that (δν , εν ), as introduced
by Bloch, forms an adjunction on ([0, 1], ≤): Indeed, theorem 2 implies for the
complete semiring R := ([0, 1], ∨, ⊗, 0, 1, sup) that the pair (δν , εν ) forms an
adjunction on R[S], that is, on L(R[S]).
In our final section we will discuss hedges and their role for information reduction.
8 Hedges
Hedges were introduced as parameters controlling the size of a fuzzy concept
lattice [7]. In [22], fuzzy concept lattices with hedges are shown to be essentially
generalized concept lattices in Krajci’s sense. Also, in our framework, they have a
natural place. We find that they are intimately connected with the substructures
of join-complete semirings. A hedge ∗ : L → L is defined as a kernel operator
on L (i.e. a∗ ≤ b ⇐⇒ a∗ ≤ b∗ ) such that it preserves the 1 (1∗ = 1) and
⊗ ⊗
weakly preserves implications ((a → b)∗ ≤ a∗ → b∗ ). Note that this definition
of a hedge obviously generalizes the notion introduced in [7] (monotonicity for
Belohlavek’s notion is shown in [22], Lemma 1). The next theorem shows that
the theory of hedges can also be formulated in a linear algebraic language within
the framework of join-complete semirings.
Theorem 3. Let L = (L, ⊗, ε) be a residuated complete lattice. Then its hedges
are in one-to-one correspondence with the substructures of the join-complete
semiring R(L).
Proof. Since hedges are kernel operators they are in one-to-one correspondence
with their kernel systems (a hedge ∗ is mapped to its image set L∗ ).
Let ∗ be a hedge on L. We will show that its image set L∗ forms a substructure
(join-complete sub-semiring) of R(L). We know already that L∗ is closed under
joins, that 1∗ = 1 ∈ L∗ , and that 0∗ = 0 ∈ L∗ . To show that L∗ is closed under
⊗ we will verify that a ⊗ b = (a ⊗ b)∗ holds for all a, b ∈ L∗ ; it suffices to prove
a ⊗ b ≤ (a ⊗ b)∗ :
a⊗b≤a⊗b
⊗
⇐⇒ b ≤ (a → (a ⊗ b))
⊗
=⇒ b∗ ≤ (a → (a ⊗ b))∗
⊗
=⇒ b∗ ≤ (a∗ → (a ⊗ b)∗ )
⇐⇒ a∗ ⊗ b∗ ≤ (a ⊗ b)∗
Since a∗ = a and b∗ = b we conclude the argument.
Let K be a substructure of a given join-complete semiring R(L). Since K is closed
under arbitrary joins it forms a kernel system in L inducing its kernel operator ∗ .
Thus, K = L∗ and 1 ∈ L∗ . It remains to be shown that implications are weakly
preserved by ∗ :
⊗ ⊗
(a → b) ≤ (a → b)
⊗
⇐⇒ a ⊗ (a → b) ≤ b
⊗
=⇒ a∗ ⊗ (a → b)∗ ≤ b
⊗
Since K is a substructure of R(L) the element a∗ ⊗ (a → b)∗ is a kernel and we
⊗ ⊗ ⊗
get a∗ ⊗ (a → b)∗ ≤ b∗ , which implies (a → b)∗ ≤ (a∗ → b∗ ).
Remark 13 (construction of hedges via substructures). Let G := (G, ∗, id) be
an action network with G := (V, E, %). We say that a subset D of E forms
a substructure of GPif idV ⊆ D and c ∗ d ∈ D holds for all (c, d) ∈ Dh2i . If
R := (R, +, ⊗, 0, 1, ) is a complete semiring and D forms a substructure of G,
then the set
U := {u ∈ S E | ue = 0 for all e ∈ E \ D}
forms a substructure of the complete semiring R[G]. In case R is a join complete
semiring, the hedge associated with U is given by
∗
: RE → RE , u 7→ uD
where uD e := ue for all e ∈ D and uD e := 0 for all e ∈ E \ D.
One application of the above for mathematical morphology is when the action
network is given by Z2add and the substructure is D := 2Z2 , where the join com-
plete semiring R is induced by a t-norm.
Finally we present a generalization of the concept of hedges.
Proposition 6. Let ⊗ : P1 × P2 → P be a biresiduation and let (∗1 ,∗2 ,∗ ) be a
triple of kernel operators. The following are equivalent
⊗ ⊗
1. ∀p1 ∈ P1 , ∀p ∈ P : (p1 → p)∗2 ≤ p∗1
1 →p
∗
2. ∀p1 ∈ P1 , ∀p2 ∈ P2 : p∗1
1 ⊗ p∗2
2 ≤ (p 1 ⊗ p2)
∗
∗1 ∗2 ∗
3. P1 ⊗ P2 ⊆ P
A star system is a triple of kernel operators where one of the above conditions
holds.
Proof. “ 1 ⇒ 2”:
p1 ⊗ p2 ≤ p1 ⊗ p2
⊗
⇐⇒ p2 ≤ (p1 → (p1 ⊗ p2 ))
⊗
=⇒ p∗2
2 ≤ (p1 → (p1 ⊗ p2 ))
∗2
⊗
=⇒ p∗2 ∗1
2 ≤ (p1 → (p1 ⊗ p2 ) )
∗
=⇒ p∗1
1 ⊗ p∗2
2 ≤ (p1 ⊗ p2 )∗
“ 2 ⇒ 1”:
⊗ ⊗
(p1 → p) ≤ (p1 → p)
⊗
⇐⇒ (p1 ⊗ (p1 → p)) ≤ p
⊗
=⇒ (p1 ⊗ (p1 → p))∗ ≤ p∗
⊗
=⇒ (p∗1 ∗2
1 ⊗ (p1 → p) ) ≤ p
∗
⊗ ⊗ ∗
⇐⇒ (p1 → p)∗2 ≤ (p∗1
1 →p )
“ 2 ⇒ 3”: By 2, p∗1 ∗2 ∗1 ∗2 ∗
1 ⊗ p2 ≤ (p1 ⊗ p2 ) and since
∗
is a kernel operator we have
∗1 ∗2 ∗
equality and therefore p1 ⊗ p2 ∈ P .
“ 3 ⇒ 2”: Since p∗1 ∗2 ∗1 ∗2 ∗
1 ⊗ p2 ≤ p1 ⊗ p2 and p1 ⊗ p2 ∈ P we have p1 ⊗ p2 ≤
∗1 ∗2
∗
(p1 ⊗ p2 ) .
The previous proposition gives rise to the following application.
Proposition 7. Let L := (L1 , L2 , L), P := (P1 , P2 , P) be triples of complete
lattices and let ⊗L : L1 × L2 → L and ⊗P : P1 × P2 → P be biresiduations. Then
for every morphism Φ := (ϕ1 , ϕ2 , ϕ) from (A(L), ⊗L ) to (A(P), ⊗P ) the triple
(ϕ1 ◦ ϕ+ + +
1 , ϕ2 ◦ ϕ2 , ϕ ◦ ϕ ) forms a star system w.r.t. (P, ⊗P ).
Proof. It suffices to verify property 3 from the previous proposition:
(ϕ1 ◦ ϕ+ + + + +
1 )P1 ⊗P (ϕ2 ◦ ϕ2 )P2 = ϕ(ϕ1 P1 ⊗L ϕ2 P2 ) ⊆ ϕL = (ϕ ◦ ϕ )P.
As a consequence of our considerations we receive the following extension of
Theorem 3.
Theorem 4. Let ⊗ be a biresiduation on a triple of complete lattices L :=
(L1 , L2 , L). Then the star systems w.r.t. (L, ⊗) are in one-to-one correspondence
with the substructures of (A(L), ⊗).
9 Conclusion
Some background information: Our paper is indeed based on our 2012 paper
”A Macroscopic Approach to FCA and its Various Fuzzifications” but goes far
beyond it. Who carefully reads our present paper will realize that notions have
been refined and adjusted to our situation. Roughly said, biresiduation general-
izes residuated posets while biadditivity generalizes complete semirings. What
we mainly need is a specialization where these two concepts meet, that is, resid-
uated complete lattices (algebraic logic point of view) which correspond to join
complete semirings (linear algebra point of view). The importance of the latter
point is for constructions.
Looking into Isabelle Bloch’s constructions for mathematical morphology, we
found out that there is a general framework in linear algebra over complete
semirings which is outlined in section 5, named ”Construction of Convolution
Algebras”. These turn out to be again complete semirings. So the bijective corre-
spondence between residuated complete lattices and join complete semirings can
be lifted from a ”coordinate level” to a ”space level”. That is what Bloch essen-
tially does in a special situation (without putting this into a general framework)
and we derive from the general construction of convolution algebras over join
complete semirings (and a subsequent paradigm shift into residuated complete
lattices).
References
1. Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.
Springer, Berlin/Heidelberg (1999)
2. Krajci, S.: The basic theorem on generalized concept lattice. In Snásel, V., Be-
lohlávek, R., eds.: CLA. Volume 110 of CEUR Workshop Proceedings., CEUR-
WS.org (2004)
3. Medina, J., Ojeda-Aciego, M., Ruiz-Calviño, J.: Formal concept analysis via multi-
adjoint concept lattices. Fuzzy Sets and Systems 160(2) (2009) 130–144
4. Medina, J., Ojeda-Aciego, M.: On the representation theorem of multi-adjoint
concept lattices. In Carvalho, J.P., Dubois, D., Kaymak, U., da Costa Sousa, J.M.,
eds.: IFSA/EUSFLAT Conf. (2009) 1091–1095
5. Davey, B.A., Priestley, H.A.: Introduction to lattices and order. Cambridge Uni-
versity Press, Cambridge (1990)
6. Belohlávek, R., Vychodil, V.: Factor analysis of incidence data via novel decompo-
sition of matrices. In Ferré, S., Rudolph, S., eds.: ICFCA. Volume 5548 of Lecture
Notes in Computer Science., Springer (2009) 83–97
7. Belohlávek, R., Vychodil, V.: Reducing the size of fuzzy concept lattices by hedges.
In: FUZZ-IEEE 2005. The IEEE International Conference on Fuzzy Systems, 22-25
May, Reno, NV, USA. (2005) 663–668
8. Belohlávek, R.: What is a fuzzy concept lattice? ii. In Kuznetsov, S.O., Slezak,
D., Hepting, D.H., Mirkin, B., eds.: Rough Sets, Fuzzy Sets, Data Mining and
Granular Computing. Volume 6743 of LNCS., Springer (2011) 19–26
9. Belohlávek, R., Vychodil, V.: What is a fuzzy concept lattice? In Bělohlávek, R.,
Snáŝel, V., eds.: Proc. CLA 2005. Volume 162 of CEUR WS., Palacký University
in Olomouc, VŠB – Technical University of Ostrava (2005) 34–45
10. Blyth, T.: Lattices and Ordered Algebraic Structures. Universitext, Springer
(2005)
11. Bloch, I.: Duality vs. adjunction for fuzzy mathematical morphology and general
form of fuzzy erosions and dilations. Volume 160. Elsevier (2009) 1858–1867
12. Bloch, I.: Fuzzy sets and mathematical morphology. Wiley Online Library (2013)
155–176
13. Bloch, I., Maı̂tre, H.: Fuzzy mathematical morphology. Volume 10. Springer (1994)
55–84
14. Kaiser, T.B., Schmidt, S.E.: A macroscopic approach to fca and its various fuzzifi-
cations. In Domenach, F.e.a., ed.: Formal Concept Analysis, Proceedings of ICFCA
2012. Volume 7278 of LNAI., Springer (2012) 140–147
15. Droste, M., Kuich, W., Vogler, H.: Handbook of Weighted Automata. Monographs
in Theoretical Computer Science, Springer (2009)
16. Belohlávek, R.: Optimal decompositions of matrices with entries from residuated
lattices. Journal of Logic and Computation (2011)
17. Bloch, I.: Bipolar fuzzy mathematical morphology for spatial reasoning. In: Math-
ematical Morphology and Its Application to Signal and Image Processing. Springer
(2009) 24–34
18. Bloch, I., Maı̂tre, H.: Ensembles flous et morphologie mathématique. (1992)
19. Bloch, I., Preteux, F., Boulanger, F., Soussaline, F.: A meta-model for segmenta-
tion problems in mathematical morphology. In de Graaf, C., Viergever, M., eds.:
Information Processing in Medical Imaging. Springer US (1988) 45–64
20. Bloch, I.: Lattices of fuzzy sets and bipolar fuzzy sets, and mathematical morphol-
ogy. Volume 181. (2011) 2002 – 2015
21. Bloch, I., Maı̂tre, H.: Constructing a fuzzy mathematical morphology: alternative
ways. In: Fuzzy Systems, 1993., Second IEEE Int. Conf., IEEE (1993) 1303–1308
22. Krajci, S.: Every concept lattice with hedges is isomorphic to some generalized
concept lattice. In Snásel, V., Belohlávek, R., eds.: CLA 2005 proceedings, ISBN
80–248–0863–3. (2005) 1–9