Two questions related to Boom hierarchy

#1 07-30-2008, 06:24 PM

Boom hierarchy is an observation that familiar algorithmic data
structures organize into a linear order

trees - lists - bags - sets

by progressively enforcing associativity, symmetry, and idempotence.

Questions:
1. Clearly boolean algebra of sets has more structure than just
associativity, symmetry, and idempotence. It has additional arguably
as important operators. Any research references?

2. Why the "trees" (and, say, not DAGs)? How is this join operation on
trees is defined?

#2 07-31-2008, 10:37 PM

On 2008-07-30 18:24:25 -0400, Tegiri Nenashi <TegiriNenashi@gmail.com> said:
> 1. Clearly boolean algebra of sets has more structure than just
> associativity, symmetry, and idempotence. It has additional arguably
> as important operators. Any research references?

Not that I've seen.

> 2. Why the "trees" (and, say, not DAGs)? How is this join operation on
> trees is defined?

If you take out side-effects, the differences between a tree and a DAG
are sometimes not very interesting. Anything you can do with a tree,
you can do with a DAG, and vice versa. The join operation essentially
composes a node out of two subtrees. Maybe the subtrees won't be
distinct (in which case you have a DAG), but the elements in your data
structure are the same in both cases, which is what matters.

Mike

#3 08-01-2008, 07:45 PM

On Jul 31, 7:37 pm, Mike Burrell <mbur...@SPAM.uwo.ca> wrote:
> On 2008-07-30 18:24:25 -0400, Tegiri Nenashi <TegiriNena...@gmail.com> said:
>
> > 1. Clearly boolean algebra of sets has more structure than just
> > associativity, symmetry, and idempotence. It has additional arguably
> > as important operators. Any research references?
>
> Not that I've seen.
>
> > 2. Why the "trees" (and, say, not DAGs)? How is this join operation on
> > trees is defined?
>
> If you take out side-effects, the differences between a tree and a DAG
> are sometimes not very interesting. Anything you can do with a tree,
> you can do with a DAG, and vice versa. The join operation essentially
> composes a node out of two subtrees. Maybe the subtrees won't be
> distinct (in which case you have a DAG), but the elements in your data
> structure are the same in both cases, which is what matters.
>
> Mike

Somehow I missed adjective "binary" and was thinking in terms of join
being not well defined operation for arbitrary trees. One more source
of the confusion is the labeling of the tree. Consider sets, bags, and
lists. They have all the elements labeled. Yet, for binary trees in
Boom hierarchy we label leaves only. In my experience I never
encountered trees where only leaves are labeled, which makes me to
conclude that they are not very natural structures.

#4 08-04-2008, 10:26 AM

In article <f8636af4-a35a-4a11-9ecc-7c97bad8b2ee@a6g2000prm.googlegroups.com>,
Tegiri Nenashi <TegiriNenashi@gmail.com> wrote:
>1. Clearly boolean algebra of sets has more structure than just
>associativity, symmetry, and idempotence. It has additional arguably
>as important operators. Any research references?

Well, lattice theorists and ring theorists have their own ways of thinking
about Boolean algebras. See for example

http://en.wikipedia.org/wiki/Boolean_algebra_(structure)
http://en.wikipedia.org/wiki/Boolean_ring

It's not clear that any of this is relevant to your concerns, though.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

#5 08-04-2008, 12:06 PM

On Fri, 1 Aug 2008 16:45:13 -0700 (PDT), Tegiri Nenashi
<TegiriNenashi@gmail.com> wrote:

>On Jul 31, 7:37 pm, Mike Burrell <mbur...@SPAM.uwo.ca> wrote:
>> On 2008-07-30 18:24:25 -0400, Tegiri Nenashi <TegiriNena...@gmail.com> said:
>>
>> > 1. Clearly boolean algebra of sets has more structure than just
>> > associativity, symmetry, and idempotence. It has additional arguably
>> > as important operators. Any research references?
>>
>> Not that I've seen.
>>
>> > 2. Why the "trees" (and, say, not DAGs)? How is this join operation on
>> > trees is defined?
>>
>> If you take out side-effects, the differences between a tree and a DAG
>> are sometimes not very interesting. Anything you can do with a tree,
>> you can do with a DAG, and vice versa. The join operation essentially
>> composes a node out of two subtrees. Maybe the subtrees won't be
>> distinct (in which case you have a DAG), but the elements in your data
>> structure are the same in both cases, which is what matters.
>>
>> Mike
>
>Somehow I missed adjective "binary" and was thinking in terms of join
>being not well defined operation for arbitrary trees. One more source
>of the confusion is the labeling of the tree. Consider sets, bags, and
>lists. They have all the elements labeled. Yet, for binary trees in
>Boom hierarchy we label leaves only. In my experience I never
>encountered trees where only leaves are labeled, which makes me to
>conclude that they are not very natural structures.

It depends on what you mean by "labeled". The canonical form of the
tree puts data only in the leaves and search keys only in the internal
nodes. In practice, many forms of trees store both keys and data in
the internal nodes (sometimes key and data are identical), but that is
an optimization of the canon form to reduce space and reduce time for
the average search.

George

#6 08-04-2008, 02:00 PM

