  
  [1X9 Iterated monodromy groups[0X
  
  Iterated  monodromy  machines  are a special class of group FR machines (see
  Section  [14X3[0m)  with  attribute  [2XIMGRelator[0m  ([14X9.1-2[0m).  This attribute records a
  cyclic ordering of the generators of the machine whose product is trivial.
  
  The  interpretation  is  the  following: the machine encodes a [13XThurston map[0m,
  i.e.  a  post-critically  finite  topological  branched self-covering of the
  sphere S^2. Generators of the machine correspond to loops in the fundamental
  group  of  the  sphere (punctured at post-critical points), that circle once
  counter-clockwise  around  a  post-critical  point.  For more details on the
  connection between self-similar groups and Thurston maps, see [Nek05].
  
  IMG  FR elements are a bit different from group FR elements: while we said a
  group  FR  element  is  trivial  if  and  only if its action on sequences is
  trivial,  we  say  that  an  IMG  FR element g is trivial if there exists an
  integer  N  such  that  unfolding  N  times  the recursion for g yields only
  trivial states (as elements of the underlying free group).
  
  
  [1X9.1 Creators and operations for IMG FR machines[0X
  
  [1X9.1-1 IMGFRMachine[0m
  
  [2X> IMGFRMachine( [0X[3Xm[, w][0X[2X ) __________________________________________[0Xoperation
  [6XReturns:[0X  An IMG FR machine.
  
  This function creates a new IMG FR machine, starting from a group FR machine
  [3Xm[0m.  If a state [3Xw[0m is specified, it is used as IMG relator; otherwise, if some
  ordering  of  the  generators  is trivial, it is used as a relator; in other
  cases,  an additional generator is added to the machine in such a way that a
  product of generators is trivial.
  
  A  standard  FR  machine  can  be  recovered  from  an  IMG  FR  machine  by
  [2XAsGroupFRMachine[0m      ([14X3.3-4[0m),      [2XAsMonoidFRMachine[0m      ([14X3.3-4[0m),      and
  [2XAsSemigroupFRMachine[0m ([14X3.3-4[0m).
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X!!![0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.1-2 IMGRelator[0m
  
  [2X> IMGRelator( [0X[3Xm[0X[2X ) _________________________________________________[0Xattribute
  [6XReturns:[0X  The relator of the IMG FR machine.
  
  This attribute stores the product of generators that is trivial. In essence,
  it  records  an  ordering  of the generators whose product is trivial in the
  punctured sphere's fundamental group.
  
  [1X9.1-3 Mating[0m
  
  [2X> Mating( [0X[3Xm1, m2[, w1, w2][0X[2X ) ______________________________________[0Xoperation
  [6XReturns:[0X  An IMG FR machine.
  
  This  function  mates  two  IMG  FR machines. The arguments [3Xw1,w2[0m are IMG FR
  elements  that  represent  adding  elements;  they  may  be omitted if [3Xm1,m2[0m
  contain  pre-specified  adding machines (through the attribute [2XAddingElement[0m
  ([14X10.1-4[0m)). The elements [3Xw1[0m and [3Xw2[0m must satisfy the same recursion.
  
  The  mating  is  defined  as  follows:  one removes a disc around the adding
  machine  in  [3Xm1[0m and [3Xm2[0m; one applies complex conjugation to [3Xm2[0m; and one glues
  the hollowed spheres along their boundary circle.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X!!![0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.1-4 PolynomialFRMachine[0m
  
  [2X> PolynomialFRMachine( [0X[3Xd, per, pre[0X[2X ) ______________________________[0Xoperation
  [2X> PolynomialIMGMachine( [0X[3Xd, per, pre[0X[2X ) _____________________________[0Xoperation
  [2X> PolynomialMealyMachine( [0X[3Xd, per, pre[0X[2X ) ___________________________[0Xoperation
  [6XReturns:[0X  An IMG FR machine.
  
  This  function  creates  a  group,  IMG  or  Mealy  machine that describes a
  topological  polynomial.  The  polynomial  is  described symbolically in the
  language of [13Xexternal angles[0m. For more details, see [DH84] and [DH85] (in the
  quadratic  case),  [BFH92]  (in  the  preperiodic  case),  and [Poi] (in the
  general case).
  
  [3Xd[0m  is  the  degree  of  the  polynomial.  [3Xper[0m and [3Xpre[0m are lists of angles or
  preangles.  In  what follows, angles are rational numbers, considered modulo
  1.  Each entry in [3Xper[0m or [3Xpre[0m is either a rational (interpreted as an angle),
  or a list of angles [a_1,dots,a_i] such that da_1=dots=da_i.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> PolynomialIMGMachine(2,[0],[]); # the adding machine[0X
    [4X<FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2 ] )/[ f2*f1 ]>[0X
    [4Xgap> Display(last);[0X
    [4X G  |     1        2[0X
    [4X----+--------+--------+[0X
    [4X f1 | <id>,2     f1,1[0X
    [4X f2 |   f2,2   <id>,1[0X
    [4X----+--------+--------+[0X
    [4XRelator: f2*f1[0X
    [4Xgap> Display(PolynomialIMGMachine(2,[1/3],[])); # the Basilica[0X
    [4X G  |      1         2[0X
    [4X----+---------+---------+[0X
    [4X f1 | f1^-1,2   f2*f1,1[0X
    [4X f2 |    f1,1    <id>,2[0X
    [4X f3 |    f3,2    <id>,1[0X
    [4X----+---------+---------+[0X
    [4XRelator: f3*f2*f1[0X
    [4Xgap> Display(PolynomialIMGMachine(2,[],[1/6])); # z^2+I[0X
    [4X G  |            1         2[0X
    [4X----+---------------+---------+[0X
    [4X f1 | f1^-1*f2^-1,2   f2*f1,1[0X
    [4X f2 |          f1,1      f3,2[0X
    [4X f3 |          f2,1    <id>,2[0X
    [4X f4 |          f4,2    <id>,1[0X
    [4X----+---------------+---------+[0X
    [4XRelator: f4*f3*f2*f1[0X
    [4Xgap> PolynomialIMGMachine(3,[[0,1/3],[5/9,8/9]],[]);[0X
    [4X<FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2, f3 ] )/[ f3*f2*f1 ]>[0X
    [4Xgap> PolynomialIMGMachine(3,[[0,1/3]],[[5/9,8/9]]);[0X
    [4X<FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2, f3, f4 ] )/[ f4*f3*f2*f1 ]>[0X
  [4X------------------------------------------------------------------[0X
  
  The following construct the examples in Poirier's paper:
  
  [4X------------------------------------------------------------------[0X
    [4XPoirierExamples := function(arg)[0X
    [4X    if arg=[1] then[0X
    [4X        return PolynomialIMGMachine(2,[1/7],[]);[0X
    [4X    elif arg=[2] then[0X
    [4X        return PolynomialIMGMachine(2,[],[1/2]);[0X
    [4X    elif arg=[3,1] then[0X
    [4X        return PolynomialIMGMachine(2,[],[5/12]);[0X
    [4X    elif arg=[3,2] then[0X
    [4X        return PolynomialIMGMachine(2,[],[7/12]);[0X
    [4X    elif arg=[4,1] then[0X
    [4X        return PolynomialIMGMachine(3,[[3/4,1/12],[1/4,7/12]],[]);[0X
    [4X    elif arg=[4,2] then[0X
    [4X        return PolynomialIMGMachine(3,[[7/8,5/24],[5/8,7/24]],[]);[0X
    [4X    elif arg=[4,3] then[0X
    [4X        return PolynomialIMGMachine(3,[[1/8,19/24],[3/8,17/24]],[]);[0X
    [4X    elif arg=[5] then[0X
    [4X        return PolynomialIMGMachine(3,[[3/4,1/12],[3/8,17/24]],[]);[0X
    [4X    elif arg=[6,1] then[0X
    [4X        return PolynomialIMGMachine(4,[],[[1/4,3/4],[1/16,13/16],[5/16,9/16]]);[0X
    [4X    elif arg=[6,2] then[0X
    [4X        return PolynomialIMGMachine(4,[],[[1/4,3/4],[3/16,15/16],[7/16,11/16]]);[0X
    [4X    elif arg=[7] then[0X
    [4X        return PolynomialIMGMachine(5,[[0,4/5],[1/5,2/5,3/5]],[[1/5,4/5]]);[0X
    [4X    elif arg=[9,1] then[0X
    [4X        return PolynomialIMGMachine(3,[[0,1/3],[5/9,8/9]],[]);[0X
    [4X    elif arg=[9,2] then[0X
    [4X        return PolynomialIMGMachine(3,[[0,1/3]],[[5/9,8/9]]);[0X
    [4X    fi;[0X
    [4Xend;[0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.1-5 DBRationalIMGGroup[0m
  
  [2X> DBRationalIMGGroup( [0X[3Xsequence, or, rational, map[0X[2X ) ________________[0Xfunction
  [6XReturns:[0X  An IMG group from Dau's database.
  
  This function returns the iterated monodromy group from a database of groups
  associated  to  quadratic  rational maps. This database has been compiled by
  Dau Truong Tan [Tan02].
  
  When called with no arguments, this command returns the database contents in
  raw form.
  
  The  argments  can  be  a  sequence;  the  first  integer is the size of the
  postcritical  set,  the  second  argument  is  an index for the postcritical
  graph,  and  sometimes a third argument distinguishes between maps with same
  post-critical graph.
  
  If the argument is a rational map, the command returns the IMG group of that
  map,  assuming  its  [2XCanonicalQuadraticRational[0m  ([14X9.1-8[0m)  form exists in the
  database.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> DBRationalIMGGroup(z^2-1);[0X
    [4XIMG((z-1)^2)[0X
    [4Xgap> DBRationalIMGGroup(z^2+1); # not post-critically finite[0X
    [4Xfail[0X
    [4Xgap> DBRationalIMGGroup(4,1,1);[0X
    [4XIMG((z/h+1)^2|2h^3+2h^2+2h+1=0,h~-0.64)[0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.1-6 ValueRational[0m
  
  [2X> ValueRational( [0X[3Xf, x[0X[2X ) ____________________________________________[0Xfunction
  [6XReturns:[0X  The value of [3Xf[0m at [3Xx[0m.
  
  This  function  is almost identical to [10XValue(f,x)[0m. It accepts [9Xinfinity[0m as an
  argument, and may return [9Xinfinity[0m as a value.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> z := Indeterminate(Rationals,"z");;[0X
    [4Xgap> ValueRational(1/z,infinity);[0X
    [4X0[0X
    [4Xgap> ValueRational(1/z,0);[0X
    [4Xinfinity[0X
    [4Xgap> ValueRational(1/z,1/2);[0X
    [4X2[0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.1-7 CriticalValuesQuadraticRational[0m
  
  [2X> CriticalValuesQuadraticRational( [0X[3Xf[0X[2X ) _____________________________[0Xfunction
  [6XReturns:[0X  The critical values of [3Xf[0m.
  
  This  function  returns,  as  a  list,  the  values of [3Xf[0m at places where the
  derivative of [3Xf[0m vanishes.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> z := Indeterminate(Rationals,"z");;[0X
    [4Xgap> CriticalValuesQuadraticRational(z^2);[0X
    [4X[ 0, infinity ][0X
    [4Xgap> CriticalValuesQuadraticRational(z^2+1);[0X
    [4X[ 1, infinity ][0X
    [4Xgap> CriticalValuesQuadraticRational((z^2+1)/(z^2-1));[0X
    [4X[ -1, 1 ][0X
    [4Xgap> CriticalValuesQuadraticRational((z^2+1)/(z^2-z-1));[0X
    [4X[ 2/5*E(5)-2/5*E(5)^2-2/5*E(5)^3+2/5*E(5)^4, -2/5*E(5)+2/5*E(5)^2+2/5*E(5)^3-2/5*E(5)^4 ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.1-8 CanonicalQuadraticRational[0m
  
  [2X> CanonicalQuadraticRational( [0X[3Xf[0X[2X ) __________________________________[0Xfunction
  [6XReturns:[0X  The canonical forms of the quadratic rational map [3Xf[0m.
  
  This  function puts the quadratic rational map [3Xf[0m in canonical form, that is,
  in form ((az+b)/(cz+d))^2, such that its critical values are [9X0[0m and [9Xinfinity[0m.
  Furthermore, it attempts to make [10Xf(infinity)=1[0m, and if this is impossible to
  make [10Xf(0)=1[0m.
  
  The command returns the set of all maps with these properties.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> z := Indeterminate(Rationals,"z");;[0X
    [4Xgap> CanonicalQuadraticRational(z^2);[0X
    [4X[ z^2 ][0X
    [4Xgap> CanonicalQuadraticRational(z^2+1);[0X
    [4X[ (z^2)/(z^2+2*z+1), z^2+2*z+1 ][0X
    [4Xgap> CanonicalQuadraticRational((z^2+1)/(z^2-1));[0X
    [4X[ (1/2*z^2+z+1/2)/(1/2*z^2-z+1/2), (-1/2*z^2+z-1/2)/(-1/2*z^2-z-1/2) ][0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.1-9 PostCriticalMachine[0m
  
  [2X> PostCriticalMachine( [0X[3Xf[0X[2X ) _________________________________________[0Xfunction
  [6XReturns:[0X  The Mealy machine of [3Xf[0m's post-critical orbit.
  
  This  function  constructs  a  Mealy  machine  [10XP[0m  on the alphabet [10X[1][0m, which
  describes  the  post-critical set of [3Xf[0m. It is in fact an oriented graph with
  constant out-degree 1. It is most conveniently passed to [2XDraw[0m ([14X5.2-1[0m).
  
  The  attribute  [10XCorrespondence(P)[0m  is the list of values associated with the
  stateset of [10XP[0m.
  
  [4X---------------------------  Example  ----------------------------[0X
    [4Xgap> z := Indeterminate(Rationals,"z");;[0X
    [4Xgap> m := PostCriticalMachine(z^2);[0X
    [4X<Mealy machine on alphabet [ 1 ] with 2 states>[0X
    [4Xgap> Display(m);[0X
    [4X   |  1[0X
    [4X---+-----+[0X
    [4X a | a,1[0X
    [4X b | b,1[0X
    [4X---+-----+[0X
    [4Xgap> Correspondence(m);[0X
    [4X[ 0, infinity ][0X
    [4Xgap> m := PostCriticalMachine(z^2-1);; Display(m); Correspondence(m);[0X
    [4X   |  1[0X
    [4X---+-----+[0X
    [4X a | c,1[0X
    [4X b | b,1[0X
    [4X c | a,1[0X
    [4X---+-----+[0X
    [4X[ -1, infinity, 0 ][0X
  [4X------------------------------------------------------------------[0X
  
  
  [1X9.2 Spiders[0X
  
  [1X9.2-1 RationalFunction[0m
  
  [2X> RationalFunction( [0X[3Xm[0X[2X ) ___________________________________________[0Xoperation
  [6XReturns:[0X  A rational function.
  
  !!!
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X!!![0X
  [4X------------------------------------------------------------------[0X
  
  [1X9.2-2 IMGFRMachine[0m
  
  [2X> IMGFRMachine( [0X[3Xm[0X[2X ) _______________________________________________[0Xoperation
  [6XReturns:[0X  An IMG FR machine.
  
  !!!
  
  [4X---------------------------  Example  ----------------------------[0X
    [4X!!![0X
  [4X------------------------------------------------------------------[0X
  
