September 2013

S M T W T F S
1 234567
891011121314
15161718192021
22232425262728
2930     

Custom Text

Most Popular Tags

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 SL = { yL : xy ∧ ∄ z xzy }. 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 ⊑ ?

Tags:
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Expand Cut Tags

No cut tags

Style Credit