Some decision and counting problems of the Duquenne-Guigues basis of implications. (English) Zbl 1160.68031

Summary: Implications of a formal context obey Armstrong rules, which allows one to define a minimal (in the number of implications) implication basis, called Duquenne-Guigues basis or stem base in the literature. In this paper we show how implications are reduced to functional dependencies and prove that the problem of determining the size of the stem base is a #P-complete problem.


68T30 Knowledge representation
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI


[1] Birkhoff, G.D., Lattice theory, (1979), American Mathematical Society
[2] E. Boros, V. Gurvich, L. Khachiyan, K. Makino, On the complexity of generating maximal frequent and minimal infrequent sets, in: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS’02), Lecture Notes in Computer Science, vol. 2285, Springer, Berlin, 2002, pp. 133-141. · Zbl 1054.68072
[3] Duquenne, V., Contextual implications between attributes and some representation properties for finite lattices, (), 213-239
[4] V. Duquenne, J.-L. Guigues, Galois Lattice Revival, in: Communication to the Third Meeting of the Psychometric Society, Jouy en Josas, July 1983.
[5] B. Ganter, Two basic algorithms in concept analysis, Preprint No. 831, Technische Hochschule Darmstadt, 1984. · Zbl 1274.68484
[6] B. Ganter, S. Kuznetsov, Formalizing hypotheses with concepts, in: Proceedings of the 8th International Conference on Conceptual Structures (ICCS’00), Lecture Notes in Artificial Intelligence, vol. 1867, 2000, pp. 342-356. · Zbl 0973.68195
[7] Ganter, B.; Wille, R., Formal concept analysis: mathematical foundations, (1999), Springer Berlin · Zbl 0909.06001
[8] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[9] J.-L. Guigues, V. Duquenne, Informative implications derived from a table of binary data. Preprint, Groupe Mathématiques et Psychologie, Université René Descartes, Paris, 1984.
[10] Guigues, J.-L.; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Math. sci. hum., 24, 95, 5-18, (1986)
[11] Kuznetsov, S.O., On computing the size of a lattice and related decision problems, Order, 18, 4, 313-321, (2001) · Zbl 0991.06006
[12] Kuznetsov, S.O.; Obiedkov, S.A., Comparing performance of algorithms for generating concept lattices, J. exp. theor. artif. intell., 14, 2-3, 189-216, (2002) · Zbl 1024.68020
[13] Kuznetsov, S.O., On the intractability of computing the duquenne – guigues base, J. universal comput. sci., 10, 8, 927-933, (2004) · Zbl 1277.68258
[14] Luxenburger, M., Implications partielles dans un contexte, Math. inform. et sci. humaines, 113, 29, 35-55, (1991) · Zbl 0751.06006
[15] Mannila, H.; Räihä, K.-J., Design of relational databases, (1992), Addison-Wesley Reading, MA · Zbl 0777.68014
[16] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Closed set based discovery of small covers for association rules, in: Proceedings of the BDA Conference, 1999, pp. 361-381.
[17] Valiant, L.G., The complexity of enumeration and reliability problems, SIAM J. comput., 8, 3, 410-421, (1979) · Zbl 0419.68082
[18] M. Wild, Computations with finite closure systems and implications, Preprint No. 1708, Technische Hochschule Darmstadt, 1994.
[19] Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, (), 445-470
[20] M.J. Zaki, M. Ogihara, Theoretical foundations of association rules, in: Proceedings of the 3rd SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 1998.
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.