<html><head><title>[automgrp] 2 Properties and operations with groups and semigroups</title></head> <body text="#000000" bgcolor="#ffffff"> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <h1>2 Properties and operations with groups and semigroups</h1><p> <P> <H3>Sections</H3> <oL> <li> <A HREF="CHAP002.htm#SECT001">Creation of groups and semigroups</a> <li> <A HREF="CHAP002.htm#SECT002">Basic properties of groups and semigroups</a> <li> <A HREF="CHAP002.htm#SECT003">Operations with groups and semigroups</a> <li> <A HREF="CHAP002.htm#SECT004">Self-similar groups and semigroups defined by wreath recursion</a> <li> <A HREF="CHAP002.htm#SECT005">Contracting groups</a> <li> <A HREF="CHAP002.htm#SECT006">Rewriting Systems</a> </ol><p> <p> <p> <h2><a name="SECT001">2.1 Creation of groups and semigroups</a></h2> <p><p> <a name = "SSEC001.1"></a> <li><code>AutomatonGroup( </code><var>string</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <li><code>AutomatonGroup( </code><var>list</var><code>[, </code><var>names</var><code>, </code><var>bind_vars</var><code>] ) O</code> <li><code>AutomatonGroup( </code><var>automaton</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <p> Creates the self-similar group generated by the finite automaton, described by <var>string</var> or <var>list</var>, or by the argument <var>automaton</var>. <p> The argument <var>string</var> is a conventional notation of the form <code>name1=(name11,name12,...,name1d)perm1, name2=...</code> where each <code>name*</code> is a name of a state or <code>1</code>, and each <code>perm*</code> is a permutation written in <font face="Gill Sans,Helvetica,Arial">GAP</font> notation. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. <p> The argument <var>list</var> is a list consisting of <i>n</i> entries corresponding to <i>n</i> states of an automaton. Each entry is of the form [<i>a</i><sub>1</sub>,...,<i>a</i><sub><i>d</i></sub>,<i>p</i>], where <i>d</i> ≥ 2 is the size of the alphabet the group acts on, <i>a</i><sub><i>i</i></sub> are <code>IsInt</code> in {1,…,<i>n</i>} and represent the sections of the corresponding state at all vertices of the first level of the tree; and <i>p</i> from <code>SymmetricGroup(</code><var>d</var><code>)</code> describes the action of the corresponding state on the alphabet. <p> The optional argument <var>names</var> 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. <p> If the optional argument <var>bind_vars</var> is <code>false</code> the names of generators of the group are not assigned to the global variables. The default value is <code>true</code>. One can use <code>AssignGeneratorVariables</code> function to assign these names later, if they were not assigned when the group was created. <p> <pre> 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 > </pre> <p> In the second form of this operation the definition of the first group looks like <pre> gap> AutomatonGroup([ [ 1, 2, ()], [ 1, 2, (1,2) ] ], [ "a", "b" ]); < a, b > </pre> The <var>bind_vars</var> argument works as follows <pre> gap> AutomatonGroup("t = (1, t)(1,2)", false);; gap> t; Variable: 't' must have a value gap> AutomatonGroup("t = (1, t)(1,2)", true);; gap> t; t </pre> <p> <a name = "SSEC001.2"></a> <li><code>AutomatonSemigroup( </code><var>string</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <li><code>AutomatonSemigroup( </code><var>list</var><code>[, </code><var>names</var><code>, </code><var>bind_vars</var><code>] ) O</code> <li><code>AutomatonSemigroup( </code><var>automaton</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <p> Creates the semigroup generated by the finite automaton, described by <var>string</var> or <var>list</var>, or by the argument <var>automaton</var>. <p> The argument <var>string</var> is a conventional notation of the form <code>name1=(name11,name12,...,name1d)trans1, name2=...</code> where each <code>name*</code> is a name of a state or <code>1</code>, and each <code>trans*</code> is either a permutation written in <font face="Gill Sans,Helvetica,Arial">GAP</font> notation, or a list defining a transformation of the alphabet via <code>Transformation(trans*)</code>. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. <p> The argument <var>list</var> is a list consisting of <i>n</i> entries corresponding to <i>n</i> states of the automaton. Each entry is of the form [<i>a</i><sub>1</sub>,·.·,<i>a</i><sub><i>d</i></sub>,<i>p</i>], where <i>d</i> ≥ 2 is the size of the alphabet the group acts on, <i>a</i><sub><i>i</i></sub> are <code>IsInt</code> in {1,…,<i>n</i>} and represent the sections of the corresponding state at all vertices of the first level of the tree; and <i>p</i> is a transformation of the alphabet describing the action of the corresponding state on the alphabet. <p> The optional arguments <var>names</var> and <var>bind_vars</var> have the same meaning as in <code>AutomatonGroup</code> (see <a href="CHAP002.htm#SSEC001.1">AutomatonGroup</a>). <p> <pre> 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 > </pre> In the second form of this operation the definition of the second semigroup looks like <pre> gap> AutomatonSemigroup([ [1,2,Transformation([2,2])], [ 1,2,(1,2)] ], ["a","b"]); < a, b > </pre> <p> <a name = "SSEC001.3"></a> <li><code>SelfSimilarGroup( </code><var>string</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <li><code>SelfSimilarGroup( </code><var>list</var><code>[, </code><var>names</var><code>, </code><var>bind_vars</var><code>] ) O</code> <li><code>SelfSimilarGroup( </code><var>automaton</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <p> Creates the self-similar group generated by the wreath recursion, described by <var>string</var> or <var>list</var>, or given by the argument <var>automaton</var>. <p> The argument <var>string</var> is a conventional notation of the form <code>name1=(word11,word12,...,word1d)perm1, name2=...</code> where each <code>name*</code> is a name of a state, <code>word*</code> is an associative word over the alphabet consisting of all <code>name*</code>, and each <code>perm*</code> is a permutation written in <font face="Gill Sans,Helvetica,Arial">GAP</font> notation. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. <p> The argument <var>list</var> is a list consisting of <i>n</i> entries corresponding to <i>n</i> generators of the group. Each entry is of the form [<i>a</i><sub>1</sub>,...,<i>a</i><sub><i>d</i></sub>,<i>p</i>], where <i>d</i> ≥ 2 is the size of the alphabet the group acts on, <i>a</i><sub><i>i</i></sub> are lists acceptable by <code>AssocWordByLetterRep</code> (e.g. if the names of generators are <code>x</code>, <code>y</code> and <code>z</code>, then <code>[1, 1, -2, -2, 1, 3]</code> will produce <code>x^2*y^-2*x*z</code>) representing the sections of the corresponding generator at all vertices of the first level of the tree; and <i>p</i> from <code>SymmetricGroup(</code><var>d</var><code>)</code> describes the action of the corresponding generator on the alphabet. <p> The optional argument <var>names</var> must be a list of names of generators of the group. These names are used to display the elements of the resulting group. <p> If the optional argument <var>bind_vars</var> is <code>false</code> the names of generators of the group are not assigned to the global variables. The default value is <code>true</code>. One can use <code>AssignGeneratorVariables</code> function to assign these names later, if they were not assigned when the group was created. <p> <pre> 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 > </pre> In the second form of this operation the definition of the first group looks like <pre> gap> SelfSimilarGroup([[ [1,2], [-2], ()], [ [], [2,2,1], (1,2) ]], ["a","b"]); < a, b > </pre> The <var>bind_vars</var> argument works as follows <pre> gap> SelfSimilarGroup("t = (t^2, t)(1,2)", false);; gap> t; Variable: 't' must have a value gap> SelfSimilarGroup("t = (t^2, t)(1,2)", true);; gap> t; t </pre> <p> <a name = "SSEC001.4"></a> <li><code>SelfSimilarSemigroup( </code><var>string</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <li><code>SelfSimilarSemigroup( </code><var>list</var><code>[, </code><var>names</var><code>, </code><var>bind_vars</var><code>] ) O</code> <li><code>SelfSimilarSemigroup( </code><var>automaton</var><code>[, </code><var>bind_vars</var><code>] ) O</code> <p> Creates the semigroup generated by the wreath recursion, described by <var>string</var> or <var>list</var>, or given by the argument <var>automaton</var>. Note, that on the contrary to <code>AutomatonSemigroup</code> (<a href="CHAP002.htm#SSEC001.2">AutomatonSemigroup</a>) 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. <p> The argument <var>string</var> is a conventional notation of the form <code>name1=(word11,word12,...,word1d)trans1, name2=...</code> where each <code>name*</code> is a name of a state, <code>word*</code> is an associative word over the alphabet consisting of all <code>name*</code>, and each <code>trans*</code> is either a permutation written in <font face="Gill Sans,Helvetica,Arial">GAP</font> notation, or a list defining a transformation of the alphabet via <code>Transformation(trans*)</code>. Trivial permutations may be omitted. This function ignores whitespace, and states may be separated by commas or semicolons. <p> The argument <var>list</var> is a list consisting of <i>n</i> entries corresponding to <i>n</i> generators of the semigroup. Each entry is of the form [<i>a</i><sub>1</sub>,...,<i>a</i><sub><i>d</i></sub>,<i>p</i>], where <i>d</i> ≥ 2 is the size of the alphabet the semigroup acts on, <i>a</i><sub><i>i</i></sub> are lists acceptable by <code>AssocWordByLetterRep</code> (e.g. if the names of generators are <code>x</code>, <code>y</code> and <code>z</code>, then <code>[1, 1, 2, 3]</code> will produce <code>x^2*y*z</code>) representing the sections of the corresponding generator at all vertices of the first level of the tree; and <i>p</i> is a transformation of the alphabet describing the action of the corresponding generator. <p> The optional arguments <var>names</var> and <var>bind_vars</var> have the same meaning as in <code>SelfSimilarGroup</code> (see <a href="CHAP002.htm#SSEC001.3">SelfSimilarGroup</a>). <p> <pre> 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 > </pre> In the second form of this operation the definition of the first semigroup looks like <pre> gap> SelfSimilarSemigroup([[[1,2], [2], ()], [[1], [2,2,1], (1,2)]],["a","b"]); < a, b > </pre> The <var>bind_vars</var> argument works as follows <pre> gap> SelfSimilarSemigroup("t = (t^2, t)(1,2)", false);; gap> t; Variable: 't' must have a value gap> SelfSimilarSemigroup("t = (t^2, t)(1,2)", true);; gap> t; t </pre> <p> <a name = "SSEC001.5"></a> <li><code>IsTreeAutomorphismGroup( </code><var>G</var><code> ) C</code> <p> The category of groups of tree automorphisms. <p> <a name = "SSEC001.6"></a> <li><code>IsAutomGroup( </code><var>G</var><code> ) C</code> <p> The category of groups generated by finite invertible initial automata (elements from category <code>IsAutom</code>). <p> <a name = "SSEC001.7"></a> <li><code>IsAutomatonGroup( </code><var>G</var><code> ) P</code> <p> is <code>true</code> if <var>G</var> is created using the command <code>AutomatonGroup</code> (<a href="CHAP002.htm#SSEC001.1">AutomatonGroup</a>) or if the generators of <var>G</var> coincide with the generators of the corresponding family, and <code>false</code> otherwise. To test whether <var>G</var> is self-similar use <code>IsSelfSimilar</code> (<a href="CHAP002.htm#SSEC002.8">IsSelfSimilar</a>) command. <p> <a name = "SSEC001.8"></a> <li><code>IsSelfSimGroup( </code><var>G</var><code> ) C</code> <p> The category of groups whose generators are defined using wreath recursion (elements from category <code>IsSelfSim</code>). These groups need not be self-similar. <p> <a name = "SSEC001.9"></a> <li><code>IsSelfSimilarGroup( </code><var>G</var><code> ) P</code> <p> is <code>true</code> if <var>G</var> is created using the command <code>SelfSimilarGroup</code> (<a href="CHAP002.htm#SSEC001.3">SelfSimilarGroup</a>) or if the generators of <var>G</var> coincide with the generators of the corresponding family, and <code>false</code> otherwise. To test whether <var>G</var> is self-similar use <code>IsSelfSimilar</code> (<a href="CHAP002.htm#SSEC002.8">IsSelfSimilar</a>) command. <p> <p> <h2><a name="SECT002">2.2 Basic properties of groups and semigroups</a></h2> <p><p> <a name = "SSEC002.1"></a> <li><code>TopDegreeOfTree( </code><var>obj</var><code> ) A</code> <p> Returns the degree of the tree on the first level, i.e. the number of vertices adjacent to the root vertex. <p> <a name = "SSEC002.2"></a> <li><code>DegreeOfTree( </code><var>obj</var><code> ) A</code> <p> This is a synonym for TopDegreeOfTree (<a href="CHAP002.htm#SSEC002.1">TopDegreeOfTree</a>) 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. <p> <a name = "SSEC002.3"></a> <li><code>IsFractal( </code><var>G</var><code> ) P</code> <p> Returns whether the group <var>G</var> is fractal (also called as <var>self-replicating</var>). In other words, if <var>G</var> acts transitively on the first level and for any vertex <i>v</i> of the tree the projection of the stabilizer of <i>v</i> in <var>G</var> on this vertex coincides with the whole group <var>G</var>. <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> IsFractal(GrigorchukGroup); true </pre> <p> <a name = "SSEC002.4"></a> <li><code>IsFractalByWords( </code><var>G</var><code> ) P</code> <p> Computes the generators of stabilizers of vertices of the first level and their projections on these vertices. Returns <code>true</code> if the preimages of these projections in the free group under the canonical epimorphism generate the whole free group for each stabilizer, and the <var>G</var> acts transitively on the first level. This is sufficient but not necessary condition for <var>G</var> to be fractal. See also <code>IsFractal</code> (<a href="CHAP002.htm#SSEC002.3">IsFractal</a>). <p> <a name = "SSEC002.5"></a> <li><code>IsSphericallyTransitive( </code><var>G</var><code> ) P</code> <p> Returns whether the group <var>G</var> is spherically transitive (see <a href="CHAP001.htm#SECT001">Short math background</a>). <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> IsSphericallyTransitive(GrigorchukGroup); true </pre> <p> <a name = "SSEC002.6"></a> <li><code>ContainsSphericallyTransitiveElement( </code><var>G</var><code> ) A</code> <p> For a self-similar group <var>G</var> acting on a binary tree returns <code>true</code> if <var>G</var> contains an element acting spherically transitively on the levels of the tree and <code>false</code> otherwise. See also <code>SphericallyTransitiveElement</code> (<a href="CHAP002.htm#SSEC003.15">SphericallyTransitiveElement</a>). <pre> 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 </pre> <p> <a name = "SSEC002.7"></a> <li><code>IsTransitiveOnLevel( </code><var>G</var><code>, </code><var>lev</var><code> ) O</code> <p> Returns whether the group (semigroup) <var>G</var> acts transitively on level <var>lev</var>. <p> <pre> gap> GrigorchukGroup := 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 </pre> <p> <a name = "SSEC002.8"></a> <li><code>IsSelfSimilar( </code><var>G</var><code> ) P</code> <p> Returns whether the group or semigroup <var>G</var> is self-similar (see <a href="CHAP001.htm#SECT001">Short math background</a>). <p> <a name = "SSEC002.9"></a> <li><code>IsContracting( </code><var>G</var><code> ) A</code> <p> Given a self-similar group <var>G</var> 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 <code>FindNucleus</code>(<var>G</var>,50) (see <a href="CHAP002.htm#SSEC003.18">FindNucleus</a>), then it tries to find evidence that the group is noncontracting using <code>IsNoncontracting</code>(<var>G</var>,10,10) (see <a href="CHAP002.htm#SSEC002.10">IsNoncontracting</a>). If the answer was not found one can try to use <code>FindNucleus</code> and <code>IsNoncontracting</code> with bigger parameters. Also one can use <code>SetInfoLevel(InfoAutomGrp, 3)</code> for more information to be displayed. <p> <pre> 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 </pre> <p> <a name = "SSEC002.10"></a> <li><code>IsNoncontracting( </code><var>G</var><code>[, </code><var>max_len</var><code>, </code><var>depth</var><code>] ) F</code> <p> Tries to show that the group <var>G</var> is not contracting. Enumerates the elements of the group <var>G</var> up to length <var>max_len</var> until it finds an element which has a section <var>g</var> of infinite order, such that <code>OrderUsingSections</code>(<var>g</var>, <var>depth</var>) (see <a href="CHAP003.htm#SSEC002.6">OrderUsingSections</a>) returns <code>infinity</code> and such that <var>g</var> stabilizes some vertex and has itself as a section at this vertex. See also <code>IsContracting</code> (<a href="CHAP002.htm#SSEC002.9">IsContracting</a>). <p> If <var>max_len</var> and <var>depth</var> are omitted they are assumed to be <code>infinity</code> and 10, respectively. <p> If <code>InfoLevel</code> of <code>InfoAutomGrp</code> is greater than or equal to 3 (one can set it by <code>SetInfoLevel( InfoAutomGrp, 3)</code>), then the proof is printed. <p> <pre> 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 </pre> <p> <a name = "SSEC002.11"></a> <li><code>IsGeneratedByAutomatonOfPolynomialGrowth( </code><var>G</var><code> ) P</code> <p> For a group <var>G</var> generated by all states of a finite automaton (see <a href="CHAP002.htm#SSEC001.7">IsAutomatonGroup</a>) determines whether this automaton has polynomial growth in terms of Sidki <a href="biblio.htm#Sid00"><cite>Sid00</cite></a>. <p> See also operations <code>IsGeneratedByBoundedAutomaton</code> (<a href="CHAP002.htm#SSEC002.12">IsGeneratedByBoundedAutomaton</a>) and <code>PolynomialDegreeOfGrowthOfUnderlyingAutomaton</code> (<a href="CHAP002.htm#SSEC002.13">PolynomialDegreeOfGrowthOfUnderlyingAutomaton</a>). <pre> 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 </pre> <p> <a name = "SSEC002.12"></a> <li><code>IsGeneratedByBoundedAutomaton( </code><var>G</var><code> ) P</code> <p> For a group <var>G</var> generated by all states of a finite automaton (see <a href="CHAP002.htm#SSEC001.7">IsAutomatonGroup</a>) determines whether this automaton is bounded in terms of Sidki <a href="biblio.htm#Sid00"><cite>Sid00</cite></a>. <p> See also <code>IsGeneratedByAutomatonOfPolynomialGrowth</code> (<a href="CHAP002.htm#SSEC002.11">IsGeneratedByAutomatonOfPolynomialGrowth</a>) and <code>PolynomialDegreeOfGrowthOfUnderlyingAutomaton</code> (<a href="CHAP002.htm#SSEC002.13">PolynomialDegreeOfGrowthOfUnderlyingAutomaton</a>). <pre> 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 </pre> <p> <a name = "SSEC002.13"></a> <li><code>PolynomialDegreeOfGrowthOfUnderlyingAutomaton( </code><var>G</var><code> ) A</code> <p> For a group <var>G</var> generated by all states of a finite automaton (see <a href="CHAP002.htm#SSEC001.7">IsAutomatonGroup</a>) of polynomial growth in terms of Sidki <a href="biblio.htm#Sid00"><cite>Sid00</cite></a> 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 <code>fail</code>. <p> See also <code>IsGeneratedByAutomatonOfPolynomialGrowth</code> (<a href="CHAP002.htm#SSEC002.11">IsGeneratedByAutomatonOfPolynomialGrowth</a>) and <code>IsGeneratedByBoundedAutomaton</code> (<a href="CHAP002.htm#SSEC002.12">IsGeneratedByBoundedAutomaton</a>). <pre> 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 </pre> <p> <a name = "SSEC002.14"></a> <li><code>IsOfSubexponentialGrowth( </code><var>G</var><code>[, </code><var>len</var><code>, </code><var>depth</var><code>] ) O</code> <p> Tries to check whether the growth function of a self-similar group <var>G</var> is subexponential. The main part of the algorithm works as follows. It looks at all words of length up to <var>len</var> and if for some length <i>l</i> for each word of this length <i>l</i> the sum of the lengths of all its sections at level <var>depth</var> is less then <i>l</i>, returns <code>true</code>. The default values of <var>len</var> and <var>depth</var> are 10 and 6 respectively. Setting <code>SetInfoLevel(InfoAtomGrp, 3)</code> will make it print for each length the words that are not contracted. It also sometimes helps to use <code>AG_UseRewritingSystem</code> (see <a href="CHAP002.htm#SSEC006.1">AG_UseRewritingSystem</a>). <p> <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> UseAGRewritingSystem(GrigorchukGroup); true gap> IsOfSubexponentialGrowth(GrigorchukGroup,10,6); true </pre> <p> <a name = "SSEC002.15"></a> <li><code>IsAmenable( </code><var>G</var><code> ) P</code> <p> In certain cases (for groups generated by bounded automata <a href="biblio.htm#BKNV05"><cite>BKNV05</cite></a>, some virtually abelian groups or finite groups) returns <code>true</code> if <var>G</var> is amenable. <p> <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> IsAmenable(GrigorchukGroup); true </pre> <p> <a name = "SSEC002.16"></a> <li><code>UnderlyingAutomaton( </code><var>G</var><code> ) A</code> <p> For a group (or semigroup) <var>G</var> returns an automaton generating a self-similar group (or semigroup) containing <var>G</var>. <pre> gap> GS := AutomatonSemigroup("x=(x,y)[1,1], y=(y,y)(1,2)"); < x, y > gap> A := UnderlyingAutomaton(GS); <automaton> gap> Print(A); a1 = (a1, a2)[ 1, 1 ], a2 = (a2, a2)[ 2, 1 ] </pre> For a subgroup of Basilica group we get the automaton generating Basilica group. <pre> gap> H := Group([u*v^-1,v^2]); < u*v^-1, v^2 > gap> Print(UnderlyingAutomaton(H)); a1 = (a1, a1), a2 = (a3, a1)(1,2), a3 = (a2, a1) </pre> <p> <a name = "SSEC002.17"></a> <li><code>AutomatonList( </code><var>G</var><code> ) AM</code> <p> Returns an <code>AutomatonList</code> of <code>UnderlyingAutomaton</code>(<var>G</var>) (see <a href="CHAP002.htm#SSEC002.16">UnderlyingAutomaton</a>). <pre> 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, () ] ] </pre> <p> <a name = "SSEC002.18"></a> <li><code>RecurList( </code><var>G</var><code> ) AM</code> <p> Returns an internal representation of the wreath recursion of the self-similar group (semigroup) containing <var>G</var>. <pre> 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 ], () ] ] </pre> <p> <p> <h2><a name="SECT003">2.3 Operations with groups and semigroups</a></h2> <p><p> <a name = "SSEC003.1"></a> <li><code>PermGroupOnLevel( </code><var>G</var><code>, </code><var>k</var><code> ) O</code> <p> Returns the group of permutations induced by the action of the group <var>G</var> at the <var>k</var>-th level. <pre> 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 </pre> <p> <a name = "SSEC003.2"></a> <li><code>TransformationSemigroupOnLevel( </code><var>G</var><code>, </code><var>k</var><code> ) O</code> <p> Returns the semigroup of transformations induced by the action of the semigroup <var>G</var> at the <var>k</var>-th level. <pre> gap> S:=AutomatonSemigroup("y=(1,u)[1,1],u=(y,u)(1,2)"); < 1, y, u > gap> T:=TransformationSemigroupOnLevel(S,3); <semigroup with 3 generators> gap> Size(T); 11 </pre> <p> <a name = "SSEC003.3"></a> <li><code>StabilizerOfLevel( </code><var>G</var><code>, </code><var>k</var><code> ) O</code> <p> Returns the stabilizer of the <var>k</var>-th level. <pre> gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> StabilizerOfLevel(Basilica, 2); < u*v^2*u^-1, u*v*u*v^2*u^-1*v^-1*u^-1, v^2, v*u^2*v^-1, u*v*u^2*v^-1*u^-1, u^ 2, v*u*v*u*v^-1*u^-1*v^-1*u^-1 > </pre> <p> <a name = "SSEC003.4"></a> <li><code>StabilizerOfFirstLevel( </code><var>G</var><code> ) A</code> <p> Returns the stabilizer of the first level, see also <a href="CHAP002.htm#SSEC003.3">StabilizerOfLevel</a>. <pre> gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> StabilizerOfFirstLevel(Basilica); < u^2, u*v*u^-1, v > </pre> <p> <a name = "SSEC003.5"></a> <li><code>StabilizerOfVertex( </code><var>G</var><code>, </code><var>v</var><code> ) O</code> <p> Returns the stabilizer of the vertex <var>v</var>. Here <var>v</var> can be a list representing a vertex, or a positive integer representing a vertex at the first level. <pre> gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> StabilizerOfVertex(Basilica, [1,2,1]); < v*u^4*v^-1, v*u^2*v^2*u^-2*v^-1, v^2, u^2, v*u^2*v*u^2*v^-1*u^-2*v^ -1, u*v*u^-1, v*u^-1*v*u*v^-1, v*u^2*v*u*v*u^-1*v^-1*u^-2*v^-1 > </pre> <p> <a name = "SSEC003.6"></a> <li><code>FixesLevel( </code><var>obj</var><code>, </code><var>lev</var><code> ) O</code> <p> Returns whether <var>obj</var> fixes level <var>lev</var>, i.e. fixes every vertex at the level <var>lev</var>. <p> <a name = "SSEC003.7"></a> <li><code>FixesVertex( </code><var>obj</var><code>, </code><var>v</var><code> ) O</code> <p> Returns whether <var>obj</var> fixes the vertex <var>v</var>. The vertex <var>v</var> may be given as a list, or as a positive integer, in which case it denotes the <var>v</var>-th vertex at the first level. <p> <a name = "SSEC003.8"></a> <li><code>Projection( </code><var>G</var><code>, </code><var>v</var><code> ) O</code> <a name = "SSEC003.8"></a> <li><code>ProjectionNC( </code><var>G</var><code>, </code><var>v</var><code> ) O</code> <p> Returns the projection of the group <var>G</var> at the vertex <var>v</var>. The group <var>G</var> must fix the vertex <var>v</var>, otherwise <code>Error</code>() will be called. The operation <code>ProjectionNC</code> does the same thing, except it does not check whether <var>G</var> fixes the vertex <var>v</var>. <pre> gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> Projection(StabilizerOfVertex(Basilica, [1,2,1]), [1,2,1]); < v, u > </pre> <p> <a name = "SSEC003.9"></a> <li><code>ProjStab( </code><var>G</var><code>, </code><var>v</var><code> ) O</code> <p> Returns the projection of the stabilizer of <var>v</var> at itself. It is a shortcut for <code>Projection</code>(<code>StabilizerOfVertex</code>(G, v), v) (see <a href="CHAP002.htm#SSEC003.8">Projection</a>, <a href="CHAP002.htm#SSEC003.5">StabilizerOfVertex</a>). <pre> gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> ProjStab(Basilica, [1,2,1]); < v, u > </pre> <p> <a name = "SSEC003.10"></a> <li><code>FindGroupRelations( </code><var>G</var><code>[, </code><var>max_len</var><code>, </code><var>max_num_rels</var><code>] ) O</code> <li><code>FindGroupRelations( </code><var>subs_words</var><code>[, </code><var>names</var><code>, </code><var>max_len</var><code>, </code><var>max_num_rels</var><code>] ) O</code> <p> Finds group relations between the generators of the group <var>G</var> or in the group generated by <var>subs_words</var>. Stops after investigating all words of length up to <var>max_len</var> elements or when it finds <var>max_num_rels</var> relations. The optional argument <var>names</var> is a list of names of generators of the same length as <var>subs_words</var>. 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 <var>subs_words</var>. If <var>max_len</var> or <var>max_num_rels</var> are not specified, they are assumed to be <code>infinity</code>. Note that if the rewring system (see <a href="CHAP002.htm#SSEC006.1">AG_UseRewritingSystem</a>) for group <var>G</var> is used, then this operation returns relations not contained in the rewriting system rules (see <a href="CHAP002.htm#SSEC006.4">AG_RewritingSystemRules</a>). This operation can be applied to any group, not only to a group generated by automata. <pre> 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*y^-1*x*y^-1*x [ x^2, y^-3, y^-1*x*y^-1*x*y^-1*x ] </pre> <p> <a name = "SSEC003.11"></a> <li><code>FindSemigroupRelations( </code><var>G</var><code>[, </code><var>max_len</var><code>, </code><var>max_num_rels</var><code>] ) O</code> <li><code>FindSemigroupRelations( </code><var>subs_words</var><code>[, </code><var>names</var><code>, </code><var>max_len</var><code>, </code><var>max_num_rels</var><code>] ) O</code> <p> Finds semigroup relations between the generators of the group or semigroup <var>G</var>, or in the semigroup generated by <var>subs_words</var>. The arguments have the same meaning as in <code>FindGroupRelations</code> (<a href="CHAP002.htm#SSEC003.10">FindGroupRelations</a>). 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 <i>w</i>=1 one has to define <var>G</var> as a monoid or to include the trivial automorphism into <var>subs_words</var> (for instance, as <code>One(g)</code> for any element <code>g</code> acting on the same tree). This operation can be applied for any semigroup, not only for a semigroup generated by automata. <pre> 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^2*v^-1*u*v^-1*u^2*v*u=u*v^-1*u^2*v*u*v*u^2*v^-1 v*u*v*u^2*v^-1*u*v^-1*u^2=u^2*v*u*v*u^2*v^-1*u*v^-1 [ [ v*u^2*v^-1*u^2, u^2*v*u^2*v^-1 ], [ v*u^2*v^-1*u*v^-1*u^2*v*u, u*v^-1*u^2*v*u*v*u^2*v^-1 ], [ v*u*v*u^2*v^-1*u*v^-1*u^2, u^2*v*u*v*u^2*v^-1*u*v^-1 ] ] 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 ] ] </pre> <p> <a name = "SSEC003.12"></a> <li><code>Iterator( </code><var>G</var><code>[, </code><var>max_len</var><code>] ) M</code> <p> Provides a possibility to loop over elements of a group (semigroup, monoid) generated by automata. If <var>max_len</var> is given stops after enumerating all elements of length up to <var>max_len</var>. <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> iter := Iterator(GrigorchukGroup, 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 ] </pre> <p> <a name = "SSEC003.13"></a> <li><code>FindElement( </code><var>G</var><code>, </code><var>func</var><code>, </code><var>val</var><code>, </code><var>max_len</var><code> ) O</code> <a name = "SSEC003.13"></a> <li><code>FindElements( </code><var>G</var><code>, </code><var>func</var><code>, </code><var>val</var><code>, </code><var>max_len</var><code> ) O</code> <p> The first function enumerates elements of the group (semigroup, monoid) <var>G</var> until it finds an element <i>g</i> of length at most <var>max_len</var>, for which <var>func</var>(<i>g</i>)=<var>val</var>. Returns <i>g</i> if such an element was found and <code>fail</code> otherwise. <p> The second function enumerates elements of the group (semigroup, monoid) of length at most <var>max_len</var> and returns the list of elements <i>g</i>, for which <var>func</var>(<i>g</i>)=<var>val</var>. <p> These functions are based on <code>Iterator</code> operation (see <a href="CHAP002.htm#SSEC003.12">Iterator</a>), so can be applied in more general settings whenever <font face="Gill Sans,Helvetica,Arial">GAP</font> 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. <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> FindElement(GrigorchukGroup, Order, 16, 5); a*b gap> FindElements(GrigorchukGroup,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*b*a*c, b*a*c*a*c, c*a*b*a*b, c*a*c*a*b ] </pre> <p> <a name = "SSEC003.14"></a> <li><code>FindElementOfInfiniteOrder( </code><var>G</var><code>, </code><var>max_len</var><code>, </code><var>depth</var><code> ) O</code> <a name = "SSEC003.14"></a> <li><code>FindElementsOfInfiniteOrder( </code><var>G</var><code>, </code><var>max_len</var><code>, </code><var>depth</var><code> ) O</code> <p> The first function enumerates elements of the group <var>G</var> up to length <var>max_len</var> until it finds an element <i>g</i> of infinite order, such that <code>OrderUsingSections</code>(<i>g</i>,<var>depth</var>) (see <a href="CHAP003.htm#SSEC002.6">OrderUsingSections</a>) is <code>infinity</code>. In other words all sections of every element up to depth <var>depth</var> are investigated. In case if the element belongs to the group generated by bounded automaton (see <a href="CHAP002.htm#SSEC002.12">IsGeneratedByBoundedAutomaton</a>) one can set <var>depth</var> to be <code>infinity</code>. <p> The second function returns the list of all such elements up to length <var>max_len</var>. <p> <pre> 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 </pre> <p> <a name = "SSEC003.15"></a> <li><code>SphericallyTransitiveElement( </code><var>G</var><code> ) A</code> <p> For a self-similar group <var>G</var> acting on a binary tree returns an element of <var>G</var> acting spherically transitively on the levels of the tree if such an element exists and <code>fail</code> otherwise. See also <code>ContainsSphericallyTransitiveElement</code> (<a href="CHAP002.htm#SSEC002.6">ContainsSphericallyTransitiveElement</a>). <pre> 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 </pre> <p> <a name = "SSEC003.16"></a> <li><code>Growth( </code><var>G</var><code>, </code><var>max_len</var><code> ) O</code> <p> Returns a list of the first values of the growth function of a group (semigroup, monoid) <var>G</var>. If <var>G</var> is a monoid it computes the growth function at {0,1,…,<i>max</i><sub><i>l</i></sub><i>en</i> }, and for a semigroup without identity at {1,…,<i>max</i><sub><i>l</i></sub><i>en</i> }. <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> Growth(GrigorchukGroup, 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 ] </pre> <p> <a name = "SSEC003.17"></a> <li><code>ListOfElements( </code><var>G</var><code>, </code><var>max_len</var><code> ) O</code> <p> Returns the list of all different elements of a group (semigroup, monoid) <var>G</var> up to length <var>max_len</var>. <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> ListOfElements(GrigorchukGroup, 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 ] </pre> <p> <a name = "SSEC003.18"></a> <li><code>FindNucleus( </code><var>G</var><code>[, </code><var>max_nucl</var><code>, </code><var>print_info</var><code>] ) O</code> <p> Given a self-similar group <var>G</var> it tries to find its nucleus. If the group is not contracting it will loop forever. When it finds the nucleus it returns the triple [<code>GroupNucleus</code>(<var>G</var>), <code>GeneratingSetWithNucleus</code>(<var>G</var>), <code>GeneratingSetWithNucleusAutom</code>(<var>G</var>)] (see <a href="CHAP002.htm#SSEC005.1">GroupNucleus</a>, <a href="CHAP002.htm#SSEC005.2">GeneratingSetWithNucleus</a>, <a href="CHAP002.htm#SSEC005.3">GeneratingSetWithNucleusAutom</a>). <p> If <var>max_nucl</var> is given it stops after finding <var>max_nucl</var> elements that need to be in the nucleus and returns <code>fail</code> if the nucleus was not found. <p> An optional argument <var>print_info</var> is a boolean telling whether to print results of intermediate computations. The default value is <code>true</code>. <p> Use <code>IsNoncontracting</code> (see <a href="CHAP002.htm#SSEC002.10">IsNoncontracting</a>) to try to show that <var>G</var> is noncontracting. <p> <pre> 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> ] </pre> <p> <a name = "SSEC003.19"></a> <li><code>LevelOfFaithfulAction( </code><var>G</var><code> ) A</code> <li><code>LevelOfFaithfulAction( </code><var>G</var><code>, </code><var>max_lev</var><code> ) A</code> <p> For a given finite self-similar group <var>G</var> determines the smallest level of the tree, where <var>G</var> acts faithfully, i.e. the stabilizer of this level in <var>G</var> is trivial. The idea here is that for a self-similar group all nontrivial level stabilizers are different. If <var>max_lev</var> is given it finds only first <var>max_lev</var> quotients by stabilizers and if all of them have different size it returns <code>fail</code>. If <var>G</var> is infinite and <var>max_lev</var> is not specified it will loop forever. <p> See also <code>IsomorphismPermGroup</code> (<a href="CHAP002.htm#SSEC003.20">IsomorphismPermGroup</a>). <pre> 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> LevelOfFaithfulAction(AddingMachine, 10); fail </pre> <p> <a name = "SSEC003.20"></a> <li><code>IsomorphismPermGroup( </code><var>G</var><code> ) O</code> <li><code>IsomorphismPermGroup( </code><var>G</var><code>, </code><var>max_lev</var><code> ) O</code> <p> For a given finite group <var>G</var> generated by initial automata or by elements defined by wreath recursion computes an isomorphism from <var>G</var> into a finite permutational group. If <var>G</var> is not known to be self-similar (see <a href="CHAP002.htm#SSEC002.8">IsSelfSimilar</a>) the isomorphism is based on the regular representation, which works generally much slower. If <var>G</var> is self-similar there is a level of the tree (see <a href="CHAP002.htm#SSEC003.19">LevelOfFaithfulAction</a>), where <var>G</var> acts faithfully. The corresponding representation is returned in this case. If <var>max_lev</var> is given it finds only the first <var>max_lev</var> quotients by stabilizers and if all of them have different size it returns <code>fail</code>. If <var>G</var> is infinite and <var>max_lev</var> is not specified it will loop forever. <p> For example, consider a subgroup 〈<i>a</i>, <i>b</i>〉 of Grigorchuk group. <pre> gap> GrigorchukGroup := 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) </pre> <p> <a name = "SSEC003.21"></a> <li><code>Random( </code><var>G</var><code> ) O</code> <p> Returns a random element of a group (semigroup) <var>G</var>. The operation is based on the generator of random elements in free groups and semigroups. <p> <pre> gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> Random( Basilica ); v*u^-3 </pre> <p> <a name = "SSEC003.22"></a> <li><code>MarkovOperator( </code><var>G</var><code>, </code><var>lev</var><code> ) F</code> <p> Computes the matrix of the Markov operator related to the group <var>G</var> on the <var>lev</var>-th level of the tree. If the group <var>G</var> is generated by <i>g</i><sub>1</sub>,<i>g</i><sub>2</sub>,…,<i>g</i><sub><i>n</i></sub> then the Markov operator is defined as (<tt>PermOnLevelAsMatrix</tt>(<i>g</i><sub>1</sub>)+…+<tt>PermOnLevelAsMatrix</tt>(<i>g</i><sub><i>d</i></sub>)+ <tt>PermOnLevelAsMatrix</tt>(<i>g</i><sub>1</sub><sup>−1</sup>)+…+<tt>PermOnLevelAsMatrix</tt>(<i>g</i><sub><i>d</i></sub><sup>−1</sup>))/(2*<i>d</i>). See also <code>PermOnLevelAsMatrix</code> (<a href="CHAP003.htm#SSEC002.9">PermOnLevelAsMatrix</a>). <pre> 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 ] ] </pre> <p> <a name = "SSEC003.23"></a> <li><code>AbelImage( </code><var>obj</var><code> ) A</code> <p> Returns image of <var>obj</var> 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. <p> <a name = "SSEC003.24"></a> <li><code>DiagonalPower( </code><var>fam</var><code>[, </code><var>k</var><code>] ) O</code> <p> For a given automaton group <var>G</var> acting on alphabet <i>X</i> and corresponding family <var>fam</var> of automata one can consider the action of <i>G</i> <sup><i>k</i> </sup> on <i>X</i><sup><i>k</i> </sup> defined by (<i>x</i><sub>1</sub>,<i>x</i><sub>2</sub>,…, <i>x</i><sub><i>k</i></sub>)<sup>(<i>g</i><sub>1</sub>,<i>g</i><sub>2</sub>,…,<i>g</i><sub><i>k</i></sub>)</sup>=(<i>x</i><sub>1</sub><sup><i>g</i><sub>1</sub></sup>,<i>x</i><sub>2</sub><sup><i>g</i><sub>2</sub></sup>,…,<i>x</i><sub><i>k</i></sub><sup><i>g</i><sub><i>k</i></sub></sup>). This function constructs a self-similar group, which encodes this action. If <var>k</var> is not given it is assumed to be 2. <pre> 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) </pre> <p> <a name = "SSEC003.25"></a> <li><code>MultAutomAlphabet( </code><var>fam</var><code> ) O</code> <p> <a name = "SSEC003.26"></a> <li><code>UnderlyingAutomFamily( </code><var>G</var><code> ) A</code> <p> Returns the family to which the elements of <var>G</var> belong. <p> <p> <h2><a name="SECT004">2.4 Self-similar groups and semigroups defined by wreath recursion</a></h2> <p><p> <a name = "SSEC004.1"></a> <li><code>IsFiniteState( </code><var>G</var><code> ) P</code> <p> For a group or semigroup of homomorphisms of the tree defined using a wreath recursion, returns <code>true</code> 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 <var>G</var> is a finite-state group it automatically computes the attributes <code>UnderlyingAutomatonGroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.4">UnderlyingAutomatonGroup</a>), <code>IsomorphicAutomGroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.2">IsomorphicAutomGroup</a>) and <code>MonomorphismToAutomatonGroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.6">MonomorphismToAutomatonGroup</a>). For a finite-state semigroup it computes the corresponding attributes <code>UnderlyingAutomatonSemigroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.5">UnderlyingAutomatonSemigroup</a>), <code>IsomorphicAutomSemigroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.3">IsomorphicAutomSemigroup</a>) and <code>MonomorphismToAutomatonSemigroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.7">MonomorphismToAutomatonSemigroup</a>). <pre> 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 </pre> <p> <a name = "SSEC004.2"></a> <li><code>IsomorphicAutomGroup( </code><var>G</var><code> ) AM</code> <p> In case <var>G</var> is finite-state tries to compute a group generated by automata, isomorphic to <var>G</var>, which is a subgroup of <code>UnderlyingAutomatonGroup</code>(<var>G</var>) (see <a href="CHAP002.htm#SSEC004.4">UnderlyingAutomatonGroup</a>). The natural isomorphism between <var>G</var> and <code>IsomorphicAutomGroup</code>(<var>G</var>) is stored in the attribute <code>MonomorphismToAutomatonGroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.6">MonomorphismToAutomatonGroup</a>). In some cases it may be useful to check if <var>G</var> is finite. <pre> 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 ] </pre> <p> All these operations work also for the subgroups of groups generated by <code>SelfSimilarGroup</code>. (<a href="CHAP002.htm#SSEC001.3">SelfSimilarGroup</a>). <pre> gap> T := Group([b*a, a*b]); < b*a, a*b > gap> IT := IsomorphicAutomGroup(T); < a1, a4 > </pre> Note, that different groups have different <code>UnderlyingAutomGroup</code> attributes. For example, the generator <code>a1</code> of group <code>IT</code> above is different from the generator <code>a1</code> of group <code>IR</code>. <p> <a name = "SSEC004.3"></a> <li><code>IsomorphicAutomSemigroup( </code><var>G</var><code> ) AM</code> <p> In case <var>G</var> is finite-state returns a semigroup generated by automata, isomorphic to <var>G</var>, which is a subsemigroup of <code>UnderlyingAutomatonSemigroup</code>(<var>G</var>) (see <a href="CHAP002.htm#SSEC004.5">UnderlyingAutomatonSemigroup</a>). The natural isomorphism between <var>G</var> and <code>IsomorphicAutomSemigroup</code>(<var>G</var>) is stored in the attribute <code>MonomorphismToAutomatonSemigroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.7">MonomorphismToAutomatonSemigroup</a>). <pre> 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 ] </pre> <p> All these operations work also for the subsemigroups of semigroups generated by <code>SelfSimilarSemigroup</code> (<a href="CHAP002.htm#SSEC001.4">SelfSimilarSemigroup</a>). <pre> gap> T := Semigroup([a*b, b^2]); < a*b, b^2 > gap> IT := IsomorphicAutomSemigroup(T); < a1, a4 > </pre> Note, that different semigroups have different <code>UnderlyingAutomSemigroup</code> attributes. For example, the generator <code>a1</code> of semigroup <code>IT</code> above is different from the generator <code>a1</code> of semigroup <code>IR</code>. <p> <a name = "SSEC004.4"></a> <li><code>UnderlyingAutomatonGroup( </code><var>G</var><code> ) AM</code> <p> In case <var>G</var> is finite-state returns a self-similar closure of <var>G</var> as a group generated by automaton. The natural monomorphism from <var>G</var> and <code>UnderlyingAutomatonGroup</code>(<var>G</var>) is stored in the attribute <code>MonomorphismToAutomatonGroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.6">MonomorphismToAutomatonGroup</a>). If <var>G</var> is created by <code>SelfSimilarGroup</code> (see <a href="CHAP002.htm#SSEC001.3">SelfSimilarGroup</a>), then the self-similar closure of <var>G</var> coincides with <var>G</var>, so one can use <code>MonomorphismToAutomatonGroup</code>(<var>G</var>) to get preimages of elements of <code>UnderlyingAutomatonGroup</code>(<var>G</var>) in <var>G</var>. See the example for <code>IsomorphicAutomGroup</code> (<a href="CHAP002.htm#SSEC004.2">IsomorphicAutomGroup</a>). <p> <a name = "SSEC004.5"></a> <li><code>UnderlyingAutomatonSemigroup( </code><var>G</var><code> ) AM</code> <p> In case <var>G</var> is finite-state returns a self-similar closure of <var>G</var> as a semigroup generated by automaton. The natural monomorphism from <var>G</var> and <code>UnderlyingAutomatonSemigroup</code>(<var>G</var>) is stored in the attribute <code>MonomorphismToAutomatonSemigroup</code>(<var>G</var>) (<a href="CHAP002.htm#SSEC004.7">MonomorphismToAutomatonSemigroup</a>). If <var>G</var> is created by <code>SelfSimilarSemigroup</code> (see <a href="CHAP002.htm#SSEC001.4">SelfSimilarSemigroup</a>), then the self-similar closure of <var>G</var> coincides with <var>G</var>, so one can use <code>MonomorphismToAutomatonSemigroup</code>(<var>G</var>) to get preimages of elements of <code>UnderlyingAutomatonSemigroup</code>(<var>G</var>) in <var>G</var>. See the example for <code>IsomorphicAutomSemigroup</code> (<a href="CHAP002.htm#SSEC004.3">IsomorphicAutomSemigroup</a>). <p> <a name = "SSEC004.6"></a> <li><code>MonomorphismToAutomatonGroup( </code><var>G</var><code> ) AM</code> <p> In case <var>G</var> is finite-state returns a monomorphism from <var>G</var> into <code>UnderlyingAutomatonGroup</code>(<var>G</var>) (see <a href="CHAP002.htm#SSEC004.4">UnderlyingAutomatonGroup</a>). If <var>G</var> is created by <code>SelfSimilarGroup</code> (see <a href="CHAP002.htm#SSEC001.3">SelfSimilarGroup</a>), then one can use <code>MonomorphismToAutomatonGroup</code>(<var>G</var>) to get preimages of elements of <code>UnderlyingAutomatonGroup</code>(<var>G</var>) in <var>G</var>. See the example for <code>IsomorphicAutomGroup</code> (<a href="CHAP002.htm#SSEC004.2">IsomorphicAutomGroup</a>). <p> <a name = "SSEC004.7"></a> <li><code>MonomorphismToAutomatonSemigroup( </code><var>G</var><code> ) AM</code> <p> In case <var>G</var> is finite-state returns a monomorphism from <var>G</var> into <code>UnderlyingAutomatonSemigroup</code>(<var>G</var>) (see <a href="CHAP002.htm#SSEC004.5">UnderlyingAutomatonSemigroup</a>). If <var>G</var> is created by <code>SelfSimilarSemigroup</code> (see <a href="CHAP002.htm#SSEC001.4">SelfSimilarSemigroup</a>), then one can use <code>MonomorphismToAutomatonSemigroup</code>(<var>G</var>) to get preimages of elements of <code>UnderlyingAutomatonSemigroup</code>(<var>G</var>) in <var>G</var>. See the example for <code>IsomorphicAutomSemigroup</code> (<a href="CHAP002.htm#SSEC004.3">IsomorphicAutomSemigroup</a>). <p> <p> <h2><a name="SECT005">2.5 Contracting groups</a></h2> <p><p> <a name = "SSEC005.1"></a> <li><code>GroupNucleus( </code><var>G</var><code> ) AM</code> <p> Tries to compute the <var>nucleus</var> (see the definition in <a href="CHAP001.htm#SECT001">Short math background</a>) of a self-similar group <var>G</var>. Note that this set need not contain the original generators of <var>G</var>. It uses <code>FindNucleus</code> (see <a href="CHAP002.htm#SSEC003.18">FindNucleus</a>) operation and behaves accordingly: if the group is not contracting it will loop forever. See also <code>GeneratingSetWithNucleus</code> (<a href="CHAP002.htm#SSEC005.2">GeneratingSetWithNucleus</a>). <p> <pre> 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 ] </pre> <p> <a name = "SSEC005.2"></a> <li><code>GeneratingSetWithNucleus( </code><var>G</var><code> ) AM</code> <p> Tries to compute the generating set of a self-similar group <var>G</var> that includes the original generators and the <var>nucleus</var> (see <a href="CHAP001.htm#SECT001">Short math background</a>) of <var>G</var>. It uses <code>FindNucleus</code> operation and behaves accordingly: if the group is not contracting it will loop forever (modulo memory constraints, of course). See also <code>GroupNucleus</code> (<a href="CHAP002.htm#SSEC005.1">GroupNucleus</a>). <p> <pre> 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 ] </pre> <p> <a name = "SSEC005.3"></a> <li><code>GeneratingSetWithNucleusAutom( </code><var>G</var><code> ) AM</code> <p> Computes the automaton of the generating set that includes the nucleus of the contracting group <var>G</var>. See also <code>GeneratingSetWithNucleus</code> (<a href="CHAP002.htm#SSEC005.2">GeneratingSetWithNucleus</a>). <pre> gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" ); < u, v > gap> B_autom := GeneratingSetWithNucleusAutom(Basilica); <automaton> gap> Print(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) </pre> <p> <a name = "SSEC005.4"></a> <li><code>ContractingLevel( </code><var>G</var><code> ) AM</code> <p> Given a contracting group <var>G</var> with generating set <i>N</i> that includes the nucleus, stored in <code>GeneratingSetWithNucleus</code>(<var>G</var>) (see <a href="CHAP002.htm#SSEC005.2">GeneratingSetWithNucleus</a>) computes the minimal level <i>n</i>, such that for every vertex <i>v</i> of the <i>n</i>-th level and all <i>g</i>, <i>h</i> ∈ <i>N</i> the section <i>gh</i>|<sub><i>v</i></sub> ∈ <i>N</i>. <p> In case if it is not known whether <var>G</var> is contracting it first tries to compute the nucleus. If <var>G</var> happens to be noncontracting, it will loop forever. One can also use <code>IsNoncontracting</code> (see <a href="CHAP002.htm#SSEC002.10">IsNoncontracting</a>) or <code>FindNucleus</code> (see <a href="CHAP002.htm#SSEC003.18">FindNucleus</a>) directly. <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> ContractingLevel(GrigorchukGroup); 1 gap> ContractingLevel(Basilica); 2 </pre> <p> <a name = "SSEC005.5"></a> <li><code>ContractingTable( </code><var>G</var><code> ) AM</code> <p> Given a contracting group <var>G</var> with generating set <i>N</i> of size <i>k</i> that includes the nucleus, stored in <code>GeneratingSetWithNucleus</code>(<var>G</var>) (see <a href="CHAP002.htm#SSEC005.2">GeneratingSetWithNucleus</a>) computes the <i>k</i>×<i>k</i> table, whose [i][j]-th entry contains decomposition of <i>N</i>[i]<i>N</i>[j] on the <code>ContractingLevel</code>(<var>G</var>) level (see <a href="CHAP002.htm#SSEC005.4">ContractingLevel</a>). By construction the sections of <i>N</i>[i]<i>N</i>[j] on this level belong to <i>N</i>. This table is used in the algorithm solving the word problem in polynomial time. <p> In case if it is not known whether <var>G</var> is contracting it first tries to compute the nucleus. If <var>G</var> happens to be noncontracting, it will loop forever. One can also use <code>IsNoncontracting</code> (see <a href="CHAP002.htm#SSEC002.10">IsNoncontracting</a>) or <code>FindNucleus</code> (see <a href="CHAP002.htm#SSEC003.18">FindNucleus</a>) directly. <pre> gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)"); < a, b, c, d > gap> ContractingTable(GrigorchukGroup); [ [ (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) ] ] </pre> <p> <a name = "SSEC005.6"></a> <li><code>UseContraction( </code><var>G</var><code> ) O</code> <a name = "SSEC005.6"></a> <li><code>DoNotUseContraction( </code><var>G</var><code> ) O</code> <p> For a contracting automaton group <var>G</var> 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 <var>true</var> 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 <code>DoNotUseContraction</code>(<var>G</var>). <p> Note also then in order to use the polynomial time algorithm the <code>ContractingTable(G)</code> (see <a href="CHAP002.htm#SSEC005.5">ContractingTable</a>) 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. <p> Below we provide an example which shows that both methods can be of use. <pre> 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; 11336 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 251 gap> FindGroupRelations(G, 5);; time; a^2 b^2 c^2 b*a*b*c*a*b*a*b*c*a b*c*a*c*a*b*c*a*c*a 881 gap> DoNotUseContraction(G);; gap> IsOne(Comm(v,w)); time; true 3855 gap> FindGroupRelations(G, 5);; time; a^2 b^2 c^2 b*a*b*c*a*b*a*b*c*a b*c*a*c*a*b*c*a*c*a 451 </pre> <p> <p> <h2><a name="SECT006">2.6 Rewriting Systems</a></h2> <p><p> It is possible to use basic relators in all computations performed in a self-similar group. <p> <a name = "SSEC006.1"></a> <li><code>AG_UseRewritingSystem( </code><var>G</var><code>[, </code><var>setting</var><code>] ) O</code> <p> Tells whether computations in the group <var>G</var> should use a rewriting system. <var>setting</var> defaults to <code>true</code> if omitted. This function initially only tries to find involutions in <var>G</var>. See <code>AG_AddRelators</code> (<a href="CHAP002.htm#SSEC006.2">AG_AddRelators</a>) and <code>AG_UpdateRewritingSystem</code> (<a href="CHAP002.htm#SSEC006.3">AG_UpdateRewritingSystem</a>) for the ways to add more relators. <p> <pre> 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 </pre> <p> <a name = "SSEC006.2"></a> <li><code>AG_AddRelators( </code><var>G</var><code>, </code><var>relators</var><code> ) O</code> <p> Adds relators from the list <var>relators</var> to the rewriting system used in <var>G</var>. <p> <pre> 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 </pre> <p> 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 <code>AG_UpdateRewritingSystem</code> (see <a href="CHAP002.htm#SSEC006.3">AG_UpdateRewritingSystem</a>) and <code>AG_UseRewritingSystem</code> (see <a href="CHAP002.htm#SSEC006.1">AG_UseRewritingSystem</a>) to use these relators in computations. In the example below we consider a finite group <i>H</i>, in which <i>a</i>=<i>b</i>, 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). <pre> 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 </pre> <p> <a name = "SSEC006.3"></a> <li><code>AG_UpdateRewritingSystem( </code><var>G</var><code>, </code><var>maxlen</var><code> ) O</code> <p> Tries to find new relators of length up to <var>maxlen</var> and adds them into the rewriting system. It can also be used after introducing new relators via <code>AG_AddRelators</code> (see <a href="CHAP002.htm#SSEC006.2">AG_AddRelators</a>). <p> <pre> 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 </pre> <p> <a name = "SSEC006.4"></a> <li><code>AG_RewritingSystemRules( </code><var>G</var><code> ) O</code> <p> Returns the list of rules used in the rewriting system of group <var>G</var>. <pre> 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^-1, a ], [ b^-1, b ], [ c^-1, c ], [ d^-1, d ] ] </pre> <p> <p> [<a href = "chapters.htm">Up</a>] [<a href ="CHAP001.htm">Previous</a>] [<a href ="CHAP003.htm">Next</a>] [<a href = "theindex.htm">Index</a>] <P> <address>automgrp manual<br>September 2008 </address></body></html>