Re: How is this collection called?

From: Mikito Harakiri <mikharakiri_at_iahu.com>
Date: Wed, 31 Mar 2004 10:29:07 -0800
Message-ID: <yfEac.29$rc5.108_at_news.oracle.com>


"Rick Decker" <rdecker_at_hamilton.edu> wrote in message news:406A2612.40402_at_hamilton.edu...
> You've already seen some examples. The problem is a
>
> bit under-specified, since one has to pick a structure
> and an aggregation operator, but I'd suggest the merge
> of two (binary? ordered?) trees, i.e., a * b is the
> tree formed by making a new node with a as the left
> child and b as the right child. Obviously none of
> the laws will be satisfied in general.
>
> We could even invent more laws, like the existence
> of an identity:
>
> There exists a (unique?) object 1 such that a * 1 = a
> and/or 1 * a = a
>
> (True for sets under union, true for bags under their "union",
>
> true for lists, true (in one direction) for Michael's stacks,
> and false for my tree example.)

Why adding empty element to a tree changes the tree? I would imagine that 1*a=a is true for binary labeled trees as well.

> Inverses are a bit trickier:
>
> For (all|all "nonzero") objects a, there is an object b
> such that a * b = 1 and/or b * a = 1 (for suitable "1").
>

x * a = b

or

a * x = b

might not necessarily have any solutions even though

x * a = 1

almost certainly doesn't have any solutions when we interpret '*' as aggregation operator. Indeed, what set do you suggest we aggregate with some nonempty set in order to get empty set?

> p^3.s. Binomial heaps?

What is the utility of min-heap ordering property? It doesn't seem to help navigating the tree when searching for an element... Received on Wed Mar 31 2004 - 20:29:07 CEST

Original text of this message