On Dualization over Distributive Lattices

Research output: Contribution to journalArticlepeer-review

Abstract

Given a partially ordered set (poset) P, and a pair of families of ideals I and filters F in P such that each pair (I, F) ∈ I × 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 F and does not contain any member of 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 A, B ⊆ L such that no a ∈ A is dominated by any b ∈ B, whether A and B cover (by domination) the entire lattice. We show that the problem can be solved in quasi-polynomial time in the sizes of P, A and 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 relational database, with respect to a given implication base of maximum premise size of one, can be enumerated in incremental quasi-polynomial time.

Original languageBritish English
Article number7
JournalDiscrete Mathematics and Theoretical Computer Science
Volume24
Issue number2
DOIs
StatePublished - 2022

Keywords

  • distributive lattice
  • dualization
  • enumeration
  • implication base
  • poset

Fingerprint

Dive into the research topics of 'On Dualization over Distributive Lattices'. Together they form a unique fingerprint.

Cite this