2 Properties and operations with groups and semigroups

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₁,...,a_d,p], where d ≥ 2 is the size of the alphabet the group acts on, a_i are IsInt in {1,…,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.

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 >

In the second form of this operation the definition of the first group looks like

gap> AutomatonGroup([ [ 1, 2, ()], [ 1, 2, (1,2) ] ], [ "a", "b" ]);
< a, b >

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₁,·.·,a_d,p], where d ≥ 2 is the size of the alphabet the group acts on, a_i are IsInt in {1,…,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).

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 >

gap> AutomatonSemigroup([ [1,2,Transformation([2,2])], [ 1,2,(1,2)] ], ["a","b"]);
< a, b >

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₁,...,a_d,p], where d ≥ 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.

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 >

gap> SelfSimilarGroup([[ [1,2], [-2], ()], [ [], [2,2,1], (1,2) ]], ["a","b"]);
< a, b >

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₁,...,a_d,p], where d ≥ 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).

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 >

gap> SelfSimilarSemigroup([[[1,2], [2], ()], [[1], [2,2,1], (1,2)]],["a","b"]);
< a, b >

The category of groups of tree automorphisms.

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

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.

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

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.

2.2 Basic properties of groups and semigroups

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

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.

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.

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

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).

Returns whether the group G is spherically transitive (see Short math background).

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

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).

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

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

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

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

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.

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

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.

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

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 Sid00.

See also operations IsGeneratedByBoundedAutomaton (IsGeneratedByBoundedAutomaton) and PolynomialDegreeOfGrowthOfUnderlyingAutomaton (PolynomialDegreeOfGrowthOfUnderlyingAutomaton).

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

For a group G generated by all states of a finite automaton (see IsAutomatonGroup) determines whether this automaton is bounded in terms of Sidki Sid00.

See also IsGeneratedByAutomatonOfPolynomialGrowth (IsGeneratedByAutomatonOfPolynomialGrowth) and PolynomialDegreeOfGrowthOfUnderlyingAutomaton (PolynomialDegreeOfGrowthOfUnderlyingAutomaton).

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

For a group G generated by all states of a finite automaton (see IsAutomatonGroup) of polynomial growth in terms of Sidki 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).

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

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).

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

In certain cases (for groups generated by bounded automata BKNV05, some virtually abelian groups or finite groups) returns true if G is amenable.

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

For a group (or semigroup) G returns an automaton generating a self-similar group (or semigroup) containing G.

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 ]

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)

Returns an AutomatonList of UnderlyingAutomaton(G) (see UnderlyingAutomaton).

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, () ] ]

Returns an internal representation of the wreath recursion of the self-similar group (semigroup) containing G.

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 ], () ] ]

2.3 Operations with groups and semigroups

Returns the group of permutations induced by the action of the group G at the k-th level.

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

Returns the semigroup of transformations induced by the action of the semigroup G at the k-th level.

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

Returns the stabilizer of the k-th level.

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 >

Returns the stabilizer of the first level, see also StabilizerOfLevel.

gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> StabilizerOfFirstLevel(Basilica);
< v, u^2, u*v*u^-1 >

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.

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 >

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

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.

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.

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 >

Returns the projection of the stabilizer of v at itself. It is a shortcut for Projection(StabilizerOfVertex(G, v), v) (see Projection, StabilizerOfVertex).

gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> ProjStab(Basilica, [1,2,1]);
< u, v >

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.

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 ]

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.

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 ] ]

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.

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 ]

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.

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 ]

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.

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

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).

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

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,…,max_len }, and for a semigroup without identity at {1,…,max_len }.

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 ]

Returns the list of all different elements of a group (semigroup, monoid) G up to length max_len.

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 ]

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.

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> ]

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).

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

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 〈a, b〉 of Grigorchuk group.

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)

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

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

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₁,g₂,…,g_n, then the Markov operator is defined as (PermOnLevelAsMatrix(g₁)+…+PermOnLevelAsMatrix(g_n)+ PermOnLevelAsMatrix(g₁⁻¹)+…+PermOnLevelAsMatrix(g_n⁻¹))/(2*n). If S is a semigroup generated by s₁,s₂,…,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).

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 ] ]

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 ] ]

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×F_r, are in Mihailova normal form. See GSESS for details.

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)

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.

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₁,x₂,…, x_k)^{(g₁,g₂,…,g_k)}=(x₁^g₁,x₂^g₂,…,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.

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)

Returns the family to which the elements of G belong.

2.4 Self-similar groups and semigroups defined by the wreath recursion

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).

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

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.

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 ]

All these operations work also for the subgroups of groups generated by SelfSimilarGroup. (SelfSimilarGroup).

gap> T := Group([b*a, a*b]);
< b*a, a*b >
gap> IT := IsomorphicAutomGroup(T);
< a1, a4 >

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).

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 ]

All these operations work also for the subsemigroups of semigroups generated by SelfSimilarSemigroup (SelfSimilarSemigroup).

gap> T := Semigroup([a*b, b^2]);
< a*b, b^2 >
gap> IT := IsomorphicAutomSemigroup(T);
< a1, a4 >

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).

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).

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).

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).

2.5 Contracting groups

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).

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 ]

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).

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 ]

Computes the automaton of the generating set that includes the nucleus of a contracting group G. See also GeneratingSetWithNucleus (GeneratingSetWithNucleus).

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)

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 ∈ N the section gh|_v ∈ 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.

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

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×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.

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) ] ]

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. testexamplefalse

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

2.6 Rewriting Systems

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

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.

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

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

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

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).

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

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).

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

Returns the list of rules used in the rewriting system of group G.

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 ] ]

[Up] [Previous] [Next] [Index]