Dualization in lattices given by ordered sets of irreducibles

详细信息    查看全文

• 关键词：Monotone Boolean dualization ; Distributive lattice ; Formal concept analysis
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PB
• 页码：316-326
• 全文大小：376 K
• 卷排序：658

文摘

Dualization of a monotone Boolean function on a finite lattice can be represented by transforming the set of its minimal 1 values to the set of its maximal 0 values. In this paper we consider finite lattices given by ordered sets of their meet and join irreducibles (i.e., as a concept lattice of a formal context). We show that in this case dualization is equivalent to the enumeration of so-called minimal hypotheses. In contrast to usual dualization setting, where a lattice is given by the ordered set of its elements, dualization in this case is shown to be impossible in output polynomial time unless P = NP. However, if the lattice is distributive, dualization is shown to be possible in subexponential time.