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?

On 2008-07-30 18:24:25 -0400, Tegiri Nenashi gmail.com> said:

Not that I've seen.

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

On Jul 31, 7:37 pm, Mike Burrell wrote:

In article a6g2000prm.googlegroups.com>,
Tegiri Nenashi gmail.com> wrote:

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.

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

On Aug 4, 9:06 am, George Neuner comcast.net> 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).

On Aug 4, 7:26 am, tc...@lsa.umich.edu wrote:

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.

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

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

George Neuner wrote:

[...]

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

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