-
Notifications
You must be signed in to change notification settings - Fork 0
Description
The partial order on trees should induce a lattice structure. These trees live in a forest where there can be multiple roots.
When the trees live in a forest it doesn't induce a join-semilattice because the least upper bound doesn't necessarily exist; two sub-trees could be in completely different trees in the forest.
The partial order on trees doesn't induce a meet-semilattice because because a greatest lower bound deesn't necessarily exist. two sub-trees will never contain the same sub-tree unless one of them is a supertree of the other.
The meet and join operations are only meaningful if we extend the lattice with an artificial top (for joins of subtrees in different trees in the forest) and an artificial bottom (for meets of subtrees that don't intersect).
The meet and join operations on forests are trivial.