Succinctness and tractability of closure operator representations. (English) Zbl 1418.06001

Summary: It is widely known that closure operators on finite sets can be represented by sets of implications (also known as inclusion dependencies) as well as by formal contexts. In this article, we consider these two representation types, as well as generalizations of them: extended implication sets and context families. We discuss the mutual succinctness of these four representations and the tractability of certain operations used to compare and modify closure operators.


06A15 Galois correspondences, closure operators (in relation to ordered sets)
68T30 Knowledge representation
Full Text: DOI


[1] Adaricheva, K. V.; Sloan, R. H.; Szörényi, B.; Turán, G., Horn belief contraction: remainders, envelopes and complexity, (Brewka, G.; Eiter, T.; McIlraith, S. A., Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR), (2012))
[2] Ausiello, G.; D’Atri, A.; Saccà, D., Minimal representation of directed hypergraphs, SIAM J. Comput., 15, 2, 418-431, (1986) · Zbl 0602.68056
[3] Boros, E.; Cepek, O.; Kucera, P., A decomposition method for CNF minimality proofs, Theoret. Comput. Sci., 510, 111-126, (2013) · Zbl 1358.68120
[4] Burosch, G.; Demetrovics, J.; Katona, G. O.H.; Kleitman, D. J.; Sapozhenko, A. A., On the number of databases and closure operations, Theoret. Comput. Sci., 78, 2, 377-381, (1991) · Zbl 0717.68019
[5] Caspard, N.; Monjardet, B., The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Appl. Math., 127, 2, 241-269, (2003) · Zbl 1026.06008
[6] Colomb, P.; Irlande, A.; Raynaud, O., Counting of Moore families for \(n = 7\), (Kwuida, L.; Sertkaya, B., Proceedings of the 8th International Conference on Formal Concept Analysis (ICFCA), LNCS, vol. 5986, (2010), Springer), 72-87 · Zbl 1274.05013
[7] Day, A., The lattice theory of functional dependencies and normal decompositions, Internat. J. Algebra Comput., 2, 4, 409-431, (1992) · Zbl 0798.68049
[8] Distel, F., Hardness of enumerating pseudo-intents in the lectic order, (Kwuida, L.; Sertkaya, B., Proceedings of the 8th International Conference on Formal Concept Analysis (ICFCA), LNCS, vol. 5986, (2010), Springer), 124-137 · Zbl 1274.68480
[9] Dowling, W. F.; Gallier, J. H., Linear-time algorithms for testing the satisfiability of propositional Horn formulae, J. Log. Program., 1, 3, 267-284, (1984) · Zbl 0593.68062
[10] Eiter, T.; Ibaraki, T.; Makino, K., Computing intersections of Horn theories for reasoning with models, (1998), Universität Gießen, Tech. rep. IFIG research report 9803
[11] Ganter, B.; Wille, R., Formal concept analysis: mathematical foundations, (1997), Springer
[12] Gottlob, G.; Libkin, L., Investigations on Armstrong relations, dependency inference, and excluded functional dependencies, Acta Cybernet., 9, 4, 385-402, (1990) · Zbl 0727.68026
[13] Guigues, J.-L.; Duquenne, V., Familles minimales d’implications informatives resultant d’un tableau de données binaires, Math. Sci. Hum., 95, 5-18, (1986)
[14] Habib, M.; Nourine, L., The number of Moore families on \(n = 6\), Discrete Math., 294, 3, 291-296, (2005) · Zbl 1083.06003
[15] Håstad, J., Computational limitations of small-depth circuits, (1987), MIT Press Cambridge, MA, USA
[16] Higuchi, A., Lattices of closure operators, Discrete Math., 179, 1-3, 267-272, (1998) · Zbl 0910.06004
[17] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations, (1972), Plenum Press), 85-103
[18] Kuznetsov, S. O., On the intractability of computing the duquenne-guigues base, J. UCS, 10, 8, 927-933, (2004) · Zbl 1277.68258
[19] Kuznetsov, S. O.; Obiedkov, S. A., Counting pseudo-intents and #P-completeness, (Eklund, P. W., Proceedings of the 4th International Conference on Formal Concept Analysis (ICFCA), LNCS, vol. 3874, (2006), Springer), 306-308 · Zbl 1177.68209
[20] Kuznetsov, S. O.; Obiedkov, S. A., Some decision and counting problems of the duquenne-guigues basis of implications, Discrete Appl. Math., 156, 11, 1994-2003, (2008) · Zbl 1160.68031
[21] Maier, D., Minimum covers in relational database model, J. ACM, 27, 4, 664-674, (1980) · Zbl 0466.68085
[22] Maier, D., The theory of relational databases, (1983), Computer Science Press · Zbl 0519.68082
[23] Mannila, H.; Räihä, K.-J., Design of relational databases, (1992), Addison-Wesley · Zbl 0777.68014
[24] McKinsey, J. C.C., The decision problem for some classes of sentences without quantifiers, J. Symbolic Logic, 8, 3, 61-76, (1943) · Zbl 0063.03864
[25] Rudolph, S., Some notes on pseudo-closed sets, (Kuznetsov, S. O.; Schmidt, S., Proceedings of the 5th International Conference on Formal Concept Analysis (ICFCA), LNCS, vol. 4390, (2007), Springer), 151-165 · Zbl 1187.68593
[26] Rudolph, S., Some notes on managing closure operators, (Domenach, F.; Ignatov, D. I.; Poelmans, J., Proceedings of the 10th International Conference on Formal Concept Analysis (ICFCA), LNCS, vol. 7278, (2012), Springer), 278-291 · Zbl 1360.68821
[27] Rudolph, S., On the succinctness of closure operator representations, (Glodeanu, C. V.; Kaytoue, M.; Sacarea, C., Proceedings of the 12th International Conference of Formal Concept Analysis (ICFCA), LNCS, vol. 8478, (2014), Springer), 15-36 · Zbl 1444.68212
[28] Sertkaya, B., Some computational problems related to pseudo-intents, (Ferré, S.; Rudolph, S., Proceedings of the 7th International Conference on Formal Concept Analysis (ICFCA), LNCS, vol. 5548, (2009), Springer), 130-145 · Zbl 1248.68483
[29] Sertkaya, B., Towards the complexity of recognizing pseudo-intents, (Rudolph, S.; Dau, F.; Kuznetsov, S. O., Proceedings of the 17th International Conference on Conceptual Structures (ICCS), LNCS, vol. 5662, (2009), Springer), 284-292
[30] Wild, M., Implicational bases for finite closure systems, (Lex, W., Arbeitstagung Begriffsanalyse und Künstliche Intelligenz, (1991), Springer), 147-169
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.