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 01:39:08 +0100 User-agent: Thunderbird 1.5.0.8 (X11/20061025)

```On 11/16/2006 01:20 AM, Gabriel Dos Reis wrote:
```
```Ralf Hemmecke <address@hidden> writes:

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

I realize my sentence could be ambiguous:  I meant "least fixed point
in the category of continuous partial orders (CPO)."
```
```
```
Well, it seems you have to be even more precise. I still cannot understand that. You mean X, 1, T are continuous partial orders?
```And what does then + and × stand for?

```
```Aha! Good point.  Now, I just need you to point me to a good
introductory point on species.
```
```
The short one you find at

http://en.wikipedia.org/wiki/Combinatorial_species

```
and the book I currently like best is given as the second reference on the above page:
```
```
François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structures arborescentes, LaCIM, Montréal (1994). English version: Combinatorial Species and Tree-like Structures, Cambridge University Press (1998).
```
Ralf

```