Although lattice theory is a rich field dating from Dedekind, Birkhoff and O¨re, few studies in FCA use lattice properties to enhance their results. Moreover, out of the many cryptomorphisms associated with lattices, only the ones associating context, lattice and implicational system are effectively studied. CryptoLat is a software implemented in C] which provides an intuitive view on different cryptomorphisms of lattices as well as on different properties of lattices. Its purpose is pedagogical, for students and researchers likewise, and work by showing incremental changes in the lattice and the associated cryptomorphisms.
This article, together with the software, originates from an observation about the
current state of research in the lattice and the FCA communities. Lattice theory
dates back to the works of Dedekind, Birkhoff [
Although it is natural that this dichotomy exists because of the nature of each
community’s focus of interest, it is the author’s suggestion that improvement of
the communication between the two communities may produce a synergistic
effect. The study of lattice cryptomorphisms and lattice properties is important
for many reasons: other than giving a better understanding of the tools being
used, it was shown to lead to the discovery of efficient algorithms in counting
the number of Moore families [
There are two main purposes for this software: first, to promote and to give a better understanding of the many shapes and forms of lattices thanks to an incremental approach - any change made in any equivalent cryptomorphism is c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 93{103, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes. transcribed to the other cryptomorphisms. Second, to help familiarize users to fundamental latticial properties that are recalculated after any modification. Its purpose is pedagogical for both students and researchers. Students can learn and get a better understanding on what is happening during the construction of the lattice and the implicational basis, while researchers can test hypotheses and find small illustrating examples. The program is written in C] and is freely available (executable and source code) at http://www.cs.unic.ac.cy/ florent/software.htm
This paper is organized as follows: we start in Sec. 2 by describing the software itself. Sec 3 will recall the well-known definitions of lattices and some of the existing cryptomorphisms implemented in CryptoLat, together with a short explanation on how the equivalence is done. Finally, we compare in Sec. 5 CryptoLat with already existing software. 2
CryptoLat software is structured around a model view controller type of software architecture: each cryptomorphism described in Sec. 3 is a view with which the user can interact. The model is the reduced context associated with a Moore family on which all the calculations are based. When a view is updated, by adding or deleting a Sperner family for example, then the Moore family associated is calculated, the associated concept lattice, together with all the properties, is computed, and the other views get updated.
Depending on which view getting updated, the process may involve different steps. If the overhanging list or the Sperner village change, then first the Moore family associated with the new list, and the reduced context is then calculated. Similarly, if the input is an arbitrary set system, then the closure system is calculated as in Sec. 3.2. If the input is on the set of implications, since implications are usually on the set of attributes, the corresponding Moore family will be dual to the previous ones. From the reduced context, we are using Closed by One algorithm to calculate the concept lattice.
Fig. 1 shows a screen shot of the software with the five different views: the Moore family on top, the context as a datagrid, the list of implications, the list of overhanging and the list of Sperner families. The drawing of the lattice is done with a simple algorithm that optimise the position of each concept depending on the number (and position) of concepts covered. 3
In this section, we present the different cryptomorphisms of lattices implemented
in CryptoLat in details; we do not claim to be exhaustive, so we refer the readers
to [
One can associate an order on the elements of L to these operators as follow: ∀x, y ∈ L, x ≤ y if x ∧ y = x or, equivalently, x ∨ y = y. Fig. 2 shows a lattice having six elements using its Hasse diagram representation: the elements of L are depicted by nodes in the plane, and a line segment connects the nodes corresponding to a covering pair x ≺ y (i.e. x ≤ y and ∀z, x ≤ z ≤ y implies x = z or y = z), where the node representing y is placed ’higher’ in the plane than the node representing x.
Some elements of lattices are of particular interest: in any lattice, we have a minimal element, usually denoted by 0L or ⊥, and a maximal element 1L or >. Irreducible elements of the lattice are also the subject of studies since they constitute minimal generating sets, and are often used to characterize classes of lattices. An element j of L is join-irreducible if j = ∨X then j ∈ X, or, f c a b e
d equivalently, j covers only one element in L. Dually, an element m of L is meetirreducible if m = ∧X then m ∈ X, or m is covered by only one element of L. Let JL and ML be the sets of join and meet-irreducible of L. Let S be a finite set. A closure system (or Moore family) C on S is a family of subsets of S satisfying S ∈ C and, for all A, B ∈ C, A ∩ B ∈ C. A closure system is a lattice with the following operations: – C1 ∧ C2 = C1 ∩ C2 – C1 ∨ C2 = ∩{C ∈ C : C1 ∪ C2 ⊆ C}
Let A be an arbitrary set system on a set S. Then one can associate a closure system CA to A:
CA = {∩{Ai : Ai ∈ A}} ∪ {S} Example 1 (continued). The family {∅, {G0}, {G1}, {G2}, {G1, G2}, {G0, G1, G2}}, with the operators previously defined, constitute a lattice isomorphic to the lattice of Fig. 2.
Another fundamental cryptomorphism of lattice concerns closure operators.
A closure operator on a set S is a map σ : P(S) → P(S) satisfying ∀X, Y ⊆ S:
– Isotone: X ⊆ Y ⇒ σ(X) ⊆ σ(Y )
– Extensive: X ⊆ σ(X)
– Idempotent: σ(σ(X)) = σ(X)
These three properties together are equivalent to extensivity and path
independence property [
The well-known equivalence between closure operators and closure systems is the following: given the closure system C, the associated closure operator is σC (X) = ∩{C ∈ C : X ⊆ C}. Conversely, given a closure operator σ, the associated closure system is the set of fixed points of σ, i.e. Cσ = {X ⊆ S : X = σ(X)}.
Context Associated with a Lattice
One of the most celebrated cryptomorphism in the FCA community is the one
between a lattice and a binary relation, also known as the basic theorem of
Formal Concept Analysis [
Formally, a context (G, M, I) is a binary relation I between a set of objects G and a set of attributes M . One can associate the Galois connection between P(G) and P(M ) to this binary relation as ∀A ⊆ G, B ⊆ M ,
A0 = {m ∈ M : ∀g ∈ A, (g, m) ∈ I}
B0 = {g ∈ G : ∀m ∈ B, (g, m) ∈ I}
The lattice associated with the context (G, M, I), also called the concept lattice or Galois lattice, is the set of all concepts (A, B), with A0 = B and B0 = A, together with the order (A1, B1) ≤ (A2, B2) ⇐⇒ A1 ⊆ A2 ( ⇐⇒ B1 ⊇ B2). Conversely, any lattice L is isomorphic to the Galois lattice of the context (JL, ML, ≤), also called the reduced context.
Two other binary relations, the arrows relations, on P(J ) × P(M ) are often used for characterization theorems. Let j ∈ J, m ∈ M , we define: – j ↑ m – j ↓ m – j l m ⇐⇒ j 6≤ m and j < m+ ⇐⇒ j 6≤ m and j− < m ⇐⇒ j ↑ m and j ↓ m Example 1 (continued). The lattice associated with the context of Fig. 3 is isomorphic to the lattice of Fig. 2. – A → B and B → C imply A → C; – A → B and C → D imply (A ∪ C) → (B ∪ D).
[
Example 1 (continued). The complete implicational system associated with the lattice in Fig. 2 is the following: c → e; d → e; b, c → d; b, c → e; bc → d, e; b, d → c; b, d → e; b, d → c, e; b, e → c; b, e → d; b, e → c, d; c, d → b; c, d → e; c, d → b, e; c, d, e → b; b, d, e → c; b, c, e → d; b, c, d → e;
As the above example shows, many implications in a complete implicational system can be redundant: in our example, it is evident that if we have c → e then we have b, c → e. So smaller implicational system allowing a smaller representation of a complete implicational system is of interest. We say that an implicational system Σ is a generating system for I if any implication of I can be obtained from Σ by applying recursively the rules defining a complete implicational system. A minimal generating system for I is called a basis for I, and a minimum basis is called a canonical basis.
One particular basis, called the stem basis [
b, e → c, d; c → e; d → e; c, d, e → b; 3.5
Overhanging Relation
An overhanging relation O is a binary relation on P(S) that was originated in
[
A O B or B O C];
We showed in [
Sperner Family A Sperner family F on S is a family s.t. ∀X, Y ∈ F, X and Y are incomparable for set inclusion. A Sperner village V = (F1, ..., Fn) on S is a set of n Sperner families. The equivalence between a closure operator and a Sperner village is obtained as follows: given σ closure operator, for any x ∈ S we create the Sperner family Cx = {X ⊆ S : x ∈ σ(X) and X minimal for that property}. Conversely, the closure operator associated with V is defined as σ(X) = {x ∈ S : X contains a set of Cx}.
Example 1 (continued). The Sperner village equivalent with our running example is the following Fig. 4.
When we add to the existing Sperner village the Sperner family {{e}, {b, c}},
the software computes the smallest Sperner village possible from the existing
village together with the new family, and from this Sperner village finds the
associated concept lattice. Fig. 5 shows the results.
The main focus of the software concerns the dependency between the different
cryptomorphisms associated with lattices. In the same pedagogical spirit, we
also implemented different properties of lattices and elements of lattices, briefly
described in Tab. 1 and in Tab. 2 for completeness sake. We refer the readers to
[
All of the software mentioned in Table 3 have different goals. In terms of ease of use, Concept Explorer is the closest to our goal, but offers limited functionalities. OpenFCA is similar to Concept Explorer, offering an interesting, web based and intuitive approach to context creation, lattice visualization and attribute exploration. FCAstone’s main purpose is file formats conversion to improve interoperability between FCA and graph editing. The other software (Galicia, ToscanaJ, Lattice Miner, FCART) were designed to push the boundaries of the scalability of analysis and lattice drawing. Research wise, Formal Concept Analysis Research Toolbox (FCART) is a particularly interesting approach of a universal x is distributive ∀y, z ∈ L, x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) x is standard ∀y, z ∈ L, y ∧ (x ∨ z) = (y ∧ x) ∨ (y ∧ z) x is neutral ∀y, z ∈ L, (x ∧ y) ∨ (y ∧ z) ∨ (x ∧ z) = (x ∨ y) ∧ (x ∨ z) ∧ (y ∨ z) x is an articulation point ∀y ∈ L, either x ≤ y or y ≤ x x is join-prime x ≤ a ∨ b implies x ≤ a or x ≤ b x is meet-prime a ∧ b ≤ x implies a ≤ x or b ≤ x integrated environment to lattice construction and Formal Concept Analysis techniques, where one can test new algorithms for drawing lattice for example. CryptoLat is a pedagogical and research oriented software in active development phase, and it is open source and freely available. It is still in alpha testing, and the next milestone of development is to make it cloud based with a web interface.
Many other cryptomorphisms of concept lattices exist but are not
implemented yet. For example, [