9 Iterated monodromy groups
  
  Iterated  monodromy  machines  are a special class of group FR machines (see
  Section  3)  with  attribute  IMGRelator  (9.1-2).  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 Thurston map,
  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).
  
  
  9.1 Creators and operations for IMG FR machines
  
  9.1-1 IMGFRMachine
  
  > IMGFRMachine( m[, w] ) __________________________________________operation
  Returns:  An IMG FR machine.
  
  This function creates a new IMG FR machine, starting from a group FR machine
  m.  If a state w 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
  AsGroupFRMachine      (3.3-4),      AsMonoidFRMachine      (3.3-4),      and
  AsSemigroupFRMachine (3.3-4).
  
  ---------------------------  Example  ----------------------------
    !!!
  ------------------------------------------------------------------
  
  9.1-2 IMGRelator
  
  > IMGRelator( m ) _________________________________________________attribute
  Returns:  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.
  
  9.1-3 Mating
  
  > Mating( m1, m2[, w1, w2] ) ______________________________________operation
  Returns:  An IMG FR machine.
  
  This  function  mates  two  IMG  FR machines. The arguments w1,w2 are IMG FR
  elements  that  represent  adding  elements;  they  may  be omitted if m1,m2
  contain  pre-specified  adding machines (through the attribute AddingElement
  (10.1-4)). The elements w1 and w2 must satisfy the same recursion.
  
  The  mating  is  defined  as  follows:  one removes a disc around the adding
  machine  in  m1 and m2; one applies complex conjugation to m2; and one glues
  the hollowed spheres along their boundary circle.
  
  ---------------------------  Example  ----------------------------
    !!!
  ------------------------------------------------------------------
  
  9.1-4 PolynomialFRMachine
  
  > PolynomialFRMachine( d, per, pre ) ______________________________operation
  > PolynomialIMGMachine( d, per, pre ) _____________________________operation
  > PolynomialMealyMachine( d, per, pre ) ___________________________operation
  Returns:  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 external angles. For more details, see [DH84] and [DH85] (in the
  quadratic  case),  [BFH92]  (in  the  preperiodic  case),  and [Poi] (in the
  general case).
  
  d  is  the  degree  of  the  polynomial.  per and pre are lists of angles or
  preangles.  In  what follows, angles are rational numbers, considered modulo
  1.  Each entry in per or pre 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.
  
  ---------------------------  Example  ----------------------------
    gap> PolynomialIMGMachine(2,[0],[]); # the adding machine
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2 ] )/[ f2*f1 ]>
    gap> Display(last);
     G  |     1        2
    ----+--------+--------+
     f1 | <id>,2     f1,1
     f2 |   f2,2   <id>,1
    ----+--------+--------+
    Relator: f2*f1
    gap> Display(PolynomialIMGMachine(2,[1/3],[])); # the Basilica
     G  |      1         2
    ----+---------+---------+
     f1 | f1^-1,2   f2*f1,1
     f2 |    f1,1    <id>,2
     f3 |    f3,2    <id>,1
    ----+---------+---------+
    Relator: f3*f2*f1
    gap> Display(PolynomialIMGMachine(2,[],[1/6])); # z^2+I
     G  |            1         2
    ----+---------------+---------+
     f1 | f1^-1*f2^-1,2   f2*f1,1
     f2 |          f1,1      f3,2
     f3 |          f2,1    <id>,2
     f4 |          f4,2    <id>,1
    ----+---------------+---------+
    Relator: f4*f3*f2*f1
    gap> PolynomialIMGMachine(3,[[0,1/3],[5/9,8/9]],[]);
    <FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2, f3 ] )/[ f3*f2*f1 ]>
    gap> PolynomialIMGMachine(3,[[0,1/3]],[[5/9,8/9]]);
    <FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2, f3, f4 ] )/[ f4*f3*f2*f1 ]>
  ------------------------------------------------------------------
  
  The following construct the examples in Poirier's paper:
  
  ------------------------------------------------------------------
    PoirierExamples := function(arg)
        if arg=[1] then
            return PolynomialIMGMachine(2,[1/7],[]);
        elif arg=[2] then
            return PolynomialIMGMachine(2,[],[1/2]);
        elif arg=[3,1] then
            return PolynomialIMGMachine(2,[],[5/12]);
        elif arg=[3,2] then
            return PolynomialIMGMachine(2,[],[7/12]);
        elif arg=[4,1] then
            return PolynomialIMGMachine(3,[[3/4,1/12],[1/4,7/12]],[]);
        elif arg=[4,2] then
            return PolynomialIMGMachine(3,[[7/8,5/24],[5/8,7/24]],[]);
        elif arg=[4,3] then
            return PolynomialIMGMachine(3,[[1/8,19/24],[3/8,17/24]],[]);
        elif arg=[5] then
            return PolynomialIMGMachine(3,[[3/4,1/12],[3/8,17/24]],[]);
        elif arg=[6,1] then
            return PolynomialIMGMachine(4,[],[[1/4,3/4],[1/16,13/16],[5/16,9/16]]);
        elif arg=[6,2] then
            return PolynomialIMGMachine(4,[],[[1/4,3/4],[3/16,15/16],[7/16,11/16]]);
        elif arg=[7] then
            return PolynomialIMGMachine(5,[[0,4/5],[1/5,2/5,3/5]],[[1/5,4/5]]);
        elif arg=[9,1] then
            return PolynomialIMGMachine(3,[[0,1/3],[5/9,8/9]],[]);
        elif arg=[9,2] then
            return PolynomialIMGMachine(3,[[0,1/3]],[[5/9,8/9]]);
        fi;
    end;
  ------------------------------------------------------------------
  
  9.1-5 DBRationalIMGGroup
  
  > DBRationalIMGGroup( sequence, or, rational, map ) ________________function
  Returns:  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  CanonicalQuadraticRational  (9.1-8)  form exists in the
  database.
  
  ---------------------------  Example  ----------------------------
    gap> DBRationalIMGGroup(z^2-1);
    IMG((z-1)^2)
    gap> DBRationalIMGGroup(z^2+1); # not post-critically finite
    fail
    gap> DBRationalIMGGroup(4,1,1);
    IMG((z/h+1)^2|2h^3+2h^2+2h+1=0,h~-0.64)
  ------------------------------------------------------------------
  
  9.1-6 ValueRational
  
  > ValueRational( f, x ) ____________________________________________function
  Returns:  The value of f at x.
  
  This  function  is almost identical to Value(f,x). It accepts infinity as an
  argument, and may return infinity as a value.
  
  ---------------------------  Example  ----------------------------
    gap> z := Indeterminate(Rationals,"z");;
    gap> ValueRational(1/z,infinity);
    0
    gap> ValueRational(1/z,0);
    infinity
    gap> ValueRational(1/z,1/2);
    2
  ------------------------------------------------------------------
  
  9.1-7 CriticalValuesQuadraticRational
  
  > CriticalValuesQuadraticRational( f ) _____________________________function
  Returns:  The critical values of f.
  
  This  function  returns,  as  a  list,  the  values of f at places where the
  derivative of f vanishes.
  
  ---------------------------  Example  ----------------------------
    gap> z := Indeterminate(Rationals,"z");;
    gap> CriticalValuesQuadraticRational(z^2);
    [ 0, infinity ]
    gap> CriticalValuesQuadraticRational(z^2+1);
    [ 1, infinity ]
    gap> CriticalValuesQuadraticRational((z^2+1)/(z^2-1));
    [ -1, 1 ]
    gap> CriticalValuesQuadraticRational((z^2+1)/(z^2-z-1));
    [ 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 ]
  ------------------------------------------------------------------
  
  9.1-8 CanonicalQuadraticRational
  
  > CanonicalQuadraticRational( f ) __________________________________function
  Returns:  The canonical forms of the quadratic rational map f.
  
  This  function puts the quadratic rational map f in canonical form, that is,
  in form ((az+b)/(cz+d))^2, such that its critical values are 0 and infinity.
  Furthermore, it attempts to make f(infinity)=1, and if this is impossible to
  make f(0)=1.
  
  The command returns the set of all maps with these properties.
  
  ---------------------------  Example  ----------------------------
    gap> z := Indeterminate(Rationals,"z");;
    gap> CanonicalQuadraticRational(z^2);
    [ z^2 ]
    gap> CanonicalQuadraticRational(z^2+1);
    [ (z^2)/(z^2+2*z+1), z^2+2*z+1 ]
    gap> CanonicalQuadraticRational((z^2+1)/(z^2-1));
    [ (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) ]
  ------------------------------------------------------------------
  
  9.1-9 PostCriticalMachine
  
  > PostCriticalMachine( f ) _________________________________________function
  Returns:  The Mealy machine of f's post-critical orbit.
  
  This  function  constructs  a  Mealy  machine  P  on the alphabet [1], which
  describes  the  post-critical set of f. It is in fact an oriented graph with
  constant out-degree 1. It is most conveniently passed to Draw (5.2-1).
  
  The  attribute  Correspondence(P)  is the list of values associated with the
  stateset of P.
  
  ---------------------------  Example  ----------------------------
    gap> z := Indeterminate(Rationals,"z");;
    gap> m := PostCriticalMachine(z^2);
    <Mealy machine on alphabet [ 1 ] with 2 states>
    gap> Display(m);
       |  1
    ---+-----+
     a | a,1
     b | b,1
    ---+-----+
    gap> Correspondence(m);
    [ 0, infinity ]
    gap> m := PostCriticalMachine(z^2-1);; Display(m); Correspondence(m);
       |  1
    ---+-----+
     a | c,1
     b | b,1
     c | a,1
    ---+-----+
    [ -1, infinity, 0 ]
  ------------------------------------------------------------------
  
  
  9.2 Spiders
  
  9.2-1 RationalFunction
  
  > RationalFunction( m ) ___________________________________________operation
  Returns:  A rational function.
  
  !!!
  
  ---------------------------  Example  ----------------------------
    !!!
  ------------------------------------------------------------------
  
  9.2-2 IMGFRMachine
  
  > IMGFRMachine( m ) _______________________________________________operation
  Returns:  An IMG FR machine.
  
  !!!
  
  ---------------------------  Example  ----------------------------
    !!!
  ------------------------------------------------------------------