• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Algorithms for k-meet-semidistributive lattices

Theoretical Computer Science. 2017. Vol. 658. P. 391-398.
Beaudou L., Nourine L., Mary A.

In this paper we consider k-meet-semidistributive lattices and we are interested in the computation of the set-colored poset associated to an implicational base. The parameter k is of interest since for any finite lattice there exists an integer k for which is k-meet-semidistributive. When

they are known as meet-semidistributive lattices.

We first give a polynomial time algorithm to compute an implicational base of a k-meet-semidistributive lattice from its associated colored poset. In other words, for a fixed k, finding a minimal implicational base of a k-meet-semidistributive lattice L from a context (FCA literature) of L can be done not just in output-polynomial time (which is open in the general case) but in polynomial time in the size of the input. This result generalizes that in [26]. Second, we derive an algorithm to compute a set-colored poset from an implicational base which is based on the enumeration of minimal transversals of a hypergraph and turns out to be in polynomial time for k-meet-semidistributive lattices [13], [20]. Finally, we show that checking whether a given implicational base describes a k-meet-semidistributive lattice can be done in polynomial time.