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
```
```
```
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

```