|terminology: double-rooted DAG? email@example.com (Mark Harrison) (1998-03-03)|
|Retraction: terminology: double-rooted DAG? firstname.lastname@example.org (1998-03-07)|
|Re: Retraction: terminology: double-rooted DAG? email@example.com (1998-03-08)|
|Re: Retraction: terminology: double-rooted DAG? firstname.lastname@example.org (David Chase) (1998-03-12)|
|Date:||7 Mar 1998 22:42:07 -0500|
|Organization:||In Mind, Inc.|
"Mark Harrison" <email@example.com> writes:
>I have a DAG data structure that has two special
>1. It always has a defined root node (like a tree), and
>2. There is also a "tail" node, which is like the root
> node except at the opposite end of the graph.
I previously stated that this is a lattice. However, I was
wrong. A lattice requires that any two elements have a
least upper bound and greatest lower bound, which are by
definition, unique. My mind clearly was not working
correctly, because I forgot the "unique" part. Thus, there
are orders which have a minimal element and a maximal
element which are not lattices. An example is...
The elements e,f have two upper bounds (b and c), but do not
have a least upper bound because b and c are not comparable.
So, this partial order has a minimal element (a) and a maximal
element (g), but is not a lattice.
I have, so far, been unable to find a consise name for a partial
order with both minimal and maximal elements. I have found
all kinds of related definitions, but nothing that is "right on".
Sorry for the misinformation.
Return to the
Search the comp.compilers archives again.