Construction du treillis de Galois d'une relation binaire
Guénoche, A.
Mathématiques et Sciences humaines, Tome 112 (1990), p. 41-53 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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, Alain},
     title = {Construction du treillis de Galois d'une relation binaire},
     journal = {Math\'ematiques et Sciences humaines},
     volume = {112},
     year = {1990},
     pages = {41-53},
     mrnumber = {1053895},
     zbl = {0707.06003},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/MSH_1990__109__41_0}
}

Guénoche, A. Construction du treillis de Galois d'une relation binaire. Mathématiques et Sciences humaines, Tome 112 (1990) pp. 41-53. http://gdmltest.u-ga.fr/item/MSH_1990__109__41_0/

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

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

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

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

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 868423

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

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 0361.05047

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

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 0196.51801

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 505912 | Zbl 0389.05003

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

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.