# Is there a data-structure for semilattices similar to a tree data-structure?

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

• Theorem 2.2 from math.hawaii.edu/~jb/math618/os2uh.pdf shows that a semilattice can be represented as a set of subsets (in a relatively trivial way) as assumed above. Oct 22, 2012 at 22:59