Re: Dimension of sequences
Igor Kachan wrote:
>
> CChris wrote:
> >
> > Igor Kachan wrote:
> > >
> > > CChris wrote:
> > > >
> > > > Igor Kachan wrote:
> > > > >
> > > > > Fernando Bauer wrote:
> > > > > >
> > > > > > Igor Kachan wrote:
> > > > > > >
>
> [snip]
>
> > > > Eu sequences model trees with atomic labels allowed, and mandatory, only
> > > > on
> > > > leaf nodes.
> > > > For instance, {1,{2,3},4} is the same as
> > > > root -> node1, node2, node3
> > > > node1: 1
> > > > node2 -> node4, node5
> > > > node3: 4
> > > > node4: 2
> > > > node5: 3
> > > >
> > > > with hopefully obvious meaning of such a description of a tree.
> > > >
> > > > Now google for some litterature on trees. You'lll see that most specific
> > > > form
> > > > of trees define their own dimension, depth or height.
> > > > Concepts that can be defined always include:
> > > > * the depth of a tree, which is the height of its root;
> > >
> > > OK, I like this theory very much as math at all, some good
> > > thing to get crazy, if you do not have or do not like vodka, sorry. 
> > >
> > > Why do they need these topsyturvy trees, Cris?
> > >
> >
> > They are the most common objects in decision theory (think of a chess
> > computer
> > program) or in searching/retrieval problems (remember the contest Derek had
> > hosted a couple years ago?). And many others, but hese may be the most
> > obvious.
> >
> > > I can understand depth of a root and height of a tree,
> > > but not on the contrary.
> > >
> >
> > This has to do with our habit to read a sheet of paper from top to bottom,
> which is why the root is usually on</font></i>
> > top
> >
> > > > * the depth of a node in a tree, which is its distance to the root (ie
> > > > the
> number</font></i>
> > > > of edges to go from the node to the root);
> > > > * the height of a node, which is the length of the longest path from the
> > > > node
> > > > to a leaf node in its subtree.
> > >
> > > Same thing, very-very demonstrative concept.
> > >
> > > > The length of a sequence is simply the number of children of the root.
> > > > This
> > > > has not much importance in tree theory, but is essential for _some_
> > > > sorts of
> > > > them, namely strings of arbitrary things, among which trees. It has been
> > > > chosen
> > > > to build this special notion in the language, and to leave out the more
> > > > general
> > > > ones. Other trees will have their own notion of depth or somsuch, which
> > > > depends
> > > > on the speifics of the layout an uses of the given family of trees.
> > > > So yes, sequences don't have a single dimension, although some sorts of
> > > > sequences
> > > > do have a more intinsic kind of dimension. Strings are an example, for
> > > > which
> > > > the length is the "natural" dimension.
> > >
> > > OK, but depth of a string exists and is 1. So sequence seems to be
> > > some 2-dimensional object anyway and always.
> > >
> > 2,3,27,... depending on the exact notion of dimension you need. A sequence
> > whose elements may freely be atoms or not has dimension 1, and strings are
> > special
> > cases of them. Otherwise, as I said, the concept is not uniquely defined,
> > and
> > the value for the dimension is always 2 or more.
>
> Here, in Russia, we use 2 words for these things:
> "izmerenie" -- it is just single "dimension"
> and
> "razmernost'" -- it is common number of dimensions, "dimensionality".
> So I'd prefer to say that any sequence has dimensionality 2,
> and its dimensions are named as "length" and "depth".
This looks ok to me, except that the length is really a very special case.
> But this 2-dimensional sequence can describe and contain
> multi-dimensional objects.
> Anyway, in machine memory, it is just 1-dimensional *range* of
> addresses.
>
Exactly. So the "length" of a general sequence would be the total number of
nodes it holds. The current definition of length() is very adequate for linear
trees - one root with length(s) children, the nature of which is not taken into
account -. For general trees, however, it barely makes sense.
CChris
> Regards,
> Igor Kachan
> kinz at peterlink.ru
|
Not Categorized, Please Help
|
|
