On the calculation of formal concept stability. (English) Zbl 1442.68226

Summary: The idea of stability has been used in many applications. However, computing stability is still a challenge and the best algorithms known so far have algorithmic complexity quadratic to the size of the lattice. To improve the effectiveness, a critical term is introduced in this paper, that is, minimal generator, which serves as the minimal set that makes a concept stable when deleting some objects from the extent. Moreover, by irreducible elements, minimal generator is derived. Finally, based on inclusion-exclusion principle and minimal generator, formulas for the calculation of concept stability are proposed.


68T30 Knowledge representation
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI


[1] Kuznetsov, S. O., Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity, Nauchno-Tekhnicheskaya Informatsiya Ser.2 (Automat. Document. Math. Linguist), 12, 21-29 (1990) · Zbl 0737.68069
[2] Kuznetsov, S. O., On stability of a formal concept, Annals of Mathematics and Artificial Intelligence, 49, 1-4, 101-115 (2007) · Zbl 1129.68086
[3] Kuznetsov, S. O.; Obiedkov, S.; Roth, C.; Priss, U.; Polovina, S.; Hill, R., Reducing the representation complexity of lattice-based taxonomies, Proceedings of the 15th International Conference on Conceptual Structures (ICCS ’07), Springer
[4] Roth, C.; Obiedkov, S.; Kourie, D. G., On succinct representation of knowledge community taxonomies with formal concept analysis, International Journal of Foundations of Computer Science, 19, 2, 383-404 (2008) · Zbl 1156.68588
[5] Roth, C.; Obiedkov, S.; Kourie, D., Towards concise representation for taxonomies of epistemic communities, Proceedings of the 4th International Conference on Concept Lattices and Their Applications · Zbl 1133.68454
[6] Efron, B., The Jackknife, the Bootstrap and Other Resampling Plans (1982), Philadelphia, Pa, USA: CBMS-NSF Regional Conference Series in Applied Mathematics, Philadelphia, Pa, USA · Zbl 0496.62036
[7] Carnap, R., The Logical Foundations of Probability (1962), Chicago, Ill, USA: University of Chicago Press, Chicago, Ill, USA · Zbl 0143.01201
[8] Babin, M. A.; Kuznetsov, S. O.; Domenach, F.; Ignatov, D.; Poelmans, J., Approximating concept stability, Formal Concept Analysis: Proceedings of the 10th International Conference, ICFCA 2012, Leuven, Belgium, May 7-10, 2012. Formal Concept Analysis: Proceedings of the 10th International Conference, ICFCA 2012, Leuven, Belgium, May 7-10, 2012, Lecture Notes in Artificial Intelligence, 7278, 7-15 (2012) · Zbl 1360.68798
[9] Finn, V. K., On machine-oriented formalization of plausible reasoning in the style of F. Bacon-J. S. Mill, Semiotika i Informatika, 20, 35-101 (1983) · Zbl 0521.03012
[10] Kuznetsov, S. O., Mathematical aspects of concept analysis, Journal of Mathematical Sciences, 80, 2, 1654-1698 (1996) · Zbl 0885.06001
[11] Ganter, B.; Kuznetsov, S. O., Formalizing hypotheses with concepts, Proceedings of the 8th International Conference on Conceptual Structures (ICCS ’00) · Zbl 0973.68195
[12] Wille, R., Concept lattices and conceptual knowledge systems, Computers and Mathematics with Applications, 23, 6-9, 493-515 (1992) · Zbl 0766.68129
[13] Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, Ordered Sets. Ordered Sets, NATO Advanced Study Institutes Series, 83, 445-470 (1982), Berlin, Germany: Springer, Berlin, Germany
[14] Ganter, B.; Kuznetsov, S. O.; de Moor, A.; Lex, W.; Ganter, B., Hypotheses and version Spaces, Proceedings of the 10th International Conference on Conceptual Structures (ICCS ’03) · Zbl 1274.68311
[15] Hong, W.; Mao, J.; Yu, J.; Song, J., The complete definitions of attributes and abstract description of attribute features of the formal context, ICIC Express Letters, 7, 3, 997-1003 (2013)
[16] Ganter, B.; Wille, R., Formal Concept Analysis: Mathematical Foundation (1999), Berlin, Germany: Springer, Berlin, Germany
[17] Kuznetsov, S. O.; Obiedkov, S. A., Comparing performance of algorithms for generating concept lattices, Journal of Experimental and Theoretical Artificial Intelligence, 14, 2-3, 189-216 (2002) · Zbl 1024.68020
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.