gchpaco

S	M	T	W	T	F	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

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

From Crypto-Gram's entry Friday Squid Blogging: Dissecting a Giant Squid:

In Santa Barbara.
Among other dissection highlights, Hochberg pulled out plastic-like pieces, which comprised what could be best described as a backbone, as well as a translucent brownish-yellow piece of the beak, which is made of fingernail-like material. The giant squid's anatomy features a mouth at the top of the head, which means the esophagus travels through the brain. "So you have to get very small chunks of food," said Hochberg, "or you'll blow your brains out." The sharp beaks, then, are used to chomp food into tiny pieces before sending it down the esophagus, through the brain, and into the gut.

Any of you bio folks heard about this? Seems up your alley.

Entries tagged with science

Profile

September 2013

Custom Text

Interesting CS problem

Friday Squid Blogging: Dissecting a Giant Squid

Page Summary

Syndicate

Expand Cut Tags

Style Credit