| View previous topic :: View next topic |
| Author |
Message |
Tegiri Nenashi
Guest
|
 Posted: Wed Jul 30, 2008 10:24 pm Post subject: Two questions related to Boom hierarchy |
 |
|
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? |
|
| |
|
 Back to top |
Mike Burrell
Guest
|
| Posted: Fri Aug 01, 2008 7:02 am Post subject: Re: Two questions related to Boom hierarchy |
|
|
On 2008-07-30 18:24:25 -0400, Tegiri Nenashi <TegiriNenashi@gmail.com> said:
[quote]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?
[/quote]
Not that I>ve seen.
[quote]2. Why the "trees" (and, say, not DAGs)? How is this join operation on
trees is defined?
[/quote]
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 |
|
| |
|
| Back to top |
|
