Hacker News new | comments | show | ask | jobs | submit login

All finite lattices are posets, but not all finite posets are lattices, so I stand by the usage.

Yes obviously, but nowhere is it clear that you actually have a lattice of any kind. Specifically, I see no reason why pruning DAGs of unused computations would yield a lattice, and this is a result you seem to rely on. Program lattice does indeed sound nicer than program bounded poset, but I would be more wary about misusing terminology than having a nice name! :)

The least upper bound can be thought of as a virtual node consisting of the set of static constants (and the set of all inputs) fed into the rest of the lattice. The greatest lower bound is a virtual node consisting of the set of final output values that are "used" (written to an output file or database). If an intermediate value is computed but is not referenced anywhere, the data dependency DAG has a local lower bound node that is not connected to the greatest lower bound since the value is not written anywhere. If these unused nodes are pruned away, the result is a lattice.


For that construction to work, these 'virtual' nodes need to exist in the poset. Your poset is just the vertex set of your DAG ordered by reachability, so they don't exist. I think your intuition is good, but the mathematics just doesn't add up. Perhaps you should look into things like trace monoids, pomsets and petri nets?

Please understand that I'm not trying to be mean here. You mention you've been applying for grants to work on this, but if you don't explain the mathematics adequately or demonstrate how it differs from existing formalisms then I imagine people are just going to reject you instantly. I would suggest seriously trying to formalise some of this stuff in a proof assistant like Coq. That'll quickly tell you if your theory works or not.


Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact