[Prev][Next][Index][Thread]

Re: clink/ilink direction (Was: anchor awareness)



At 16:02 28/12/96 -0500, David G. Durand wrote:
>At 4:11 PM 12/27/96, W. Eliot Kimber wrote:
>>At 05:04 PM 12/27/96 -0500, David G. Durand wrote:
>>>    A "grove" is just a new name for what everyone else in the world calls
>>>a "parse tree".
>>
>>Not exactly correct: groves are a new name for what everyone else in the
>>world calls a direct graph data structure.  It happens that one obvious
>>application of directed graphs is the representation of parse trees, but
>>that's not the only thing groves are used for.  Groves are useful because
>>the provide the following features on top of the basic directed graph of
>>nodes concept:
>
>trees are directed graphs. Are you saying that groves can include cyles of
>nodes (ie node that are their own ancestors), or multiple inheritance
>(directed _acyclic graphs_)? If not, groves are part of that subset of
>directed graphs known as trees, and you are spreading more smoke into the
>air, instead of shedding light on the issues.

Groves are directed graphs (not acyclic), but they can also be considered as
trees.  More precisely:

- A subset of the edges are distinguished as representing
"origin-to-subnode" relationships.  If you delete all edges other than
these, then the graph becomes a single tree.

- A subset of the "origin-to-subnode" edges are distinguished as
representing parent-child relationships.  If you delete all edges other than
these, then the graph becomes a set of disjoint trees: one of these trees is
the normal ESIS-like element structure tree; each attribute assignment (name
plus value) is also its own tree.

James