*L*, ⊑) (our problem has a lattice that is also distributive, so you may presume that) and a node

*x*in that lattice,

efficientlycompute 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 ⊑ ?

## (no subject)

Date: 2009-09-02 01:40 am (UTC)layah.livejournal.com## (no subject)

Date: 2009-09-02 08:03 pm (UTC)natetg.livejournal.comIf we consider, for a moment, the possible example of a fully ordered set (which is a distributive lattice) then you're basically stuck sorting the entire set to find an immediate parent, so I don't think that there's a generic solution without considering every element in the worst case.

I was under the impression that you were generating the lattice, and making it distributive by construction. I'd be inclined to guess that you can get the L_x work done in construction.

## (no subject)

Date: 2009-09-02 08:03 pm (UTC)natetg.livejournal.com## (no subject)

Date: 2009-09-14 04:38 am (UTC)gchpaco.livejournal.com