groups.tex

% This file was created automatically from groups.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Properties and operations with groups and semigroups}

In this chapter we present the functionality applicable to groups and semigroups.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Creation of groups and semigroups}

\>AutomatonGroup( <string>[, <bind_vars>] ) O
\>AutomatonGroup( <list>[, <names>, <bind_vars>] ) O
\>AutomatonGroup( <automaton>[, <bind_vars>] ) O

Creates the self-similar group generated by the finite automaton, described by <string>
or <list>, or by the argument <automaton>.

The argument <string> is a conventional notation of the form
`name1=(name11,name12,...,name1d)perm1, name2=...'
where each `name\*' is a name of a state or `1', and each `perm\*' is a
permutation written in {\GAP} notation. Trivial permutations may be
omitted. This function ignores whitespace, and states may be separated
by commas or semicolons.

The argument <list> is a list consisting of $n$ entries corresponding to $n$ states of an automaton.
Each entry is of the form $[a_1,\.\.\.,a_d,p]$,
where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are `IsInt' in
$\{1,\ldots,n\}$ and
represent the sections of the corresponding state at all vertices of the first level of the tree;
and $p$ from `SymmetricGroup(<d>)' describes the action of the corresponding state on the
alphabet.

The optional argument <names> must be a list of names of generators of the group, corresponding to the
states of the automaton.
These names are used to display elements of the resulting group.

If the optional argument <bind_vars> is `false' the names of generators of the group are not assigned
to the global variables. The default value is `true'. One can use
`AssignGeneratorVariables' function to assign these names later, if they were not assigned
when the group was created.

\beginexample
gap> AutomatonGroup("a=(a,b), b=(a, b)(1,2)");
< a, b >
gap> AutomatonGroup("a=(b,a,1)(2,3), b=(1,a,b)(1,2,3)");
< a, b >
gap> A := MealyAutomaton("a=(b,1)(1,2), b=(a,1)");
<automaton>
gap> G := AutomatonGroup(A);
< a, b >
\endexample

In the second form of this operation the definition of the first group
looks like
\beginexample
gap> AutomatonGroup([ [ 1, 2, ()], [ 1, 2, (1,2) ] ], [ "a", "b" ]);
< a, b >
\endexample


\>AutomatonSemigroup( <string>[, <bind_vars>] ) O
\>AutomatonSemigroup( <list>[, <names>, <bind_vars>] ) O
\>AutomatonSemigroup( <automaton>[, <bind_vars>] ) O

Creates the semigroup generated by the finite automaton, described by <string>
or <list>, or by the argument <automaton>.

The argument <string> is a conventional notation of the form
`name1=(name11,name12,...,name1d)trans1, name2=...'
where each `name\*' is a name of a state or `1', and each `trans\*' is either a
permutation written in {\GAP} notation, or a list defining a transformation
of the alphabet via `Transformation(trans\*)'. Trivial permutations may be
omitted. This function ignores whitespace, and states may be separated
by commas or semicolons.

The argument <list> is a list consisting of $n$ entries corresponding to $n$ states of the automaton.
Each entry is of the form $[a_1,...,a_d,p]$,
where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are `IsInt' in
$\{1,\ldots,n\}$ and
represent the sections of the corresponding state at all vertices of the first level of the tree;
and $p$ is a transformation of the alphabet describing the action of the corresponding
state on the alphabet.

The optional arguments <names> and <bind_vars> have the same meaning as in `AutomatonGroup' (see "AutomatonGroup").

\beginexample
gap> AutomatonSemigroup("a=(a, b)[2,2], b=(a,b)(1,2)");
< a, b >
gap> AutomatonSemigroup("a=(b,a,1)[1,1,3], b=(1,a,b)(1,2,3)");
< 1, a, b >
gap> A := MealyAutomaton("f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]");
<automaton>
gap> G := AutomatonSemigroup(A);
< f0, f1 >
\endexample
In the second form of this operation the definition of the second semigroup
looks like
\beginexample
gap> AutomatonSemigroup([ [1,2,Transformation([2,2])], [ 1,2,(1,2)] ], ["a","b"]);
< a, b >
\endexample



\>SelfSimilarGroup( <string>[, <bind_vars>] ) O
\>SelfSimilarGroup( <list>[, <names>, <bind_vars>] ) O
\>SelfSimilarGroup( <automaton>[, <bind_vars>] ) O

Creates the self-similar group generated by the wreath recursion, described by <string>
or <list>, or given by the argument <automaton>.

The argument <string> is a conventional notation of the form
`name1=(word11,word12,...,word1d)perm1, name2=...'
where each `name\*' is a name of a state, `word\*' is an associative word
over the alphabet consisting of all `name\*', and each `perm\*' is a
permutation written in {\GAP} notation. Trivial permutations may be
omitted. This function ignores whitespace, and states may be separated
by commas or semicolons.

The argument <list> is a list consisting of $n$ entries corresponding to $n$ generators of the group.
Each entry is of the form $[a_1,\.\.\.,a_d,p]$,
where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are lists
acceptable by `AssocWordByLetterRep' (e.g. if the names of generators are `x', `y' and `z',
then `[1, 1, -2, -2, 1, 3]' will produce `x^2*y^-2*x*z')
representing the sections of the corresponding generator at all vertices of the first level of the tree;
and $p$ from `SymmetricGroup(<d>)' describes the action of the corresponding generator on the
alphabet.

The optional argument <names> must be a list of names of generators of the group.
These names are used to display the elements of the resulting group.

If the optional argument <bind_vars> is `false' the names of generators of the group are not assigned
to the global variables. The default value is `true'. One can use
`AssignGeneratorVariables' function to assign these names later, if they were not assigned
when the group was created.

\beginexample
gap> SelfSimilarGroup("a=(a*b, b^-1), b=(1, b^2*a)(1,2)");
< a, b >
gap> SelfSimilarGroup("a=(b,a,a^-1)(2,3), b=(1,a*b,b)(1,2,3)");
< a, b >
gap> A := MealyAutomaton("f0=(f0,f0)(1,2),f1=(f1,f0)");
<automaton>
gap> SelfSimilarGroup(A);
< f0, f1 >
\endexample
In the second form of this operation the definition of the first group
looks like
\beginexample
gap> SelfSimilarGroup([[ [1,2], [-2], ()], [ [], [2,2,1], (1,2) ]], ["a","b"]);
< a, b >
\endexample


\>SelfSimilarSemigroup( <string>[, <bind_vars>] ) O
\>SelfSimilarSemigroup( <list>[, <names>, <bind_vars>] ) O
\>SelfSimilarSemigroup( <automaton>[, <bind_vars>] ) O

Creates the semigroup generated by the wreath recursion, described by <string>
or <list>, or given by the argument <automaton>. Note, that on the contrary to
`AutomatonSemigroup' ("AutomatonSemigroup") in some cases the defined semigroup
may not be self-similar, since the sections of generators may include inverses of
generators or trivial homomorphisms, not included in the semigroup generated by the
generators. If one needs to have self-similarity it is always possible to include the
necessary sections in the generating set.

The argument <string> is a conventional notation of the form
`name1=(word11,word12,...,word1d)trans1, name2=...'
where each `name\*' is a name of a state, `word\*' is an associative word
over the alphabet consisting of all `name\*', and each `trans\*' is either a
permutation written in {\GAP} notation, or a list defining a transformation
of the alphabet via `Transformation(trans\*)'. Trivial permutations may be
omitted. This function ignores whitespace, and states may be separated
by commas or semicolons.

The argument <list> is a list consisting of $n$ entries corresponding to $n$ generators of the semigroup.
Each entry is of the form $[a_1,\.\.\.,a_d,p]$,
where $d \geq 2$ is the size of the alphabet the semigroup acts on, $a_i$ are lists
acceptable by `AssocWordByLetterRep' (e.g. if the names of generators are `x', `y' and `z',
then `[1, 1, 2, 3]' will produce `x^2*y*z')
representing the sections of the corresponding generator at all vertices of the first level of the tree;
and $p$ is a transformation of the alphabet describing the action of the corresponding
generator.

