[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[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 (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. ;-)


reply via email to

[Prev in Thread] Current Thread [Next in Thread]