[Next][Prev] [Right] [Left] [Up] [Index] [Root] 
Accessing Automata





GrowthFunction(G) : GrpAtc -> FldFunRatElt



Compute the rational growth function of one of the four automata associated 
with G. The rational growth function of an automaton A is the quotient of 
two integral polynomials in a single variable x. The coefficient of x^n 
in the Taylor expansion of this quotient is equal to the number of accepted
words of A of length n.
To avoid the danger of integer overflow, the calculations are not done
over the integers, but modulo a sequence of primes. If, on lifting to the
integers, different primes give different results, then the coefficients of
the polynomials are too large, and the results are likely to be wrong.
A warning message is printed when this happens.
The code for this program was written by Laurent Bartholdi.







     Machine: MonStgElt                  Default: "Acc"




Setting the Machine parameter controls which of the four automata 
associated with G will have its rational growth function computed. Setting
Machine := "Diff1", "Diff2", "Acc", or "Mult"
means we compute the rational growth function of the first word difference 
automaton, the second word difference automaton, the word acceptor.
or the word multiplier, respectively.





     Primes: SeqEnum                     Default: [32749, 32719, 32717]




Specify a list of primes over which the calculation of the rational
growth function is done.





Example GrpAtc_GrowthFunction (H31E8)

We construct a cyclic group of order 5 and compute the
rational growth function of its word acceptor.
Note here that the R!f is
only necessary to get pretty printing, specifically to ensure that
f is printed in the variable x.





> R<x> := RationalFunctionField(Integers());
> FG<a> := FreeGroup(1);
> Q := quo< FG | a^5=1>;
> G := AutomaticGroup(Q);
> f := GrowthFunction(G: Machine := "Acc");
> print R!f;
2*x^2 + 2*x + 1





 [Next][Prev] [Right] [Left] [Up] [Index] [Root]