×

Recursive decomposition tree of a Moore co-family and closure algorithm. (English) Zbl 1311.06004

Summary: A collection of sets on a ground set \(U_n\) (\(U_n=\{1,2,\ldots,n\}\)) closed under intersection and containing \(U_n\) is known as a Moore family. The set of Moore families for a fixed \(n\) is in bijection with the set of Moore co-families (union-closed families containing the empty set) denoted \(\mathbb M_n\). This paper follows the work initiated by P. Colomb et al. [Ann. Math. Artif. Intell. 67, No. 2, 109-122 (2013; Zbl 1311.06003)] in which we have given an inductive definition of the lattice of Moore co-families. In the present paper we use this definition to define a recursive decomposition tree of any Moore co-family and we design an original algorithm to compute the closure under union of any family. Then we compare performance of this algorithm to performance of Ganter’s algorithm and Norris’ algorithm.

MSC:

06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B05 Structure theory of lattices

Citations:

Zbl 1311.06003
PDF BibTeX XML Cite
Full Text: DOI HAL

References:

[1] Barbut, M., Monjardet, B.: Ordre et Classification. Hachette (1970)
[2] Beaudou, L., Colomb, P., Raynaud, O.: Structural properties and algorithms on the lattice of Moore co-families. In: Proceedings of ICFCA (Supplementary Actes), pp. 41-52 (2012)
[3] Birkhoff, G, Rings of sets, Duke Math. J., 3, 443-454, (1937) · Zbl 0017.19403
[4] Birkhoff, G.: Lattice Theory, 3rd edn. American Mathematical Society (1967) · Zbl 0153.02501
[5] Bordat, JP, Calcul pratique du treillis de Galois d’une correspondance, Math. Sci. Hum., 96, 31-47, (1986) · Zbl 0626.06007
[6] Burosh, G; Demetrovics, J; Katona, G; Kleitman, D; Sapozhenko, A, On the number of databases and closure operations, Theor. Comput. Sci., 78, 377-381, (1991) · Zbl 0717.68019
[7] Caspard, N; Monjardet, B, The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Appl. Math., 127, 241-269, (2003) · Zbl 1026.06008
[8] Colomb, P., Irlande, A., Raynaud, O.: Counting of Moore families on \(n\) = 7. In: Proceedings of ICFCA, LNAI 5986, pp. 72-87 (2010) · Zbl 1274.05013
[9] Colomb, P; Irlande, A; Raynaud, O; Renaud, R, Recursive decomposition and bounds of the lattice of Moore co-families, Ann. Math. Artif. Intell. AMAI, 67, 109-122, (2013) · Zbl 1311.06003
[10] Cohn, P.: Universal Algebra. Harper and Row, New York (1965) · Zbl 0141.01002
[11] Doignon, J.P., Falmagne, J.C.: Knowledge Spaces. Springer, Berlin (1999) · Zbl 0908.92040
[12] Demetrovics, J; Libkin, L; Muchnik, I, Functional dependencies in relational databases: a lattice point of view, Discrete Appl. Math., 40, 155-185, (1992) · Zbl 0767.68029
[13] Demetrovics, J., Libkin, L., Muchnik, I.: Functional dependencies and the semilattice of closed classes. In: MFDBS, LNCS, 364, pp. 136-147 (1989) · Zbl 0626.06007
[14] Davey, B.A., Priestley, H.A.: Introduction to Lattices and Orders. Cambridge University Press (1991) · Zbl 0701.06001
[15] Demetrovics, J; Molnar, A; Thalheim, B, Reasoning methods for designing and surveying relationships described by sets of functional constraints, Serdica J. Computing, 3, 179-204, (2009) · Zbl 1187.68189
[16] Duquenne, V, Latticial structure in data analysis, Theor. Comput. Sci., 217, 407-436, (1999) · Zbl 1034.68510
[17] Ganter, B., Wille, R.: Formal Concept Analysis, Mathematical Foundations. Springer, Berlin (1999) · Zbl 0909.06001
[18] Ganter, B.: Two Basic Algorithms in Concept Analysis, Preprint 831, Technische Hochschule Darmstadt (1984) · Zbl 1274.68484
[19] Gely, A.: A generic algorithm for generating closed sets of a binary relation. In: Proceedings of ICFCA, pp. 223-234 (2005) · Zbl 1078.68773
[20] Habib, M; Nourine, L, The number of Moore families on \(n\) = 6, Discrete Math., 294, 291-296, (2005) · Zbl 1083.06003
[21] Lindig, C.: Fast concept analysis. In: Proceedings of ICCS, pp. 152-161. Shaker (2000)
[22] Norris, EM, An algorithm for computing the maximal rectangles in a binary relation, J. ACM, 21, 356-366, (1974) · Zbl 0293.94020
[23] Sierksma, G, Convexity on union of sets, Compos. Math., 42, 391-400, (1980) · Zbl 0454.52001
[24] van de Ven, L.M.J.: Theory of Convex Structures. North-Holland, Amsterdam (1993) · Zbl 0454.52001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.