Interesting CS problem

[gchpaco]

I've come across a rather interesting CS problem during work that I thought I'd throw out there. The problem is this: given a finite lattice (L, ⊑) (our problem has a lattice that is also distributive, so you may presume that) and a node x in that lattice, efficiently compute the set S ⊆ L = { y ∈ L : x ⊏ y ∧ ∄ z x ⊏ z ⊏ y }. This is well defined, and starting from ⊥ it is possible to walk the entire lattice easily (which is why we care). If you precompute the lattice you can do this trivially. Is it possible to do so without considering every node in the lattice?

Failing that, can you give me an efficient algorithm for computing the structure of the lattice from a set L and a partial order ⊑ ?

Comments

[natetg.livejournal.com]

L_x should be S_x at the end of the first para.

[gchpaco.livejournal.com]

As it happens, there's a closely related problem in formal concept analysis concerning the Galois lattice, and there are techniques for reconstructing the Hasse diagram, which implicitly requires knowledge of the covering set, in time O(|L|); however, they are not incremental. I'm looking into alternatives but have been told to stop thinking about this and do something business related.