axiom-developer
[Top][All Lists]

[Axiom-developer] Re: FW: data structure vs. mathematical structure

 From: Ralf Hemmecke Subject: [Axiom-developer] Re: FW: data structure vs. mathematical structure Date: Thu, 16 Nov 2006 00:15:13 +0100 User-agent: Thunderbird 1.5.0.8 (X11/20061025)

The definition you gave is it: least fixed point of

X |-> 1 + T × X × X

Hmmm, good question. In Aldor-combinat (AC) we deal with combinatorial species. They encode actual structures. The corresponding generating series G(x) for binary trees given by your X above has to fulfil the equation

G(x) = 1 + x * G(x) * G(x)                                (+)

As a quadratic formula it has at most 2 solutions. And only one of those solution is a power series with only non-negative coefficients. Since I don't know what it should mean to say "there are -5 trees with 3 nodes", it is clear which solution I choose for the generating series.

Assuming that I understand a bit of the theory of species, then there is only *one* solution to

X = 1 + T * X * X.

We are not yet dealing with "virtual species" which would allow negative coefficients in the generating series.

The interesting bit about those inductive definition is that they come
with "fold" (reduce in Axiom-speak) for free.

Hmmm, lazyness is important here. Unfortunately the internal definition of formal power series in AC does not allow to write equation (+) as such. One first has to say (something like)

g: FormalPowerSeries Integer := new();
set!(g, 1+x*g*g);

where x corresponds to the inteterminate of "FormalPowerSeries Integer".

| Recently, Martin Rubey has done some work to make Aldor-combinat
| available for Axiom, but for the underlying compilation we still need
| the Aldor compiler. So, Gaby, I consider Aldor-combinat a testcase for
| the compiler-improvements branch. ;-)

OK, I don't feel it like a pressure :-) :-)

No. No pressure intended. It's just something to motivate you. ;-)

Ralf

reply via email to