Construction du treillis de Galois d'une relation binaire
Mathématiques informatique et sciences humaines, Tome 109 (1990), pp. 41-53.

Cet article constitue une présentation unifiée des principales méthodes de construction du treillis de Galois d'une correspondance. Nous rappelons d'abord sa définition, puis nous décrivons quatre algorithmes de construction des éléments du treillis qui sont les rectangles maximaux de la relation binaire. Ces algorithmes ne sont pas originaux. Les descriptions précises de algorithmes, le plus souvent absentes des publications originales, permettent une programmation simple, dans un langage procédural à l'aide d'une structure de données commune.

This text is a survey of different methods used to build the Galois Lattice of a binary relation between two finite sets. We first recall its definition and common notations. Then we present four algorithms to construct the elements of the lattice that are maximal rectangles in the binary relation. These algorithms have already been published during these last twenty years. Precise descriptions, often missing in the original publications, are given and permit a simple programming job in any procedural language.

@article{MSH_1990__109__41_0,
     author = {Gu\'enoche, A.},
     title = {Construction du treillis de {Galois} d'une relation binaire},
     journal = {Math\'ematiques informatique et sciences humaines},
     pages = {41--53},
     publisher = {Ecole des hautes-\'etudes en sciences sociales},
     volume = {109},
     year = {1990},
     mrnumber = {1053895},
     zbl = {0707.06003},
     language = {fr},
     url = {http://archive.numdam.org/item/MSH_1990__109__41_0/}
}
TY  - JOUR
AU  - Guénoche, A.
TI  - Construction du treillis de Galois d'une relation binaire
JO  - Mathématiques informatique et sciences humaines
PY  - 1990
SP  - 41
EP  - 53
VL  - 109
PB  - Ecole des hautes-études en sciences sociales
UR  - http://archive.numdam.org/item/MSH_1990__109__41_0/
LA  - fr
ID  - MSH_1990__109__41_0
ER  - 
%0 Journal Article
%A Guénoche, A.
%T Construction du treillis de Galois d'une relation binaire
%J Mathématiques informatique et sciences humaines
%D 1990
%P 41-53
%V 109
%I Ecole des hautes-études en sciences sociales
%U http://archive.numdam.org/item/MSH_1990__109__41_0/
%G fr
%F MSH_1990__109__41_0
Guénoche, A. Construction du treillis de Galois d'une relation binaire. Mathématiques informatique et sciences humaines, Tome 109 (1990), pp. 41-53. http://archive.numdam.org/item/MSH_1990__109__41_0/

Barbut M., Monjardet B., Ordre et Classification, Algèbre et Combinatoire (tome 2), Paris, Hachette, 1970. | Zbl

Birkhoff G., Lattice Theory, A.M.S., 25, Providence, 1967. | MR | Zbl

Bordat J.P., Calcul pratique du treillis de Galois d'une correspondance, Mathématiques et Sciences humaines, 96, 1986, p. 31-47. | Numdam | MR | Zbl

Chein M., Algorithme de recherche des sous-matrices premières d'une matrice, Bull. Math. R.S. Roumanie, 13, 1969. | MR | Zbl

Duquenne V., Guigues J.L., Familles minimales d'implications informatives résultant d'un tableau de données binaires, Mathématiques et Sciences humaines, 95, 1986, p. 5-18. | Numdam | MR

Fay G., An algorithm for finite Galois connexions, Journal of Computational Linguistic and Computational Languages, 10, 1975, p. 99-123. | MR | Zbl

Ganter B., Two basic algorithms in Concept Analysis, Preprint 831, Technische Hochschule Darmstadt, 1984, 28p.

Kaufmann A., Pichat E., Méthodes mathématiques non numériques et leurs algorithmes, Paris, Masson, 1977. | Zbl

Lavallée I., Rectangles maximaux dans une relation binaire quelconque, Preprint Université Paris VI, p.157-171. | MR | Zbl

Malgrange Y., Recherche des sous-matrices premières d'une matrice à coefficients binaires; Application à certains problèmes de graphe, Deuxième congrès de l'AFCALTI, Gauthier-Villars, 1962, p. 231-242. | Zbl

Norris E.M., An algorithm for computing the maximal rectangles in a binary relation, Revue Roumaine de Mathématiques Pures et Appliquées, 1978, 23, 2, p. 243-250. | MR | Zbl

Wille R., Restructuring lattice theory : an approach based on hierarchies of concepts, in Ordered Sets, I. Rival (Ed.), Dordrecht, Reidel, 1982. | MR | Zbl

Wille R., Knowledge acquisition by methods of formal concept analysis, Data Analysis, Learning symbolic and numeric knowledge, E. Diday (Ed.), New York, Nova Science Publisher, 1989, p. 365-380.