
From:  Ralf Hemmecke 
Subject:  [Axiomdeveloper] Re: FW: data structure vs. mathematical structure 
Date:  Thu, 16 Nov 2006 00:15:13 +0100 
Useragent:  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 Aldorcombinat (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 nonnegative 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 Axiomspeak) 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 Aldorcombinat  available for Axiom, but for the underlying compilation we still need  the Aldor compiler. So, Gaby, I consider Aldorcombinat a testcase for  the compilerimprovements branch. ;)
OK, I don't feel it like a pressure :) :)
No. No pressure intended. It's just something to motivate you. ;) Ralf
[Prev in Thread]  Current Thread  [Next in Thread] 