[Solved]: Is there a data-structure for semilattices similar to a tree data-structure?

Problem Detail: 

If we regard a tree as a partial ordered set, it becomes a special case of a join-semilattice. For a join-semilattice, we want to be able to compute the (unique) least upper bound of two elements (more or less) efficiently. In the case of a tree, a data structure which would enable this would be to store for each element in the corresponding node a pointer to the parent and a distance measure to the root. (Actually, a labeling based on topological sort usually used for "a distance measure to the root", effectively all that is needed is a compatible partial order which can be evaluated efficiently).

Each finite join-semilattice can be represented as a set of subsets of a finite set with containment as order such that the least upper bound is given by the union of the sets. Hence, representing each element by a finite number of tags, and computing the least upper bound by the union of the corresponding tags would be one possible data structure. (By looking at the complement, one sees that defining the least upper bound as the intersection of the corresponding tags would also be possible.) A much more common data-structure is to simply use a matrix to store all results of "a <= b" or even all results of "join(a,b)".

However, using such a data-structure to represent a tree would be sort of strange. Are there more tree-like data-structures for join-semilattices, which still allow (more or less) efficient computation of the (unique) least upper bound of two elements? (Perhaps some sort of directed acyclic graph with additional information in the nodes similar to the distance measure to the root for the tree?)

Asked By : Thomas Klimpel

Answered By : Thomas Klimpel

This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg. Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

The first two data structures discussed are the adjacency list representation of the transitive reduction graph (=Hasse diagram/cover relation) and transitive closure graph (=poset relation). A remark about the advantages of using a topological sort to label the nodes precedes that discussion. Note that the labels of topological sort would be good enough as "a distance measure to the root", which was one part of the data-structure for a tree in the question.

The other discussed representations are "Skeletal Representation", "Matrix Representation" and "Dimension Based Representation". The "Skeletal Representation" is interesting and useful, but based on a (=any) chain decomposition of the poset. The "Matrix Representation" might seem trivial, but its probably be the best representation for most practical problems. The "Dimension Based Representation" represents the poset as the subset of the Cartesian product of linear orders, but computing the minimal representation of this kind is NP-hard.

In conclusion, the most treelike representation of these is the adjacency list representation of the transitive reduction together with a labeling of the nodes by a topological sort (instead of "a distance measure to the root"). This is actually one of the representations used by Sage (the other is the "Matrix Representation").

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6245