论文标题
关于分配晶格的双重化
On Dualization over Distributive Lattices
论文作者
论文摘要
给定部分订单集（poset）$ p $，以及一对$ \ nathcal {i} $和$ p $中的$ \ nathcal {f} $的过滤器，以使每个$（i，f）\ in \ in \ mathcal {i} \ times \ times \ nation \ nathcal is a prifate a prection a prection a dective a dectization是否not-expliative，dectization是否notization nikection nige and dual n d d ar d d ar d d ar n d d d auciative， $ x $ in $ p $与$ \ mathcal {f} $的每个成员相交，并且不包含$ \ Mathcal {i} $的任何成员。同等地，问题是要检查是否有一套poset $ p $给出了一套inter-irreducibles的popet $ p $，还有两个给定的抗敌人$ \ mathcal {a}，\ mathcal {b} \ subseteq l $ $ b \ in \ Mathcal {b} $，无论$ \ Mathcal {a} $和$ \ Mathcal {B} $ cover（通过统治）整个晶格。我们表明，该问题可以在$ p $，$ \ mathcal {a} $和$ \ Mathcal {b} $的大小中解决问题，从而在Babin and Kuznetsov（2017）中回答了一个空旷的问题。作为一个应用程序，我们表明，在有理数据库中的最小封闭属性集相对于一个给定的最大前提大小的给定含义基础，可以在递增的准级别 - 多种元素时间中列举。
Given a partially order set (poset) $P$, and a pair of families of ideals $\mathcal{I}$ and filters $\mathcal{F}$ in $P$ such that each pair $(I,F)\in \mathcal{I}\times\mathcal{F}$ has a non-empty intersection, the dualization problem over $P$ is to check whether there is an ideal $X$ in $P$ which intersects every member of $\mathcal{F}$ and does not contain any member of $\mathcal{I}$. Equivalently, the problem is to check for a distributive lattice $L=L(P)$, given by the poset $P$ of its set of joint-irreducibles, and two given antichains $\mathcal{A},\mathcal{B}\subseteq L$ such that no $a\in\mathcal{A}$ is dominated by any $b\in\mathcal{B}$, whether $\mathcal{A}$ and $\mathcal{B}$ cover (by domination) the entire lattice. We show that the problem can be solved in quasi-polynomial time in the sizes of $P$, $\mathcal{A}$ and $\mathcal{B}$, thus answering an open question in Babin and Kuznetsov (2017). As an application, we show that minimal infrequent closed sets of attributes in a rational database, with respect to a given implication base of maximum premise size of one, can be enumerated in incremental quasi-polynomial time.
