3
$\begingroup$

In a partially ordered set L, an antichain is a subset A of L such that no two elements of A are comparable.

Antichains are commonly used to represent upward-closed subsets of L, that is, sets S such that if x is in S, any y ≥ x is also in S: if L is finite (the situation is more complicated in the infinite case), then any such S can be represented as the upward closure of the antichain of its minimal elements.

Given S1 and S2 respectively defined as the upward closures of antichains A1 and A2, the literature describes how to compute an antichain describing the union (respectively, the intersection) of S1 and S2:

  • For union, take the union of S1 and S2 and keep only the minimal elements.

  • For intersection, assuming L is a lattice, take the least upper bounds of pairs of elements (a1,a2) from A1×A2, and retain the minimal elements.

There is a trivial quadratic algorithm for retaining only minimal elements (perform all pairwise comparisons and remove elements shown not to be minimal). Naively, union is thus quadratic and intersection degree 4.

I have not been able to find in the literature any more detailed description of suitable algorithms or data structures; for instance can the antichain be represented as a BDD-like structure, etc.

I'd be curious to know about literature on non-naive implementations of antichains, particularly if L is the lattice of subsets of a finite set.

$\endgroup$
  • $\begingroup$ Your question is describing already describing efficient algorithms for union and intersection. Perhaps you're interested in the complexity of computing the union and intersection of antichains. $\endgroup$ – Yuval Filmus Mar 1 '18 at 8:59
  • $\begingroup$ These algorithms I wrote about assume an explicit representation of the antichain and "black box" inclusion tests. I was thinking of more clever representations, in the same way that a BDD is more clever than an explicit list of states. $\endgroup$ – David Monniaux Mar 1 '18 at 9:32
  • $\begingroup$ Can you clarify what you are asking? You say you couldn't find more detailed descriptions, but why do you need more detail? The algorithm you presented already seems very clear. I imagine that if you want an algorithm more sophisticated than the straightforward trivial quadratic-time algorithm you allude to, that might depend on the specific lattice and/or how lattice elements are represented. Can you edit the question to clarify what you are asking? $\endgroup$ – D.W. Mar 1 '18 at 21:14
  • $\begingroup$ Possibly relevant: cstheory.stackexchange.com/q/37361/5038. $\endgroup$ – D.W. Mar 1 '18 at 21:16
  • $\begingroup$ The algorithms I gave do not specify the representation of the antichain elements and just rely on black-box comparison. As said in the question, I'm more focused on the case where L is the lattice of subsets of a set, in which case there may be better data structures and algorithms. $\endgroup$ – David Monniaux Mar 2 '18 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.