×

The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey. (English) Zbl 1026.06008

Discrete Appl. Math. 127, No. 2, 241-269 (2003); erratum ibid. 145, No. 3, 333 (2005).
Summary: Closure systems (i.e. families of subsets of a set \(S\) containing \(S\) and closed by set intersection) or, equivalently, closure operators and full implicational systems appear in many fields in pure or applied mathematics and computer science. We present a survey of properties of the lattice of closure systems on a finite set \(S\) with proofs of the more significant results. In particular we show that this lattice is atomistic and lower bounded and that there exists a canonical basis for the representation of any closure system by “implicational” closure systems. Since the lattices of closure operators and of full implicational systems are anti-isomorphic with the lattice of closure systems they have the dual properties.

MSC:

06A15 Galois correspondences, closure operators (in relation to ordered sets)
68P15 Database theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Adaricheva, K.V., Characterization of finite lattices of sublattices, Algebra i logica, 30, 385-404, (1991), (in Russian) · Zbl 0716.06001
[2] Adaricheva, K.V., Two embedding theorems for lower bounded lattices, Algebra universalis., 36, 425-430, (1996) · Zbl 0901.06005
[3] Alexseev, V.B., The number of families of subsets closed with respect to intersection, Diskrete math., 1, 129-136, (1989), (in Russian) · Zbl 0725.05009
[4] Armstrong, W.W., Dependency structures of data base relationships, Inform. process., 74, 580-583, (1974) · Zbl 0296.68038
[5] M. Barbut, Note sur l’algèbre des techniques d’analyse hiérarchique, in: B. Matalon (Ed.), L’analyse hiérarchique, Gauthier-Villars, Paris, 1965.
[6] M. Barbut and B. Monjardet, Ordre et Classification, Algèbre et Combinatoire, tomes I and II, Hachette, Paris, 1970. · Zbl 0267.06001
[7] Birkhoff, G., Lattice theory, (1967), American Mathematical Society Providence, RI · Zbl 0126.03801
[8] G.H. Bordalo, B. Monjardet, The lattice of strict completions of a finite lattice, Algebra Universalis 47 (2002) -200. · Zbl 1058.06001
[9] Buchi, J.R., Finite automata, their algebras and grammars. towards a theory of formal expressions, (1989), Springer Berlin · Zbl 0715.68062
[10] Burigana, L., Organization by rules in finite sequences, J. math. psych., 35, 3, 345-370, (1991) · Zbl 0747.92031
[11] Burosch, G.; Demetrovics, J.; Katona, G.O.H., The poset of closures as a model of changing databases, Order, 4, 127-142, (1987) · Zbl 0648.06004
[12] Burosch, G.; Demetrovics, J.; Katona, G.O.H.; Kleitman, D.J.; Sapozhenko, A., On the number of databases and closure operations, Theoret. comput. sci., 78, 377-381, (1991) · Zbl 0717.68019
[13] G. Burosch, J. Demetrovics, G.O.H. Katona, D.J. Kleitman, A. Sapozhenko, On the number of closure operators, in the book Combinatorics, Paul Erdös is Eighty, Vol. 1, Jànos Bolyai Mathematical Society, Budapest, 1993 pp. 91-95. · Zbl 0794.05003
[14] Caspard, N., A characterization theorem for the canonical basis of a closure operator, Order, 16, 3, 227-230, (1999) · Zbl 0959.06005
[15] Caspard, N.; Monjardet, B., The lattice of Moore families and closure operators on a finite seta survey, Electronic notes in discrete mathematics, 2, (1999), (http://www.elsevier.nl/locate/endm)
[16] Davey, B.A.; Priestley, H.A., Introduction to lattices and order, (1990), Cambridge University Press Cambridge · Zbl 0701.06001
[17] Day, A., Characterizations of finite lattices that are bounded-homomorphic images or sublattices of free lattices, Canad. J. math., 31, 69-78, (1979) · Zbl 0432.06007
[18] Day, A., The lattice theory of functional dependencies and normal decompositions, Internat. J. algebra comput., 2, 4, 409-431, (1992) · Zbl 0798.68049
[19] Demetrovics, J.; Hua, N.S., Databases, closure operations and sperner families, (), 199-203 · Zbl 0839.68025
[20] J. Demetrovics, L.O. Libkin, I.B. Muchnik, Functional dependencies and the semilattice of closed classes, Proceedings of MFDBS 89, Lecture Notes in Computer Science, Vol. 364, Springer, Berlin, 1989, pp. 136-147.
[21] Demetrovics, J.; Libkin, L.O.; Muchnik, I.B., Functional dependencies in relational databasesa lattice point of view, Discrete appl. math., 40, 155-185, (1992) · Zbl 0767.68029
[22] Dikranjan, D.; Tholen, W., Categorical structure of closure operators: with applications to topology, algebra and discrete mathematics, (1995), Kluwer Academic Publishers Dordrecht · Zbl 0853.18002
[23] Doignon, J.P.; Falmagne, J.C., Knowledge spaces, (1999), Springer Berlin
[24] Doignon, J.P.; Koppen, M., How to build a knowledge space by querying an expert, J. math. psych., 34, 3, 311-331, (1989) · Zbl 0725.92029
[25] Duntsch, I.; Gediga, G., A note on the correspondence among entail relations, rough set dependencies and logical consequence, J. math. psych., 45, 393-401, (2001) · Zbl 0995.06001
[26] Duquenne, V., Contextual implications between attributes and some representation properties for finite lattices, (), 213-239
[27] V. Duquenne, The lattice of all 1-meet-subsemilattices of a finite lattice, 1987 (unpublished notes).
[28] Duquenne, V., The core of finite lattice, Discrete math., 88, 2-3, 133-147, (1991) · Zbl 0736.06012
[29] Duquenne, V., Latticial structure in data analysis, Theoret. comput. sci., 217, 407-436, (1999) · Zbl 1034.68510
[30] Finkbeiner, D.T., A general dependence relation for lattices, Proc. amer. math. soc. 2, 7, 56-59, (1951)
[31] Freese, R.; Jezek, J.; Nation, J.B., Free lattices, Mathematical surveys and monographs, Vol. 42, (1991), American Mathematical Society Providence, RI · Zbl 0839.06005
[32] Ganter, B., Two basic algorithms in concept analysis, report 831 TH darsmastadt, FB Mathematik 1984; published as algorithmen zur formalen begriffsanalyse, (), 241-254
[33] Ganter, B., Attribute exploration with background knowledge, Theoret. comput. sci., 217, 215-234, (1999) · Zbl 0914.68168
[34] Ganter, B.; Wille, R., Formal concept analysis, mathematical foundations, (1999), Springer Berlin · Zbl 0909.06001
[35] Grätzer, G., General lattice theory, (1978), Birkhäuser Basel · Zbl 0385.06015
[36] Guigues, J.L.; Duquenne, V., Familles minimales d’implications informatives résultant d’une table de données binaires, Math. sci. humaines, 95, 5-18, (1986)
[37] M. Habib, L. Nourine, Algorithms for Moore families generation, preprint, 2000.
[38] Hawrylycz, M.; Reiner, V., The lattice of closure relations on a poset, Algebra universalis, 30, 301-310, (1993) · Zbl 0785.06003
[39] Higuchi, A., Lattices of closure operators, Discrete math., 179, 267-272, (1998) · Zbl 0910.06004
[40] Iseki, K., On closure operation in lattice theory, Nederl. akad. wetensch. proc. ser. A 54; indag. math., 13, 318-320, (1951) · Zbl 0043.03501
[41] Jamison, R.E., Copoints in antimatroı̈ds, Congr. numer., 29, 535-544, (1980) · Zbl 0463.05005
[42] Jamison-Waldner, R.E., Partition numbers for trees and ordered sets, Pacific J. math., 96, 1, 115-140, (1981) · Zbl 0482.52010
[43] Koshevoy, G.A., Choice functions and abstract convex geometries, Math. social sci., 38, 1, 35-44, (1999) · Zbl 0943.91031
[44] Libkin, L.O., Direct subdecomposition of atomistic algebraic lattices, Algebra universalis, 33, 127-135, (1995) · Zbl 0818.06004
[45] Libkin, L.O.; Muchnik, I.B., On a subsemilattice-lattice of a semilattice, MTA SZTAKI Kölemények, 39, 101-110, (1988) · Zbl 0676.06012
[46] Libkin, L.O.; Muchnik, I.B., Separatory subsemilattices and their properties, MTA SZTAKI Kölemények, 39, 83-92, (1988) · Zbl 0676.06011
[47] Maier, D., The theory of relational data bases, (1983), Computer Science Press Rockville, MD
[48] Malishevski, A.V., Path independence in serial-parallel data processing, Math. social sci., 27, 335-367, (1994) · Zbl 0884.68040
[49] Malishevski, A.V., Structural characterization of the path independence property for set transformations, (), 319-329 · Zbl 0897.90009
[50] G. Markowsky, Some combinatorial aspects of lattice theory, Proceedings of Houston Lattice Theory Conference, University of Houston, Houston, 1973, pp. 36-68. · Zbl 0302.06010
[51] Martin, N.M.; Pollard, S., Closure spaces and logic, (1996), Kluwer Academic Publishers Dordrecht · Zbl 0855.54001
[52] Monjardet, B., Arrowian characterizations of latticial federation consensus functions, Math. social sci., 20, 1, 51-71, (1990) · Zbl 0746.90002
[53] Monjardet, B., The consequences of Dilworth’s work on lattices with unique irreducible decompositions, (), 192-201
[54] Monjardet, B.; Caspard, N., On a dependance relation in finite lattices, Discrete math., 165/166, 497-505, (1997) · Zbl 0870.06003
[55] Monjardet, B.; Raderanirina, V., The duality between the semi-lattices of anti-exchange closure operators and path-independent choice operators, Math. social sci., 41, 2, 131-150, (2001) · Zbl 0994.91012
[56] Monteiro, A., Caractérisation de l’opération de fermeture par un seul axiome, Portugal. math., 4, 158-160, (1943) · Zbl 0060.39406
[57] Morgado, J., A characterization of closure operators by means of one axiom, Portugal. math., 21, 3, 155-156, (1962) · Zbl 0107.25203
[58] Morgado, J., Note on the distributive closure operators of a complete lattice, Portugal. math., 23, 11-25, (1964) · Zbl 0136.00903
[59] Müller, C.E., A procedure for facilitating an Expert’s judgements on a set of rules, ()
[60] Nation, J.B.; Pogel, A., The lattice of completions of an ordered set, Order, 14, 1, 1-7, (1997) · Zbl 0888.06003
[61] Nicoletti, G.; White, N., Axiom systems, () · Zbl 0587.05016
[62] Öre, O., Combinations of closure relations, Ann. math., 44, 514-533, (1943) · Zbl 0060.06203
[63] V. Raderanirina, Treillis de familles de Moore et de fonctions de choix. Applications aux problèmes de consensus, Thèse Université Paris 1, 2001.
[64] Repnitskii, V.B., On finite lattices which are embeddable in subsemigroups lattices, Semigroup forum, 46, 388-397, (1993) · Zbl 0797.20052
[65] Rusch, A.; Wille, R., Knowledge spaces and formal concept analysis, () · Zbl 0899.92041
[66] V. Soltan, Abstract convexity, Shtiintsa, Kishinev, 1984 (in Russian). · Zbl 0559.52001
[67] Stanley, R.P., Supersolvable lattices, Algebra universalis, 2, 197-217, (1972) · Zbl 0256.06002
[68] Stern, M., Semimodular lattices, (1999), Cambridge University Press Cambridge · Zbl 0957.06008
[69] Szàsz, G., Introduction to lattice theory, (1963), Academic Press New York · Zbl 0126.03703
[70] Van den Vel, M.L.J., Theory of convex structures, (1993), North-Holland Amsterdam · Zbl 0785.52001
[71] Wild, M., A theory of finite closure spaces based on implications, Adv. math., 108, 1, 118-139, (1994) · Zbl 0863.54002
[72] Wild, M., Computations with finite closure systems and implications, Lecture notes in comput. sci., 959, 111-120, (1995)
[73] Birkhoff, G., On the combination of topologies, Fundamenta mathematicae, 26, 156-166, (1936) · Zbl 0013.36804
[74] Monteiro, A., LES ensembles femés et LES fondements de la topologie, Portugal. math., 2, 56-66, (1941) · JFM 67.0159.01
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.