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.