[Next][Prev] [Right] [Left] [Up] [Index] [Root]
Primes: SeqEnum Default: [32749, 32719, 32717]
Compute the rational growth function of the word acceptor automaton 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 xn
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.
Setting the Primes parameter allows the specification of
a list of primes over which the calculation of the rational
growth function is done.
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);
Running Knuth-Bendix with the following parameter values
MaxRelations = 200
MaxStates = 0
TidyInt = 20
MaxWdiffs = 512
HaltingFactor = 100
MinTime = 5
#System is confluent.
#Halting with 4 equations.
#First word-difference machine with 5 states computed.
#Second word-difference machine with 5 states computed.
#System is confluent, or halting factor condition holds.
#Word-acceptor with 4 states computed.
#General multiplier with 8 states computed.
#Validity test on general multiplier succeeded.
#General length-2 multiplier with 14 states computed.
#Checking inverse and short relations.
#Checking relation: _1^3 = _2^2
#Axiom checking succeeded.
> f := GrowthFunction(G);
#result modulo prime 32749:
transitions(1 + 2*x + 2*x^2)/(1);
#result modulo prime 32719: (as previous)
#result modulo prime 32717: (as previous)
Warning: The polynomials modulo the primes chosen were not
consistent.
so the integral coefficients output are unlikely to be correct.
> print R!f;
2*x^2 + 2*x + 1
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
