Canonical dichotomous direct bases. (English) Zbl 1428.68291

Summary: Closure systems are usually characterized in terms of implications. The directness property of implicational systems is a key issue in their computational usability. In this work we focus on this property, studying its connection with the structure of implicational systems and the design of methods for transforming any implicational system into an equivalent direct implicational system. We introduce a new paradigm based on the bipartition of the implicational sets into two components, according to their behavior wrt the closure. In addition, we present the notions of two new direct bases, named DD-basis and canonical DD-basis, also providing two methods to compute each of them. The advantages of the dichotomous approach will be shown both from the theoretical and empirical points of view.


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


[1] Adaricheva, K. V.; Nation, J. B.; Rand, R., Ordered direct implicational basis of a finite closure system, Discrete Appl. Math., 161, 6, 707-723 (2013)
[2] Bastide, Y.; Stumme, G.; Taouil, R., Fast computation of concept lattices using data mining techniques, Proceedings Seventh International Workshop on Knowledge Representation Meets Databases, 129-139 (2000)
[3] Belohlavek, R.; Vychodil, V., A logic of graded attributes, Arch. Math. Logic, 54, 7-8, 785-802 (2015)
[4] Bertet, K.; Nebut, M., Efficient algorithms on the Moore family associated to an implicational system, Discrete Math. Theor. Comput. Sci., 6, 2, 315-338 (2004)
[5] Bertet, K.; Monjardet, B., The multiple facets of the canonical direct unit implicational basis, Theor. Comput. Sci., 411, 22-24, 2155-2166 (2010)
[6] Colomb, P.; Nourine, L., About keys of formal context and conformal hypergraph, Proceedings of the 6th International Conference on Formal Concept Analysis, 140-149 (2008)
[7] Cordero, P.; Enciso, M.; Mora, A.; de Guzmán, I. P., A tableaux-like method to infer all minimal keys, Logic J. IGPL, 22, 6, 1019-1044 (2014)
[8] Cordero, P.; Enciso, M.; Mora, A.; Ojeda-Aciego, M.; Rossi, C., Knowledge discovery in social networks by using a logic-based treatment of implications, Knowl.-Based Syst., 87, 16-25 (2015)
[9] Cordero, P.; Enciso, M.; Mora, A.; Ojeda-Aciego, M., Computing left-minimal direct basis of implications, Concept lattice and their applications (CLA), 293-298 (2013)
[10] Cordero, P.; Mora, A.; Enciso, M.; Pérez de Guzmán, I., SLFD Logic: Elimination of Data Redundancy in Knowledge Representation, Lecture Notes in Computer Science, 2527, 141-150 (2002)
[11] Duquenne, V., Some variations on Alan Day’s algorithm for calculating canonical basis of implications, Concept lattice and their applications (CLA): Volume 331 of CEUR Workshop Proceedings, CEUR-WS (2007)
[12] Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput., 24, 6, 1278-1304 (1995)
[13] Freese, R. S.; Ježek, J.; Nation, J. B., Free lattices, Advances in the Mathematical Sciences (1995), American Mathematical Society
[14] Ganter, B.; Wille, R., Formal Concept Analysis: Mathematical Foundations (1999), Springer
[15] Guigues, J. L.; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Math. Sci. Humaines, 95, 5-18 (1986)
[16] Kuznetsov, S. O.; Obiedkov, S., Some decision and counting problems of the Duquenne-Guigues basis of implications, Discrete Appl. Math., 156, 1994-2003 (2008)
[17] Missaoui, R.; Nourine, L.; Renaud, Y., Computing implications with negation from a formal context, Fundam. Inf., 115, 4, 357-375 (2012)
[18] Mora, A.; Enciso, M.; Cordero, P.; Fortes, I., Closure via functional dependence simplification, Int. J. Comput. Math., 89, 4, 510-526 (2012)
[19] Mora, A.; Enciso, M.; Cordero, P.; de Guzmán, I. P., An efficient preprocessing transformation for functional dependencies sets based on the substitution paradigm, Lecture Notes in Computer Science, 3040, 136-146 (2004)
[20] Mora, A.; de Guzmán, I. P.; Enciso, M.; Cordero, P., Ideal non-deterministic operators as a formal framework to reduce the key finding problem, Int. J. Comput. Math., 88, 9, 1860-1868 (2011)
[21] Ore, O., Galois connections, Trans. Am. Math. Soc., 55, 493-513 (1944)
[22] Lorenzo, E. R.; Bertet, K.; Cordero, P.; Enciso, M.; Mora, A.; Ojeda-Aciego, M., From implicational systems to direct-optimal bases: alogic-based approach, Appl. Math. Inf. Sci., 2L, 305-317 (2015)
[23] Jiménez, J. M.R.; Lorenzo, E. R.; Cordero, P.; Enciso, M.; Mora, A., A normal form for fuzzy functional dependencies, IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI’15), 984-989 (2015)
[24] Rudolph, S., Some notes on managing closure operators, Lecture Notes in Computer Science, 7278, 278-291 (2012)
[25] Toman, D.; Weddell, G. E., On keys and functional dependencies as first-class citizens in description logics, J. Autom. Reasoning, 40, 117-132 (2008)
[26] Vychodil, V., On minimal sets of graded attribute implications, Inf. Sci., 294, 478-488 (2015)
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.