Re: Link-3: Sets, Singletons, and Determinism

At 06:42 PM 5/22/97 -0700, Joe English wrote:
>
>
>
>W. Eliot Kimber <eliot@isogen.com> wrote:
>
>> As defined in terms of groves in HyTime, a span addresses the list of nodes
>> in the grove from the span start to the span end, inclusive, in left-list
>> pre-order traversal.
>
>What precisely is a "left-list pre-order traversal"?
>I've seen that term used dozens of times and have always
>assumed it to mean the same thing as "preorder traversal",
>but this makes me wonder.

That's certainly what I take it to mean--I believe "left list" simply means
that the earlier nodes are on the left in the visualization of the tree,
i.e., that the youngest child of a node is visualized as being to the left
of its siblings. 

>
>For example, consider:
>
>    <nameloc id=THESPAN spanloc=spanloc>
>	<nmlist nametype=element>  C2 C3  </>
>    </nameloc>
>    <z id=Z>
>	<a id=A>
>	    <b id=B1>
>		<c id=C1>...</c>
>		<c id=C2>...</c>		<!-- span start -->
>	    </b>
>	    <d id=D>...</d>
>	    <b id=B2>
>		<c id=C3>...</c>		<!-- span end -->
>		<c id=C4>...</c>
>	    </b>
>	</a>
>    </z>
>
>
Here's the miminum tree that contains the span (for easier visualization):

                            .---A---.
                           /    |    \
                          B1    D    B2
                         /  \       /  \
                        C1  C2     C3  C4

>Does THESPAN include B1?  B2?  In a preorder traversal, B2 is visited
>between C2 and C3, but B1 is not.  Does THESPAN include A?  Z?

>I can think of three reasonable (to me) interpretations of SPANLOC:
>THESPAN consists of either:
>
>    (1) only C2, D, and C3, and their respective content; or
>    (2) B1, and B2, in addition to (1) (since the span crosses
>	B1's and B2's boundaries); or
>    (3) A, in addition to (2) (since A is the root of the smallest
>	subtree containing the span).
>

This is a good question.  My initial interpretation is that the span
addresses the following node list:

(C2 D C3)

In other words, the *complete* nodes between the span start and end
(inclusive).  By *complete* I mean nodes that are completely within the
scope of the span.  B1, A, and B2 are not completely within the scope of
the span, so they are not addressed.  

>Going by the "preorder traversal" interpretation, THESPAN
>contains (1) and B2, but not B1 or A.  Is this correct?

I can certainly see an argument for including B1, but I don't think it
should be included.

What do people think?  It's not too late to clarify the language of SPANLOC
in HyTime, so I'm open to suggestion.  If nobody says otherwise, I'll
clarify it to mean "complete" nodes as explained above and include this
example.

>> The nodes are either those in the content tree that
>> includes all of the span or the nodes in the subnode tree that includes the
>> span.
>
>That can't be right!  That would mean that THESPAN contains
>the Z and A nodes, but *not* C2, C3, or any of their descendants!

I didn't mean the list is all the nodes in those trees.  I meant that the
tree the nodes are selected from is either a content tree or a subnode
tree.  For example, if nodes B1 and B2 are element nodes and they have
attributes, then those attributes could be part of the span if the span is
addressing the subnode tree, but would not be if the span is addressing the
content tree (attributes are not part of an element node's content by
definition in the SGML property set).

Cheers,

Eliot

Received on Friday, 23 May 1997 10:49:35 UTC