The optional arguments <names> and <bind_vars> have the same meaning as in `SelfSimilarGroup' (see "SelfSimilarGroup").

\beginexample
gap> SelfSimilarSemigroup("a=(a*b,b)[1,1], b=(a,b^2*a)(1,2)");
< a, b >
gap> SelfSimilarSemigroup("a=(b,a,a^3)(2,3), b=(1,a*b,b^-1)(1,2,3)");
< a, b >
gap> A := MealyAutomaton("f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]");
<automaton>
gap> SelfSimilarSemigroup(A);
< f0, f1 >
\endexample
In the second form of this operation the definition of the first semigroup
looks like
\beginexample
gap> SelfSimilarSemigroup([[[1,2], [2], ()], [[1], [2,2,1], (1,2)]],["a","b"]);
< a, b >
\endexample



\>IsTreeAutomorphismGroup( <G> ) C

The category of groups of tree automorphisms.


\>IsAutomGroup( <G> ) C

The category of groups generated by finite invertible initial automata
(elements from category `IsAutom').


\>IsAutomatonGroup( <G> ) P

is `true' if <G> is created using the command `AutomatonGroup' ("AutomatonGroup")
or if the generators of <G> coincide with the generators of the corresponding family, and `false' otherwise.
To test whether <G> is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command.


\>IsSelfSimGroup( <G> ) C

The category of groups whose generators are defined using wreath recursion
(elements from category `IsSelfSim'). These groups need not be self-similar.


\>IsSelfSimilarGroup( <G> ) P

is `true' if <G> is created using the command `SelfSimilarGroup' ("SelfSimilarGroup")
or if the generators of <G> coincide with the generators of the corresponding family, and `false' otherwise.
To test whether <G> is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Basic properties of groups and semigroups}

\>TopDegreeOfTree( <obj> ) A

Returns the degree of the tree on the first level, i.e. the number of vertices
adjacent to the root vertex.


\>DegreeOfTree( <obj> ) A

This is a synonym for TopDegreeOfTree~("TopDegreeOfTree") for the case of
a regular tree. It is an error to call this method for an object which acts
on a non-regular tree.


\>IsFractal( <G> ) P

Returns whether the group <G> is fractal (also called as <self-replicating>). In other
words, if <G> acts transitively on the first level and for any vertex $v$ of the tree
the projection of the stabilizer of $v$ in <G>
on this vertex coincides with the whole group <G>.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> IsFractal(Grigorchuk_Group);
true
\endexample


\>IsFractalByWords( <G> ) P

Computes the generators of stabilizers of vertices of the first level
and their projections on these vertices. Returns `true' if  the preimages of these
projections in the free group under the canonical epimorphism generate the whole free
group for each stabilizer, and the <G> acts transitively on the first level.
This is sufficient but not necessary condition for <G> to be fractal. See also
`IsFractal' ("IsFractal").


\>`IsSphericallyTransitive( <G> )'{IsSphericallyTransitive}!{[treehomsg]} P

Returns whether the group <G> is spherically transitive (see~"Short math background").
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> IsSphericallyTransitive(Grigorchuk_Group);
true
\endexample


\>ContainsSphericallyTransitiveElement( <G> ) A

For a self-similar group <G> acting on a binary tree returns `true' if <G> contains
an element acting spherically transitively on the levels of the tree and `false'
otherwise. See also `SphericallyTransitiveElement' ("SphericallyTransitiveElement").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> ContainsSphericallyTransitiveElement(Basilica);
true
gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)");
< a, b >
gap> ContainsSphericallyTransitiveElement(G);
false
\endexample


\>`IsTransitiveOnLevel( <G>, <lev> )'{IsTransitiveOnLevel}!{[treehomsg]} O

Returns whether the group (semigroup) <G> acts transitively on level <lev>.

\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> IsTransitiveOnLevel(Group([a,b]),3);
true
gap> IsTransitiveOnLevel(Group([a,b]),4);
false
\endexample


\>IsSelfSimilar( <G> ) P

Returns whether the group or semigroup <G> is self-similar (see "Short math background").


\>IsContracting( <G> ) A

Given a self-similar group <G> tries to compute whether it is contracting or not.
Only a partial method is implemented (since there is no general algorithm so far).
First it tries to find the nucleus up to size 50 using `FindNucleus'(<G>,50) (see~"FindNucleus"), then
it tries to find evidence that the group is noncontracting using
`IsNoncontracting'(<G>,10,10) (see~"IsNoncontracting"). If the answer was not found one can try to use
`FindNucleus' and `IsNoncontracting' with bigger parameters.  Also one can use
`SetInfoLevel(InfoAutomGrp, 3)' for more information to be displayed.

\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> IsContracting(Basilica);
true
gap> IsContracting(AutomatonGroup("a=(c,a)(1,2), b=(c,b), c=(b,a)"));
false
\endexample


\>IsNoncontracting( <G>[, <max_len>, <depth>] ) F

Tries to show that the group <G> is not contracting.
Enumerates the elements of the group <G> up to length <max_len>
until it finds an element which has a section <g> of infinite order, such that
`OrderUsingSections'(<g>, <depth>) (see "OrderUsingSections")
returns `infinity' and such that <g> stabilizes some vertex and has itself as a
section at this vertex. See also `IsContracting'~("IsContracting").

