Algorithms for k-meet-semidistributive lattices

详细信息    查看全文

• 作者：Laurent Beaudou^a ; ^{laurent.beaudou@univ-bpclermont.fr} ; Arnaud Mary^b ; ^{arnaud.mary@univ-lyon1.fr} ; Lhouari Nourine^a ; ^{nourine@isima.fr}
• 关键词：k-Meet-semidistributive lattice ; Colored poset ; Implicational base
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PB
• 页码：391-398
• 全文大小：467 K
• 卷排序：658

文摘

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 LL there exists an integer k   for which LL is k  -meet-semidistributive. When k=1k=1 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  and . Finally, we show that checking whether a given implicational base describes a k-meet-semidistributive lattice can be done in polynomial time.