A depth-first search algorithm for computing pseudo-closed sets. (English) Zbl 1397.05013

Summary: The question of the lower bounds for the delay in the computation of the Duquenne-Guigues implication basis in non-lectic orders is still open. As a step towards an answer, we propose an algorithm that can enumerate pseudo-closed sets in orders that do not necessarily extend the inclusion order using depth-first searches in a sequence of closure systems. Empirical comparisons with NextClosure on the runtime and number of closed sets computed are provided.


05A15 Exact enumeration problems, generating functions
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T30 Knowledge representation
Full Text: DOI HAL


[1] Babin, Mikhail A.; Kuznetsov, Sergei O., Recognizing pseudo-intents is conp-complete, (Kryszkiewicz, Marzena; Obiedkov, Sergei A., Concept Lattices and Applications, CEUR Workshop Proceedings, vol. 672, (2010), CEUR-WS.org), 294-301
[2] Babin, Mikhail A.; Kuznetsov, Sergei O., Computing premises of a minimal cover of functional dependencies is intractable, Discrete Appl. Math., 161, 6, 742-749, (2013) · Zbl 1263.68046
[3] Bazhanov, Konstantin; Obiedkov, Sergei A., Comparing performance of algorithms for generating the duquenne-guigues basis, (Napoli, Amedeo; Vychodil, Vilém, Concept Lattices and Applications, CEUR Workshop Proceedings, vol. 959, (2011), CEUR-WS.org), 43-57
[4] Bazin, Alexandre; Ganascia, Jean-Gabriel, Computing the duquenne-guigues basis: an algorithm for choosing the order, Int. J. Gen. Syst., 1-29, (2015) · Zbl 1365.68410
[5] Beaudou, Laurent; Mary, Arnaud; Nourine, Lhouari, Algorithms for k-meet-semidistributive lattices, Theoret. Comput. Sci., (2015) · Zbl 1357.68287
[6] Bertet, Karell; Monjardet, Bernard, The multiple facets of the canonical direct unit implicational basis, Theoret. Comput. Sci., 411, 22, 2155-2166, (2010) · Zbl 1209.68187
[7] Birkhoff, Garrett, Lattice theory, vol. 25, (1948), American Mathematical Society · Zbl 0033.10103
[8] Borchmann, Daniel, A generalized next-closure algorithm - enumerating semilattice elements from a generating set, (Szathmary, Laszlo; Priss, Uta, Concept Lattices and Applications, CEUR Workshop Proceedings, vol. 972, (2012), CEUR-WS.org), 9-20
[9] Distel, Felix; Sertkaya, Barış, On the complexity of enumerating pseudo-intents, Discrete Appl. Math., 159, 6, 450-466, (2011) · Zbl 1214.68387
[10] Duquenne, Vincent, The core of finite lattices, Discrete Math., 88, 2, 133-147, (1991) · Zbl 0736.06012
[11] Ganter, Bernhard; Reuter, Klaus, Finding all closed sets: A general approach, Order, 8, 3, 283-290, (1991) · Zbl 0754.06003
[12] Gély, Alain; Nourine, Lhouari, About the family of closure systems preserving non-unit implications in the guigues-duquenne base, (Missaoui, Rokia; Schmidt, Jrg, Formal Concept Analysis, Lecture Notes in Computer Science, vol. 3874, (2006), Springer), 306-308 · Zbl 1177.68207
[13] Guigues, Jean-Louis; Duquenne, Vincent, Familles minimales d’implications informatives résultant d’un tableau de données binaires, Math. Sci. Hum., 95, 5-18, (1986)
[14] Janssen, Philippe; Nourine, Lhouari, Minimum implicational basis for meet-semidistributive lattices, Inform. Process. Lett., 99, 5, 199-202, (2006) · Zbl 1185.06009
[15] Kuznetsov, Sergei O., On the intractability of computing the duquenne-guigues basis, J. UCS, 10, 8, 927-933, (2004) · Zbl 1277.68258
[16] Kuznetsov, Sergei O.; Obiedkov, Sergei A., Counting pseudo-intents and #P-completeness, (Missaoui, Rokia; Schmidt, Jrg, Formal Concept Analysis, Lecture Notes in Computer Science, vol. 3874, (2006), Springer), 306-308 · Zbl 1177.68209
[17] Obiedkov, Sergei A.; Duquenne, Vincent, Attribute-incremental construction of the canonical implication basis, Ann. Math. Artif. Intell., 49, 1-4, 77-99, (2007) · Zbl 1125.68121
[18] Stumme, Gerd, Attribute exploration with background implications and exceptions, (Data Analysis and Information Systems, (1996), Springer), 457-469 · Zbl 0897.68104
[19] Wild, Marcel, Computations with finite closure systems and implications, (International Computing and Combinatorics Conference, (1995), Springer), 111-120
[20] Wild, Marcel, Optimal implicational bases for finite modular lattices, Quaest. Math., 23, 2, 153-161, (2000) · Zbl 0963.06006
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.