Optimum basis of finite convex geometry. (English) Zbl 1423.06012

Summary: Convex geometries form a subclass of closure systems with unique criticals, or \(U C\)-systems. We show that the \(F\)-basis introduced in [the author and J. B. Nation, Discrete Appl. Math. 162, 51–69 (2014; Zbl 1341.06003)] for \(U C\)-systems, becomes optimum in convex geometries, in two essential parts of the basis: right sides (conclusions) of binary implications and left sides (premises) of non-binary ones. The right sides of non-binary implications can also be optimized, when the convex geometry either satisfies the Carousel property, or does not have \(D\)-cycles. The latter generalizes a result of P. L. Hammer and A. Kogan [“Quasi-acyclic propositional Horn knowledge bases: optimal compression”, IEEE Trans. Knowl. Data Eng. 7, No. 5, 751–762, (1995; doi:10.1109/69.469822)] for acyclic Horn Boolean functions. Convex geometries of order convex subsets in a poset also have tractable optimum basis. The problem of tractability of optimum basis in convex geometries in general remains to be open.


06A15 Galois correspondences, closure operators (in relation to ordered sets)
52A01 Axiomatic and generalized convexity
06E30 Boolean functions


Zbl 1341.06003
Full Text: DOI arXiv


[1] K. Adaricheva, Supersolvable semidistributive lattices, preprint. · Zbl 0716.06001
[2] Adaricheva, K., Two embedding theorems for lower bounded lattices, Algebra Universalis, 36, 425-430, (1996) · Zbl 0901.06005
[3] Adaricheva, K., Representing finite convex geometries by relatively convex sets, European J. Combin., 37, 68-78, (2014) · Zbl 1282.05022
[4] Adaricheva, K. V.; Gorbunov, V. A.; Tumanov, V. I., Join-semidistributive lattices and convex geometries, Adv. Math., 173, 1-49, (2003) · Zbl 1059.06003
[5] Adaricheva, K.; Nation, J. B., On implicational bases of closure systems with unique critical sets, Discrete Appl. Math., 162, 51-69, (2014) · Zbl 1341.06003
[6] Adaricheva, K.; Nation, J. B.; Rand, R., Ordered direct implicational basis of a finite closure system, Discrete Appl. Math., 161, 707-723, (2013) · Zbl 1288.06007
[7] Adaricheva, K.; Wild, M., Realization of abstract convex geometries by point configurations, European J. Combin., 31, 379-400, (2010) · Zbl 1181.52002
[8] Armstrong, D., The sorting order on a Coxeter group, J. Combin. Theory Ser. A, 116, 1285-1305, (2009) · Zbl 1211.20033
[9] Bertet, K.; Monjardet, B., The multiple facets of the canonical direct unit implicational basis, Theoret. Comput. Sci., 411, 2155-2166, (2010) · Zbl 1209.68187
[10] Boros, E.; Čepek, O.; Kogan, A.; Kučera, P., A subclass of Horn CNFs optimally compressible in poynomial time, Ann. Math. Artif. Intell., 57, 3-4, 249-291, (2009) · Zbl 1253.68311
[11] Caspard, N.; Monjardet, B., The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Appl. Math., 127, 241-269, (2003) · Zbl 1026.06008
[12] Dietrich, B., A circuit characterization of antimatroids, J. Combin. Theory Ser. B, 43, 314-321, (1987) · Zbl 0659.05036
[13] Duquenne, V., On the core of finite lattices, Discrete Math., 88, 133-147, (1991) · Zbl 0736.06012
[14] Edelman, P. H.; Jamison, R., The theory of convex geometries, Geom. Dedicata, 19, 247-274, (1985) · Zbl 0577.52001
[15] Freese, R.; Ježek, J.; Nation, J. B., (Free Lattices, Mathematical Surveys and Monographs, vol. 42, (1995), Amer. Math. Soc. Providence) · Zbl 0839.06005
[16] Guigues, J. L.; Duquenne, V., Familles minimales d’implications informatives résultant d’une tables de données binares, Math. Sci. Hum., 95, 5-18, (1986)
[17] Hammer, P. L.; Kogan, A., Quasi-acyclic propositional Horn knowledge bases: optimal compression, IEEE Trans. Knowl. Data Eng., 7, 751-762, (1995)
[18] Jónsson, B.; Kiefer, J. E., Finite sublattices of a free lattice, Canad. J. Math., 14, 487-497, (1962) · Zbl 0107.25202
[19] K. Kashiwabara, M. Nakamura, The rooted circuits, the rooted cocircuits of convex geometries, the closure operators and monotone extensive operators, preprint. The slides of AAB II workshop: http://www.math.u-szeged.hu/ horvath/aabslides.
[20] Kashiwabara, K.; Nakamura, M., The prime stems of rooted circuits of closure spaces, Electron. J. Combin., 20, (2013), paper 22, 13 pages · Zbl 1264.06006
[21] Maier, D., Minimum covers in the relational database model, J. Assoc. Comput. Mach., 27, 664-674, (1980) · Zbl 0466.68085
[22] McNamara, P., EL-labelings, supersolvability and \(0\)-Hecke algebra actions on posets, J. Combin. Theory Ser. A, 101, 69-89, (2003) · Zbl 1020.06004
[23] Monjardet, B., A use for frequently rediscovering a concept, Order, 1, 415-417, (1985) · Zbl 0558.06010
[24] Santocanale, L.; Wehrung, F., Lattices of regular closed subsets of closure spaces, Internat. J. Algebra Comput., 24, 969-1030, (2014) · Zbl 1404.06006
[25] Sivak, B., Representation of finite lattices by orders on finite sets, Math. Slovaca, 28, 203-215, (1978) · Zbl 0395.06002
[26] Stanley, R., Supersolvable lattices, Algebra Universalis, 2, 197-217, (1972) · Zbl 0256.06002
[27] Wild, M., A theory of finite closure spaces based on implications, Adv. Math., 108, 118-139, (1994) · Zbl 0863.54002
[28] Wild, M., Optimal implicational bases for finite modular lattices, Quaestiones Math., 23, 153-161, (2000) · Zbl 0963.06006
[29] Yoshikawa, H.; Hirai, H.; Makino, K., A representation of antimatroids by Horn rules and its application to educational systems, J. Math. Psych., 77, 82-93, (2017) · Zbl 1396.91660
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.