Construction du treillis de Galois d'une relation binaire

A. Guénoche

Mathématiques et Sciences Humaines (1990)

  • Volume: 109, page 41-53
  • ISSN: 0987-6936

Abstract

top
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.

How to cite

top

Guénoche, A.. "Construction du treillis de Galois d'une relation binaire." Mathématiques et Sciences Humaines 109 (1990): 41-53. <http://eudml.org/doc/94390>.

@article{Guénoche1990,
abstract = {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.},
author = {Guénoche, A.},
journal = {Mathématiques et Sciences Humaines},
keywords = {survey; Galois lattice of a binary relation; algorithms},
language = {fre},
pages = {41-53},
publisher = {Ecole des hautes-études en sciences sociales},
title = {Construction du treillis de Galois d'une relation binaire},
url = {http://eudml.org/doc/94390},
volume = {109},
year = {1990},
}

TY - JOUR
AU - Guénoche, A.
TI - Construction du treillis de Galois d'une relation binaire
JO - Mathématiques et Sciences Humaines
PY - 1990
PB - Ecole des hautes-études en sciences sociales
VL - 109
SP - 41
EP - 53
AB - 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.
LA - fre
KW - survey; Galois lattice of a binary relation; algorithms
UR - http://eudml.org/doc/94390
ER -

References

top
  1. Barbut M., Monjardet B., Ordre et Classification, Algèbre et Combinatoire (tome 2), Paris, Hachette, 1970. Zbl0267.06001
  2. Birkhoff G., Lattice Theory, A.M.S., 25, Providence, 1967. Zbl0153.02501MR227053
  3. Bordat J.P., Calcul pratique du treillis de Galois d'une correspondance, Mathématiques et Sciences humaines, 96, 1986, p. 31-47. Zbl0626.06007MR878296
  4. Chein M., Algorithme de recherche des sous-matrices premières d'une matrice, Bull. Math. R.S. Roumanie, 13, 1969. Zbl0209.06401MR263225
  5. 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. MR868423
  6. Fay G., An algorithm for finite Galois connexions, Journal of Computational Linguistic and Computational Languages, 10, 1975, p. 99-123. Zbl0359.06009MR429692
  7. Ganter B., Two basic algorithms in Concept Analysis, Preprint 831, Technische HochschuleDarmstadt, 1984, 28p. Zbl1274.68484
  8. Kaufmann A., Pichat E., Méthodes mathématiques non numériques et leurs algorithmes, Paris, Masson, 1977. Zbl0361.05047
  9. Lavallée I., Rectangles maximaux dans une relation binaire quelconque, Preprint Université Paris VI, p.157-171. Zbl0414.90057MR541245
  10. 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. Zbl0196.51801
  11. 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. Zbl0389.05003MR505912
  12. Wille R., Restructuring lattice theory : an approach based on hierarchies of concepts, in Ordered Sets, I. Rival (Ed.), Dordrecht, Reidel, 1982. Zbl0491.06008MR661303
  13. 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. 

NotesEmbed ?

top

You must be logged in to post comments.