Preface of the special issue on concept lattices and their applications

This special issue is devoted to selected revised papers of the 2015 International Conference on Concept Lattices and their Applications (CLA’2015) held in Clermont-Ferrand (France).

The first attempt to define a lattice theory, as a mathematic model, was made by Birkhoff (1940). An underlying deep concept is the notion of Galois connection that emerged in the early 1940s, after a long gestation since the beginning of the twentieth century. Over the last two decades, research has demonstrated how concept lattices formalize conceptual structures by coding any kind of duality, such as the duality between the intent and the extent of a concept. Application in data analysis using this duality for analyzing questionnaire data was done by Barbut and Monjardet in the domain of social sciences (Barbut and Monjardet 1970). The concept lattice also named “Galois lattice” was then promoted by R. Wille, and then extended as a discipline called formal concept analysis (Ganter and Wille 1999).

Formal concept analysis (FCA) is a mathematical tool for analyzing data and formally representing conceptual knowledge. FCA helps forming conceptual structures from data. Such structures consist of units, which are formal abstractions of concepts of human thought allowing meaningful and comprehensible interpretation. FCA is a mathematical discipline whose features include:

(1)	Visualizing inherent properties in data-sets,
(2)	interactively exploring attributes of objects and their corresponding contexts, and
(3)	formally classifying systems based on relationships among objects and attributes through the concept of mathematical lattices.

Several subareas of research can be unified by their common interest in concept lattices structures, which are starting to play an important role in all computer science fields, as pointed out by the different special issues appeared in well-known journals. Thus, FCA mathematical settings have recently been shown to provide a theoretical framework for the efficient resolution of many practical problems from data mining, software engineering, and information retrieval, to name just a few.

The ultimate aim of this special issue is to provide state-of-the-art information to academics, researchers, and industry practitioners whom are involved or interested in both theoretical and practical aspects of formal concept analysis.

Among the 20 papers presented during the conference, this special issue attracted eight submissions, of which seven were accepted after a careful, two-level reviewing process. From the harvest of selected papers, specially theoretical aspects of FCA are covered.

These contributions, putting the focus on algorithmic aspects of concept lattices, also show links of FCA with domains such as Knowledge Extraction.

Albano and Chornomaz introduce this issue by reporting on results regarding the extremal combinatorics of (concept) lattices. The occasional explosion of some lattices is rigorously explained through a sharp upper bound, which is shown to be linked with a famous lemma of Sauer and Shelah and the notion of Vapnik–Chervonenkis dimension.

In the second paper, Kauer and Krupka propose a contribution to basic theoretical foundations of FCA. It shows how methods of FCA can be used to compute efficiently the complete sublattice of a complete lattice generated by a given subset.

The third paper, authored by Kriegel, proposes a parallel algorithm for computing canonical bases of formal contexts with respect to implicational background knowledge. In particular, it is not required that the background knowledge must be valid in the formal context to be axiomatized. Experimental results are presented, and it is concluded that for sufficiently large data-sets the speed-up is proportional to the number of available CPU cores.

Kriegel, in the fourth paper, introduces probabilistic formal contexts and a corresponding notion of probability of implications. A construction for bases of implications the probabilities of which exceed a pre-defined threshold is presented and its soundness and correctness is proven. The results are then extended to the light-weight description logic EL, which allows for the usage of binary roles for interconnecting individuals in the data-set to be analyzed. Eventually, in order to provide a higher expressivity the notion of a quantified attribute is defined and a technique for computing corresponding bases is shown.

The fifth paper, authored by Kridlo et al., puts the focus on the importance of the Chu construction in the categorical description of the theory of FCA and its generalizations, in particular, the second-order FCA, can be represented in terms of the arrows of CHU. The Chu construction plays here the role of some recipe for constructing a suitable category that covers the second-order generalization of FCA.

Rodriguez-Lorenzo et al., in the sixth paper, introduce a new algorithm to compute the D-basis from a given set of implications is proposed. The work is based on a new technique that allows to build minimal generators and prune the non-minimal covers at the same time. The authors have carried out an experiment which provides evidence that the introduced method is very efficient for the computation of the D-basis.

Uta Priss authored the last paper of this special issue. She introduces the Semiotic-Conceptual Analysis (SCA), which is a mathematical modeling of core semiotic and linguistic notions (such as “sign”, “interpretation”, “synonymy” and “polysemy”). SCA considers signs as having three components each of which can be represented by an FCA concept lattice. Mathematically interesting questions for SCA are whether and how structures among sets of signs relate to lattice theoretical structures.

We would like to take this opportunity to acknowledge the tireless cooperation and support of the reviewers, even if deadlines were tight. All submissions were reviewed by at least two reviewers. The preeminent panel of reviewers composing the Program Committee, that worked diligently to guarantee a thorough review of each paper, was as follows:

Jaume Baixeries (UPC, Spain), Alexander Bazin (Blaise Pascal University, Clermont-Ferrand, France), Marco Cerami (Palacky University, Olomouc, Czech Republic), Dmitry Ignatov (State University Higher School of Economics, Moscow, Russia), Leonard Kwuida (University of Bern, Switzerland), Jan Konecny (Olomouc University, Czech Republic), Tarek Hamrouni (ISAMM, Manouba, Tunisia), Amedeo Napoli (LORIA, Nancy, France), Michal Krupka (Palacky University, Olomouc, Czech Republic), Francesco Kriegel (Technische Universitaet Dresden, Germany), Petr Osicka (Palacky University, Olomouc, Czech Republic), Francois Rioult (GREYC, Caen, France), Christian Sacarea (Babes-Bolyai University of Cluj-Napoca, Romania), Jan Outrata (Palacky University, Olomouc, Czech Republic), Francisco J. Valverde-Albacete (University Carlos III, Madrid, Spain).

In closing, we would like to express our gratitude to the authors who contributed to this ijgs special issue that will definitely be of great interest for everyone working in the field of concept lattices and their applications. Last but not least, we are grateful to the ijgs Editor-in-Chief, Radim Belohlavek who provided continuous support and advice during the preparation of this special issue.

Sadok Ben Yahia and Jan Konecny, Guest Editors

Sadok Ben Yahia Faculté des Sciences de Tunis, Université de Tunis El Manar, LIPAH,LR11ES14, Tunisia[email protected] Jan Konecny Dept. Computer Science, Palacky University in Olomouc, Czech Republic