Direct-optimal basis computation by means of the fusion of simplification rules. (English) Zbl 1398.68520

Summary: The importance of the computation of direct bases of implications has been motivated by several authors in different areas. They emphasize the use of direct bases in several problems, where a large number of closures are needed. The more efficient the basis computation is, the better performance the methods solving these problems has. Here, we propose a new method, named SLgetdo, to calculate the direct-optimal basis. The main characteristic of SLgetdo is the full integration of simplification paradigm, providing a limited rise of the implicational set throughout its execution. We have showed the better behavior of SLgetdo in an empirical experiment. The general conclusion is that it improves the performance of previous methods, providing a better management of time and space resources.


68T30 Knowledge representation
68T27 Logic in artificial intelligence


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, 5, 707-723, (2013) · Zbl 1288.06007
[2] Bazhanov, K.; Obiedkov, S. A., Optimizations in computing the duquenne-guigues basis of implications, Ann. Math. Artif. Intell, 70, 1-2, 5-24, (2014) · Zbl 1310.68193
[3] K. Bertet, C. Demko, J.F. Viaud, C. Guerin, Lattices, closures systems and implication bases: A survey of structural aspects and algorithms, Theoret. Comput. Sci., http://dx.doi.org/10.1016/j.tcs.2016.11.021. · Zbl 1398.68510
[4] Bertet, K.; Monjardet, B., The multiple facets of the canonical direct unit implicational basis, Theoret. Comput. Sci., 411, 22-24, 2155-2166, (2010) · Zbl 1209.68187
[5] Bertet, K.; Nebut, M., Efficient algorithms on the Moore family associated to an implicational system, DMTCS, 6, 2, 315-338, (2004) · Zbl 1062.06004
[6] P. Cordero, M. Enciso, A. Mora, M. Ojeda-Aciego, Computing minimal generators from implications: a logic-guided approach, in: CLA, 2012, pp. 187-198.
[7] P. Cordero, M. Enciso, A. Mora, M. Ojeda-Aciego, Computing left-minimal direct basis of implications, in: CLA, 2013, pp. 293-298.
[8] Cordero, P.; Mora, A.; Enciso, M.; de Guzmán, I. Péérez, SLFD logic: elimination of data redundancy in knowledge representation, Lecture Notes in Comput. Sci., 2527, 141-150, (2002) · Zbl 1037.68136
[9] Ganter, B., Two Basic Algorithms in Concept Analysis, (1984), Technische Hochschule Darmstadt
[10] 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)
[11] Kuznetsov, S. O., Complexity of learning in concept lattices from positive and negative examples, Discrete Appl. Math., 142, 1-3, 111-125, (2004) · Zbl 1077.68039
[12] S.O. Kuznetsov, S. Obiedkov, Counting Pseudo-intents and \(\# P\)-completeness, in: ICFCA, 2006, pp. 306-308. · Zbl 1177.68209
[13] M. Lichman, UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences, 2013, http://archive.ics.uci.edu/ml.
[14] Mora, A.; Enciso, M.; Cordero, P.; Fortes, I., Closure via functional dependence simplification, Int. J. Comput. Math., 89, 4, 510-526, (2012) · Zbl 1257.68064
[15] Mora, A.; Enciso, M.; Cordero, P.; Pérez de Guzmán, I., An efficient preprocessing transformation for functional dependencies sets based on the substitution paradigm, Lecture Notes in Comput. Sci., 3040, 136-146, (2004)
[16] E. Rodríguez-Lorenzo, K. Bertet, P. Cordero, M. Enciso, A. Mora, The Direct-optimal basis via reductions, CLA, 2014, pp. 145-156.
[17] Rodríguez-Lorenzo, E.; Bertet, K.; Cordero, P.; Enciso, M.; Mora, A.; Ojeda-Aciego, M., From implicational systems to direct-optimal bases: A logic-based approach, Appl. Math. Inf. Sci., 2L, 305-317, (2015)
[18] E. Rodríguez-Lorenzo, P. Cordero, M. Enciso, A. Mora, Dichotomous sets of implications and directness, in: Proceedings of 7th European Symposium on Computational Intelligence and Mathematics - ESCIM, 2015, pp. 186-191.
[19] S. Rudolph, Some notes on managing closure operators, in: ICFCA, 2012, pp. 278-291. · Zbl 1360.68821
[20] Ryssel, U.; Distel, F.; Borchmann, D., Fast algorithms for implication bases and attribute exploration using proper premises, Ann. Math. Artif. Intell., 70, 1-2, 25-53, (2014) · Zbl 1314.68305
[21] M. Wild, The joy of implications, aka pure Horn functions: mainly a survey, CoRR abs/1411.6432, 2014. · Zbl 1418.03144
[22] M. Wild, Computations with finite closure systems and implications, in: Proceedings of the First Anual International Conference on Computing and Combinatorics, COCOON, 1995, pp. 111-120.
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.