Minimum implicational basis for \(\wedge\)-semidistributive lattices. (English) Zbl 1185.06009

Summary: For a \(\wedge\)-semidistributive lattice \(L\), we study some particular implicational systems and show that the cardinality of a minimum implicational basis is polynomial in the size of join-irreducible elements of the lattice \(L\). We also provide a polynomial-time algorithm to compute a minimum implicational basis for \(L\).


06D75 Other generalizations of distributive lattices
03G10 Logical aspects of lattices and related structures
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI Link


[1] Caspard, N.; Monjardet, B., The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey, Discrete applied mathematics, 127, 2, 241-269, (2003) · Zbl 1026.06008
[2] Duquenne, V., The core of finite lattice, Discrete mathematics, 88, 133-147, (1991) · Zbl 0736.06012
[3] Eiter, T.; Gottlob, G., Identifying the minimal transversals of a hypergraph and related problems, SIAM journal on computing, 24, 6, 1278-1304, (1995) · Zbl 0842.05070
[4] T. Eiter, G. Gottlob, Hypergraph transversal computation and related problems in logic and AI, in: European Conference on Logics in Artificial Intelligence (JELIA’02), 2002, pp. 549-564 · Zbl 1013.68143
[5] Fredman, M.L.; Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms, Journal of algorithms, 21, 618-628, (1996) · Zbl 0864.68038
[6] Ganter, B.; Wille, R., Formal concept analysis: mathematical foundations, (1996), Springer-Verlag Berlin · Zbl 0861.06001
[7] Guigues, J.L.; Duquenne, V., Families minimales d’implications informatives resultant d’un tableau de donnes binaires, Mathétiques et sciences humaines, 95, 5-18, (1986)
[8] Freeze, R.; Jezek, K.; Nation, J.B., Free lattices, (1995), American Mathematical Society Providence, RI
[9] Janssen, P.; Nourine, L., A simplicial scheme for meet-semidistributive lattices and interval collapsing, Universalis algebra, 50, 2, 171-178, (2003) · Zbl 1092.06004
[10] Maier, D., The theory of relational data bases, (1983), Computer Science Press Rockville, MD
[11] Nation, J.B., Unbounded semidistributive lattices, Algebra and logic, 39, 87-92, (2000) · Zbl 0954.06008
[12] L. Nourine, Une structuration algorithmique de la théorie des treillis, Habilitation à diriger des recherches, Université de Montpellier II, France, July 2000
[13] Shock, R.C., Computing the minimum cover of functional dependencies, Information processing letters, 22, 3, 157-159, (1986) · Zbl 0587.68088
[14] Wild, M., Optimal implicational bases for finite modular lattices, Quaestiones mathematicae, 23, 153-161, (2000) · Zbl 0963.06006
[15] Wille, R., Subdirect decomposition of concept lattices, Algebra universalis, 17, 275-287, (1983) · Zbl 0539.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.