# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
A fast algorithm for building lattices. (English) Zbl 0998.06005
Summary: This paper presents a simple, efficient algorithm to compute the covering graph of the lattice generated by a family $B$ of subsets of a set $X$. The implementation of this algorithm has $O((|X|+|B|)||B|)$ time complexity per lattice element. This improves previous algorithms of Bordat (1986), Ganter and Kuznetsov (1998) and Jard et al. (1994). This algorithm can be used to compute the Galois (concept) lattice, the maximal antichains lattice or the Dedekind-MacNeille completion of a partial order, without increasing time complexity.

##### MSC:
 06B23 Complete lattices, completions 68W40 Analysis of algorithms
##### Keywords:
algorithm; covering graph of a lattice
Full Text:
##### References:
 [1] Aı\ddot{}t-Kaci, H.; Boyer, R.; Lincoln, P.; Nasr, R.: Efficient implementation of lattice operations. ACM trans. Program. languages systems 11, No. 1, 115-146 (1989) [2] Bordat, J. P.: Calcul pratique du treillis de Galois d’une correspondance. Math. sci. Hum. 96, 31-47 (1986) · Zbl 0626.06007 [3] Chein, M.: Algorithme de recherche de sous-matrice première d’une matrice. Bull. math. R. S. Roumanie 13 (1969) · Zbl 0209.06401 [4] Dahl, V.; Fall, A.: Logical encoding of conceptual graph lattice. (1993) [5] Davey, B. A.; Priestley, H. A.: Introduction to lattices and orders. (1991) · Zbl 0701.06001 [6] Ganter, B.: Two basic algorithms in concept analysis. (1984) · Zbl 1274.68484 [7] Ganter, B.; Kuznetsov, S. O.: Stepwise construction of the Dedekind--macneille. Lecture notes in computer sci. 1453, 295-302 (1998) · Zbl 0928.06004 [8] Godin, R.; Gecsei, J.: Lattice model of browsable data spaces. Inform. sci. 40, 89-116 (1996) · Zbl 0639.68110 [9] Godin, R.; Mili, H.: Building and maintaining analysis-level class hierarchies using Galois lattices. 394-410 (1993) [10] Godin, R.; Missaoui, R.; Alaoui, H.: Learning algorithms using a Galois lattice structure. Proc. 1991 IEEE international conference on tools for AI, San Jose, CA, 22-29 (1991) [11] Godin, R.; Missaoui, R.; April, A.: Experimental comparison of navigation in Galois lattice with conventional information retrieval methods. Internat. J. Man. machine studies 38, 747-767 (1993) [12] Habib, M.; Medina, R.; Nourine, L.; Steiner, G.: Efficient algorithms on distributive lattices. (1995) [13] Habib, M.; Nourine, L.: Tree structure for distributive lattices and its applications. Theoret. comput. Sci. 165, No. 2, 391-405 (1996) · Zbl 0887.68016 [14] Jard, C.; Jourdan, G. -V.; Rampon, J. -X.: Computing on-line the lattice of maximal antichains of posets. Order 11, No. 3, 197-210 (1994) · Zbl 0814.06004 [15] Missikoff, M.; Scholl, M.: An algorithm for insertion into lattices: application to type classification. (1989) [16] Norris, E. M.: An algorithm for computing the maximal rectangles of a binary relation. J. ACM 21, 356-366 (1974) [17] Wille, R.: Restructuring lattice theory: an approach based on hierarchies of contexts. NATO ASI, no. 83, 445-470 (1982) · Zbl 0491.06008 [18] Wille, R.: Lattices in data analysis: how to draw them with a computer. Algorithms and orders, 33-58 (1989) · Zbl 1261.68140 [19] Zaki, M. J.; Parthasarathy, S.; Ogihara, M.; Li, W.: New algorithms for fast discovery of association rules. (1997)