3 Functionally recursive machines
  
  At  the  core  of  this  package  are  functionally  recursive machines. The
  internals  of  machine  will  be  described later, but each machine M has an
  associated  alphabet X, a set of states Q, and a transition function phi:Q x
  X  ->  X x Q. An element, as we will see in Section 4, is given by a machine
  and an initial state qin Q.
  
  The element (M,q) defines a transformation on the set X^* of strings (finite
  or  infinite)  over  the  alphabet X, as follows: the empty string is always
  fixed.  Given a string x_1x_2dots x_n with nge0, compute phi(q,x_1)=(y_1,r);
  then  compute  the  action  of (M,r) on the string x_2dots x_n, and call the
  result  y_2dots  y_n.  Then  the  action  of  (M,q) on x_1x_2dots x_n yields
  y_1y_2dots y_n.
  
  This can be understood more formally as follows. The transition function phi
  induces  a map phi^n:Qx X^n -> X^n x Q, defined by successively applying phi
  to  move the Q from the left to the right. Similarly, phi can be extended to
  a map Q^mx X^n -> X^n x Q^m.
  
  We  see  that  the action on finite strings preserves their length, and also
  preserves  prefixes:  if  (M,q)  maps  x_1dots  x_n  to  y_1dots  y_m,  then
  necessarily m=n; and if k<n then T maps x_1dots x_k to y_1dots y_k.
  
  The  strings  over  the  alphabet X can be naturally organised into a rooted
  tree.  The root represents the empty string, and the strings x_1dots x_n and
  x_1dots x_n+1 are connected by an edge, for all x_iin X.
  
  
  3.1 Types of machines
  
  Machines  must  be  accessible to computation; therefore it is reasonable to
  assume that their alphabet X is finite.
  
  If the stateset Q is also finite, the machine is called a Mealy machine, and
  its transition function phi can be stored as a table.
  
  More general machines are obtained if one allows the stateset Q to be a free
  group/semigroup/monoid  generated  by  a  finite  set  S, and the transition
  function phi to be specified on Sx X. Its values are then extended naturally
  by composition.
  
  Machines  store  their  transitions  (second  coordinate  of phi), and their
  output,  (first  coordinate of phi) in a matrix indexed by state and letter.
  In particular, PermList(output[state]) gives the action on the first level.
  
  Because   of  the  way  GAP  handles  permutations  and  transformations,  a
  permutation  is never equal to a transformation, even though both can answer
  true  to IsOne. Therefore, FR introduces a new type of transformation, which
  can  be  equal  to  a  permutation,  and  which is actually represented as a
  permutation  is it is invertible. Like permutations, the new transformations
  do not have a fixed degree. They are created by Trans(list).
  
  
  3.2 Products of machines
  
  Machines  can  be  combined in different manners. If two machines act on the
  same  alphabet,  then  their  sum and product are defined as machines acting
  again  on  the  same alphabet; the statesets are the free products (which is
  also  their sum, in the category of semigroups) of the respective statesets.
  The  sum or product of machines has a stateset of highest possible category,
  i.e.  is  a group unless some argument is a monoid, and a monoid unless some
  argument  is  a semigroup. The transition and output functions are the union
  of the respective functions of their arguments.
  
  If  a non-empty collection of machines have same stateset, then their tensor
  sum  and tensor product are machines again with same stateset; the alphabets
  on  which  the  machines  act are the disjoint union, respectively cartesian
  product,  of  the  arguments' alphabets. The transition and output functions
  are  again  the  union  or  composition of the respective functions of their
  arguments.
  
  The  direct  sum  and  direct product of a collection of machines are always
  defined. Its stateset is generated by the union of the arguments' statesets,
  as  for a sum or a product; its alphabet is the disjoint union, respectively
  cartesian  product  of  its  arguments'  alphabets,  as  for a tensor sum or
  product.  The  transition  and  output  functions are again the union of the
  respective functions of their arguments.
  
  
  3.3 Creators for FRMachines
  
  3.3-1 FRMachineNC
  
  > FRMachineNC( fam, free, transitions, outputs ) __________________operation
  Returns:  A new FR machine.
  
  This  function  constructs a new FR machine, belonging to family fam. It has
  stateset  the free group/semigroup/monoid free, and transitions described by
  states and outputs.
  
  transitions  is  a list of lists; transitions[s][x] is a word in free, which
  is the state reached by the machine when started in state s and fed input x.
  
  outputs is also a list of lists; outputs[s][x] is the output produced by the
  machine is in state s and inputs x.
  
  ---------------------------  Example  ----------------------------
    gap> f := FreeGroup(2);
    <free group on the generators [ f1, f2 ]>
    gap> m := FRMachineNC(FRMFamily([1,2]),f,[[One(f),f.1],[One(f),f.2^-1]],
                          [[2,1],[1,2]]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2 ] )>
  ------------------------------------------------------------------
  
  3.3-2 FRMachine
  
  > FRMachine( [names, ]transitions, outputs ) ______________________operation
  > FRMachine( free, transitions, outputs ) _________________________operation
  Returns:  A new FR machine.
  
  This  function  constructs  a  new  FR  machine.  It  has  stateset  a  free
  group/semigroup/monoid, and structure described by transitions and outputs.
  
  If  there  is  an argument free, it is the free group/monoid/semigroup to be
  used  as  stateset.  Otherwise,  the  stateset  will  be  guessed  from  the
  transitions  and  outputs;  it  will  be  a  free  group  if  all states are
  invertible,  and a monoid otherwise. names is then an optional list, with at
  position  s  a  string naming generator s of the stateset. If names contains
  too few entries, they are completed by the names __1,__2,....
  
  transitions  is  a list of lists; transitions[s][x] is either an associative
  word, or a list of integers describing the state reached by the machine when
  started  in  state s and fed input x. Positive integers indicate a generator
  index,  negative integers its inverse, the empty list in the identity state,
  and  lists  of  length  greater than one indicate a product of states. If an
  entry  is  an  FR  element,  then its machine is incorporated into the newly
  constructed one.
  
  outputs   is   a   list;   at  position  s  it  contains  a  permutation,  a
  transformation,  or  a  list  of  integers (the images of a transformation),
  describing  the  activity  of  state  s.  If  all states are invertible, the
  outputs   are   all   converted   to  permutations,  while  if  there  is  a
  non-invertible state then the outputs are all converted to transformations.
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ tau, mu ] )>
    gap> m=n;
    true
    gap> Display(n);
         |     1         2
    -----+--------+---------+
     tau | <id>,2     tau,1
      mu | <id>,2   mu^-1,1
    -----+--------+---------+
    gap> m := FRMachine([[[],[FRElement(n,1)]]],[()]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2, f3 ] )>
    gap> Display(m);
        |     1         2
    ----+--------+---------+
     f1 | <id>,1      f2,2
     f2 | <id>,2      f2,1
     f3 | <id>,2   f1^-1,1
    ----+--------+---------+
    gap> f := FreeGroup(2);
    <free group on the generators [ f1, f2 ]>
    gap> p := FRMachine(f,[[One(f),f.1],[One(f),f.2^-1],[(1,2),(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1, f2 ] )>
    gap> n=p;
    true
  ------------------------------------------------------------------
  
  3.3-3 UnderlyingFRMachine
  
  > UnderlyingFRMachine( obj ) ______________________________________attribute
  Returns:  An FR machine underlying obj.
  
  FR  elements,  FR  groups etc. often have an underlying FR machine, which is
  returned by this command.
  
  ---------------------------  Example  ----------------------------
    gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ a, b ] )>
    gap> a := FRElement(m,1); b := FRElement(m,2);
    <2|a>
    <2|b>
    gap> UnderlyingFRMachine(a)=m;
    true
  ------------------------------------------------------------------
  
  3.3-4 AsGroupFRMachine
  
  > AsGroupFRMachine( m ) ___________________________________________attribute
  > AsMonoidFRMachine( m ) __________________________________________attribute
  > AsSemigroupFRMachine( m ) _______________________________________attribute
  Returns:  An FR machine isomorphic to m, on a free group.
  
  This  function constructs, from the FR machine m, an isomorphic FR machine n
  with    a   free   group/monoid/semigroup   as   stateset.   The   attribute
  Correspondence(n) is a mapping (homomorphism or list) from the stateset of m
  to the stateset of n.
  
  ---------------------------  Example  ----------------------------
    gap> s := FreeSemigroup(1);;
    gap> sm := FRMachine(s,[[GeneratorsOfSemigroup(s)[1],
                             GeneratorsOfSemigroup(s)[1]^2]],[(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s1 ] )>
    gap> m := FreeMonoid(1);;
    gap> mm := FRMachine(m,[[One(m),GeneratorsOfMonoid(m)[1]^2]],[(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m1 ], ... )>
    gap> g := FreeGroup(1);;
    gap> gm := FRMachine(g,[[One(g),GeneratorsOfGroup(g)[1]^-2]],[(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
    gap> AsGroupFRMachine(sm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
        |   1        2
    ----+------+--------+
     f1 | f1,2   f1^2,1
    ----+------+--------+
    gap> Correspondence(last);
    MappingByFunction( <free semigroup on the generators
    [ s1 ]>, <free group on the generators [ f1 ]>, function( w ) ... end )
    gap> AsGroupFRMachine(mm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
        |     1        2
    ----+--------+--------+
     f1 | <id>,2   f1^2,1
    ----+--------+--------+
    gap> AsGroupFRMachine(gm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
        |     1         2
    ----+--------+---------+
     f1 | <id>,2   f1^-2,1
    ----+--------+---------+
    gap> AsMonoidFRMachine(sm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m1 ], ... )>
        |   1        2
    ----+------+--------+
     m1 | m1,2   m1^2,1
      ----+------+--------+
    gap> AsMonoidFRMachine(mm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m1 ], ... )>
        |     1        2
    ----+--------+--------+
     m1 | <id>,2   m1^2,1
    ----+--------+--------+
    gap> AsMonoidFRMachine(gm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m1, m2 ], ... )>
        |     1        2
    ----+--------+--------+
     m1 | <id>,2   m2^2,1
     m2 | m1^2,2   <id>,1
    ----+--------+--------+
    gap> AsSemigroupFRMachine(sm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s1 ] )>
        |   1        2
    ----+------+--------+
     s1 | s1,2   s1^2,1
    ----+------+--------+
    gap> AsSemigroupFRMachine(mm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s1, s2 ] )>
        |   1        2
    ----+------+--------+
     s1 | s2,2   s1^2,1
     s2 | s2,1     s2,2
    ----+------+--------+
    gap> AsSemigroupFRMachine(gm); Display(last);
    <FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s1, s2, s3 ] )>
        |     1        2
    ----+--------+--------+
     s1 |   s3,2   s2^2,1
     s2 | s1^2,2     s3,1
     s3 |   s3,1     s3,2
    ----+--------+--------+
    gap>
    gap> Display(GuptaSidkiMachines(3));
       |  1     2     3
    ---+-----+-----+-----+
     a | a,1   a,2   a,3
     b | a,2   a,3   a,1
     c | a,3   a,1   a,2
     d | b,1   c,2   d,3
    ---+-----+-----+-----+
    gap> AsGroupFRMachine(GuptaSidkiMachines(3));
    <FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2 ] )>
    gap> Display(last);
        |     1         2        3
    ----+--------+---------+--------+
     f1 | <id>,2    <id>,3   <id>,1
     f2 |   f1,1   f1^-1,2     f2,3
    ----+--------+---------+--------+
    gap> Correspondence(last);
    [ <identity ...>, f1, f1^-1, f2 ]
  ------------------------------------------------------------------
  
  3.3-5 ChangeFRMachineBasis
  
  > ChangeFRMachineBasis( m[, l] ) __________________________________attribute
  Returns:  An equivalent FR machine, in a new basis.
  
  This  function constructs a new group FR machine, given a group FR machine m
  and a list of states l (as elements of the free object StateSet(m)).
  
  The  new  machine  has  the  following  transitions: if alphabet letter a is
  mapped to b by state s in m, leading to state t, then in the new machine the
  new state is l[a]^-1*t*l[b].
  
  The  group generated by the new machine is isomorphic to the group generated
  by  m.  This command amounts to a change of basis of the associated bimodule
  (see  [Nek05,  Section  2.2]). It amounts to conjugation by the automorphism
  c=FRElement("c",[l[1]*c,...,l[n]*c],[()],1).
  
  If  the  second argument is absent, this command attempts to choose one that
  makes many entries of the recursion trivial.
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);;
    gap> Display(n);
     G   |     1         2
    -----+--------+---------+
     tau | <id>,2     tau,1
      mu | <id>,2   mu^-1,1
    -----+--------+---------+
    gap> nt := ChangeFRMachineBasis(n,GeneratorsOfFRMachine(n){[1,1]});;
    gap> Display(nt);
     G   |     1                    2
    -----+--------+--------------------+
     tau | <id>,2                tau,1
      mu | <id>,2   tau^-1*mu^-1*tau,1
    -----+--------+--------------------+
  ------------------------------------------------------------------
  
  
  3.4 Attributes for FRMachines
  
  3.4-1 StateSet
  
  > StateSet( m ) ___________________________________________________attribute
  Returns:  The set of states associated with m.
  
  This  function  returns  the  stateset of m. It can be either a list (if the
  machine  is  of  Mealy type), or a free group/semigroup/monoid (in all other
  cases).
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ tau, mu ] )>
    gap> StateSet(n);
    <free group on the generators [ tau, mu ]>
    gap> StateSet(AsMealyMachine(n));
    [ 1 .. 4 ]
  ------------------------------------------------------------------
  
  3.4-2 GeneratorsOfFRMachine
  
  > GeneratorsOfFRMachine( m ) ______________________________________attribute
  Returns:  The generating set of the stateset of m.
  
  This function returns the generating set of the stateset of machine. If m is
  a Mealy machine, it returs the stateset.
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ tau, mu ] )>
    gap> GeneratorsOfFRMachine(n);
    [ tau, mu ]
  ------------------------------------------------------------------
  
  3.4-3 Output
  
  > Output( m, s ) __________________________________________________operation
  > Output( m, s, x ) _______________________________________________operation
  Returns:  A transformation of m's alphabet.
  
  This  function  returns  the  transformation of m's alphabet associated with
  state s. This transformation is returned as a list of images.
  
  s  is  also  allowed  to  be  a list, in which case it is interpreted as the
  corresponding product of states.
  
  In the second form, the result is actually the image of x under Output(m,s).
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ a, b ] )>
    gap> Output(n,[1,2]);
    [2,1]
    gap> Output(n,Product(GeneratorsOfFRMachine(n)));
    [2,1]
  ------------------------------------------------------------------
  
  3.4-4 Transition
  
  > Transition( m, s, i ) ___________________________________________operation
  Returns:  An element of m's stateset.
  
  This function returns the state reached by m when started in state s and fed
  input  i.  This  input  may  be an alphabet letter or a sequence of alphabet
  letters.
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ a, b ] )>
    gap> Transition(n,[2,1],2);
    a*b
    gap> Transition(n,Product(GeneratorsOfFRMachine(n))^2,1);
    a*b
  ------------------------------------------------------------------
  
  3.4-5 WreathRecursion
  
  > WreathRecursion( machine ) ______________________________________attribute
  Returns:  A function on the stateset of machine.
  
  This  function  returns  a function on machine's stateset. This function, on
  receiving  state  q  as  input,  returns  a  list. Its first entry is a list
  indexed by machine's alphabet, with in position x the state machine would be
  in  if  it received input x when in state q. The second entry is the list of
  the permutation of machine's alphabet induced by q.
  
  WreathRecursion(machine)(q)[1][a]  is  equal  to Transition(machine,q,a) and
  WreathRecursion(machine)(q)[2] is equal to Output(machine,q).
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ a, b ] )>
    gap> WreathRecursion(n)(GeneratorsOfFRMachine(n)[1]);
    [ [ <identity ...>, b ], [2,1] ]
    gap> WreathRecursion(n)(GeneratorsOfFRMachine(n)[2]);
    [ [ <identity ...>, a ], [1,2] ]
  ------------------------------------------------------------------
  
  
  3.5 Operations for FRMachines
  
  3.5-1 StructuralGroup
  
  > StructuralGroup( machine ) ______________________________________operation
  > StructuralMonoid( machine ) _____________________________________operation
  > StructuralSemigroup( machine ) __________________________________operation
  Returns:  A   finitely   presented   group/monoid/semigroup   capturing  the
            structure of machine.
  
  This  function  returns  a  finitely  presented group/monoid/semigroup, with
  generators    the    union    of   the   AlphabetOfFRObject   (11.1-3)   and
  GeneratorsOfFRMachine (3.4-2) of machine, and relations all qa'=aq' whenever
  phi(q,a)=(a',q').
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["a","b","c"],[[[2],[3]],[[3],[2]],[[1],[1]]],[(1,2),(1,2),()]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ a, b, c ] )>
    gap> StructuralGroup(n);
    <fp group on the generators [ a, b, c, 1, 2 ]>
    gap> RelatorsOfFpGroup(last);
    [ a*2*b^-1*1^-1, a*1*c^-1*2^-1, b*2*c^-1*1^-1,
      b*1*b^-1*2^-1, c*1*a^-1*1^-1, c*2*a^-1*2^-1 ]
    gap> SimplifiedFpGroup(last2);
    <fp group on the generators [ a, 1 ]>
    gap> RelatorsOfFpGroup(last);
    [ 1^-1*a^2*1^4*a^-2*1^-1*a*1^-2*a^-1, 1*a*1^-1*a*1^2*a^-1*1*a^-2*1^-3*a,
      1^-1*a^2*1^2*a^-1*1^-1*a*1^2*a^-2*1^-2 ]
  ------------------------------------------------------------------
  
  3.5-2 \+
  
  > \+( machine1, machine2 ) ___________________________________________method
  Returns:  A new FR machine, in the same family as its arguments.
  
  This function returns a new FR machine, with stateset generated by the union
  of  the statesets of its arguments. The arguments machine1 and machine2 must
  operate  on  the  same  alphabet. If the stateset of machine1 is free on n_1
  letters  and  the  stateset  of  machine2  is  free on n_2 letters, then the
  stateset  of  their  sum  is  free  on  n_1+n_2  letters, with the first n_1
  identified with machine1's states and the next n_2 with machine2's.
  
  The transition and output functions are naturally extended to the sum.
  
  The  arguments may be free groups, semigroups or monoid machines. The sum is
  in  the weakest containing category: it is a group machine if both arguments
  are  group  machines;  a monoid if both are either group of monoid machines;
  and a semigroup machine otherwise.
  
  The  maps  from  the stateset of machine1 or machine2 to the stateset of the
  result  r can be recovered as Correspondence(r)[1] and Correspondence(r)[2];
  see Correspondence (3.5-11).
  
  ---------------------------  Example  ----------------------------
    gap> tau := FRMachine([[[],[1]]],[(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
    gap> mu := FRMachine([[[],[-1]]],[(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
    gap> sum := tau+mu;; Display(sum);
         |     1          2
    -----+--------+----------+
     f11 | <id>,2      f11,1
     f12 | <id>,2   f12^-1,1
    -----+--------+----------+
    gap> Correspondence(sum)[1];
    [ f1 ] -> [ f11 ]
    gap> GeneratorsOfFRMachine(tau)[1]^last;
    f11
  ------------------------------------------------------------------
  
  3.5-3 \*
  
  > \*( machine1, machine2 ) ___________________________________________method
  Returns:  A new FR machine, in the same family as its arguments.
  
  The  product  of two FR machines coincides with their sum, since the natural
  free  object  mapping  to  the  product of the statesets is generated by the
  union of the statesets. See therefore \+ (3.5-2).
  
  3.5-4 TensorSumOp
  
  > TensorSumOp( FR_machines, machine ) ________________________________method
  Returns:  A  new  FR  machine  on  the  disjoint  union  of  the  arguments'
            alphabets.
  
  The  tensor  sum  of  FR  machines  with  same stateset is defined as the FR
  machine  acting  on  the disjoint union of the alphabets; if these alphabets
  are  [1..n1] up to [1..nk], then the alphabet of their sum is [1..n1+...+nk]
  and the transition functions are similarly concatenated.
  
  The  first  argument  is  a list; the second argument is any element of that
  list, and is used only to improve the method selection algorithm.
  
  ---------------------------  Example  ----------------------------
    gap> m := TensorSum(AddingMachine(2),AddingMachine(3),AddingMachine(4));
    AddingMachine(2)(+)AddingMachine(3)(+)AddingMachine(4)
    gap> Display(m);
       |  1     2     3     4     5     6     7     8     9
    ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
     a | a,1   a,2   a,3   a,4   a,5   a,6   a,7   a,8   a,9
     b | a,2   b,1   a,4   a,5   b,3   a,7   a,8   a,9   b,6
    ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  ------------------------------------------------------------------
  
  3.5-5 TensorProductOp
  
  > TensorProductOp( FR, machines, machine ) ___________________________method
  Returns:  A  new  FR  machine  on  the  cartesian  product of the arguments'
            alphabets.
  
  The  tensor  product  of FR machines with same stateset is defined as the FR
  machine  acting  on  the  cartesian product of the alphabets. The transition
  function  and  output  function  behave as if a single letter, in the tensor
  product's  alphabet,  were a word (read from left to right) in the machines'
  alphabets.
  
  The  first  argument  is  a list; the second argument is any element of that
  list, and is used only to improve the method selection algorithm.
  
  Due  to an overloading problem in the GAP library, the user-level command is
  temporarily renamed TensorProductX.
  
  ---------------------------  Example  ----------------------------
    gap> m := TensorProductX(AddingMachine(2),AddingMachine(3));
    AddingMachine(2)(*)AddingMachine(3)
    gap> Display(last);
       |  1     2     3     4     5     6
    ---+-----+-----+-----+-----+-----+-----+
     a | a,1   a,2   a,3   a,4   a,5   a,6
     b | a,4   a,5   a,6   a,2   a,3   b,1
    ---+-----+-----+-----+-----+-----+-----+
  ------------------------------------------------------------------
  
  3.5-6 DirectSumOp
  
  > DirectSumOp( FR, machines, machine ) _______________________________method
  Returns:  A  new  FR  machine  on  the  disjoint  union  of  the  arguments'
            alphabets.
  
  The  direct  sum  of  FR machines is defined as the FR machine with stateset
  generated  by  the  disjoint  union of the statesets, acting on the disjoint
  union  of  the alphabets; if these alphabets are [1..n1] up to [1..nk], then
  the  alphabet  of  their sum is [1..n1+...+nk] and the output and transition
  functions are similarly concatenated.
  
  The  first  argument  is  a list; the second argument is any element of that
  list, and is used only to improve the method selection algorithm.
  
  ---------------------------  Example  ----------------------------
    gap> m := DirectSum(AddingMachine(2),AddingMachine(3),AddingMachine(4));
    AddingMachine(2)#AddingMachine(3)#AddingMachine(4)
    gap> Display(m);
       |  1     2     3     4     5     6     7     8     9
    ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
     a | a,1   a,2   a,3   a,4   a,5   a,6   a,7   a,8   a,9
     b | a,2   b,1   b,3   b,4   b,5   b,6   b,7   b,8   b,9
     c | c,1   c,2   a,3   a,4   a,5   c,6   c,7   c,8   c,9
     d | d,1   d,2   a,4   a,5   b,3   d,6   d,7   d,8   d,9
     e | e,1   e,2   e,3   e,4   e,5   a,6   a,7   a,8   a,9
     f | f,1   f,2   f,3   f,4   f,5   a,7   a,8   a,9   b,6
    ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  ------------------------------------------------------------------
  
  3.5-7 DirectProductOp
  
  > DirectProductOp( FR, machines, machine ) ___________________________method
  Returns:  A  new  FR  machine  on  the  cartesian  product of the arguments'
            alphabets.
  
  The direct product of FR machines is defined as the FR machine with stateset
  generated  by  the  product  of  the statesets, acting on the product of the
  alphabets;  if  these alphabets are [1..n1] up to [1..nk], then the alphabet
  of  their  product is [1..n1*...*nk] and the output and transition functions
  act component-wise.
  
  The  first  argument  is  a list; the second argument is any element of that
  list, and is used only to improve the method selection algorithm.
  
  ---------------------------  Example  ----------------------------
    gap> m := DirectProduct(AddingMachine(2),AddingMachine(3));
    AddingMachine(2)xAddingMachine(3)
    gap> Display(last);
       |  1     2     3     4     5     6
    ---+-----+-----+-----+-----+-----+-----+
     a | a,1   a,2   a,3   a,4   a,5   a,6
     b | a,2   a,3   b,1   a,5   a,6   b,4
     c | a,4   a,5   a,6   c,1   c,2   c,3
     d | a,5   a,6   b,4   c,2   c,3   d,1
    ---+-----+-----+-----+-----+-----+-----+
  ------------------------------------------------------------------
  
  3.5-8 TreeWreathProduct
  
  > TreeWreathProduct( m, n, x0, y0 ) __________________________________method
  Returns:  A  new  FR  machine  on  the  cartesian  product of the arguments'
            alphabets.
  
  The  tree-wreath  product  of  two  FR  machines  is a machine acting on the
  product  of  its arguments' alphabets X,Y, in such a way that many images of
  the first machine's states under conjugation by the second commute.
  
  It  is  introduced  (in  lesser  generality,  and  with small variations) in
  [Sid05],  and  may  be  described  as  follows:  one takes two copies of the
  stateset  of  m,  one copy of the stateset of n, and, if necessary, an extra
  identity state.
  
  The  first  copy  of  m  fixes  the  alphabet  Xx  Y;  its state tilde s has
  transitions  to  the  identity except tilde s at (x0,y0) and s at (*,y0) for
  any  other  *.  The  second  copy of m is also trivial except that, on input
  (x,y0),  its  state  s  goes  to  state  s'  with  output (x',y0) whenever s
  originally  went,  on  input  x,  to state s' with output x'. This copy of m
  therefore  acts  only  in the X direction, on the subtree (Xx{y0})^infty, on
  subtrees below vertices of the form (x0,y0)^t(x,y0).
  
  A  state  t  in the copy of n maps the input (x,y) to (x,y') and proceeds to
  state  t'  if y=y0, and to the identity state otherwise, when on input y the
  original machine mapped state t to output t' and output y'.
  
  ---------------------------  Example  ----------------------------
    gap> m := TreeWreathProduct(AddingMachine(2),AddingMachine(3),1,1);
    AddingMachine(2)~AddingMachine(3)
    gap> Display(last);
       |  1     2     3     4     5     6
    ---+-----+-----+-----+-----+-----+-----+
     a | c,2   c,3   a,1   c,5   c,6   c,4
     b | c,4   c,2   c,3   b,1   c,5   c,6
     c | c,1   c,2   c,3   c,4   c,5   c,6
     d | d,1   c,2   c,3   b,4   c,5   c,6
    ---+-----+-----+-----+-----+-----+-----+
  ------------------------------------------------------------------
  
  3.5-9 SubFRMachine
  
  > SubFRMachine( machine1, machine2 ) ______________________________operation
  Returns:  Either  fail  or  an  embedding  of  the states of machine2 in the
            states of machine1.
  
  This  function  attempts  to  locate  a  copy of machine2 in machine1. If is
  succeeds,  it  returns a homomorphism from the stateset of machine2 into the
  stateset of machine1; otherwise it returns fail.
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ tau, mu ] )>
    gap> tauinv := FRMachine([[[1],[]]],[(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
    gap> SubFRMachine(n,tauinv);
    [ f1 ] -> [ tau^-1 ]
  ------------------------------------------------------------------
  
  3.5-10 Minimized
  
  > Minimized( m ) __________________________________________________operation
  Returns:  A minimized machine equivalent to m.
  
  This  function  attempts  to construct a machine equivalent to m, but with a
  stateset  of  smaller  rank.  Identical generators are collapsed to a single
  generator  of  the  stateset; if m is a group or monoid machine then trivial
  generators  are  removed;  if  m  is  a  group machine then mutually inverse
  generators  are  grouped.  This  function  sets  as Correspondence(result) a
  mapping  between  the  stateset  of  m  and  the stateset of the result; see
  Correspondence (3.5-11).
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);;
    gap> m := FRMachine(["tauinv"],[[[1],[]]],[(1,2)]);;
    gap> sum := n+m+n;
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ tau1, mu1, tauinv1, tau2, mu2 ] )>
    gap> min := Minimized(sum);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ tau1, mu1 ] )>
    gap> Correspondence(min);
    [ tau1, mu1, tauinv1, tau2, mu2 ] -> [ tau1, mu1, tau1^-1, tau1, mu1 ]
  ------------------------------------------------------------------
  
  3.5-11 Correspondence
  
  > Correspondence( m ) _____________________________________________attribute
  Returns:  A mapping between statesets of FR machines.
  
  If  a  machine  m was created as a minimized group/monoid/semigroup machine,
  then  Correspondence(m)  is  a  mapping between the stateset of the original
  machine and the stateset of m. See Minimized (3.5-10) for an example.
  
  If  m  was created as a minimized Mealy machine, then Correspondence(m) is a
  list identifying, for each state of the original machine, a state of the new
  machine. If the original state is inaccessible, the corresponding list entry
  is unbound. See Minimized (5.2-2) for an example.
  
  If  m was created using AsGroupFRMachine (3.3-4), AsMonoidFRMachine (3.3-4),
  AsSemigroupFRMachine    (3.3-4),    or    AsMealyMachine    (5.2-18),   then
  Correspondence(m) is a list or a homomorphism identifying for each generator
  of  the  original machine a generator, or word in the generators, of the new
  machine. It is a list if either the original or the final machine is a Mealy
  machine, and a homomorphism in other cases.
  
  If  m  was  created  as  a  sum  of  two  machines,  then  m  has  a mapping
  Correspondence(m)[i]  between  the  stateset  of  machine  i=1,2 and its own
  stateset. See \+ (3.5-2) for an example.