11 FR implementation details
  
  FR creates new categories for the various objects considered in the package.
  The  first  category is FRObject; all objects are in this category, and have
  an Alphabet method.
  
  There  are  two categories below: FRMachine and FRElement. An FRMachine must
  have  a StateSet, and methods for Output and a Transition. An FRElement must
  have  an  underlying FRMachine and InitialState, and Output and a Transition
  that use the initial state.
  
  A  self-similar  group is simply a collections category of FR elements which
  is also a group.
  
  
  11.1 The family of FR objects
  
  All FR objects have an associated AlphabetOfFRObject (11.1-3).
  
  11.1-1 FRMFamily
  
  > FRMFamily( obj ) ________________________________________________operation
  Returns:  the family of FR machines on alphabet obj.
  
  The  family  of  an FR object is the arity of the tree on which elements cat
  act; in other words, there is one family for each alphabet.
  
  11.1-2 FREFamily
  
  > FREFamily( obj ) ________________________________________________operation
  Returns:  the family of FR elements on alphabet obj.
  
  The  family  of  an FR object is the arity of the tree on which elements cat
  act; in other words, there is one family for each alphabet.
  
  The argument may be an FR machine, an alphabet, or a family of FR machines.
  
  11.1-3 AlphabetOfFRObject
  
  > AlphabetOfFRObject( obj ) _______________________________________operation
  Returns:  the alphabet associated with obj.
  
  This  command  applies  to  the  family  of  any FR object, or to the object
  themselves. Alphabets are returned as lists, and in pratice are generally of
  the form [1..n].
  
  11.1-4 AsPermutation
  
  > AsPermutation( o ) _________________________________________________method
  
  This  method  takes  as argument an FR object o: machine, element, or group,
  and  produces  an  equivalent  object  whose  outputs  are  permutations. In
  particular,  it  converts  Mealy  machines from domain representation to int
  representation.
  
  If this is not possible, the method returns fail.
  
  11.1-5 AsTransformation
  
  > AsTransformation( o ) ______________________________________________method
  
  This  method  takes  as argument an FR object o: machine, element, or group,
  and  produces  an  equivalent  object  whose outputs are transformations. In
  particular,  it  converts  Mealy  machines from domain representation to int
  representation.
  
  Since  transformations  can  never  be  inverted  by GAP, even when they are
  invertible, this function returns a monoid when applied to a full SC group.
  
  
  11.2 Filters for FRObjects
  
  11.2-1 IsGroupFRMachine
  
  > IsGroupFRMachine( obj ) __________________________________________property
  > IsMonoidFRMachine( obj ) _________________________________________property
  > IsSemigroupFRMachine( obj ) ______________________________________property
  Returns:  true   if   obj  is  an  FR  machine  whose  stateset  is  a  free
            group/monoid/semigroup.
  
  This  function  is  the  acceptor  for those functionally recursive machines
  whose  stateset (accessible via StateSet (3.4-1)) is a free group, monoid or
  semigroup.   The   generating   set   of  its  stateset  is  accessible  via
  GeneratorsOfFRMachine (3.4-2).
  
  11.2-2 IsFRMachineStrRep
  
  > IsFRMachineStrRep( obj ) ___________________________________________filter
  Returns:  true if obj is a standard (group,monoid,semigroup) FR machine.
  
  There is a free object free, of rank N, a list transitions of length N, each
  entry  a  list,  indexed  by  the  alphabet, of elements of free, and a list
  output of length N of transformations or permutations of the alphabet.
  
  11.2-3 IsMealyMachine
  
  > IsMealyMachine( obj ) ______________________________________________filter
  Returns:  true if obj is a Mealy machine.
  
  This  function  is  the  acceptor  for  the  Mealy machine subcategory of FR
  machines.
  
  11.2-4 IsMealyElement
  
  > IsMealyElement( obj ) ______________________________________________filter
  Returns:  true if obj is a Mealy element.
  
  This  function  is  the  acceptor  for  the  Mealy element subcategory of FR
  elements.
  
  11.2-5 IsMealyMachineIntRep
  
  > IsMealyMachineIntRep( obj ) ________________________________________filter
  Returns:  true if obj is a Mealy machine in integer representation.
  
  A   Mealy   machine  in  integer  representation  has  components  nrstates,
  transitions, output and optionally initial.
  
  Its   stateset   is   [1..nrstates],   its  transitions  is  a  matrix  with
  transitions[s][x]  the transition from state s with input x, its output is a
  list  of  transformations  or  permutations,  and  its  initial  state is an
  integer.
  
  11.2-6 IsMealyMachineDomainRep
  
  > IsMealyMachineDomainRep( obj ) _____________________________________filter
  Returns:  true if obj is a Mealy machine in domain representation.
  
  A Mealy machine in domain representation has components states, transitions,
  output and optionally initial.
  
  Its  states is a domain, its transitions is a function with transitions(s,x)
  the  transition  from  state  s  with input x, its output is a function with
  output(s,x)  the output from input x in state s, and its initial state is an
  elemnent of states.
  
  11.2-7 IsVectorFRMachineRep
  
  > IsVectorFRMachineRep( obj ) ________________________________________filter
  Returns:  true if obj is a vector machine
  
  A   vector   machine   is   a  representation  of  a  linear  machine  by  a
  finite-dimensional  vector  space  (implicit in the structure), a transition
  tensor  (represented  as  a  matrix  of  matrices),  and  an  output  vector
  (represented as a list).
  
  11.2-8 IsAlgebraFRMachineRep
  
  > IsAlgebraFRMachineRep( obj ) _______________________________________filter
  Returns:  true if obj is an algebra machine
  
  An  algebra  machine  is  a representation of a linear machine by a finitely
  generated  free algebra, a tensor of transitions, indexed by generator index
  and  two  alphabet  indices,  and  an  output vector, indexed by a generator
  index.
  
  The  transition  tensor's  last  two entries are the 0 and 1 matrix over the
  free  algebra,  and  the  output  tensor's  last two entries are the 0 and 1
  elements of the left acting domain.
  
  11.2-9 IsLinearFRMachine
  
  > IsLinearFRMachine( obj ) ___________________________________________filter
  Returns:  true if obj is a linear machine.
  
  This  function  is  the  acceptor  for  the linear machine subcategory of FR
  machines.
  
  11.2-10 IsLinearFRElement
  
  > IsLinearFRElement( obj ) ___________________________________________filter
  Returns:  true if obj is a linear element.
  
  This  function  is  the  acceptor  for  the linear element subcategory of FR
  elements.
  
  11.2-11 IsFRElement
  
  > IsFRElement( obj ) _________________________________________________filter
  Returns:  true if obj is an FR element.
  
  This  function  is  the  acceptor  for  the  functionally  recursive element
  category.
  
  It  implies that obj has an underlying FR machine, may act on sequences, and
  has a recursive DecompositionOfFRElement (4.2-5).
  
  11.2-12 IsFRObject
  
  > IsFRObject( obj ) __________________________________________________filter
  Returns:  true if obj is an FR machine or element.
  
  This function is the acceptor for the most general FR category (which splits
  up as IsFRMachine (11.2-13) and IsFRElement (11.2-11)).
  
  It implies that obj has an attribute AlphabetOfFRObject (11.1-3).
  
  11.2-13 IsFRMachine
  
  > IsFRMachine( obj ) _________________________________________________filter
  Returns:  true if obj is an FR machine.
  
  This  function  is  the  acceptor  for  the  functionally  recursive machine
  category.  It  splits  up as IsGroupFRMachine (11.2-1), IsSemigroupFRMachine
  (11.2-1), IsMonoidFRMachine (11.2-1) and IsMealyMachine (11.2-3)).
  
  It  implies  that obj has attributes StateSet (3.4-1), GeneratorsOfFRMachine
  (3.4-2),  and WreathRecursion (3.4-5); the last two are usually not used for
  Mealy machines.
  
  11.2-14 IsInvertible
  
  > IsInvertible( m ) ________________________________________________property
  Returns:  true if m is an invertible FR machine.
  
  This  function  accepts  invertible  FR machines, i.e. machines machine such
  that  (machine,q)  is an invertible transformation of the alphabet for all q
  in the stateset of machine.
  
  ---------------------------  Example  ----------------------------
    gap> m := FRMachine([[[],[]]],[(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ f1 ] )>
    gap> IsInvertible(m);
    true
    gap> m := FRMachine([[[],[]]],[[1,1]]);
    <FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m1 ], ... )>
    gap> IsInvertible(m);
    false
  ------------------------------------------------------------------
  
  11.2-15 IsFRGroup
  
  > IsFRGroup( obj ) ___________________________________________________filter
  > IsFRMonoid( obj ) __________________________________________________filter
  > IsFRSemigroup( obj ) _______________________________________________filter
  Returns:  true if obj is a FR group/monoid/semigroup.
  
  These   functions   accept   self-similar   groups/monoids/semigroups,  i.e.
  groups/monoids/semigroups whose elements are FR elements.
  
  11.2-16 IsFRAlgebra
  
  > IsFRAlgebra( obj ) _________________________________________________filter
  > IsFRAlgebraWithOne( obj ) __________________________________________filter
  Returns:  true if obj is a FR algebra [with one].
  
  These functions accept self-similar algebras [with one], i.e. algebras whose
  elements are linear FR elements.
  
  
  11.3 Some of the algorithms implemented
  
  Few calculations with infinite groups can be guaranteed to terminate --- and
  especially  to terminate within reasonable time. This section describes some
  of the algorithms implemented in FR.
  
  11.3-1 FRMachineRWS
  
  > FRMachineRWS( m ) _______________________________________________attribute
  Returns:  A record containing a rewriting system for m.
  
  Elements  of  an  FR  machine  are  compared using a rewriting system, which
  records all known relations among states of the machine.
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ a, b ] )>
    gap> FRMachineRWS(n);
    rec( rws := Knuth Bendix Rewriting System for Monoid( [ a^-1, a, b^-1, b
         ], ... ) with rules
        [ [ a^-1*a, <identity ...> ], [ a*a^-1, <identity ...> ],
          [ b^-1*b, <identity ...> ], [ b*b^-1, <identity ...> ] ],
      tzrules := [ [ [ 1, 2 ], [  ] ], [ [ 2, 1 ], [  ] ], [ [ 3, 4 ], [  ] ],
          [ [ 4, 3 ], [  ] ] ], letterrep := function( w ) ... end,
      pi := function( w ) ... end, reduce := function( w ) ... end,
      addgprule := function( w ) ... end, commit := function(  ) ... end,
      restart := function(  ) ... end )
  ------------------------------------------------------------------
  
  
  11.3-2 Order of FR elements
  
  The  order  of an FR element e is computed as follows: the tree is traversed
  recursively,  filling it as follows. For each cycle of e on the first level,
  the  product  of the states on that cycle are computed. The method continues
  recursively  with  that  product, remembering the order of the cycle. Once a
  state reappears in the traversal, FR determines if one instance of the state
  is  in the subtree of the other, and if so whether the top one was raised to
  a  non-trivial  power  to  yield the second one as a state. If this happens,
  then  e  has  infinite  order.  Otherwise,  the least common multiple of the
  powers that appeared in the traversal is returned.
  
  This  method  is guaranteed to succeed if e is a bounded element. To improve
  chances   of   success,   FR   first  computes  whether  e  acts  by  vertex
  transformations  belonging to an abelian group; and if so, if e is conjugate
  to an adding machine. In that case too, e has infinite order.
  
  
  11.3-3 Membership in semigroups
  
  The following algorithm is used to determine whether a Mealy element belongs
  to  a  self-similar  group. The corresponding problem of membership of an FR
  element in a state-closed self-similar group can be much simpler, because an
  FR  element  has an associated FR machine, all of whose states belong to the
  group.
  
  Assume  the  group  is given by generators. FR attempts to express the given
  Mealy  element  as  a product of generators. At the same time, it constructs
  epimorphisms  to  finite groups. It is hoped that one of these two processes
  will stop.
  
  This  amounts,  in  fact,  to  the following. Consider a group G acting on a
  tree.  It  has  a  natural, profinite closure overline G. The algorithm then
  attempts either to write an element x as a product of generators of G, or to
  show that x does not belong to overline G.
  
  There  are  groups  G  such  that overline G\ G contains Mealy machines. For
  these, the above algorithm will not terminate.
  
  An   additional   refinement   is   implemented   for  bounded  groups  (see
  IsBoundedFRSemigroup  (7.2-13)).  The  Germs  (5.2-24)  of  an  element  are
  computed, and compared to the germs of elements in the group.
  
  Finally,  for a group that possesses self-similar data (see Section 11.3-5),
  very  fast methods are implemented to recognize and express an FR element as
  a product of generators.
  
  
  11.3-4 Order of groups
  
  The  order  of  an  FR  group  is computed as follows: if all generators are
  finitary,  then  enumeration  will  succeed  in  computing the order. If the
  action  of  the  group  is  primitive,  and  it  comes  from  a bireversible
  automaton,  then  the  Thompson-Wielandt  theorem  is  tested  against. This
  theorem states that, in our context (a group acting on a rooted tree, coming
  from  a  larger  group acting transitively), if the group is finite then the
  stabilizer  of  a  sphere  of radius 2 is a p-group; see [BM00a, Proposition
  2.1.1].  Then, FR attempts to find whether the group is level-transitive (in
  which  case  it  would  be  infinite). Finally, it attempts to enumerate the
  group's  elements,  testing  at  the  same  time whether these elements have
  infinite order.
  
  Needless to say, none except the first few steps are guaranteed to succeed.
  
  
  11.3-5 Images and preimages of some groups in f.p. and l.p. groups
  
  Contracting,  branched  groups  admit finite L-presentations (see [Bar03b]),
  that   is,   presentations   by   finitely  many  generators,  relators  and
  endomorphisms;  the  (usual)  relators  are the images of the given relators
  under iteration by all endomorphisms.
  
  Using  the  package  NQL,  it  is  possible  to construct infinite nilpotent
  quotients of self-similar groups, and perform fast computations in them.
  
  It  is possible to construct, algorithmically, such an L-presentation from a
  self-similar  groups;  however, this algorithm has not been implemented yet,
  mainly  because  efficiency  issues  would  make  it usable only in very few
  cases.
  
  For  groups  with  an  isomorphism  to  an L-presented group (constructed by
  IsomorphismLpGroup  (7.2-27)),  a  fast  method  expresses group elements as
  words  in the L-presented group's generators. It proceeds recursively on the
  decomposition of the element, mapping elements that are expressible by short
  words  over  the  nucleus  (usually  length  1;  length  3 is needed for the
  BrunnerSidkiVieiraGroup  (10.1-12)) to their value in the L-presented group,
  and   using   the   presentation's  endomorphism  to  construct  words  with
  appropriate decompositions.
  
  In  particular,  the  algorithm  will  stop,  returning  fail, if during the
  recursion it reaches an element x such that x is a state of x but x does not
  belong to the nucleus.
  
  
  11.3-6 Comparison of FR, Mealy, vector, and algebra elements
  
  FR and Mealy elements can be compared quite efficiently, as long as they are
  distinct.  The  algorithm  runs as follows: let the two elements be x and y.
  Considering  both  in turn, FR constructs the first entries of minimal Mealy
  elements  expressing  x  and y; as soon as an output entry is distinct for x
  and  for  y,  the  status of x<y is determined; and similarly for transition
  entries.  Finally,  if either of x or y is finite-state and the entries were
  identical  up  to  that  step,  then  the  element with smallest stateset is
  considered smaller.
  
  In  this  way,  FR and Mealy elements can efficiently be compared. For Mealy
  elements,  it suffices to follow their internal data; while for FR elements,
  this  amounts  to  constructing  Mealy  elements  approximating  them  to  a
  sufficient precision so that they can be compared as such.
  
  The  algorithm  first tries to test its arguments for equality; this test is
  not guaranteed to succeed.
  
  A similar algorithm applies for linear elements. Here, one constructs vector
  element approximations; and compares, for ever-increasing values of i, first
  the  output  vectors  of basis state i; then the transitions from state i to
  state j, for all jin{1,dots,i}; then the transitions from state j to state i
  for all jin{1,dots,i-1}.
  
  
  11.3-7 Inverses of linear elements
  
  It  is  probably  difficult  to compute the inverse of a vector element. The
  following  approach  is  used:  to  compute the inverse of x, large (scalar)
  matrix  approximations  of  x  are  computed; they are inverted using linear
  algebra;  a  vector  element  representing  this inverse is guessed; and the
  guess  is  checked.  As  long as that check fails, larger approximations are
  computed.
  
  Needless to say, this method need not succeed; for there are vector elements
  that  are invertible, but whose inverse is not a vector element. A good test
  example  appears  in  [Bac07]:  consider the infinite matrix with 1's on the
  diagonal,  and  omega  below the diagonal. This element admits an inverse if
  and only if omega is a root of unity. The complexity of the inverse grows as
  the degree of omega grows. Here is an illustation:
  
  ---------------------------  Example  ----------------------------
    gap> bacher := function(n)
      local f;
      f := CyclotomicField(n);
      return VectorElement(f,One(f)*[[[[1,0],[0,0]],
            [[0,0],[0,1]]],[[[0,1],[0,0]],[[1,0],[0,0]]]],[One(f),E(n)],[One(f),Zero(f)]);
    end;;
    gap> Inverse(bacher(3));
    <Linear element on alphabet CF(3)^2 with 4-dimensional stateset>
    6 gap> Inverse(bacher(5));
    <Linear element on alphabet CF(5)^2 with 6-dimensional stateset>
  ------------------------------------------------------------------
  
                n | 1    2    3    4    5    6    7    8    9    10
        dimension |      2    4    4    6    3    5    5    8    5 
      ------------------------------------------------------------
                n | 11   12   13   14   15   16   17   18   19   20
        dimension | ?    5    ?    4    6    6    ?    7    ?    7 
      ------------------------------------------------------------
                n | 22   24   26   28   30   32   34   36   38   40
        dimension | ?    6    ?    6    ?    7    ?    ?    ?    ? 
  
       Table: Dimension of states of inverse