If <max_len> and <depth> are omitted they are assumed to be `infinity' and 10, respectively.

If `InfoLevel' of `InfoAutomGrp' is greater than
or equal to 3 (one can set it by `SetInfoLevel( InfoAutomGrp, 3)'), then the proof
is printed.

\beginexample
gap> G := AutomatonGroup("a=(b,a)(1,2), b=(c,b), c=(c,a)");
< a, b, c >
gap> IsNoncontracting(G);
true
gap> H := AutomatonGroup("a=(c,b)(1,2), b=(b,a), c=(a,a)");
< a, b, c >
gap> SetInfoLevel(InfoAutomGrp, 3);
gap> IsNoncontracting(H);
#I  There are 37 elements of length up to 2
#I  There are 187 elements of length up to 3
#I  a^2*c^-1*b^-1 is obtained from (a^2*c^-1*b^-1)^2
    by taking sections and cyclic reductions at vertex [ 1, 1 ]
#I  a^2*c^-1*b^-1 has b*c*a^-2 as a section at vertex [ 2 ]
true
\endexample


\>IsGeneratedByAutomatonOfPolynomialGrowth( <G> ) P

For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup")
determines whether this automaton has polynomial growth in terms of Sidki~\cite{Sid00}.

See also operations `IsGeneratedByBoundedAutomaton' ("IsGeneratedByBoundedAutomaton") and
`PolynomialDegreeOfGrowthOfUnderlyingAutomaton' ("PolynomialDegreeOfGrowthOfUnderlyingAutomaton").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> IsGeneratedByAutomatonOfPolynomialGrowth(Basilica);
true
gap> D := AutomatonGroup( "a=(a,b)(1,2), b=(b,a)" );
< a, b >
gap> IsGeneratedByAutomatonOfPolynomialGrowth(D);
false
\endexample


\>IsGeneratedByBoundedAutomaton( <G> ) P

For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup")
determines whether this automaton is bounded in terms of Sidki~\cite{Sid00}.

See also `IsGeneratedByAutomatonOfPolynomialGrowth' ("IsGeneratedByAutomatonOfPolynomialGrowth")
and `PolynomialDegreeOfGrowthOfUnderlyingAutomaton' ("PolynomialDegreeOfGrowthOfUnderlyingAutomaton").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> IsGeneratedByBoundedAutomaton(Basilica);
true
gap> C := AutomatonGroup("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)");
< a, b, c >
gap> IsGeneratedByBoundedAutomaton(C);
false
\endexample


\>PolynomialDegreeOfGrowthOfUnderlyingAutomaton( <G> ) A

For a group <G> generated by all states of a finite automaton (see "IsAutomatonGroup")
of polynomial growth in terms of Sidki~\cite{Sid00} determines the degree of
polynomial growth of this automaton. This degree is 0 if and only if the automaton is bounded.
If the growth of automaton is exponential returns `fail'.

See also `IsGeneratedByAutomatonOfPolynomialGrowth' ("IsGeneratedByAutomatonOfPolynomialGrowth")
and `IsGeneratedByBoundedAutomaton' ("IsGeneratedByBoundedAutomaton").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> PolynomialDegreeOfGrowthOfUnderlyingAutomaton(Basilica);
0
gap> C := AutomatonGroup("a=(a,b)(1,2), b=(b,c), c=(c,1)(1,2)");
< a, b, c >
gap> PolynomialDegreeOfGrowthOfUnderlyingAutomaton(C);
2
\endexample


\>IsOfSubexponentialGrowth( <G>[, <len>, <depth>] ) O

Tries to check whether the growth function of a self-similar group <G> is subexponential.
The main part of the algorithm works as follows. It looks at all words of length up to <len>
and if for some length $l$ for each word of this length $l$ the sum of the lengths of
all its sections at level <depth> is less then $l$, returns `true'. The default values of
<len> and <depth> are 10 and 6 respectively. Setting `SetInfoLevel(InfoAtomGrp, 3)' will make it
print for each length the words that are not contracted.  It also sometimes helps to use
`AG_UseRewritingSystem' (see "AG_UseRewritingSystem").

\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> AG_UseRewritingSystem(Grigorchuk_Group);
gap> IsOfSubexponentialGrowth(Grigorchuk_Group,10,6);
true
\endexample


\>IsAmenable( <G> ) P

In certain cases (for groups generated by bounded automata~\cite{BKNV05},
some virtually abelian groups or finite groups) returns `true' if <G> is
amenable.

\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> IsAmenable(Grigorchuk_Group);
true
\endexample


\>UnderlyingAutomaton( <G> ) A

For a group (or semigroup) <G> returns an automaton generating a
self-similar group (or semigroup) containing <G>.
\beginexample
gap> GS := AutomatonSemigroup("x=(x,y)[1,1], y=(y,y)(1,2)");
< x, y >
gap> A := UnderlyingAutomaton(GS);
<automaton>
gap> Display(A);
a1 = (a1, a2)[ 1, 1 ], a2 = (a2, a2)[ 2, 1 ]
\endexample
For a subgroup of Basilica group we get the automaton generating Basilica group.
\beginexample
gap> H := Group([u*v^-1,v^2]);
< u*v^-1, v^2 >
gap> Display(UnderlyingAutomaton(H));
a1 = (a1, a1), a2 = (a3, a1)(1,2), a3 = (a2, a1)
\endexample


\>`AutomatonList( <G> )'{AutomatonList}!{[automsg]} AM

Returns an `AutomatonList' of `UnderlyingAutomaton'(<G>) (see "UnderlyingAutomaton").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> AutomatonList(Basilica);
[ [ 2, 5, (1,2) ], [ 1, 5, () ], [ 5, 4, (1,2) ], [ 3, 5, () ], [ 5, 5, () ] ]
\endexample


\>`RecurList( <G> )'{RecurList}!{[selfsimsg]} AM

Returns an internal representation of the wreath recursion of the
self-similar group (semigroup) containing <G>.
\beginexample
gap> R := SelfSimilarGroup("a=(a^-1*b,b^-1*a)(1,2), b=(a^-1,b^-1)");
< a, b >
gap> RecurList(R);
[ [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ -1 ], [ -2 ], () ],
  [ [ -1, 2 ], [ -2, 1 ], (1,2) ], [ [ 1 ], [ 2 ], () ] ]
\endexample




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations with groups and semigroups}

\>PermGroupOnLevel( <G>, <k> ) O

Returns the group of permutations induced by the action of the group <G> at the <k>-th
level.
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> PermGroupOnLevel(Basilica, 4);
Group([ (1,11,3,9)(2,12,4,10)(5,13)(6,14)(7,15)(8,16), (1,6,2,5)(3,7)(4,8) ])
gap> H := PermGroupOnLevel(Group([u,v^2]),4);
Group([ (1,11,3,9)(2,12,4,10)(5,13)(6,14)(7,15)(8,16), (1,2)(5,6) ])
gap> Size(H);
64
\endexample


\>TransformationSemigroupOnLevel( <G>, <k> ) O

Returns the semigroup of transformations induced by the action of the semigroup <G> at the <k>-th
level.
\beginexample
gap> S := AutomatonSemigroup("y=(1,u)[1,1],u=(y,u)(1,2)");
< 1, y, u >
gap> T := TransformationSemigroupOnLevel(S,3);
<transformation monoid on 8 pts with 2 generators>
gap> Size(T);
11
\endexample


\>StabilizerOfLevel( <G>, <k> ) O

Returns the stabilizer of the <k>-th level.
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> StabilizerOfLevel(Basilica, 2);
< u^2, v^2, u*v^2*u^-1, v*u^2*v^-1, u*v*u^2*v^-1*u^-1, (v*u)^2*(v^-1*u^-1)^2, v*u*\
v^2*u^-1*v^-1, (u*v)^2*u*v^-1*u^-1*v^-1, (u*v)^2*v*u^-1*v^-1*u^-1 >
\endexample


\>StabilizerOfFirstLevel( <G> ) A

Returns the stabilizer of the first level, see also~"StabilizerOfLevel".
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> StabilizerOfFirstLevel(Basilica);
< v, u^2, u*v*u^-1 >
\endexample


\>StabilizerOfVertex( <G>, <v> ) O

Returns the stabilizer of the vertex <v>. Here <v> can be a list representing a
vertex, or a positive integer representing a vertex at the first level.
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> StabilizerOfVertex(Basilica, [1,2,1]);
< u^2, u*v*u^-1, v^2, v*u*v*u^-1*v^-1, v*u^-1*v*u*v^-1, v*u^4*v^-1, v*u^2*v^2*u^-2\
*v^-1, (v*u^2)^2*v^-1*u^-2*v^-1, v*u*(u*v)^2*u^-1*v^-1*u^-2*v^-1 >
\endexample


\>FixesLevel( <obj>, <lev> ) O

Returns whether <obj> fixes level <lev>, i.e. fixes every vertex at the level
<lev>.


\>FixesVertex( <obj>, <v> ) O

Returns whether <obj> fixes the vertex <v>. The vertex <v> may be given as a list, or as
a positive integer, in which case it denotes the <v>-th vertex at the first
level.


\>Projection( <G>, <v> ) O
\>ProjectionNC( <G>, <v> ) O

Returns the projection of the group <G> at the vertex <v>. The group <G> must fix the
vertex <v>, otherwise `Error'() will be called. The operation `ProjectionNC' does the
same thing, except it does not check whether <G> fixes the vertex <v>.
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> Projection(StabilizerOfVertex(Basilica, [1,2,1]), [1,2,1]);
< u, v >
\endexample


\>ProjStab( <G>, <v> ) O

Returns the projection of the stabilizer of <v> at itself. It is a shortcut for
`Projection'(`StabilizerOfVertex'(G, v), v) (see "Projection",
"StabilizerOfVertex").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> ProjStab(Basilica, [1,2,1]);
< u, v >
\endexample


