Dualization in lattices given by implicational bases. (English) Zbl 1435.68115
Cristea, Diana (ed.) et al., Formal concept analysis. 15th international conference, ICFCA 2019, Frankfurt, Germany, June 25–28, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11511, 89-98 (2019).
Summary: It was recently proved that the dualization in lattices given by implicational bases is impossible in output-polynomial time unless \(\mathrm{P}=\mathrm{NP}\). In this paper, we show that this result holds even when the premises in the implicational base are of size at most two. In the case of premises of size one – when the lattice is distributive – we show that the dualization is possible in output quasi-polynomial time whenever the graph of implications is of bounded maximum induced matching. Lattices that share this property include distributive lattices coded by the ideals of an interval order.
For the entire collection see [Zbl 1412.68008].
For the entire collection see [Zbl 1412.68008].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 03G10 | Logical aspects of lattices and related structures |
| 06B05 | Structure theory of lattices |
| 06D05 | Structure and representation theory of distributive lattices |
| 06D50 | Lattices and duality |
| 68R05 | Combinatorics in computer science |
Keywords:
lattice dualization; transversals enumeration; implicational base; distributive lattices; interval orderReferences:
| [1] | Babin, MA; Kuznetsov, SO; Valtchev, P.; Jäschke, R., Enumerating minimal hypotheses and dualizing monotone boolean functions on lattices, Formal Concept Analysis, 42-48, 2011, Heidelberg: Springer, Heidelberg · Zbl 1326.68281 · doi:10.1007/978-3-642-20514-9_5 |
| [2] | Babin, MA; Kuznetsov, SO, Dualization in lattices given by ordered sets of irreducibles, Theor. Comput. Sci., 658, 316-326, 2017 · Zbl 1356.68225 · doi:10.1016/j.tcs.2016.01.005 |
| [3] | Birkhoff, G., Rings of sets, Duke Math. J., 3, 3, 443-454, 1937 · JFM 63.0832.02 · doi:10.1215/S0012-7094-37-00334-X |
| [4] | Birkhoff, G., Lattice Theory, 1940, New York: American Mathematical Society, New York · Zbl 0063.00402 |
| [5] | Bogart, KP, An obvious proof of Fishburn’s interval order theorem, Discrete Mathe., 118, 1-3, 239-242, 1993 · Zbl 0781.06001 · doi:10.1016/0012-365X(93)90065-2 |
| [6] | Creignou, N., Kröll, M., Pichler, R., Skritek, S., Vollmer, H.: A complexity theory for hard enumeration problems. Discrete Appl. Math. (2019). doi:10.1016/j.dam.2019.02.025 · Zbl 1419.05016 |
| [7] | Davey, BA; Priestley, HA, Introduction to Lattices and Order, 2002, Cambridge: Cambridge University Press, Cambridge · Zbl 1002.06001 · doi:10.1017/CBO9780511809088 |
| [8] | Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM J. Comput., 24, 6, 1278-1304, 1995 · Zbl 0842.05070 · doi:10.1137/S0097539793250299 |
| [9] | Eiter, T.; Gottlob, G.; Makino, K., New results on monotone dualization and generating hypergraph transversals, SIAM J. Comput., 32, 2, 514-537, 2003 · Zbl 1052.68101 · doi:10.1137/S009753970240639X |
| [10] | Eiter, T.; Makino, K.; Gottlob, G., Computational aspects of monotone dualization: a brief survey, Discrete Appl. Math., 156, 11, 2035-2049, 2008 · Zbl 1160.68016 · doi:10.1016/j.dam.2007.04.017 |
| [11] | Elbassioni, KM; Möhring, R.; Raman, R., An algorithm for dualization in products of lattices and its applications, Algorithms — ESA 2002, 424-435, 2002, Heidelberg: Springer, Heidelberg · Zbl 1019.68130 · doi:10.1007/3-540-45749-6_39 |
| [12] | Elbassioni, KM, Algorithms for dualization over products of partially ordered sets, SIAM J. Discrete Math., 23, 1, 487-510, 2009 · Zbl 1185.68356 · doi:10.1137/050622250 |
| [13] | Fishburn, PC, Intransitive indifference with unequal indifference intervals, J. Math. Psychol., 7, 1, 144-149, 1970 · Zbl 0191.31501 · doi:10.1016/0022-2496(70)90062-3 |
| [14] | Fredman, ML; Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21, 3, 618-628, 1996 · Zbl 0864.68038 · doi:10.1006/jagm.1996.0062 |
| [15] | Garey, MR; Johnson, DS, Computers and Intractability, 2002, New York: W. H. Freeman, New York |
| [16] | Grätzer, G., Lattice Theory: Foundation, 2011, Basel: Springer, Basel · Zbl 1233.06001 · doi:10.1007/978-3-0348-0018-1 |
| [17] | Gunopulos, D., Mannila, H., Khardon, R., Toivonen, H.: Data mining, hypergraph transversals, and machine learning. In: PODS, pp. 209-216. ACM (1997) |
| [18] | Johnson, DS; Yannakakis, M.; Papadimitriou, CH, On generating all maximal independent sets, Inf. Process. Lett., 27, 3, 119-123, 1988 · Zbl 0654.68086 · doi:10.1016/0020-0190(88)90065-8 |
| [19] | Kavvadias, DJ; Sideri, M.; Stavropoulos, EC, Generating all maximal models of a boolean expression, Inf. Process. Lett., 74, 3-4, 157-162, 2000 · Zbl 1339.03015 · doi:10.1016/S0020-0190(00)00023-5 |
| [20] | Nourine, L., Petit, J.M.: Extending set-based dualization: application to pattern mining. In: Proceedings of the 20th European Conference on Artificial Intelligence, pp. 630-635. IOS Press (2012) · Zbl 1327.68281 |
| [21] | Nourine, L.; Petit, JM; Kotzinos, D.; Choong, YW; Spyratos, N.; Tanaka, Y., Dualization on partially ordered sets: preliminary results, Information Search, Integration and Personalization, 23-34, 2016, Cham: Springer, Cham · doi:10.1007/978-3-319-38901-1_2 |
| [22] | Wild, M., The joy of implications, aka pure horn formulas: mainly a survey, Theor. Comput. Sci., 658, 264-292, 2017 · Zbl 1418.03144 · doi:10.1016/j.tcs.2016.03.018 |
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.
