5 Mealy machines and elements
  
  Mealy  machines form a special class of FR machines. They have as stateset a
  finite  set,  as  opposed  to  a  free  group/monoid/semigroup. All commands
  available  for  FR  machines  are also available for Mealy machines, but the
  latter have added functionality.
  
  There  are  currently  two  types  of Mealy machines; one has as stateset an
  interval  of  integers of the form [1..m] and as alphabet a set of integers;
  the  other  has  an  arbitrary  domain  as  stateset and alphabet. Almost no
  functionality  is  implemented  for the latter type, but there is a function
  converting it to the former type (see AsMealyMachine (5.2-18)).
  
  The  internal  representation  of a Mealy machine of the first kind is quite
  different  from  that  of  FR  machines.  The  alphabet  is assumed to be an
  interval  [1..n],  and the stateset is assumed to be an interval [1..m]. The
  transitions  are  stored  as a m x n matrix, and the outputs are stored in a
  list of length m, consisting of permutations or transformations.
  
  Mealy  machines  have  additional  properties, in particular they can act on
  periodic  sequences  (see  PeriodicList (12.1-6)). For example, the periodic
  sequence  PeriodicList([1],[1,2])  describes the infinite ray [1,1,2,1,2,..]
  in the tree. In principle, Mealy machines could act on sequences accepted by
  an automaton, although this is not yet implemented.
  
  Mealy  elements  are  Mealy  machines  with an initial state. For efficiency
  reasons,  Mealy  elements are always minimized, and their states are ordered
  in  a  canonical  top-down, left-to-right order of traversal of the tree. In
  particular,  their  initial  state  is  always  1.  In  this implementation,
  multiplication  of  Mealy elements is slower than multiplication of group FR
  elements,  while  comparison  of Mealy elements is faster than comparison of
  group  FR elements. In practise, it is better to work with Mealy elements as
  often as possible.
  
  Products  of Mealy machines behave in the same way as products of general FR
  machines,  see  3.2. The only difference is that now the sum and products of
  statesets are distinct; the sum of statesets being their disjoint union, and
  their product being their cartesian product.
  
  
  5.1 Creators for MealyMachines and MealyElements
  
  5.1-1 MealyMachine
  
  > MealyMachine( [alphabet, ]transitions, output ) _________________operation
  > MealyElement( [alphabet, ]transitions, output, init ) ___________operation
  Returns:  A new Mealy machine/element.
  
  This function constructs a new Mealy machine or element, of integer type.
  
  transitions  is  a  list of lists; transitions[s][x] is an integer, which is
  the state reached by the machine when started in state s and fed input x.
  
  output  is a list; at position s it contains a permutation, a transformation
  describing  the  activity of state s, or a list describing the images of the
  transformation.
  
  alphabet  is an optional domain given as first argument; When present, it is
  assumed  to  be  a  finite  domain,  mapped  bijectively  to  [1..n]  by its
  enumerator. The indices "[s]" above are then understood with respect to this
  enumeration.
  
  init  is  an  integer  describing  the initial state the newly created Mealy
  element should be in.
  
  ---------------------------  Example  ----------------------------
    gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states>
    gap> Display(b);
       |  1     2
    ---+-----+-----+
     a | c,2   b,1
     b | c,1   a,2
     c | c,1   c,2
    ---+-----+-----+
    gap> n := MealyMachine(Domain([11,12]),[[3,2],[3,1],[3,3]],[(1,2),(),()]);
    <Mealy machine on alphabet [ 11, 12 ] with states [ 1 .. 3 ]>
    gap> Display(n);
       |  11     12
    ---+------+------+
     a | c,12   b,11
     b | c,11   a,12
     c | c,11   c,12
    ---+------+------+
  ------------------------------------------------------------------
  
  ---------------------------  Example  ----------------------------
    gap> tau := MealyElement([[2,1],[2,2]],[(1,2),()],1);
    <Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
    gap> Display(tau);
       |  1     2
    ---+-----+-----+
     a | b,2   a,1
     b | b,1   b,2
    ---+-----+-----+
    Initial state:  a
    gap> [1,1]^tau; [[1]]^tau; [[2]]^tau;
    [ 2, 1 ]
    [ 2, [ 1 ] ]
    [ [ 1 ] ]
  ------------------------------------------------------------------
  
  5.1-2 MealyMachine
  
  > MealyMachine( stateset, alphabet, transitions, output ) _________operation
  > MealyElement( stateset, alphabet, transitions, output, init ) ___operation
  Returns:  A new Mealy machine/element.
  
  This function constructs a new Mealy machine or element, of domain type.
  
  stateset and alphabet are domains; they are not necessarily finite.
  
  transitions  is  a  function;  it takes as arguments a state and an alphabet
  letter, and returns a state.
  
  output  is  either  a function, accepting as arguments a state and a letter,
  and returning a letter.
  
  init  is  an  element  of  stateset  describing  the initial state the newly
  created Mealy element should be in.
  
  ---------------------------  Example  ----------------------------
    gap> g := Group((1,2));; n := MealyMachine(g,g,\*,\*);
    <Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
    gap> [(1,2),()]^FRElement(n,());
    [ (1,2), (1,2) ]
    gap> a := MealyElement(g,g,\*,\*,());
    <Mealy machine on alphabet [ (), (1,2) ] with states Group(
    [ (1,2) ] ), initial state ()>
    gap> [(1,2),()]^a;
    [ (1,2), (1,2) ]
  ------------------------------------------------------------------
  
  5.1-3 MealyMachineNC
  
  > MealyMachineNC( fam, transitions, output ) ______________________operation
  > MealyElementNC( fam, transitions, output, init ) ________________operation
  Returns:  A new Mealy machine/element.
  
  This function constructs a new Mealy machine or element, of integer type. No
  tests  are  performed  to  check  that  the  arguments contain values within
  bounds,  or  even of the right type (beyond the simple checking performed by
  GAP's method selection algorithms). In particular, Mealy elements are always
  assumed to be minimized, but these functions leave this task to the user.
  
  fam is the family to which the newly created Mealy machine will belong.
  
  transitions  is  a  list of lists; transitions[s][x] is an integer, which is
  the state reached by the machine when started in state s and fed input x.
  
  output   is   a  list;  at  position  s  it  contains  a  permutation  or  a
  transformation describing the activity of state s.
  
  init  is  an  integer  describing  the initial state the newly created Mealy
  element should be in.
  
  ---------------------------  Example  ----------------------------
    gap> taum := MealyMachine([[2,1],[2,2]],[(1,2),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 2 states>
    gap> tauminv := MealyMachineNC(FamilyObj(taum),[[1,2],[2,2]],[(1,2),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 2 states>
    gap> tau := MealyElement([[2,1],[2,2]],[(1,2),()],1);
    <Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
    gap> tauinv := MealyElementNC(FamilyObj(n),[[1,2],[2,2]],[(1,2),()],1);
    <Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
    gap> tau=FRElement(taum,1); tauinv=FRElement(tauminv,1);
    true
    true
    gap> IsOne(tau*tauinv);
    true
  ------------------------------------------------------------------
  
  5.1-4 AllMealyMachines
  
  > AllMealyMachines( m, n[, filters] ) ______________________________function
  Returns:  A list of all Mealy machines with specified properties.
  
  This function constructs all mealy with alphabet [1..m], stateset [1..n] and
  specified properties.
  
  These  properties  are  specified  as additional arguments. They can include
  IsInvertible  (11.2-14),  IsReversible  (5.2-4), IsBireversible (5.2-7), and
  IsMinimized (5.2-5) to specify that the machines should have that property.
  
  A  group/monoid/semigroup  p  may also be passed as argument; this specifies
  the   allowable   vertex  transformations  of  the  machines.  The  property
  IsTransitive  requires  that  the state-closed group/monoid/semigroup of the
  machine act transitively on its alphabet, and IsSurjective requires that its
  VertexTransformationsFRMachine (5.2-15) be precisely equal to p.
  
  The  argument  EquivalenceClasses  returns  one  isomorphism  class of Mealy
  machine, under the permutations of the stateset and alphabet.
  
  The  following  example  constructs  the  two  Mealy machines AleshinMachine
  (10.1-14) and BabyAleshinMachine (10.1-15):
  
  ---------------------------  Example  ----------------------------
    gap> l := AllMealyMachines(2,3,IsBireversible,IsSurjective,EquivalenceClasses);;
    gap> Length(l);
    20
    gap> Filtered(l,x->VertexTransformationsFRMachine(DualMachine(x))=SymmetricGroup(3)
    >                     and Size(StateSet(Minimized(x)))=3);
    [ <Mealy machine on alphabet [ 1, 2 ] with 3 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 3 states> ]
     gap> Display(last[1]);
       |  1     2
    ---+-----+-----+
     a | a,1   b,2
     b | c,2   c,1
     c | b,1   a,2
    ---+-----+-----+
    gap> Display(last[2]);
       |  1     2
    ---+-----+-----+
     a | a,2   b,1
     b | c,1   c,2
     c | b,2   a,1
    ---+-----+-----+
  ------------------------------------------------------------------
  
  
  5.2 Operations and Attributes for MealyMachines and MealyElements
  
  5.2-1 Draw
  
  > Draw( m[, filename] ) ___________________________________________operation
  
  This function creates a graph description of the Mealy machine/element m. If
  a  second  argument  filename is present, the graph is saved, in dot format,
  under  that  filename;  otherwise  it  is  converted to Postscript using the
  program  dot  from  the  graphviz  package, and is displayed in a separate X
  window using the program display. This works on UNIX systems.
  
  A  circle  is displayed for every state of m, and there is an edge for every
  transition  in  m. It has label of the form x/y, where x is the input symbol
  and y is the corresponding output. Edges are coloured according to the input
  symbol,  in  the  order  "red",  "blue",  "green", "gray", "yellow", "cyan",
  "orange",  "purple".  If m has an initial state, it is indicated as a doubly
  circled state.
  
  If  m  is a FR machine, Draw first attempts to convert it to a Mealy machine
  (see AsMealyMachine (5.2-18)).
  
  It  is  assumed,  but  not  checked,  that graphviz and display are properly
  installed on the system.
  
  5.2-2 Minimized
  
  > Minimized( m ) __________________________________________________operation
  Returns:  A minimized machine equivalent to m.
  
  This function contructs the minimized Mealy machine r corresponding to m, by
  identifying   isomorphic   states;   and,  if  m  is  initial,  by  removing
  inaccessible states.
  
  If  m  is  initial,  the  minimized  automaton  is  such that its states are
  numbered  first by distance to the initial state, and then lexicographically
  by  input  letter.  (in  particular,  the  initial  state  is 1). This makes
  comparison of minimized automata efficient.
  
  Furthermore,  Correspondence(r)  is a list describing, for each (accessible)
  state of m, its corresponding state in r; see Correspondence (3.5-11).
  
  ---------------------------  Example  ----------------------------
    gap> GrigorchukMachine := MealyMachine([[2,3],[4,4],[2,5],[4,4],[4,1]],
                                           [(),(1,2),(),(),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 5 states>
    gap> g2 := GrigorchukMachine^2;
    <Mealy machine on alphabet [ 1, 2 ] with 25 states>
    gap> Minimized(g2);
    <Mealy machine on alphabet [ 1, 2 ] with 11 states, minimized>
    gap> Correspondence(last);
    [ 2, 1, 4, 11, 9, 1, 2, 5, 7, 6, 4, 3, 2, 9, 11, 11, 10, 9, 2, 4, 9, 8, 11, 4, 2 ]
    gap> e := FRElement(g2,11);
    <Mealy element on alphabet [ 1, 2 ] with 25 states, initial state 11>
    gap> Minimized(e);
    <Mealy element on alphabet [ 1, 2 ] with 5 states, initial state 1, minimized>
    gap> Correspondence(last);
    [ 3, 2, 1, 4, 5, 2, 3,,,, 1,, 3, 5, 4, 4,, 5, 3, 1, 5,, 4, 1, 3 ]
  ------------------------------------------------------------------
  
  5.2-3 DualMachine
  
  > DualMachine( m ) ________________________________________________operation
  Returns:  The dual Mealy machine of m.
  
  This  function  constructs  the  dual  machine  of  m, i.e. the machine with
  stateset  the  alphabet of m, with alphabet the stateset of m, and similarly
  with transitions and output switched.
  
  ---------------------------  Example  ----------------------------
    gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states>
    gap> d := DualMachine(b)^4);
    <Mealy machine on alphabet [ 1, 2, 3 ] with 16 states>
    gap> Draw(d); # action on 2^4 points
    gap> DualMachine(d);
    <Mealy machine on alphabet [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
     ] with 3 states>
    gap> Output(last,1)=Activity(FRElement(b,1),4);
    true
  ------------------------------------------------------------------
  
  5.2-4 IsReversible
  
  > IsReversible( m ) ________________________________________________property
  Returns:  true if m is a reversible Mealy machine.
  
  This  function  tests  whether m is reversible, i.e. whether the DualMachine
  (5.2-3) of m is invertible. See [MNS00] for more details.
  
  ---------------------------  Example  ----------------------------
    gap> IsReversible(MealyMachine([[1,2],[2,2]],[(1,2),()]));
    false
    gap> IsReversible(MealyMachine([[1,2],[2,1]],[(),(1,2)]));
  ------------------------------------------------------------------
  
  5.2-5 IsMinimized
  
  > IsMinimized( m ) _________________________________________________property
  Returns:  true if m is a minimized Mealy machine.
  
  This  function tests whether m is minimized, i.e. whether nono of its states
  can be removed or coalesced. All Mealy elements are automatically minimized.
  
  ---------------------------  Example  ----------------------------
    gap> AllMealyMachines(2, 2, IsBireversible,EquivalenceClasses);
    [ <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
      <Mealy machine on alphabet [ 1, 2 ] with 2 states> ]
    gap> List(last,IsMinimized);
    [ false, true, false, false, false, false, true, false ]
  ------------------------------------------------------------------
  
  5.2-6 AlphabetInvolution
  
  > AlphabetInvolution( m ) _________________________________________attribute
  Returns:  A list giving, for each alphabet letter, its inverse.
  
  If  m is a bireversible machine, it may happen that the stateset of the dual
  of  m  (see  DualMachine  (5.2-3))  is closed under taking inverses. If this
  happens,  then this list records the mapping from an alphabet letter of m to
  its inverse.
  
  ---------------------------  Example  ----------------------------
    gap> m := GammaPQMachine(3,5);; AlphabetOfFRObject(m);
    [ 1 .. 6 ]
    gap> IsBireversible(m); AlphabetInvolution(GammaPQMachine(3,5));
    true
    [ 6, 5, 4, 3, 2, 1 ]
  ------------------------------------------------------------------
  
  5.2-7 IsBireversible
  
  > IsBireversible( m ) ______________________________________________property
  Returns:  true if m is a bireversible Mealy machine.
  
  This  function  tests  whether  m  is  bireversible,  i.e. whether all eight
  machines   obtained  from  m  using  DualMachine  (5.2-3)  and  Inverse  are
  well-defined. See [MNS00] for more details.
  
  ---------------------------  Example  ----------------------------
    gap> IsBireversible(MealyMachine([[1,2],[2,1]],[(),(1,2)]));
    false
    gap> IsBireversible(MealyMachine([[1,1],[2,2]],[(),(1,2)]));
    true
  ------------------------------------------------------------------
  
  5.2-8 StateGrowth
  
  > StateGrowth( m[, x] ) ___________________________________________operation
  Returns:  The state growth of the Mealy machine or element m.
  
  This  function computes, as a rational function, the power series in x whose
  coefficient  of  degree  n is the number of non-trivial states at level n of
  the tree.
  
  If x is absent, it is assumed to be Indeterminate(Rationals).
  
  If  m  is  a  Mealy  machine,  this function is computed with respect to all
  possible starting states. If m is a Mealy element, this function is computed
  with respect to the initial state of m.
  
  ---------------------------  Example  ----------------------------
    gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states>
    gap> StateGrowth(b,Indeterminate(Rationals));
    (2)/(-x_1+1)
    gap> StateGrowth(FRElement(b,1),Indeterminate(Rationals));
    (1)/(-x_1+1)
  ------------------------------------------------------------------
  
  5.2-9 Degree
  
  > Degree( m ) _____________________________________________________operation
  > DegreeOfFRMachine( m ) __________________________________________operation
  > DegreeOfFRElement( m ) __________________________________________operation
  Returns:  The growth degree of the Mealy machine or element m.
  
  This  function computes the order of the pole at x=1 of StateGrowth(m,x), in
  case  its  denominator  is  a  product  of cyclotomics; and returns infinity
  otherwise.
  
  This attribute of Mealy machines was studied inter alia in [Sid00].
  
  ---------------------------  Example  ----------------------------
    gap> m := MealyMachine([[2,1],[3,2],[3,3]],[(),(1,2),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states>
    gap> StateGrowth(m,Indeterminate(Rationals));
    (-x_1+2)/(x_1^2-2*x_1+1)
    gap> List(StateSet(m),i->Degree(FRElement(m,i)));
    [ 2, 1, -1 ]
    gap> a := MealyMachine(Group((1,2)),Group((1,2)),\*,\*);
    <Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
    gap> Degree(a);
    infinity
  ------------------------------------------------------------------
  
  5.2-10 IsFinitaryFRElement
  
  > IsFinitaryFRElement( e ) _________________________________________property
  > IsFinitaryFRMachine( e ) _________________________________________property
  Returns:  true if e is a finitary element.
  
  This function tests whether e is a finitary element. These are by definition
  the elements of growth degree at most 0.
  
  When  applied  to  a  Mealy  machine, it returns true if all states of e are
  finitary.
  
  ---------------------------  Example  ----------------------------
    gap> m := GuptaSidkiMachines(3);; Display(m);
       |  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> Filtered(StateSet(m),i->IsFinitaryFRElement(FRElement(m,i)));
    [ 1, 2, 3 ]
    gap> IsFinitaryFRElement(m);
    false
  ------------------------------------------------------------------
  
  5.2-11 Depth
  
  > Depth( m ) ______________________________________________________attribute
  > DepthOfFRMachine( m ) ___________________________________________attribute
  > DepthOfFRElement( m ) ___________________________________________attribute
  Returns:  The depth of the finitary Mealy machine or element m.
  
  This  function  computes the maximal level at which the m has an non-trivial
  state.  In  particular the identity has depth 0, and FR elements acting only
  at  the root vertex have depth 1. The value infinity is returned if m is not
  finitary (see IsFinitaryFRElement (5.2-10)).
  
  ---------------------------  Example  ----------------------------
    gap> m := MealyMachine([[2,1],[3,3],[4,4],[4,4]],[(),(),(1,2),()]);
    <Mealy machine on alphabet [ 1, 2 ] with 4 states>
    gap> DepthOfFRMachine(m);
    infinity
    gap> List(StateSet(m),i->DepthOfFRElement(FRElement(m,i)));
    [ infinity, 2, 1, 0 ]
  ------------------------------------------------------------------
  
  5.2-12 IsBoundedFRElement
  
  > IsBoundedFRElement( e ) __________________________________________property
  > IsBoundedFRMachine( e ) __________________________________________property
  Returns:  true if e is a finitary element.
  
  This  function tests whether e is a bounded element. These are by definition
  the elements of growth degree at most 1.
  
  When  applied  to  a  Mealy  machine, it returns true if all states of e are
  bounded.
  
  ---------------------------  Example  ----------------------------
    gap> m := GuptaSidkiMachines(3);; Display(m);
       |  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> Filtered(StateSet(m),i->IsBoundedFRElement(FRElement(m,i)));
    [ 1, 2, 3, 4 ]
    gap> IsBoundedFRMachine(m);
    true
  ------------------------------------------------------------------
  
  5.2-13 IsPolynomialGrowthFRElement
  
  > IsPolynomialGrowthFRElement( e ) _________________________________property
  > IsPolynomialGrowthFRMachine( e ) _________________________________property
  Returns:  true if e is an element of polynomial growth.
  
  This  function  tests  whether  e  is  a  polynomial  element.  These are by
  definition the elements of polynomial growth degree.
  
  When  applied  to a Mealy machine, it returns true if all states of e are of
  polynomial growth.
  
  ---------------------------  Example  ----------------------------
    gap> m := GuptaSidkiMachines(3);; Display(m);
       |  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> Filtered(StateSet(m),i->IsPolynomialGrowthFRElement(FRElement(m,i)));
    [ 1, 2, 3, 4 ]
    gap> IsPolynomialGrowthFRMachine(m);
    true
  ------------------------------------------------------------------
  
  5.2-14 Signatures
  
  > Signatures( e ) _________________________________________________operation
  Returns:  A list describing the product of the activities on each level.
  
  This function computes the product of the activities of e on each level, and
  returns a periodic list describing it (see PeriodicList (12.1-6)).
  
  The  entries  pi are permutations, and their values are meaningful only when
  projected in the abelianization of VertexTransformationsFRElement(e).
  
  ---------------------------  Example  ----------------------------
    gap> Signatures(GrigorchukGroup.1);
    [ (1,2), / () ]
    gap> Signatures(GrigorchukGroup.2);
    [/ (), (1,2), (1,2) ]
    gap> last[50];
    (1,2)
    gap> Signatures(AddingMachine(3)[2]);
    [/ (1,2,3) ]
  ------------------------------------------------------------------
  
  5.2-15 VertexTransformationsFRMachine
  
  > VertexTransformationsFRMachine( m ) _____________________________operation
  > VertexTransformationsFRElement( e ) _____________________________operation
  Returns:  The group/monoid generated by all vertex transformations of states
            of m.
  
  The  first  function  computes the finite permutation group / transformation
  monoid generated by all outputs of states of m.
  
  The        second        command       is       a       short-hand       for
  VertexTransformationsFRMachine(UnderlyingFRMachine(e)).
  
  ---------------------------  Example  ----------------------------
    gap> m := MealyMachine([[1,3,2],[3,2,1],[2,1,3]],[(2,3),(1,3),(1,2)]);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states>
    gap> VertexTransformationsFRMachine(m);
    Group([ (2,3), (1,3), (1,2) ])
  ------------------------------------------------------------------
  
  5.2-16 FixedRay
  
  > FixedRay( e ) ___________________________________________________operation
  Returns:  The lexicographically first ray fixed by e.
  
  This function computes the lexicographically first infinite sequence that is
  fixed  by  the  FR  element  e,  and  returns  it  as  a  periodic list (see
  PeriodicList (12.1-6)). It returns fail if no such ray exists.
  
  ---------------------------  Example  ----------------------------
    gap> m := MealyMachine([[1,3,2],[3,2,1],[2,1,3]],[(2,3),(1,3),(1,2)]);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states>
    gap> FixedRay(FRElement(m,1));
    [/ 1 ]
    gap> last^FRElement(m,1);
    [/ 1 ]
    gap> FixedRay(FRElement(m,[1,2]));
    fail
  ------------------------------------------------------------------
  
  5.2-17 IsLevelTransitive
  
  > IsLevelTransitive( e ) ___________________________________________property
  Returns:  true if e acts transitively on each level of the tree.
  
  This  function  tests whether e acts transitively on each level of the tree.
  It is implemented only if VertexTransformationsFRElement(e) is abelian.
  
  This  function  is  used  as  a simple test to detect whether an element has
  infinite  order:  if  e  has  a  fixed  vertex v such that the State(e,v) is
  level-transitive, then e has infinite order.
  
  ---------------------------  Example  ----------------------------
    gap> m := AddingMachine(3);; Display(m);
       |  1     2     3
    ---+-----+-----+-----+
     a | a,1   a,2   a,3
     b | a,2   a,3   b,1
    ---+-----+-----+-----+
    Initial state:  b
    gap> IsLevelTransitive(m);
    true
    gap> IsLevelTransitive(Product(UnderlyingFRMachine(GrigorchukOverGroup){[2..5]}));
    true
  ------------------------------------------------------------------
  
  5.2-18 AsMealyMachine
  
  > AsMealyMachine( m ) _____________________________________________attribute
  Returns:  A Mealy machine isomorphic to m.
  
  This function constructs a Mealy machine r, which is as close as possible to
  the  FR machine m. Furthermore, Correspondence(r) is a list identifying, for
  every generator of the stateset of m, a corresponding state in the new Mealy
  machine; see Correspondence (3.5-11).
  
  m  may  be a group/monoid/semigroup FR machine, or a Mealy machine; in which
  case the result is returned unchanged.
  
  In  particular, FRElement(m,s) and FRElement(AsMealyMachine(m),s) return the
  same tree automorphism, for any FR machine m and any state s.
  
  This function is not guaranteed to return; if m does not have finite states,
  then it will loop forever.
  
  ---------------------------  Example  ----------------------------
    gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);
    <FR machine with alphabet [ 1 .. 2 ] on Group( [ tau, mu ] )>
    gap> Display(n);
         |     1         2
    -----+--------+---------+
     tau | <id>,2     tau,1
      mu | <id>,2   mu^-1,1
    -----+--------+---------+
    gap> AsMealyMachine(n);
    <Mealy machine on alphabet [ 1, 2 ] with 4 states>
    gap> Display(last);
       |  1     2
    ---+-----+-----+
     a | c,2   a,1
     b | c,2   d,1
     c | c,1   c,2
     d | b,2   c,1
    ---+-----+-----+
    gap> Correspondence(last);
    [ 1, 2 ]
  ------------------------------------------------------------------
  
  5.2-19 AsMealyMachine
  
  > AsMealyMachine( l ) _____________________________________________attribute
  Returns:  A Mealy machine constructed out of the FR elements in l.
  
  This  function  constructs a Mealy machine r, with states l (which must be a
  state-closed  set).  Its  outputs  are  the outputs of its elements, and its
  transitions   are   the   transitions   of   its  elements;  in  particular,
  FRElement(r,i) is equal to l[i] as an FR element.
  
  Correspondence(r) records the argument l.
  
  This function returns fail if l is not state-closed.
  
  ---------------------------  Example  ----------------------------
    gap>  mu := FRElement([[[],[-1]]],[(1,2)],[1]);
    <2|f1>
    gap>
    gap> States(mu);
    [ <2|f1>, <2|identity ...>, <2|f1^-1> ]
    gap> AsMealyMachine(last);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states>
    gap> Display(last);
       |  1     2
    ---+-----+-----+
     a | b,2   c,1
     b | b,1   b,2
     c | a,2   b,1
    ---+-----+-----+
  ------------------------------------------------------------------
  
  5.2-20 AsMealyElement
  
  > AsMealyElement( m ) _____________________________________________attribute
  Returns:  A Mealy element isomorphic to m.
  
  This  function  constructs  a  Mealy  element,  which  induces the same tree
  automorphism as the FR element m.
  
  m  may  be a group/monoid/semigroup FR element, or a Mealy element; in which
  case the result is returned unchanged.
  
  This function is not guaranteed to return; if m does not have finite states,
  then it will loop forever.
  
  ---------------------------  Example  ----------------------------
    gap> mu := FRElement([[[],[-1]]],[(1,2)],[1]);
    <2|f1>
    gap> AsMealyElement(mu);
    <Mealy machine on alphabet [ 1, 2 ] with 3 states, initial state 1>
    gap> [[2,1]]^last;
    [ [ 1, 2 ] ]
    gap> [2,1,2,1]^mu;
    [ 1, 2, 1, 2 ]
  ------------------------------------------------------------------
  
  5.2-21 AsIntMealyMachine
  
  > AsIntMealyMachine( m ) __________________________________________attribute
  > AsIntMealyElement( m ) __________________________________________attribute
  Returns:  A Mealy machine in integer format, isomorphic to m.
  
  This function constructs a Mealy machine r, which has similar behaviour as m
  while  having  stateset  [1..n] for some natural n. Most FR commands operate
  efficiently only on Mealy machines of this type.
  
  This function is not guaranteed to return; if m does not have finite states,
  then it will loop forever.
  
  ---------------------------  Example  ----------------------------
    gap> g := Group((1,2));; n := MealyMachine(g,g,\*,\*);
    <Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
    gap> Display(n);
           |      ()            (1,2)
    -------+-------------+-------------+
        () |    (),()      (1,2),(1,2)
     (1,2) | (1,2),(1,2)      (),()
    -------+-------------+-------------+
    gap> AsIntMealyMachine(n);
    <Mealy machine on alphabet [ 1, 2 ] with 2 states>
    gap> Display(last);
       |  1     2
    ---+-----+-----+
     a | a,1   b,2
     b | b,2   a,1
    ---+-----+-----+
    gap> Correspondence(last);
    [ 1, 2 ]
  ------------------------------------------------------------------
  
  5.2-22 TopElement
  
  > TopElement( p[, n] ) ____________________________________________attribute
  Returns:  A  Mealy  machine in integer format, acting on the first symbol of
            sequences.
  
  This  function  constructs  a  Mealy machine r, which acts as p on the first
  letter  of sequences and fixes the other letters. The argument n is the size
  of the alphabet of r; if it is ommitted, then it is assumed to be the degree
  of  the  transformation  p, or the largest moved point of the permutation or
  trans p.
  
  ---------------------------  Example  ----------------------------
    gap> a := TopElement((1,2));
    <Mealy element on alphabet [ 1, 2 ] with 2 states>
    gap> last=GrigorchukGroup.1;
    true
    gap> a := TopElement((1,2),3);
    <Mealy element on alphabet [ 1, 2, 3 ] with 2 states>
    gap> last in GuptaSidkiGroup;
    false
  ------------------------------------------------------------------
  
  5.2-23 ConfinalityClasses
  
  > ConfinalityClasses( e ) _________________________________________attribute
  > IsWeaklyFinitaryFRElement( e ) __________________________________attribute
  Returns:  A list describing the non-trivial confinality classes of e.
  
  If  e  is  a  bounded  element  (see IsBoundedFRElement (5.2-12)), there are
  finitely  many  infinite  sequences  that have confinality class larger that
  one;  i.e.  ultimately periodic sequences that are mapped by e to a sequence
  with  different  period. This function returns a list of equivalence classes
  of periodic lists, see PeriodicList (12.1-6), which are related under e.
  
  By  definition,  an  element  is  weakly finitary if it has no non-singleton
  confinality classes.
  
  ---------------------------  Example  ----------------------------
    gap> g := FRGroup("t=<,,t>(2,3)","u=<u,,>(1,2)","v=<u,t,>");;
    gap> ConfinalityClasses(g.1);
    [ {PeriodicList([  ],[ 2 ])} ]
    gap> List(GeneratorsOfGroup(g),x->Elements(ConfinalityClasses(x)[1]));
    [ [ [/ 2 ], [/ 3 ] ],
      [ [/ 1 ], [/ 2 ] ],
      [ [/ 1 ], [/ 2 ], [/ 3 ] ] ]
    gap> IsWeaklyFinitaryFRElement(BinaryAddingElement);
    false
    gap> IsWeaklyFinitaryFRElement(GuptaSidkiGroup.2);
    true
  ------------------------------------------------------------------
  
  5.2-24 Germs
  
  > Germs( e ) ______________________________________________________attribute
  > NormOfBoundedFRElement( e ) _____________________________________attribute
  Returns:  The germs of the bounded element e.
  
  The  germs  of  a  bounded element are the finitely many ultimately periodic
  sequences on which the state of e does not vanish. This function returns the
  germs  of  e,  as  a  list of pairs; the first entry is a ray described as a
  periodic  sequence  of  integers (see PeriodicList (12.1-6)), and the second
  entry is the periodic sequence of states that appear along that ray.
  
  The norm of a bounded element is the length of its list of germs.
  
  ---------------------------  Example  ----------------------------
    gap> Germs(BinaryAddingElement);
    [ [ [/ 2 ], [/ 1 ] ] ]
    gap> Germs(GrigorchukGroup.1);
    [  ]
    gap> Germs(GrigorchukGroup.2);
    [ [ [/ 2 ], [/ 1, 3, 5 ] ] ]
    gap> Display(GrigorchukGroup.2);
       |  1     2
    ---+-----+-----+
     a | b,1   c,2
     b | d,2   d,1
     c | b,1   e,2
     d | d,1   d,2
     e | d,1   a,2
    ---+-----+-----+
    Initial state: a
  ------------------------------------------------------------------
  
  5.2-25 HasOpenSetConditionFRElement
  
  > HasOpenSetConditionFRElement( e ) ________________________________property
  Returns:  true if e has the open set condition.
  
  An  FR element e has the open set condition if for every infinite ray in the
  tree which is fixed by e, there is an open set around that ray which is also
  fixed  by  e.  This  function tests for e to have the open set condition. It
  currently is implemented only for bounded elements.
  
  ---------------------------  Example  ----------------------------
    gap> HasOpenSetConditionFRElement(GrigorchukGroup.1);
    true
    gap> HasOpenSetConditionFRElement(GrigorchukGroup.2);
    false
  ------------------------------------------------------------------
  
  5.2-26 LimitMachine
  
  > LimitMachine( m ) _______________________________________________attribute
  Returns:  The submachine of m on all recurrent states.
  
  This  command creates a new Mealy machine, with stateset the limit states of
  m.
  
  ---------------------------  Example  ----------------------------
    gap> m := MealyMachine([[2,2,3],[2,3,3],[3,3,3]],[(),(),(1,2,3)]);
    <Mealy machine on alphabet [ 1 .. 3 ] with 3 states>
    gap> Display(m);
       |  1     2     3
    ---+-----+-----+-----+
     a | b,1   b,2   c,3
     b | b,1   c,2   c,3
     c | c,2   c,3   c,1
    ---+-----+-----+-----+
    gap> LimitStates(m);
    [ <Mealy element on alphabet [ 1 .. 3 ] with 2 states>,
      <Mealy element on alphabet [ 1 .. 3 ] with 1 state> ]
    gap> LimitMachine(m);
    <Mealy machine on alphabet [ 1 .. 3 ] with 2 states>
    gap> Display(last);
       |  1     2     3
    ---+-----+-----+-----+
     a | a,1   b,2   b,3
     b | b,2   b,3   b,1
    ---+-----+-----+-----+
  ------------------------------------------------------------------
  
  5.2-27 NucleusMachine
  
  > NucleusMachine( m ) _____________________________________________attribute
  Returns:  The nucleus of m.
  
  This   command   creates   a  new  Mealy  machine  n,  which  is  such  that
  LimitMachine(m*n)  is  isomorphic  to  n,  after  minimisation.  It  is also
  isomorphic  to  the  NucleusMachine  (7.2-18)  of  the  state closure of the
  SCSemigroup  (7.1-2)  of  m.  (Note  that  the ordering of the states in the
  resulting  machine  is not necessarily the same as in m; however, if m and n
  are isomorphic, then this command returns m).
  
  ---------------------------  Example  ----------------------------
    gap> m := MealyMachine([[2,1,1],[2,2,2]],[(1,2,3),()]);
    <Mealy machine on alphabet [ 1, 2, 3 ] with 2 states>
    gap> Display(m);
       |  1     2     3
    ---+-----+-----+-----+
     a | b,2   a,3   a,1
     b | b,1   b,2   b,3
    ---+-----+-----+-----+
    gap> NucleusMachine(m);
    <Mealy machine on alphabet [ 1, 2, 3 ] with 3 states>
    gap> Display(last);
       |  1     2     3
    ---+-----+-----+-----+
     a | a,1   a,2   a,3
     b | c,3   b,1   c,2
     c | a,2   c,3   c,1
    ---+-----+-----+-----+
  ------------------------------------------------------------------
  
  5.2-28 GuessMealyElement
  
  > GuessMealyElement( p, d, n ) ____________________________________operation
  Returns:  A Mealy element that probably has the same activity as p.
  
  This  function  receives a permutation or transformation p, a degree d and a
  level  n,  and attempts to find a Mealy element on the alphabet [1..d] whose
  activity on level n is p.
  
  This  function  returns  fail if it thinks that the given level is not large
  enough  to  make  a  reasonable  guess.  In  all  cases, the function is not
  guaranteed to return the correct Mealy machine.
  
  ---------------------------  Example  ----------------------------
    gap> GuessMealyElement(Activity(GrigorchukGroup.2,6),2,6);
    <Mealy element on alphabet [ 1, 2 ] with 5 states>
    gap> last=GrigorchukGroup.2;
    true
    gap> GuessMealyElement(Activity(GrigorchukGroup.2,5),2,5);
    fail
    gap> ComposeElement([GrigorchukGroup.2,One(GrigorchukGroup)],());
    <Mealy element on alphabet [ 1, 2 ] with 6 states>
    gap> last=GuessMealyElement(Activity(GrigorchukGroup.2,6),2,7);
    true
  ------------------------------------------------------------------