Re: Bags vs. Sets

Date: 28 Jun 2006 14:10:33 -0700

vc wrote:
> > vc wrote:
> > > That does not look right. Take different values for 'y'.
> >
> > OK, let's add a tuple {(x=2,y=2)} so that the relation becomes
>
> No, let's just consider {(1,2), (3,4)}. You'd see that there would be
> 4 defining equations instead if just two as was in the case of {(1,1),
> (2,1)}.

There are 4 equations indeed

```(x-1)(x-3)=0
(x-1)(y-4)=0
(y-2)(x-3)=0
(y-2)(y-4)=0

```

However, take your favorite computer algebra system, compute Groebner basis, and withness that the system reduces to just 2 equations:

(y-2)(y-4)=0
x-y+1=0

It is easy to see that we need only 2 equations. One defines domain y in {2,4}. The other one is linear interpolation polynome y=x+1. There would be 2 equations for any binary relation which has functional dependency!

> My point is that you want to explain to those interested how
> you recover polynoms from the variety and what computational complexity
> it would entail, not just say "Can we write those equations explicitly?
> Sure".

It could be constructed by adding tuples one by one like in the example in my previous message. It might be beneficial to apply Buchberger algorithm at each step in order to collapse the system.

I haven't research complexity issues. Buchberger algorithm is known to be theoretically non-efficient, while it has good behaviour on practice.

> > > For example, what field did you have
> > > in mind when you talked about polynomials ?
> >
> > C ? This matter doesn't seem important to me.
>
> Then, how do you intend to handle non-numeric domains like strings of
> characters, or user defined finite domains ?

I expected this question:-) Map them to numbers somehow? Received on Wed Jun 28 2006 - 23:10:33 CEST

Original text of this message