<h3>7 <span class="Heading">Self-similar groups, monoids and semigroups</span></h3>
<p>Self-similar groups, monoids and semigroups (below <em>FR semigroups</em>) are simply groups, monoids and semigroups whose elements are FR machines. They naturally act on the alphabet of their elements, and on sequences over that alphabet.</p>
<p>Most non-trivial calculations in FR groups are performed as follows: <strong class="pkg">GAP</strong> searches through words of short length in the generating set of a FR group to find a solution to a group-theoretic question, and at the same time searches through the finite quotients to prove the inexistence of a solution. Often the calculation ends with the answer <code class="keyw">fail</code>, which means that no definite answer, neither positive nor negative, could be found; however, the cases where the calculation actually terminates have been most useful.</p>
<p>The maximal length of words to consider in the search is controlled by the variable <code class="code">FR_SEARCH.radius</code> (initially 10), and the maximal depth of the tree in which to search is controlled by the variable <code class="code">FR_SEARCH.depth</code> (initially 6). These limits can be modified in any function call using <strong class="pkg">GAP</strong>'s options mechanism, e.g. in Index(G,H:FRdepth:=5,FRradius:=5).
<h4>7.1 <span class="Heading">Creators for FR semigroups</span></h4>
<p>The most straightforward creation method for FR groups is <code class="code">Group()</code>, applied with FR elements as arguments. There are shortcuts to this somewhat tedious method:</p>
<p>This function constructs a new FR group/monoid/semigroup, generated by group FR elements. It receives as argument any number of strings, each of which represents a generator of the object to be constructed.</p>
<p>Each <var class="Arg">definition</var> is of the form <code class="code">"name=projtrans"</code>, where each of <code class="code">proj</code> and <code class="code">trans</code> is optional. <code class="code">proj</code> is of the form <code class="code"><w1,...,wd></code>, where each <code class="code">wi</code> is a (possibly empty) word in the <code class="code">name</code>s or is 1. <code class="code">trans</code> is either a permutation in disjoint cycle notation, or a list, representing the images of a permutation.</p>
<p>The last argument may be one of the filters <code class="code">IsMealyElement</code>, <code class="code">IsFRMealyElement</code> or <code class="code">IsFRElement</code>. By default, if each of the states of generators is a generator or 1, the elements of the created object will be Mealy elements; otherwise, they will be FR elements. Specifying such a filter requires them to be in the appropriate category; e.g., <code class="code">FRGroup("a=(1,2)",IsFRMealyElement)</code> asks for the resulting group to be generated by FR-Mealy elements. The generators must of course be finite-state.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FRGroup("a=(1,2)","b=(1,2,3,4,5)"); Size(last);</span>
<self-similar group over [ 1 .. 5 ] with 2 generators>
120
<span class="GAPprompt">gap></span> <span class="GAPinput">Dinfinity := FRGroup("a=(1,2)","b=<a,b>");</span>
<self-similar group over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(Dinfinity);</span>
#I Assigned the global variables [ a, b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(a); Order(b); Order(a*b);</span>
2
2
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">ZZ := FRGroup("t=<,t>[2,1]");</span>
<self-similar group over [ 1 .. 2 ] with 1 generator>
tau := FRElement([[[b,1],[1]]],[()],[1]);
<2|f3>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(Dinfinity,ZZ);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(Dinfinity^tau,ZZ);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">Index(Dinfinity^tau,ZZ);</span>
2
</pre></div>
<p>This command constructs a new FR machine, in a format similar to <code class="func">FRGroup</code> (<a href="chap7.html#X7AE8F92383272329"><span class="RefLink">7.1-1</span></a>); namely, the arguments are strings of the form"gen=<word-1,...,word-d>perm"; each <code class="code">word-i</code> is a word in the generators; and <code class="code">perm</code> is a transformation, either written in disjoint cycle or in images notation.</p>
<p>Except in the semigroup case, <code class="code">word-i</code> is allowed to be the empty string; and the "<...>" may be skipped altogether. In the group or IMG case, each <code class="code">word-i</code> may also contain inverses.</p>
<p>The following example constructs the "universal Grigorchuk machine".</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := NewGroupFRMachine("a=(1,2)(3,4)(5,6)","b=<a,b,a,b,,b>",</span> "c=<a,c,,c,a,c>","d=<,d,a,d,a,d>");
<span class="GAPprompt">gap></span> <span class="GAPinput"><FR machine with alphabet [ 1, 2, 3, 4, 5, 6 ] on Group( [ a, b, c, d ] )></span>
</pre></div>
<p>This function constructs a new FR group/monoid/semigroup <code class="code">g</code>, generated by all the states of the FR machine <var class="Arg">m</var>. There is a bijective correspondence between <code class="code">GeneratorsOfFRMachine(m)</code> and the generators of <code class="code">g</code>, which is accessible via <code class="code">Correspondence(g)</code> (See <code class="func">Correspondence</code> (<a href="chap7.html#X7F15D57A7959FEF6"><span class="RefLink">7.1-4</span></a>)); it is a homomorphism from the stateset of <var class="Arg">m</var> to <code class="code">g</code>, or a list indicating for each state of <var class="Arg">m</var> a corresponding generator index in the generators of <code class="code">g</code> (with negatives for inverses, and 0 for identity).</p>
<p>In the non-<code class="code">NC</code> forms, redundant (equal, trivial or mutually inverse) states are removed from the generating set of <code class="code">g</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);; g := SCGroupNC(b);</span>
<self-similar group over [ 1 .. 2 ] with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(g);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">IsOne(Comm(g.2,g.2^g.1));</span>
true
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Correspondence</code>( <var class="Arg">g</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A correspondence between the generators of the underlying FR machine of <var class="Arg">g</var> and <var class="Arg">g</var>.</p>
<p>If <var class="Arg">g</var> was created as the state closure of an FR machine <code class="code">m</code>, this attribute records the correspondence between <code class="code">m</code> and <var class="Arg">g</var>.</p>
<p>If <code class="code">m</code> is a group/monoid/semigroup/algebra FR machine, then <code class="code">Correspondence(g)</code> is a homomorphism from the stateset of <code class="code">m</code> to <var class="Arg">g</var>.</p>
<p>If <code class="code">m</code> is a Mealy or vector machine, then <code class="code">Correspondence(g)</code> is a list, with in position <span class="SimpleMath">i</span> the index in the generating set of <var class="Arg">g</var> of state number <span class="SimpleMath">i</span>. This index is 0 if there is no corresponding generator because the state is trivial, and is negative if there is no corresponding generator because the inverse of state number <span class="SimpleMath">i</span> is a generator.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FullSCGroup</code>( <var class="Arg">...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FullSCMonoid</code>( <var class="Arg">...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FullSCSemigroup</code>( <var class="Arg">...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A maximal state-closed group/monoid/semigroup on the alphabet <var class="Arg">a</var>.</p>
<p>This function constructs a new FR group, monoid or semigroup, which contains all transformations with given properties of the tree with given alphabet.</p>
<p>The arguments can be, in any order: a semigroup, specifying which vertex actions are allowed; a set or domain, specifying the alphabet of the tree; an integer, specifying the maximal depth of elements; and a filter among <code class="func">IsFinitaryFRElement</code> (<a href="chap5.html#X793C427084F830CE"><span class="RefLink">5.2-10</span></a>), <code class="func">IsBoundedFRElement</code> (<a href="chap5.html#X82F4410E85C54C7E"><span class="RefLink">5.2-12</span></a>), <code class="func">IsPolynomialGrowthFRElement</code> (<a href="chap5.html#X81D4A3F27C5FAD96"><span class="RefLink">5.2-13</span></a>) and <code class="func">IsFiniteStateFRElement</code> (<a href="chap4.html#X7C4076707CBBE945"><span class="RefLink">4.2-12</span></a>).</p>
<p>This object serves as a container for all FR elements with alphabet <var class="Arg">a</var>. Random elements can be drawn from it; they are Mealy elements with a random number of states, and with the required properties.</p>
<p>This function constructs a new group/monoid/semigroup/Mealy FR machine, with (at least) one generator per generator of <var class="Arg">g</var>. This is done by adding all machines of all generators of <var class="Arg">g</var>, and minimizing.</p>
<p>In particular, if <var class="Arg">g</var> is state-closed, then <code class="code">SCGroup(FRMachineFRGroup(g))</code> gives a group isomorphic to <var class="Arg">g</var>, and similarly for monoids and semigroups.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismFRGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismFRMonoid</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An isomorphism towards a group/monoid/semigroup on a single FR machine.</p>
<p>Thisfunction constructs a new FR group/monoid/semigroup, such that all elements of the resulting object have the same underlying group/monoid/semigroup FR machine.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := IsomorphismFRGroup(GuptaSidkiGroup);</span>
[ <Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>,
<Mealy element on alphabet [ 1, 2, 3 ] with 4 states, initial state 1> ] ->
[ <3|identity ...>, <3|f1>, <3|f1^-1>, <3|f2> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(GuptaSidkiGroup.2);</span>
| 1 2 3
---+-----+-----+-----+
a | a,1 a,2 a,3
b | a,2 a,3 a,1
c | a,3 a,1 a,2
d | b,1 c,2 d,3
---+-----+-----+-----+
Initial state: d
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(GuptaSidkiGroup.2^phi);</span>
| 1 2 3
----+--------+---------+--------+
f1 | <id>,2 <id>,3 <id>,1
f2 | f1,1 f1^-1,2 f2,3
----+--------+---------+--------+
Initial state: f2
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FRGroupByVirtualEndomorphism</code>( <varclass="Arg">hom</var>[, <varclass="Arg">transversal</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A new self-similar group.</p>
<p>Thisfunction constructs a new FR group <code class="code">P</code>, generated by group FR elements. Its first argument is a virtual endomorphism of a group <code class="code">G</code>, i.e. a homomorphism from a subgroup <code class="code">H</code> to <code class="code">G</code>. The constructed FR group acts on a tree with alphabet a transversal of <code class="code">H</code> in <code class="code">G</code> (represented as <code class="code">[1..d]</code>), and is a homomorphic image of <code class="code">G</code>. The stabilizer of the first-level vertex corresponding to the trivial coset is the image of <code class="code">H</code>. Thisfunction is loosely speaking an inverse of <code class="func">VirtualEndomorphism</code> (<a href="chap7.html#X7DF2D9838625CDED"><span class="RefLink">7.2-29</span></a>).</p>
<p>The optional second argument is a transversal of <code class="code">H</code> in <code class="code">G</code>, either of type <code class="code">IsRightTransversal</code> or a list.</p>
<p>Furthermore, an option "MealyElement" can be passed to the function, as <code class="code">FRGroupByVirtualEndomorphism(f:MealyElement)</code>, to require the resulting group to be generated by Mealy elements and not FR elements. The call will succeed, of course, only if the representation of <code class="code">G</code> is finite-state.</p>
<p>The resulting FR group has an attribute <code class="code">Correspondence(P)</code> that records a homomorphism from <code class="code">G</code> to <code class="code">P</code>.</p>
<p>The example below constructs the binary adding machine, and a non-standard representation of it.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := FreeGroup(1);</span>
<free group on the generators [ f1 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := GroupHomomorphismByImages(Group(G.1^2),G,[G.1^2],[G.1]);</span>
[ f1^2 ] -> [ f1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">H := FRGroupByVirtualEndomorphism(f);</span>
<self-similar group over [ 1 .. 2 ] with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(H.1);</span>
| 1 2
----+--------+------+
x1 | <id>,2 x1,1
----+--------+------+
Initial state: x1
<span class="GAPprompt">gap></span> <span class="GAPinput">Correspondence(H);</span>
[ f1 ] -> [ <2|x1> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">H := FRGroupByVirtualEndomorphism(f,[G.1^0,G.1^3]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(H.1);</span>
| 1 2
----+---------+--------+
x1 | x1^-1,2 x1^2,1
----+---------+--------+
Initial state: x1
<span class="GAPprompt">gap></span> <span class="GAPinput">H := FRGroupByVirtualEndomorphism(f:MealyElement);</span>
<self-similar group over [ 1 .. 2 ] with 1 generator>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(H.1);</span>
| 1 2
---+-----+-----+
a | b,2 a,1
b | b,1 b,2
---+-----+-----+
Initial state: a
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TreeWreathProduct</code>( <varclass="Arg">g</var>, <varclass="Arg">h</var>, <varclass="Arg">x0</var>, <varclass="Arg">y0</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The tree-wreath product of groups <varclass="Arg">g,h</var>.</p>
<p>The tree-wreath product of two FR groups is a group generated by a copy of <varclass="Arg">g</var> and of <varclass="Arg">h</var>, in such a way that many conjugates of <varclass="Arg">g</var> commute.</p>
<p>More formally, assume without loss of generality that all generators of <varclass="Arg">g</var> are states of a machine <code class="code">m</code>, and that all generators of <varclass="Arg">h</var> are states of a machine <code class="code">n</code>. Then the tree-wreath product is generated by the images of generators of <varclass="Arg">g,h</var> in <code class="code">TreeWreathProduct(m,n,x0,y0)</code>.</p>
<p>For the operation on FR machines see <code class="func">TreeWreathProduct</code> (<a href="chap3.html#X7A0858097AA3FBDA"><span class="RefLink">3.5-8</span></a>)). It is described (with small variations, and in lesser generality) in <a href="chapBib.html#biBMR2197828">[Sid05]</a>. For example, in</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">w := TreeWreathProduct(AddingGroup(2),AddingGroup(2),1,1);</span>
<recursive group over [ 1 .. 4 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := w.1; b := w.2;</span>
<Mealy element on alphabet [ 1 .. 4 ] with 3 states>
<Mealy element on alphabet [ 1 .. 4 ] with 2 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(a); Order(b);</span>
infinity
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([-100..100],i->IsOne(Comm(a,a^(b^i))));</span> true
</pre></div>
<p>the group <code class="code">w</code> is the wreath product <span class="SimpleMath">Z≀ Z</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WeaklyBranchedEmbedding</code>( <varclass="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A embedding of <varclass="Arg">g</var> in a weakly branched group.</p>
<p>Thisfunction constructs a new FR group, on alphabet the square of the alphabet of <varclass="Arg">g</var>. It is generated by the canonical copy of <varclass="Arg">g</var> and by the tree-wreath product of <varclass="Arg">g</var> with an adding machine on the same alphabet as <varclass="Arg">g</var> (see <code class="func">TreeWreathProduct</code> (<a href="chap7.html#X79D75A7D80DD9AD1"><span class="RefLink">7.1-10</span></a>)). The function returns a group homomorphism into thisnew FR group.</p>
<p>The main result of <a href="chapBib.html#biBMR1995624">[SW03]</a> is that the resulting group <span class="SimpleMath">h</span> is weakly branched. More precisely, <span class="SimpleMath">h' contains |X|^2 copies of itself. gap> f := WeaklyBranchedEmbedding(BabyAleshinGroup);; gap> Range(f); <recursive group over [ 1 .. 4 ] with 8 generators> constructs a finitely generated branched group containing a free subgroup.
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermGroup</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismPermGroup</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the permutation group of <varclass="Arg">g</var>'s action on level l.
<p>The first function returns a permutation group on <span class="SimpleMath">d^l</span> points, where <span class="SimpleMath">d</span> is the size of <varclass="Arg">g</var>'s alphabet. It has as many generators as g, and represents the action of g on the lth layer of the tree.
<p>The second function returns a homomorphism from <varclass="Arg">g</var> to this permutation group.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FRGroup("a=(1,2)","b=<a,>"); Size(g);</span>
<self-similar group over [ 1 .. 2 ] with 2 generators>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">PermGroup(g,2);</span>
Group([ (1,3)(2,4), (1,2) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">PermGroup(g,3);</span>
Group([ (1,5)(2,6)(3,7)(4,8), (1,3)(2,4) ])
<span class="GAPprompt">gap></span> <span class="GAPinput">List([1..6],i->LogInt(Size(PermGroup(GrigorchukGroup,i)),2));</span>
[ 1, 3, 7, 12, 22, 42 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FRGroup("t=<,t>(1,2)"); Size(g);</span>
<self-similar group over [ 1 .. 2 ] with 1 generator>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">pi := EpimorphismPermGroup(g,5);</span>
MappingByFunction( <self-similar group over [ 1 .. 2 ] with 1 generator,
of size infinity>, Group([ (1,17,9,25,5,21,13,29,3,19,11,27,7,23,15,31,
2,18,10,26,6,22,14,30,4,20,12,28,8,24,16,32) ]), function( w ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(g.1);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(g.1^pi);</span>
32
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PcGroup</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismPcGroup</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the pc group of <varclass="Arg">g</var>'s action on level l.
<p>The first function returns a polycyclic group representing the action of <varclass="Arg">g</var> on the <varclass="Arg">l</var>th layer of the tree. It converts the permutation group <code class="code">PermGroup(g,l)</code> to a Pc group, in which computations are often faster.</p>
<p>The second function returns a homomorphism from <varclass="Arg">g</var> to this pc group.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := PcGroup(GrigorchukGroup,7); time;</span>
<pc group with 5 generators>
3370
<span class="GAPprompt">gap></span> <span class="GAPinput">NormalClosure(g,Group(g.3)); time;</span>
<pc group with 79 generators>
240
<span class="GAPprompt">gap></span> <span class="GAPinput">g := PermGroup(GrigorchukGroup,7); time;</span>
<permutation group with 5 generators>
3
<span class="GAPprompt">gap></span> <span class="GAPinput">NormalClosure(g,Group(g.3)); time;</span>
<permutation group with 5 generators>
5344
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FRGroup("t=<,t>(1,2)"); Size(g);</span>
<self-similar group over [ 1 .. 2 ] with 1 generator>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">pi := EpimorphismPcGroup(g,5);</span>
MappingByFunction( <self-similar group over [ 1 .. 2 ] with
1 generator, of size infinity>, Group([ f1, f2, f3, f4, f5 ]), function( w ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(g.1);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">Order(g.1^pi);</span>
32
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TransformationMonoid</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismTransformationMonoid</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the transformation monoid of <varclass="Arg">g</var>'s action on level l.
<p>The first function returns a transformation monoid on <span class="SimpleMath">d^l</span> points, where <span class="SimpleMath">d</span> is the size of <varclass="Arg">g</var>'s alphabet. It has as many generators as g, and represents the action of g on the lth layer of the tree.
<p>The second function returns a homomorphism from <varclass="Arg">g</var> to this transformation monoid.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TransformationSemigroup</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismTransformationSemigroup</code>( <varclass="Arg">g</var>, <varclass="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the transformation semigroup of <varclass="Arg">g</var>'s action on level l.
<p>The first function returns a transformation semigroup on <span class="SimpleMath">d^l</span> points, where <span class="SimpleMath">d</span> is the size of <varclass="Arg">g</var>'s alphabet. It has as many generators as g, and represents the action of g on the lth layer of the tree.
<p>The second function returns a homomorphism from <varclass="Arg">g</var> to this transformation semigroup.</p>
<p>Thisfunction returns an epimorphism to a polycyclic group, encoding the action on the first <varclass="Arg">l</var> levels of the tree and on the germs below. If <varclass="Arg">l</var> is omitted, it is assumed to be <span class="SimpleMath">0</span>.</p>
<p>Since the elements of <varclass="Arg">g</var> are finite automata, they map periodic sequences to periodic sequences. The action on the periods, and in the immediate vicinity of them, is called the <em>germ action</em> of <varclass="Arg">g</var>. Thisfunction returns the natural homomorphism from <varclass="Arg">g</var> to the wreath product of this germ group with the quotient of <varclass="Arg">g</var> acting on the <varclass="Arg">l</var>th layer of the tree.</p>
<p>The germ group, by default, is abelian. If it is finite, thisfunction returns a homomorphism to a Pc group; otherwise, a homomorphism to a polycyclic group.</p>
<p>The <code class="func">GrigorchukTwistedTwin</code> (<a href="chap9.html#X7E765AF77AAC21A6"><span class="RefLink">9.1-12</span></a>) is, for now, the only example with a hand-coded, non-abelian germ group.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">EpimorphismGermGroup(GrigorchukGroup,0);</span>
MappingByFunction( GrigorchukGroup, <pc group of size 4 with 2 generators>, function( g ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">List(GeneratorsOfGroup(GrigorchukGroup),x->x^last);</span>
[ <identity> of ..., f1, f1*f2, f2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StructureDescription(Image(last2));</span> "C2 x C2"
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FRGroup("t=<,t>(1,2)","m=<,m^-1>(1,2)");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">EpimorphismGermGroup(g,0);</span>
MappingByFunction( <state-closed, bounded group over [ 1, 2 ] with 2
generators>, Pcp-group with orders [ 0, 0 ], function( x ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">EpimorphismGermGroup(g,1);; Range(last); Image(last2);</span>
Pcp-group with orders [ 2, 0, 0, 0, 0 ]
Pcp-group with orders [ 2, 0, 0, 0 ]
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GermData</code>( <varclass="Arg">group</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GermValue</code>( <varclass="Arg">element</var>, <varclass="Arg">data</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The first command computes some data useful to determine the germ value of a group element; the second command computes these germ values. For more information on germs, see <code class="func">Germs</code> (<a href="chap5.html#X81592E3D79745A40"><span class="RefLink">5.2-24</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">data := GermData(GrigorchukGroup);</span>
rec( endo := [ f1, f2 ] -> [ f1*f2, f1 ], group := <pc group of size 4 with 2 generators>,
machines := [ ], map := [ <identity> of ..., f2, f1, f1*f2, <identity> of ... ],
nucleus := [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>, d, c, b, a ],
nucleusmachine := <Mealy machine on alphabet [ 1 .. 2 ] with 5 states> )
<span class="GAPprompt">gap></span> <span class="GAPinput">List(GeneratorsOfGroup(GrigorchukGroup),x->GermValue(x,data));</span>
[ <identity> of ..., f1*f2, f1, f2 ]
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StabilizerImage</code>( <varclass="Arg">g</var>, <varclass="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The group of all states at <varclass="Arg">v</var> of elements of <varclass="Arg">g</var> fixing <varclass="Arg">v</var>.</p>
<p>Thisfunction constructs a new FR group, consisting of all states at vertex <varclass="Arg">v</var> (which can be an integer or a list) of the stabilizer of <varclass="Arg">v</var> in <varclass="Arg">g</var>.</p>
<p>The result is <varclass="Arg">g</var> itself precisely if <varclass="Arg">g</var> is recurrent (see <code class="func">IsRecurrentFRSemigroup</code> (<a href="chap7.html#X7E2F34417EBB7673"><span class="RefLink">7.2-11</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := FRGroup("t=<,t>(1,2)","u=<,u^-1>(1,2)","b=<u,t>");</span>
<self-similar group over [ 1 .. 2 ] with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Stabilizer(G,1);</span>
<self-similar group over [ 1 .. 2 ] with 5 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfGroup(last);</span>
[ <2|u*t^-1>, <2|b>, <2|t^2>, <2|t*u>, <2|t*b*t^-1> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StabilizerImage(G,1);</span>
<self-similar group over [ 1 .. 2 ] with 5 generators>
<* manual.js Lübeck*
[ <2|identity between several styles and don't see the corresponding button.
</pre></div>
(jscontentfuncs.push(newfunc);).
<h5>7 A user can change the preferred style permanently by using the [ link and choosing one. Or one can append '?GAPDocStyle=mystyle' to the URL
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LevelStabilizer</code>( <varclass="Arg">g</var>, <varclass="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The fixator of the <varclass="Arg">n</var>th level of the tree.</p>
l subgroup java.lang.StringIndexOutOfBoundsException: Range [7, 5) out of bounds for length 36
<div class="example"><pre>
<span
&v stlist.(")java.lang.StringIndexOutOfBoundsException: Index 34 out of bounds for length 34
<span
tself-similar 1. with &;
<span class="GAPprompt">gap></span> <span class="GAPinput">Index(G,last);</ documentcreateAttributehref
java.lang.StringIndexOutOfBoundsException: Index 1 out of bounds for length 1
spanGAPprompt&<> =""IsNormallast2<span true
</pre></div>
C5002E683A044C1=X7C5002E683A044C1<a<pjava.lang.StringIndexOutOfBoundsException: Index 62 out of bounds for length 62
<h5>7.2-9 IsStateClosed</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsStateClosed</code>( <varclass="Arg">g</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if all states of elements of <varclass="Arg">g</var> belong to <varclass="Arg">g</var>.</p>
<p>Thisfunction tests whether <varclass="Arg">g</var> is a <em>state-closed</em> group, i.e. a group such that all states of all elements of <varclass="Arg">g</var> belong to <varclass="Arg">g</var>.</p>
<p>The smallest state-closed group containing <varclass="Arg">g</var> is computed with <code class="func">StateClosure</code> (<a href="chap7.html#X79246DB482BEAF2D"><span class="RefLink">7.2-10</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Dinfinity := FRGroup("a=(1,2)","b=<a,b>");</span>
<self-similar group over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(Dinfinity);</span>
#I Assigned the global variables [ a, b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsStateClosed(Group(a));</span>
IsStateClosed(Group(b));
IsStateClosed(Dinfinity); true false true
</pre></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StateClosure</code>( <varclass="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The smallest state-closed group containing <varclass="Arg">g</var>.</p>
<p>Thisfunction computes the smallest group containing all states of all elements of <varclass="Arg">g</var>, i.e. the smallest group containing <varclass="Arg">g</var> and for which <code class="func">IsStateClosed</code> (<a href="chap7.html#X7C5002E683A044C1"><span class="RefLink">7.2-9</span></a>) returns <code class="keyw">true</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Dinfinity := FRGroup("a=(1,2)","b=<a,b>");</span>
<self-similar group over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(Dinfinity);</span>
#I Assigned the global variables [ a, b ]
--> --------------------
--> maximum size reached
--> --------------------
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.0.46Bemerkung:
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
