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

At 8:42 PM -0500 5/22/97, Joe English wrote:
>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.

I've never known, since it only occurs in the HyTime and SGML documents. I
have complained before, but I think we can take it to mean whatever we want
it to mean.

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

(4) The consistents of _whatever information the application chooses to
extract_ from the tree, between the two points in the tree.

For instance, the ESIS gives a pre- _and_ post- order traversal (of tags)
and an in-order traversal of data (you could call it pre- or post-order if
you want, since data are always leaves).

So the most plausible answer to me is that it includes:
C@2, _the and of B1_, D, _the beginning of B2_, and C3.

This is just as well defined as anything else. Of course an applicaiton
mufh legitimately need to know that this is all wrapped in an A and a Z,
too.

Think of a Span as a pointer to starting and ending nodes of the tree -- to
be used for structural operations or traversal, depending on your
application's needs. The only time you migth need to pick a set of complete
elements would be if you want to use a span as a locsrc -- which I would
personally forbid or avoid as obfuscatory.

I think that the prevalance of ESIS in parser interfaces also offers
practical evidence that this is a sensible interpretation.

>Going by the "preorder traversal" interpretation, THESPAN
>contains (1) and B2, but not B1 or A.  Is this correct?
>
>
>> 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 guess that's what left-list means!(?)

  -- David

_________________________________________
David Durand              dgd@cs.bu.edu  \  david@dynamicDiagrams.com
Boston University Computer Science        \  Sr. Analyst
http://www.cs.bu.edu/students/grads/dgd/   \  Dynamic Diagrams
--------------------------------------------\  http://dynamicDiagrams.com/
MAPA: mapping for the WWW                    \__________________________

Received on Friday, 23 May 1997 13:54:21 UTC