×

Dualization in lattices given by ordered sets of irreducibles. (English) Zbl 1356.68225

Summary: Dualization of a monotone Boolean function on a finite lattice can be represented by transforming the set of its minimal 1 values to the set of its maximal 0 values. In this paper we consider finite lattices given by ordered sets of their meet and join irreducibles (i.e., as a concept lattice of a formal context). We show that in this case dualization is equivalent to the enumeration of so-called minimal hypotheses. In contrast to usual dualization setting, where a lattice is given by the ordered set of its elements, dualization in this case is shown to be impossible in output polynomial time unless P = NP. However, if the lattice is distributive, dualization is shown to be possible in subexponential time.

MSC:

68T30 Knowledge representation
06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B23 Complete lattices, completions
06E30 Boolean functions
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Order (2002), University of Oxford · Zbl 1002.06001
[2] Guigues, J. L.; Duquenne, V., Familles minimales d’implications informatives resultant d’un tableau de données binaires, Math. Inform. Sci. Hum., 95, 5-18 (1986) · Zbl 1504.68217
[3] Dyer, M.; Goldberg, L. A.; Greenhill, C.; Jerrum, M., The relative complexity of approximate counting problems, Algorithmica, 38, 471-500 (2004) · Zbl 1138.68424
[4] Eiter, T.; Makino, K.; Gottlob, G., Computational aspects of monotone dualization: a brief survey, Discrete Appl. Math., 156, 2035-2049 (2008) · Zbl 1160.68016
[5] Elbassioni, K. M., An algorithm for dualization in products of lattices and its applications, (Möhring, R.; Raman, R., Proc. 10th Annual European Symposium (ESA 2002). Proc. 10th Annual European Symposium (ESA 2002), Lecture Notes in Computer Science, vol. 2461 (2002), Springer), 424-435 · Zbl 1019.68130
[6] Elbassioni, K. M., On dualization in products of forests, (STACS 2002 (2002)), 142-153 · Zbl 1054.68582
[7] Elbassioni, K. M., Algorithms for dualization over products of partially ordered sets, SIAM J. Discrete Math., 23, 1, 487-510 (2009) · Zbl 1185.68356
[8] Finn, V. K., On machine-oriented formalization of plausible reasoning in the style of F. Backon-J.S. Mill, Semiot. Inform., 20, 35-101 (1983), in Russian · Zbl 0521.03012
[9] Finn, V. K., Plausible reasoning in systems of JSM type, Itogi Nauki Teh., Ser. Inform., 15, 54-101 (1991), in Russian
[10] Fredman, M. L.; Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21, 618-628 (1996) · Zbl 0864.68038
[11] Ganter, B.; Wille, R., Formal Concept Analysis: Mathematical Foundations (1999), Springer: Springer Berlin · Zbl 0909.06001
[12] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[13] Ganter, B.; Kuznetsov, S. O., Hypotheses and version spaces, (de Moor, A.; Lex, W.; Ganter, B., Proc. 10th Int. Conf. on Conceptual Structures. Proc. 10th Int. Conf. on Conceptual Structures, ICCS’03. Proc. 10th Int. Conf. on Conceptual Structures. Proc. 10th Int. Conf. on Conceptual Structures, ICCS’03, Lecture Notes in Artificial Intelligence, vol. 2746 (2003)), 83-95 · Zbl 1274.68311
[14] Grätzer, G., Lattice Theory: Foundation (2011), Birkhäuser · Zbl 1233.06001
[15] Kavvadias, D. J.; Sideri, M.; Stavropoulos, E. C., Generating all maximal models of a Boolean expression, Inform. Process. Lett., 74, 3-4, 157-162 (2000) · Zbl 1339.03015
[16] Kuznetsov, S. O., Mathematical aspects of concept analysis, J. Math. Sci., 80, 2, 1654-1698 (1996) · Zbl 0885.06001
[17] Kuznetsov, S. O., Complexity of learning in concept lattices from positive and negative examples, Discrete Appl. Math., 142, 111-125 (2004) · Zbl 1077.68039
[18] Kuznetsov, S. O.; Obiedkov, S. A., Some decision and counting problems of the Duquenne-Guigues basis of implications, Discrete Appl. Math., 156, 11, 1994-2003 (2008) · Zbl 1160.68031
[19] Nourine, L.; Petit, J.-M., Extending set-based dualization: application to pattern mining, (de Raedt, Luc, Proc. European Conference on Artificial Intelligence. Proc. European Conference on Artificial Intelligence, ECAI’2012 (2012)), 630-635 · Zbl 1327.68281
[20] Dechter, R.; Pearl, J., Structure identification in relational data, Artificial Intelligence, 5, 237-270 (1992) · Zbl 0782.68095
[21] Khardon, R., Translating between Horn representations and their characteristic models, J. Artificial Intelligence Res., 3, 349-372 (1995) · Zbl 0900.68197
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.