Retraction: terminology: double-rooted DAG?

"Mark Harrison" <markh@usai.asiainfo.com> writes:


>I have a DAG data structure that has two special
>features:


>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...


            a
          / \
        / \
        b c
        |\ /|
        | |
        |/ \|
        e f
          \ /
              g


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 comp.compilers page.
Search the comp.compilers archives again.