Re: Dimension of sequences
CChris wrote:
>
> 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</font></i>
> > > > > 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</font></i>
> > > > > 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</font></i>
> > > > > 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</font></i>
> > > > > them, namely strings of arbitrary things, among which trees. It has
> > > > > been
> chosen</font></i>
> > > > > to build this special notion in the language, and to leave out the
> > > > > more
> general</font></i>
> > > > > ones. Other trees will have their own notion of depth or somsuch,
> > > > > which
> depends</font></i>
> > > > > 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</font></i>
> > > > > 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.
OK, let's see what is every atom in some complicated sequence.
I think, that every atom can be, so to say, one of the dimensions
or coordinates of some multi-dimensional object, described by that
given sequence.
So the common number of atoms of some given sequence is very
interesting thing - it gives us sometimes the number of
dimensions of the described object!
We can name this parameter with some suitable word to
characterize, so to say, a volume of a sequence, or its
capacity or something.
It is not the sum of all lengths, it is number of atoms,
and a function for calculation of this number may be
very simple.
Well, I'll be out of town several days, sorry...
Regards,
Igor Kachan
kinz at peterlink.ru
|
Not Categorized, Please Help
|
|