\>FindGroupRelations( <G>[, <max_len>, <max_num_rels>] ) O
\>FindGroupRelations( <subs_words>[, <names>, <max_len>, <max_num_rels>] ) O

Finds group relations between the generators of the group <G>
or in the group generated by <subs_words>. Stops after investigating all words
of length up to <max_len> elements or when it finds <max_num_rels>
relations. The optional argument <names> is a list of names of generators of the same length
as <subs_words>. If this argument is given the relations are given in terms of these names.
Otherwise they are given in terms of the elements of the group generated by <subs_words>.
If <max_len> or <max_num_rels> are not specified, they are assumed to be `infinity'.
Note that if the rewring system (see "AG_UseRewritingSystem") for group <G> is used, then this operation
returns relations not contained in the rewriting system rules (see "AG_RewritingSystemRules").
This operation can be applied to any group, not only to a group generated by automata.
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> FindGroupRelations(Basilica, 6);
v*u*v*u^-1*v^-1*u*v^-1*u^-1
v*u^2*v^-1*u^2*v*u^-2*v^-1*u^-2
v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1
[ v*u*v*u^-1*v^-1*u*v^-1*u^-1, v*u^2*v^-1*u^2*v*u^-2*v^-1*u^-2,
  v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1 ]
gap> FindGroupRelations([u*v^-1, v*u], ["x", "y"], 5);
y*x^2*y*x^-1*y^-2*x^-1
[ y*x^2*y*x^-1*y^-2*x^-1 ]
gap> FindGroupRelations([u*v^-1, v*u], 5);
u^-2*v*u^-2*v^-1*u^2*v*u^2*v^-1
[ u^-2*v*u^-2*v^-1*u^2*v*u^2*v^-1 ]
gap> FindGroupRelations([(1,2)(3,4), (1,2,3)], ["x", "y"]);
x^2
y^-3
(y^-1*x)^3
[ x^2, y^-3, (y^-1*x)^3 ]
\endexample


\>FindSemigroupRelations( <G>[, <max_len>, <max_num_rels>] ) O
\>FindSemigroupRelations( <subs_words>[, <names>, <max_len>, <max_num_rels>] ) O

Finds semigroup relations between the generators of the group or semigroup <G>,
or in the semigroup generated by <subs_words>. The arguments have the same meaning
as in `FindGroupRelations'~("FindGroupRelations"). It returns a list of pairs of equal words.
In order to make the list of relations shorter
it also tries to remove relations that can
be derived from the known ones. Note, that by default the trivial automorphism is
not included in every semigroup. So if one needs to find relations of the form
$w=1$ one has to define <G> as a monoid or to include the trivial automorphism
into <subs_words> (for instance, as `One(g)' for any element `g' acting on the same
tree).
This operation can be applied for any semigroup, not only for a semigroup generated by automata.
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> FindSemigroupRelations([u*v^-1, v*u], ["x", "y"], 6);
y*x^2*y=x*y^2*x
y*x^3*y^2=x^2*y^3*x
y^2*x^3*y=x*y^3*x^2
[ [ y*x^2*y, x*y^2*x ], [ y*x^3*y^2, x^2*y^3*x ], [ y^2*x^3*y, x*y^3*x^2 ] ]
gap> FindSemigroupRelations([u*v^-1, v*u],6);
v*u^2*v^-1*u^2 = u^2*v*u^2*v^-1
v*u*(u*v^-1)^2*u^2*v*u = u*v^-1*u*(u*v)^2*u^2*v^-1
(v*u)^2*(u*v^-1)^2*u^2 = u*(u*v)^2*u*(u*v^-1)^2
[ [ v*u^2*v^-1*u^2, u^2*v*u^2*v^-1 ],
  [ v*u*(u*v^-1)^2*u^2*v*u, u*v^-1*u*(u*v)^2*u^2*v^-1 ],
  [ (v*u)^2*(u*v^-1)^2*u^2, u*(u*v)^2*u*(u*v^-1)^2 ] ]
gap> x := Transformation([1,1,2]);;
gap> y := Transformation([2,2,3]);;
gap> FindSemigroupRelations([x,y],["x","y"]);
y*x=x
y^2=y
x^3=x^2
x^2*y=x*y
[ [ y*x, x ], [ y^2, y ], [ x^3, x^2 ], [ x^2*y, x*y ] ]
\endexample




\>Iterator( <G>[, <max_len>] ) M

Provides a possibility to loop over elements of a group (semigroup, monoid)
generated by automata. If <max_len>  is given, it stops after enumerating all elements
of length up to <max_len>.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> iter := Iterator(Grigorchuk_Group, 5);
<iterator>
gap> l:=[];;
gap> for g in iter do
>      if Order(g)=16 then Add(l,g); fi;
>    od;
gap> l;
[ b*a, a*b, d*a*c, c*a*d, d*a*c*a, d*a*b*a, c*a*d*a, b*a*d*a, a*d*a*c,
  a*d*a*b, a*c*a*d, a*b*a*d, c*a*c*a*b, c*a*b*a*b, b*a*c*a*c, b*a*b*a*c,
  a*d*a*c*a, a*c*a*d*a ]
\endexample

\>FindElement( <G>, <func>, <val>, <max_len> ) O
\>FindElements( <G>, <func>, <val>, <max_len> ) O

The first function enumerates elements of the group (semigroup, monoid) <G> until it finds
an element $g$ of length at most <max_len>, for which <func>($g$)=<val>. Returns $g$ if
such an element was found and `fail' otherwise.

The second function enumerates elements of the group (semigroup, monoid) of length at most <max_len>
and returns the list of elements $g$, for which <func>($g$)=<val>.

These functions are based on `Iterator' operation (see "Iterator"), so can be applied in
more general settings whenever \GAP\ knows how to solve word problem in the group.
The following example illustrates how to find an element of order 16 in
Grigorchuk group and the list of all such elements of length at most 5.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> FindElement(Grigorchuk_Group, Order, 16, 5);
a*b
gap> FindElements(Grigorchuk_Group,Order,16,5);
[ a*b, b*a, c*a*d, d*a*c, a*b*a*d, a*c*a*d, a*d*a*b, a*d*a*c, b*a*d*a, c*a*d*a,
  d*a*b*a, d*a*c*a, a*c*a*d*a, a*d*a*c*a, (b*a)^2*c, b*(a*c)^2, c*(a*b)^2,
  (c*a)^2*b ]
\endexample


\>FindElementOfInfiniteOrder( <G>, <max_len>, <depth> ) O
\>FindElementsOfInfiniteOrder( <G>, <max_len>, <depth> ) O

The first function enumerates elements of the group <G> up to length <max_len>
until it finds an element $g$ of infinite order, such that
`OrderUsingSections'($g$,<depth>) (see "OrderUsingSections") is `infinity'.
In other words all sections of every element up to depth <depth> are
investigated. In case if the element belongs to the group generated by bounded
automaton (see "IsGeneratedByBoundedAutomaton") one can set <depth> to be `infinity'.

The second function returns the list of all such elements up to length <max_len>.

\beginexample
gap> G := AutomatonGroup("a=(1,1)(1,2), b=(a,c), c=(b,1)");
< a, b, c >
gap> FindElementOfInfiniteOrder(G, 5, 10);
a*b*c
\endexample


\>SphericallyTransitiveElement( <G> ) A

For a self-similar group <G> acting on a binary tree returns
an element of <G> acting spherically transitively on the levels of the tree if
such an element exists and `fail'
otherwise. See also `ContainsSphericallyTransitiveElement'
("ContainsSphericallyTransitiveElement").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> SphericallyTransitiveElement(Basilica);
u*v
gap> G := SelfSimilarGroup("a=(a^-1*b^-1,1)(1,2), b=(b^-1,a*b)");
< a, b >
gap> SphericallyTransitiveElement(G);
fail
\endexample


\>Growth( <G>, <max_len> ) O

Returns a list of the first values of the growth function of a group
(semigroup, monoid) <G>.
If <G> is a monoid it computes the growth function at $\{0,1,\ldots,<max_len>\}$,
and for a semigroup without identity at $\{1,\ldots,<max_len>\}$.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> Growth(Grigorchuk_Group, 7);
There are 11 elements of length up to 2
There are 23 elements of length up to 3
There are 40 elements of length up to 4
There are 68 elements of length up to 5
There are 108 elements of length up to 6
There are 176 elements of length up to 7
[ 1, 5, 11, 23, 40, 68, 108, 176 ]
gap> H := AutomatonSemigroup("a=(a,b)[1,1], b=(b,a)(1,2)");
< a, b >
gap> Growth(H,6);
[ 2, 6, 14, 30, 62, 126 ]
\endexample


\>ListOfElements( <G>, <max_len> ) O

Returns the list of all different elements of a group (semigroup, monoid)
<G> up to length <max_len>.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> ListOfElements(Grigorchuk_Group, 3);
[ 1, a, b, c, d, a*b, a*c, a*d, b*a, c*a, d*a, a*b*a, a*c*a, a*d*a, b*a*b,
  b*a*c, b*a*d, c*a*b, c*a*c, c*a*d, d*a*b, d*a*c, d*a*d ]
\endexample


\>FindNucleus( <G>[, <max_nucl>, <print_info>] ) O

Given a self-similar group <G> it tries to find its nucleus. If <G>
is not contracting it will loop forever. When it finds the nucleus it returns
the triple [`GroupNucleus'(<G>), `GeneratingSetWithNucleus'(<G>),
`GeneratingSetWithNucleusAutom'(<G>)] (see "GroupNucleus", "GeneratingSetWithNucleus",
"GeneratingSetWithNucleusAutom").

If <max_nucl> is given it stops after finding <max_nucl> elements that need to be in
the nucleus and returns `fail' if the nucleus was not found.

An optional argument <print_info> is a boolean telling whether to print results of
intermediate computations. The default value is `true'.

Use `IsNoncontracting'~(see "IsNoncontracting") to try to show that <G> is
noncontracting.

\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> FindNucleus(Basilica);
Trying generating set with 5 elements
Elements added:[ u^-1*v, v^-1*u ]
Trying generating set with 7 elements
[ [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ],
  [ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ], <automaton> ]
\endexample


\>LevelOfFaithfulAction( <G> ) A
\>LevelOfFaithfulAction( <G>, <max_lev> ) A

For a given finite self-similar group <G> determines the smallest level of
the tree, where <G> acts faithfully, i.e. the stabilizer of this level in <G>
is trivial. The idea here is that for a self-similar group all nontrivial level
stabilizers are different. If <max_lev> is given it finds only first <max_lev>
quotients by stabilizers and if all of them have different size it returns `fail'.
If <G> is infinite and <max_lev> is not specified it will loop forever.

See also `IsomorphismPermGroup' ("IsomorphismPermGroup").
\beginexample
gap> H := SelfSimilarGroup("a=(a,a)(1,2), b=(a,a), c=(b,a)(1,2)");
< a, b, c >
gap> LevelOfFaithfulAction(H);
3
gap> Size(H);
16
gap> Adding_Machine := AutomatonGroup("a=(1,a)(1,2)");
< a >
gap> LevelOfFaithfulAction(Adding_Machine, 10);
fail
\endexample


\>IsomorphismPermGroup( <G> ) O
\>IsomorphismPermGroup( <G>, <max_lev> ) O

For a given finite group <G> generated by initial automata or by elements defined by
wreath recursion
computes an isomorphism from <G> into a finite permutational group.
If <G> is not known to be self-similar (see "IsSelfSimilar") the isomorphism is based on the
regular representation, which works generally much slower. If <G> is self-similar
there is a level of the tree (see "LevelOfFaithfulAction"), where <G> acts faithfully.
The corresponding representation is returned in this case. If <max_lev> is given
it finds only the first <max_lev> quotients by stabilizers and if all of them have
different size it returns `fail'.
If <G> is infinite and <max_lev> is not specified it will loop forever.

For example, consider a subgroup $\langle a, b\rangle$ of Grigorchuk group.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> f := IsomorphismPermGroup(Group(a, b));
MappingByFunction( < a, b >, Group(
[ (1,2)(3,5)(4,6)(7,9)(8,10)(11,13)(12,14)(15,17)(16,18)(19,21)(20,22)(23,
    25)(24,26)(27,29)(28,30)(31,32), (1,3)(2,4)(5,7)(6,8)(9,11)(10,12)(13,
    15)(14,16)(17,19)(18,20)(21,23)(22,24)(25,27)(26,28)(29,31)(30,32)
 ]), function( g ) ... end, function( b ) ... end )
gap> Size(Image(f));
32
gap> H := SelfSimilarGroup("a=(a*b,1)(1,2), b=(1,b*a^-1)(1,2), c=(b, a*b)");
< a, b, c >
gap> f1 := IsomorphismPermGroup(H);
MappingByFunction( < a, b, c >, Group([ (1,3)(2,4), (1,3)(2,4), (1,2)
 ]), function( g ) ... end, function( b ) ... end )
gap> Size(Image(f1));
8
gap> PreImagesRepresentative(f1, (1,3,2,4));
a*c
gap> (a*c)^f1;
(1,3,2,4)
\endexample


\>Random( <G> ) O

Returns a random element of a group (semigroup) <G>. The operation is based
on the generator of random elements in free groups and semigroups.

\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> Random( Basilica );
v*u^-3
\endexample


\>MarkovOperator( <G>, <lev>, <weights> ) O

Computes the matrix of the Markov operator related to the (semi)group <G> on the <lev>-th level
of the tree. If <G> is a group generated by $g_1,g_2,\ldots,g_n$, then the Markov operator
is defined as $(`PermOnLevelAsMatrix'(g_1)+\cdots+`PermOnLevelAsMatrix'(g_n)+
`PermOnLevelAsMatrix'(g_1^{-1})+\cdots+`PermOnLevelAsMatrix'(g_n^{-1}))/(2*n)$.
If <S> is a semigroup generated by $s_1,s_2,\ldots,s_n$, then the Markov operator
is defined similarly with `PermOnLevelAsMatrix' being replaced with `TransformationOnLevelAsMatrix'.
If the list of <weights> is given, uses its entries as coefficients of operators correspondings to
the generators of a group or semigroup. In the case of a group, the length of <weights> must be twice
as big as the number of generators of <G>. The list <weights> may consist either of numbers or of strings
representing the names of indeterminates.
See also
`PermOnLevelAsMatrix' ("PermOnLevelAsMatrix") and `TransformationOnLevelAsMatrix' ("TransformationOnLevelAsMatrix").
\beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> MarkovOperator(L, 3);
[ [ 0, 0, 1/4, 1/4, 0, 1/4, 0, 1/4 ], [ 0, 0, 1/4, 1/4, 1/4, 0, 1/4, 0 ],
  [ 1/4, 1/4, 0, 0, 1/4, 0, 1/4, 0 ], [ 1/4, 1/4, 0, 0, 0, 1/4, 0, 1/4 ],
  [ 0, 1/4, 1/4, 0, 0, 1/2, 0, 0 ], [ 1/4, 0, 0, 1/4, 1/2, 0, 0, 0 ],
  [ 0, 1/4, 1/4, 0, 0, 0, 1/2, 0 ], [ 1/4, 0, 0, 1/4, 0, 0, 0, 1/2 ] ]
gap> MarkovOperator(L,3,["a","b","c","d"]);
[ [ 0, 0, d, b, 0, c, 0, a ], [ 0, 0, b, d, c, 0, a, 0 ],
  [ b, d, 0, 0, a, 0, c, 0 ], [ d, b, 0, 0, 0, a, 0, c ],
  [ 0, a, c, 0, 0, b+d, 0, 0 ], [ a, 0, 0, c, b+d, 0, 0, 0 ],
  [ 0, c, a, 0, 0, 0, b+d, 0 ], [ c, 0, 0, a, 0, 0, 0, b+d ] ]
\endexample
In the case of semigroups we have:
\beginexample
gap> S := AutomatonSemigroup("c=(c,d)[1,1],d=(c,c)(1,2)");
< c, d >
gap> MarkovOperator(S,3,["w1","w2"]);
[ [ w1, 0, 0, 0, w2, 0, 0, 0 ], [ w1, 0, 0, 0, w2, 0, 0, 0 ],
  [ 0, w1, 0, 0, 0, w2, 0, 0 ], [ w1, 0, 0, 0, w2, 0, 0, 0 ],
  [ w2, 0, w1, 0, 0, 0, 0, 0 ], [ w2, 0, w1, 0, 0, 0, 0, 0 ],
  [ w1, w2, 0, 0, 0, 0, 0, 0 ], [ w1+w2, 0, 0, 0, 0, 0, 0, 0 ] ]
gap> MarkovOperator(S,3,[1/3,2/3]);
[ [ 1/3, 0, 0, 0, 2/3, 0, 0, 0 ], [ 1/3, 0, 0, 0, 2/3, 0, 0, 0 ],
  [ 0, 1/3, 0, 0, 0, 2/3, 0, 0 ], [ 1/3, 0, 0, 0, 2/3, 0, 0, 0 ],
  [ 2/3, 0, 1/3, 0, 0, 0, 0, 0 ], [ 2/3, 0, 1/3, 0, 0, 0, 0, 0 ],
  [ 1/3, 2/3, 0, 0, 0, 0, 0, 0 ], [ 1, 0, 0, 0, 0, 0, 0, 0 ] ]
\endexample


\>`MihailovaSystem( <G> )'{MihailovaSystem}!{[automgroup]} AM

In the case when <G> is an automaton fractal group acting on a binary
tree, computes the generating set for the first level stabilizer in G
such that the sections of these generators at the first level,
viewed as elements of $F_r\times F_r$, are in Mihailova normal form.
See~\cite{GSESS} for details.

\beginexample
gap> G := AutomatonGroup("a=(b,c)(1,2),b=(a,c),c=(a,a)");
< a, b, c >
gap> M := MihailovaSystem(G);
[ c^-1*b, c^-1*b^-1*c*a^-1*b*c*b^-1*a, a^-1*b*c*b^-1*a, a*c^-1*b^-1*a*c,
  c^-1*a^-1*b*c*a ]
gap> for g in M do
>      Print(g,"=",Decompose(g),"\n");
>    od;
c^-1*b=(1, a^-1*c)
c^-1*b^-1*c*a^-1*b*c*b^-1*a=(1, a^-1*c^-1*a*b^-1*a*b)
a^-1*b*c*b^-1*a=(a, b^-1*a*b)
a*c^-1*b^-1*a*c=(b, c*a^-2*b*a)
c^-1*a^-1*b*c*a=(c, a^-1*b^-1*a^2*b)
\endexample





\>AbelImage( <obj> ) A

Returns image of <obj> in the canonical projection onto the abelianization of
the full group of tree automorphisms, represented as a subgroup of the additive
group of rational functions.


\>DiagonalPower( <fam>[, <k>] ) O

For a given automaton group <G> acting on alphabet $X$ and corresponding family
<fam> of automata one can consider the action of $<G>^<k>$ on $X^<k>$ defined by
$(x_1,x_2,\ldots, x_k)^{(g_1,g_2,\ldots,g_k)}=(x_1^{g_1},x_2^{g_2},\ldots,x_k^{g_k})$.
This function constructs a self-similar group, which encodes this action. If
<k> is not given it is assumed to be $2$.
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> S := DiagonalPower(UnderlyingAutomFamily(Basilica));
< uu, uv, u1, vu, vv, v1, 1u, 1v >
gap> Decompose(uu);
(vv, v1, 1v, 1)(1,4)(2,3)
\endexample


\>MultAutomAlphabet( <fam> ) O



\>UnderlyingAutomFamily( <G> ) A

Returns the family to which the elements of <G> belong.



%Declaration{UnderlyingFreeGroup}
%Declaration{UnderlyingFreeSubgroup}
%Declaration{UnderlyingFreeGenerators}
%Declaration{TrivialSubgroup}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Self-similar groups and semigroups defined by the wreath recursion}

\>`IsFiniteState( <G> )'{IsFiniteState![selfsimsg]}@{`IsFiniteState'!`[selfsimsg]'} P

For a group or semigroup of homomorphisms of the tree defined using a
wreath recursion, returns `true' if all
generators can be represented as finite automata (have finitely many different
sections).
It will never stop if the free reduction of words is not sufficient to establish
the finite-state property or if the group is not finite-state.
In case <G> is a finite-state group it automatically computes the attributes
`UnderlyingAutomatonGroup'(<G>) ("UnderlyingAutomatonGroup"),
`IsomorphicAutomGroup'(<G>) ("IsomorphicAutomGroup") and
`MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup").
For a finite-state semigroup it computes the corresponding attributes
`UnderlyingAutomatonSemigroup'(<G>) ("UnderlyingAutomatonSemigroup"),
`IsomorphicAutomSemigroup'(<G>) ("IsomorphicAutomSemigroup") and
`MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup").
\beginexample
gap> W := SelfSimilarGroup("x=(x^-1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)");
< x, y, z >
gap> IsFiniteState(W);
true
gap> Size(GeneratorsOfGroup(UnderlyingAutomatonGroup(W)));
50
\endexample

\>IsomorphicAutomGroup( <G> ) AM

In case <G> is finite-state tries to compute a group generated by automata, isomorphic to <G>,
which is a subgroup of `UnderlyingAutomatonGroup'(<G>) (see "UnderlyingAutomatonGroup").
The natural isomorphism between <G> and `IsomorphicAutomGroup'(<G>) is stored in the
attribute `MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup").
In some cases it may be useful to check if <G> is finite.
\beginexample
gap> R := SelfSimilarGroup("a=(a^-1*b,b^-1*a)(1,2), b=(a^-1,b^-1)");
< a, b >
gap> UR := UnderlyingAutomatonGroup(R);
< a1, a2, a4, a5 >
gap> IR := IsomorphicAutomGroup(R);
< a1, a5 >
gap> hom := MonomorphismToAutomatonGroup(R);
MappingByFunction( < a, b >, < a1, a5 >, function( a ) ... end, function( b ) \
... end )
gap> (a*b)^hom;
a1*a5
gap> PreImagesRepresentative(hom, last);
a*b
gap> List(GeneratorsOfGroup(UR), x -> PreImagesRepresentative(hom, x));
[ a, a^-1*b, b^-1*a, b ]
\endexample

All these operations work also for the subgroups of groups generated by `SelfSimilarGroup'.
("SelfSimilarGroup").
\beginexample
gap> T := Group([b*a, a*b]);
< b*a, a*b >
gap> IT := IsomorphicAutomGroup(T);
< a1, a4 >
\endexample
Note, that different groups have different `UnderlyingAutomGroup' attributes. For example,
the generator `a1' of group `IT' above is different from the generator `a1' of group `IR'.


\>IsomorphicAutomSemigroup( <G> ) AM

In case <G> is finite-state returns a semigroup generated by automata, isomorphic to <G>,
which is a subsemigroup of `UnderlyingAutomatonSemigroup'(<G>) (see "UnderlyingAutomatonSemigroup").
The natural isomorphism between <G> and `IsomorphicAutomSemigroup'(<G>) is stored in the
attribute `MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup").
\beginexample
gap> R := SelfSimilarSemigroup("a=(1,1)[1,1], b=(a*c,1)(1,2), c=(1,a*b)");
< a, b, c >
gap> UR := UnderlyingAutomatonSemigroup(R);
< 1, a1, a3, a5, a6 >
gap> IR := IsomorphicAutomSemigroup(R);
< a1, a3, a5 >
gap> hom := MonomorphismToAutomatonSemigroup(R);
MappingByFunction( < a, b, c >, < a1, a3, a5 >, function( a ) ... end, functio\
n( b ) ... end )
gap> (a*b)^hom;
a1*a3
gap> PreImagesRepresentative(hom, last);
a*b
gap> List(GeneratorsOfSemigroup(UR), x -> PreImagesRepresentative(hom, x));
[ 1, a, b, c, a*b ]
\endexample

All these operations work also for the subsemigroups of semigroups generated by
`SelfSimilarSemigroup' ("SelfSimilarSemigroup").
\beginexample
gap> T := Semigroup([a*b, b^2]);
< a*b, b^2 >
gap> IT := IsomorphicAutomSemigroup(T);
< a1, a4 >
\endexample
Note, that different semigroups have different `UnderlyingAutomSemigroup' attributes. For example,
the generator `a1' of semigroup `IT' above is different from the generator `a1' of semigroup `IR'.



\>UnderlyingAutomatonGroup( <G> ) AM

In case <G> is finite-state returns a self-similar closure of <G> as a group
generated by automaton.
The natural monomorphism from <G> and `UnderlyingAutomatonGroup'(<G>) is stored in the
attribute `MonomorphismToAutomatonGroup'(<G>) ("MonomorphismToAutomatonGroup"). If
<G> is created by `SelfSimilarGroup' (see "SelfSimilarGroup"), then the self-similar closure
of <G> coincides with <G>, so one can use `MonomorphismToAutomatonGroup'(<G>) to
get preimages of elements of `UnderlyingAutomatonGroup'(<G>) in <G>. See the example for
`IsomorphicAutomGroup' ("IsomorphicAutomGroup").


\>UnderlyingAutomatonSemigroup( <G> ) AM

In case <G> is finite-state returns a self-similar closure of <G> as a semigroup
generated by automaton.
The natural monomorphism from <G> and `UnderlyingAutomatonSemigroup'(<G>) is stored in the
attribute `MonomorphismToAutomatonSemigroup'(<G>) ("MonomorphismToAutomatonSemigroup"). If
<G> is created by `SelfSimilarSemigroup' (see "SelfSimilarSemigroup"), then the self-similar closure
of <G> coincides with <G>, so one can use `MonomorphismToAutomatonSemigroup'(<G>) to
get preimages of elements of `UnderlyingAutomatonSemigroup'(<G>) in <G>. See the example for
`IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup").



\>MonomorphismToAutomatonGroup( <G> ) AM

In case <G> is finite-state returns a monomorphism from <G> into `UnderlyingAutomatonGroup'(<G>)
(see "UnderlyingAutomatonGroup"). If <G> is created by `SelfSimilarGroup' (see "SelfSimilarGroup"),
then one can use `MonomorphismToAutomatonGroup'(<G>) to
get preimages of elements of `UnderlyingAutomatonGroup'(<G>) in <G>. See the example for
`IsomorphicAutomGroup' ("IsomorphicAutomGroup").


\>MonomorphismToAutomatonSemigroup( <G> ) AM

In case <G> is finite-state returns a monomorphism from <G> into `UnderlyingAutomatonSemigroup'(<G>)
(see "UnderlyingAutomatonSemigroup"). If <G> is created by `SelfSimilarSemigroup'
(see "SelfSimilarSemigroup"),
then one can use `MonomorphismToAutomatonSemigroup'(<G>) to
get preimages of elements of `UnderlyingAutomatonSemigroup'(<G>) in <G>. See the example for
`IsomorphicAutomSemigroup' ("IsomorphicAutomSemigroup").





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Contracting groups}

\>GroupNucleus( <G> ) AM

Tries to compute the <nucleus> (see the definition in "Short math background") of
a self-similar group <G>. Note that this set need not contain the original
generators of <G>. It uses `FindNucleus' (see "FindNucleus")
operation and behaves accordingly: if the group is not contracting it will loop
forever. See also `GeneratingSetWithNucleus' ("GeneratingSetWithNucleus").

\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> GroupNucleus(Basilica);
[ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ]
\endexample


\>GeneratingSetWithNucleus( <G> ) AM

Tries to compute the generating set of a self-similar group <G> that includes
the original generators and the <nucleus> (see "Short math background") of <G>.
It uses `FindNucleus' operation
and behaves accordingly: if the group is not contracting
it will loop forever (modulo memory constraints, of course).
See also `GroupNucleus' ("GroupNucleus").

\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> GeneratingSetWithNucleus(Basilica);
[ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ]
\endexample


\>GeneratingSetWithNucleusAutom( <G> ) AM

Computes the automaton of the generating set that includes the nucleus of a contracting group <G>.
See also `GeneratingSetWithNucleus' ("GeneratingSetWithNucleus").
\beginexample
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> B_autom := GeneratingSetWithNucleusAutom(Basilica);
<automaton>
gap> Display(B_autom);
a1 = (a1, a1), a2 = (a3, a1)(1,2), a3 = (a2, a1), a4 = (a1, a5)
(1,2), a5 = (a4, a1), a6 = (a1, a7)(1,2), a7 = (a6, a1)(1,2)
\endexample


\>ContractingLevel( <G> ) AM

Given a contracting group <G> with generating set $N$ that includes the nucleus, stored in
`GeneratingSetWithNucleus'(<G>) (see "GeneratingSetWithNucleus") computes the
minimal level $n$, such that for every vertex $v$ of the $n$-th
level and all $g, h \in N$ the section $gh|_v \in N$.

In the case if it is not known whether <G> is contracting, it first tries to compute
the nucleus. If <G> happens to be noncontracting, it will loop forever. One can
also use `IsNoncontracting' (see "IsNoncontracting") or `FindNucleus' (see
"FindNucleus") directly.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> ContractingLevel(Grigorchuk_Group);
1
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> ContractingLevel(Basilica);
2
\endexample


\>ContractingTable( <G> ) AM

Given a contracting group <G> with a generating set $N$  of size $k$ that includes the nucleus, stored in
`GeneratingSetWithNucleus'(<G>)~(see "GeneratingSetWithNucleus")
computes the $k\times k$ table, whose
[i][j]-th entry contains decomposition of $N$[i]$N$[j] on
the `ContractingLevel'(<G>) level~(see "ContractingLevel"). By construction the sections of
$N$[i]$N$[j] on this level belong to $N$. This table is used in the
algorithm solving the word problem in polynomial time.

In the case if it is not known whether <G> is contracting it first tries to compute
the nucleus. If <G> happens to be noncontracting, it will loop forever. One can
also use `IsNoncontracting' (see "IsNoncontracting") or `FindNucleus' (see
"FindNucleus") directly.
\beginexample
gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> ContractingTable(Grigorchuk_Group);
[ [ (1, 1), (1, 1)(1,2), (a, c), (a, d), (1, b) ],
  [ (1, 1)(1,2), (1, 1), (c, a)(1,2), (d, a)(1,2), (b, 1)(1,2) ],
  [ (a, c), (a, c)(1,2), (1, 1), (1, b), (a, d) ],
  [ (a, d), (a, d)(1,2), (1, b), (1, 1), (a, c) ],
  [ (1, b), (1, b)(1,2), (a, d), (a, c), (1, 1) ] ]
\endexample


\>UseContraction( <G> ) O
\>DoNotUseContraction( <G> ) O

For a contracting automaton group <G> these two operations determine whether to
use the algorithm
of polynomial complexity solving the word problem in the group. By default
it is set to <true> as soon as the nucleus of the group was computed. Sometimes
when the nucleus is very big, the standard algorithm of exponential complexity
is faster for short words, but this heavily depends on the group. Therefore
the decision on which algorithm to use is left to the user. To use the
exponential algorithm one can use the second operation `DoNotUseContraction'(<G>).

Note also then in order to use the polynomial time algorithm the `ContractingTable(G)'
(see "ContractingTable") has to be computed first, which takes some time when the
nucleus is big. This attribute is computed automatically when the word problem is solved
for the first time. This sometimes causes some delay.

Below we provide an example which shows that both methods can be of use.
%notest
\beginexample|unstableoutput
gap> G := AutomatonGroup("a=(b,b)(1,2), b=(c,a), c=(a,a)");
< a, b, c >
gap> IsContracting(G);
true
gap> Size(GroupNucleus(G));
41
gap> ContractingLevel(G);
6
gap> ContractingTable(G);; time;
4719
gap> v := a*b*a*b^2*c*b*c*b^-1*a^-1*b^-1*a^-1;;
gap> w := b*c*a*b*a*b*c^-1*b^-2*a^-1*b^-1*a^-1;;
gap> UseContraction(G);;
gap> IsOne(Comm(v,w)); time;
true
110
gap> FindGroupRelations(G, 9);; time;
a^2
b^2
c^2
(b*a*b*c*a)^2
(b*(c*a)^2)^2
(b*c*b*a*(b*c)^2*a)^2
(b*(c*b*c*a)^2)^2
11578
gap> DoNotUseContraction(G);;
gap> IsOne(Comm(v,w)); time;
true
922
gap> FindGroupRelations(G, 9);; time;
a^2
b^2
c^2
(b*a*b*c*a)^2
(b*(c*a)^2)^2
(b*c*b*a*(b*c)^2*a)^2
(b*(c*b*c*a)^2)^2
23719
\endexample




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Rewriting Systems}

It is possible to use basic relators in all computations performed
in a self-similar group.

\>AG_UseRewritingSystem( <G>[, <setting>] ) O

Tells whether computations in the group <G> should use a rewriting system.
<setting> defaults to `true' if omitted. This function initially only
tries to find involutions in <G>. See `AG_AddRelators' ("AG_AddRelators")
and `AG_UpdateRewritingSystem' ("AG_UpdateRewritingSystem") for the ways
to add more relators.

\beginexample
gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> Comm(a*b, b*a);
b^-1*a^-2*b^-1*a*b^2*a
gap> AG_UseRewritingSystem(G);
gap> Comm(a*b, b*a);
1
gap> AG_UseRewritingSystem(G, false);
gap> Comm(a*b, b*a);
b^-1*a^-2*b^-1*a*b^2*a
\endexample


\>AG_AddRelators( <G>, <relators> ) O

Adds relators from the list <relators> to the rewriting system used in
<G>.

\beginexample
gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> AG_UseRewritingSystem(G);
gap> b*c;
b*c
gap> AG_AddRelators(G, [b*c*d]);
gap> b*c;
d
\endexample

In some cases it's hard to find relations directly from the wreath
recursion of a self-similar group (at least, there is no general agorithm).
This function provides possibility to add relators manually. After that
one can use `AG_UpdateRewritingSystem' (see "AG_UpdateRewritingSystem")
and `AG_UseRewritingSystem' (see "AG_UseRewritingSystem") to use these
relators in computations. In the example below we consider a finite group
$H$, in which $a=b$, but the standard algorithm is unable to solve the
word problem. There are two solutions for that. One can manually add a
relator, or one can ask if the group is finite (which does not stop
generally if the group is infinite).
\beginexample
gap> H := SelfSimilarGroup("a=(a*b,1)(1,2), b=(1,b*a^-1)(1,2), c=(b, a*b)");
< a, b, c >
gap> AG_AddRelators(H, [a*b^-1]);
gap> AG_UseRewritingSystem(H);
gap> Order(a*c);
4
\endexample


\>AG_UpdateRewritingSystem( <G>, <maxlen> ) O

Tries to find new relators of length up to <maxlen> and adds them into
the rewriting system. It can also be used after introducing new relators
via `AG_AddRelators' (see "AG_AddRelators").

\beginexample
gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> AG_UseRewritingSystem(G);
gap> b*c;
b*c
gap> AG_UpdateRewritingSystem(G, 3);
gap> b*c;
d
\endexample


\>AG_RewritingSystemRules( <G> ) O

Returns the list of rules used in the rewriting system of group <G>.
\beginexample
gap> G := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> AG_UseRewritingSystem(G);
gap> AG_RewritingSystemRules(G);
[ [ a^2, <identity ...> ], [ b^2, <identity ...> ], [ c^2, <identity ...> ],
  [ d^2, <identity ...> ], [ A, a ], [ B, b ], [ C, c ], [ D, d ] ]
\endexample





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%