On Aug 4, 9:06*am, George Neuner <gneun...@comcast.net> wrote:
> The canonical form of the
> tree puts data only in the leaves and search keys only in the internal
> nodes. *

Is there such thing as "canonical form" of the tree? I fail to notice
trees being defined anywhere as mathematical structures. Aren't they
pure ad-hock CS invention (unlike graphs, which are pretty much
established math subject with dozen of textbooks devoted to the topic).

#7 08-04-2008, 02:07 PM

On Aug 4, 7:26*am, tc...@lsa.umich.edu wrote:
> In article <f8636af4-a35a-4a11-9ecc-7c97bad8b...@a6g2000prm.googlegroups.com>,
> Tegiri Nenashi *<TegiriNena...@gmail.com> wrote:
>
> >1. Clearly boolean algebra of sets has more structure than just
> >associativity, symmetry, and idempotence. It has additional arguably
> >as important operators. Any research references?
>
> Well, lattice theorists and ring theorists have their own ways of thinking
> about Boolean algebras. *See for example
>
> *http://en.wikipedia.org/wiki/Boolean_algebra_(structure)
> *http://en.wikipedia.org/wiki/Boolean_ring
>
> It's not clear that any of this is relevant to your concerns, though.

I'm aware of the ring perspective, thank you. This is direction
towards Kleene algebras, idempotent semirings, etc. It is indeed
speculative if there is any connection with Boom hierarchy.

#8 08-05-2008, 11:04 AM

On Mon, 4 Aug 2008 11:00:46 -0700 (PDT), Tegiri Nenashi
<TegiriNenashi@gmail.com> wrote:

>On Aug 4, 9:06*am, George Neuner <gneun...@comcast.net> wrote:
>> The canonical form of the
>> tree puts data only in the leaves and search keys only in the internal
>> nodes. *
>
>Is there such thing as "canonical form" of the tree? I fail to notice
>trees being defined anywhere as mathematical structures. Aren't they
>pure ad-hock CS invention (unlike graphs, which are pretty much
>established math subject with dozen of textbooks devoted to the topic).

Mathematically a tree is a graph. see
http://mathworld.wolfram.com/Tree.html

The form most often seen in computing is the rooted tree, but other
forms are also used. The canon form of the rooted tree was, I think,
just a CS invention to facilitate studying properties of the
structure. Offhand I don't have a reference for who first described
it, but it is found in virtually every elementary data structure text.

George

#9 08-11-2008, 05:26 AM

George Neuner wrote:

>On Mon, 4 Aug 2008 11:00:46 -0700 (PDT), Tegiri Nenashi
><TegiriNenashi@gmail.com> wrote:

[...]

>>Is there such thing as "canonical form" of the tree? I fail to notice
>>trees being defined anywhere as mathematical structures. Aren't they
>>pure ad-hock CS invention (unlike graphs, which are pretty much
>>established math subject with dozen of textbooks devoted to the topic).
>
>Mathematically a tree is a graph. see
>http://mathworld.wolfram.com/Tree.html
>
>The form most often seen in computing is the rooted tree, but other
>forms are also used.

I think in CS a tree is always rooted, unless we're specifically
discussing them in the context of undirected graphs.

>The canon form of the rooted tree was, I think,
>just a CS invention to facilitate studying properties of the
>structure. Offhand I don't have a reference for who first described
>it, but it is found in virtually every elementary data structure text.

Pretty much all trees in CS have another property: the children of
nodes are ordered. (Adjacent nodes in graphs are not.)
The term "tree" must have been used at least as far back as
the parse tree, which entered CS in the 1950s or earlier,
and also has this property.

>George

--
Reinier Post

#10 08-11-2008, 01:50 PM

On Mon, 11 Aug 2008 09:26:53 +0000 (UTC), rpost@PCWIN607.campus.tue.nl
(rpost) wrote:

>George Neuner wrote:
>
>>On Mon, 4 Aug 2008 11:00:46 -0700 (PDT), Tegiri Nenashi
>><TegiriNenashi@gmail.com> wrote:
>
>[...]
>
>>>Is there such thing as "canonical form" of the tree? I fail to notice
>>>trees being defined anywhere as mathematical structures. Aren't they
>>>pure ad-hock CS invention (unlike graphs, which are pretty much
>>>established math subject with dozen of textbooks devoted to the topic).
>>
>>Mathematically a tree is a graph. see
>>http://mathworld.wolfram.com/Tree.html
>>
>>The form most often seen in computing is the rooted tree, but other
>>forms are also used.
>
>I think in CS a tree is always rooted, unless we're specifically
>discussing them in the context of undirected graphs.

Yes, as a practical matter, there must always be at least one root to
access the tree.

>>The canon form of the rooted tree was, I think,
>>just a CS invention to facilitate studying properties of the
>>structure. Offhand I don't have a reference for who first described
>>it, but it is found in virtually every elementary data structure text.
>
>Pretty much all trees in CS have another property: the children of
>nodes are ordered. (Adjacent nodes in graphs are not.)

Almost all. Spanning trees are an oddity though in that they have
multiple roots and the nodes are (theoretically at least) considered
to be unordered. As a practical matter, it's the shape of the tree
that's important - the nodes themselves are irrelevant.

George

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode