7 Mar 1998 22:42:07 -0500

Related articles |
---|

terminology: double-rooted DAG? markh@usai.asiainfo.com (Mark Harrison) (1998-03-03) |

Retraction: terminology: double-rooted DAG? mfinney@inmind.com (1998-03-07) |

Re: Retraction: terminology: double-rooted DAG? jjones@cs.uiuc.edu (1998-03-08) |

Re: Retraction: terminology: double-rooted DAG? chase@naturalbridge.com (David Chase) (1998-03-12) |

From: | mfinney@inmind.com |

Newsgroups: | comp.compilers |

Date: | 7 Mar 1998 22:42:07 -0500 |

Organization: | In Mind, Inc. |

References: | 98-03-021 |

Keywords: | theory |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.