Re: Co-optation Today

Rusty Sites wrote:
John Harshman wrote:
[snips for norman]

I have been caught somewhere between trees as a useful data structure and trees in the abstract. In its bare essence, a tree is nothing but nodes and arcs. It has no values associated with it. I don't think a nested hierarchy can exist even in the abstract with no values. Otherwise, there is nothing to distinguish one member from another. The meaning of nested hierarchy in set notation is obvious. Allow nested sets and don't let any member appear twice. There is also a very obvious translation between nested hierarchies and trees with values associated with the leaf nodes. So nested hierarchies are equivalent to trees with values associated with their leaves. That's my final answer.

Sounds reasonable, if by "value" you mean only some kind of label, and if by "leaf" you refer to a branch with one end free (i.e. a node with only one branch connected to it, a terminal node).

Yes except one such node is the root, the rest are leaves.

Actually, I misspoke. I should have said one such node *could* be the root. In fact, any node in a tree can be chosen as the root.

Not in the understanding of systematists. What you choose as a root is a new node, which can be anywhere along any branch.

It would be my hope that the root would have at least two branches connected to it.

Differences in terminology for the same thing between mathematics and systematics can be confusing,


I realized that the messages on this newsgroup form a nested hierarchy.

I would call it a non-nested hierarchy, since no message is part of another message. Both nested and non-nested hierarchies correspond to trees.

I was really only considering the ID's and group name as the message.

Even worse, since the ID of the child is not part of the ID of the parent; it's the other way around. A nested hierarchy can be made of sets of messages that are easily designated by looking at the message IDs, i.e. "all messages with 12345 as the first 5 digits".

Every message contains a unique ID and the newsgroup on which it was posted. It also contains a reference string. When a message starts a new thread, its reference string is null. Each time a message is posted in response to another message, the reference string of the new message is formed by appending the message ID of the previous message to the reference string of the previous message. Each message ID in the reference string is a characteristic or attribute. All messages in a subthread have reference strings that begin with the same substring. Because ID's are unique, none of the individual ID's in that substring appear anywhere outside that subthread. Obviously, a newsgroup reader is able to construct a tree from the nested hierarchy. The root is actually outside the display of the newsgroup messages in the newsreaders I am familiar with. I am not very familiar with nntp, but I am pretty sure that the readers use the information in the reference strings and the newsgroup field of the headers to construct the trees.

Makes sense to me. Note that this tree (I suppose you can call it a nested hierarchy if you really want to) arises from a process of descent with modification and branching. In this case the modification is purely additive and very simple.

Interestingly, this tree can't be represented by set notation.

I believe it can, sort of, though once again one can't distinguish an element present at an internal node from one present at a terminal node extending from that internal node. But I believe you may have hit upon a difference between nested and non-nested hierarchies. A nested hierarchy would seem to have elements only at terminal nodes, and can thus be represented in set notation, while a non-nested hierarchy has elements at terminal nodes, and can't. So you can turn the thread non-nested hierararchy into a nested one by adding a bunch of virtual terminal branches.

If the reference string and the ID of each message are considered as the characteristics of each message, the tree could be reconstructed from the leaves, however. All nodes that differ in just one characteristic are descended from a node that had just the characteristics that these nodes have in common.

I don't think so. You have to add the additional proviso that the difference must be terminal. If I had two messages 12345 and 22345, they wouldn't be close relatives even though they differ only in one characeristic.

Maybe that is cheating. By the definition you gave for a nested hierarchy, all the messages on the newsgroup really don't represent a nested hierarchy because they can't be represented as a set of groups, but the leaf messages do.

I agree. A thread isn't a nested hierarchy, but can be turned into one. It's a non-nested hierarchy.

.

Relevant Pages

  • Re: Co-optation Today
    ... a tree is nothing but nodes and arcs. ... I don't think a nested hierarchy can exist even in the abstract with no values. ... When a message starts a new thread, its reference string is null. ... A nested hierarchy would seem to have elements only at terminal nodes, and can thus be represented in set notation, while a non-nested hierarchy has elements at terminal nodes, and can't. ...
    (talk.origins)
  • Re: Yet again, human evolution: huh?
    ... >>>I'm still not entirely grasping the concept of the nested hierarchy. ... >>provide clues to the structure of that tree. ... > example, all humans are primates, but not all primates are humans; ... would it be so far fetched for an octopus to evolve a skull? ...
    (talk.origins)
  • Re: Yet again, human evolution: huh?
    ... >> I'm still not entirely grasping the concept of the nested hierarchy. ... none of the circles cross each ... > provide clues to the structure of that tree. ... example, all humans are primates, but not all primates are humans; ...
    (talk.origins)
  • Re: More proof you boons dont know what your on about.
    ... Or the amount of genes a life form has. ... Screamed spintwitty at the face in the mirror. ... A nested hierarchy is 'groups within groups'; your inexplained 'tree' ...
    (talk.origins)
  • Re: "Logic" trumps science?
    ... scales and fractals exhibit self-similarity across scales, ... in the way that the tree of life is. ... nor is it what makes the tree a nested hierarchy. ...
    (talk.origins)