Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/fr/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 11.0.2024 mit Größe 110 kB image not shown  

Quelle  chap7.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/fr/doc/chap7.html


<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (FR) - Chapter 7: Self-similar groups, monoids and semigroups</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap7"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap6.html">[Previous Chapter]</a>    <a href="chap8.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap7_mj.html">[MathJax on]</a></p>
<p><a id="X86C0E6F083DCCDC8" name="X86C0E6F083DCCDC8"></a></p>
<div class="ChapSects"><a href="chap7.html#X86C0E6F083DCCDC8">7 <span class="Heading">Self-similar groups, monoids and semigroups</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X80A26BAA7B53C1BD">7.1 <span class="Heading">Creators for FR semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7AE8F92383272329">7.1-1 FRGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7D4A6996874A3DF3">7.1-2 NewSemigroupFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X853E3F0680C76F56">7.1-3 SCGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7F15D57A7959FEF6">7.1-4 Correspondence</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7D0B8334786E2802">7.1-5 FullSCGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7DB92C34827D513F">7.1-6 FRMachineFRGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7BF4AC9F830A8E1A">7.1-7 IsomorphismFRGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7DE1CAE981F2825B">7.1-8 IsomorphismMealyGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7BB8DDEA83946C73">7.1-9 FRGroupByVirtualEndomorphism</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X79D75A7D80DD9AD1">7.1-10 TreeWreathProduct</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X85840A047C04BFC6">7.1-11 WeaklyBranchedEmbedding</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X84E20571841DE1E4">7.2 <span class="Heading">Operations for FR semigroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7C6D7BA0818A3A3D">7.2-1 PermGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8620BEAF7957FA4D">7.2-2 PcGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X83834FF77F972912">7.2-3 TransformationMonoid</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8768C22D859BE75F">7.2-4 TransformationSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7BDC634086437315">7.2-5 EpimorphismGermGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X812242E584462766">7.2-6 GermData</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X87378D53791D0B70">7.2-7 StabilizerImage</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7B4CD9CA872BA368">7.2-8 LevelStabilizer</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7C5002E683A044C1">7.2-9 IsStateClosed</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X79246DB482BEAF2D">7.2-10 StateClosure</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7E2F34417EBB7673">7.2-11 IsRecurrentFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X825688FD7CE96479">7.2-12 IsLevelTransitiveFRGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7D95219481AEDD20">7.2-13 IsInfinitelyTransitive</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7A6CB30181662C77">7.2-14 IsFinitaryFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X791BCD9D782C6237">7.2-15 Degree</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7FA67E4387C91BD8">7.2-16 HasOpenSetConditionFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7D870F9E82ACB54C">7.2-17 HasCongruenceProperty</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7EAB4B5B843C0EC5">7.2-18 IsContracting</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7CA062A67C1554BB">7.2-19 NucleusOfFRSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8443D711796F06E4">7.2-20 NucleusMachine</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X824A9E177F5A9753">7.2-21 AdjacencyBasesWithOne</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7A874A107D4944E1">7.2-22 BranchingSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X78ADACCD8586D3C7">7.2-23 FindBranchingSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X832D98E47ACA099C">7.2-24 IsBranched</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7A905CE87B49213F">7.2-25 IsBranchingSubgroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8404ECA782F2521A">7.2-26 BranchStructure</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8749E0797A99F531">7.2-27 TopVertexTransformations</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7C56C90086070A2E">7.2-28 VertexTransformations</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7DF2D9838625CDED">7.2-29 VirtualEndomorphism</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7C81CB1C7F0D7A90">7.2-30 EpimorphismFromFpGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8740656382656D63">7.2-31 IsomorphismSubgroupFpGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X7E8485A081EBB3AA">7.3 <span class="Heading">Properties for infinite groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X840ED7D279ECAB7F">7.3-1 IsTorsionGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7914F2D68077F503">7.3-2 IsTorsionFreeGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X87E93FFC820ED40E">7.3-3 IsAmenableGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X873C0A7C8422C0C9">7.3-4 IsVirtuallySimpleGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X79A3A0CF82B6F089">7.3-5 IsResiduallyFinite</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X86E1182E7EEFAADB">7.3-6 IsSQUniversal</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7FDAEAFF78A5E7D2">7.3-7 IsJustInfinite</a></span>
</div></div>
</div>

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



<p><a id="X80A26BAA7B53C1BD" name="X80A26BAA7B53C1BD"></a></p>

<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><a id="X7AE8F92383272329" name="X7AE8F92383272329"></a></p>

<h5>7.1-1 FRGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FRGroup</code>( <var class="Arg">{definition</var>, <var class="Arg">}</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">‣ FRMonoid</code>( <var class="Arg">{definition</var>, <var class="Arg">}</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">‣ FRSemigroup</code>( <var class="Arg">{definition</var>, <var class="Arg">}</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A new self-similar group/monoid/semigroup.</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>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">i4 := FRMonoid("s=(1,2)","f=<s,f>[1,1]");</span>
<self-similar monoid over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := GeneratorsOfMonoid(i4){[1,2]};;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for i in [1..10] do Add(f,f[i]*f[i+1]); od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f[1]^2=One(m);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">f[2]^3=f[2];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];</span>
true
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">i2 := FRSemigroup("f0=<f0,f0>(1,2)","f1=<f1,f0>[2,2]");</span>
<self-similar semigroup over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(i2);</span>
#I  Assigned the global variables [ "f0", "f1" ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f0^2=One(i2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);</span>
true
</pre></div>

<p><a id="X7D4A6996874A3DF3" name="X7D4A6996874A3DF3"></a></p>

<h5>7.1-2 NewSemigroupFRMachine</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NewSemigroupFRMachine</code>( <var class="Arg">...</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">‣ NewMonoidFRMachine</code>( <var class="Arg">...</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">‣ NewGroupFRMachine</code>( <var class="Arg">...</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A new FR machine, based on string descriptions.</p>

<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><a id="X853E3F0680C76F56" name="X853E3F0680C76F56"></a></p>

<h5>7.1-3 SCGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SCGroup</code>( <var class="Arg">m</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">‣ SCGroupNC</code>( <var class="Arg">m</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">‣ SCMonoid</code>( <var class="Arg">m</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">‣ SCMonoidNC</code>( <var class="Arg">m</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">‣ SCSemigroup</code>( <var class="Arg">m</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">‣ SCSemigroupNC</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The state-closed group/monoid/semigroup generated by the machine <var class="Arg">m</var>.</p>

<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="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">i4machine := MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsInvertible(i4machine);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">i4 := SCMonoidNC(i4machine);</span>
<self-similar monoid over [ 1 .. 2 ] with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := GeneratorsOfMonoid(i4){[1,2]};;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for i in [1..10] do Add(f,f[i]*f[i+1]); od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f[1]^2=One(m);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">f[2]^3=f[2];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];</span>
true
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">i2machine := MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 2 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">i2 := SCSemigroupNC(i2machine);</span>
<self-similar semigroup over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f0^2=One(i2);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);</span>
true
</pre></div>

<p><a id="X7F15D57A7959FEF6" name="X7F15D57A7959FEF6"></a></p>

<h5>7.1-4 Correspondence</h5>

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

<p>See <code class="func">SCGroupNC</code> (<a href="chap7.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>), <code class="func">SCGroup</code> (<a href="chap7.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>), <code class="func">SCMonoidNC</code> (<a href="chap7.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>), <code class="func">SCMonoid</code> (<a href="chap7.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>), <code class="func">SCSemigroupNC</code> (<a href="chap7.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>), <code class="func">SCSemigroup</code> (<a href="chap7.html#X853E3F0680C76F56"><span class="RefLink">7.1-3</span></a>), <code class="func">SCAlgebraNC</code> (<a href="chap8.html#X844B890F7BF56236"><span class="RefLink">8.1-2</span></a>), <code class="func">SCAlgebra</code> (<a href="chap8.html#X844B890F7BF56236"><span class="RefLink">8.1-2</span></a>), <code class="func">SCAlgebraWithOneNC</code> (<a href="chap8.html#X844B890F7BF56236"><span class="RefLink">8.1-2</span></a>), and <code class="func">SCAlgebraWithOne</code> (<a href="chap8.html#X844B890F7BF56236"><span class="RefLink">8.1-2</span></a>) for examples.</p>

<p><a id="X7D0B8334786E2802" name="X7D0B8334786E2802"></a></p>

<h5>7.1-5 FullSCGroup</h5>

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


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FullSCGroup([1..3]);</span>
FullSCGroup([ 1 .. 3 ]);
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(g,GuptaSidkiGroup);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FullSCGroup([1..3],Group((1,2,3)));</span>
FullSCGroup([ 1 .. 3 ], Group( [ (1,2,3) ] ))
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(g,GuptaSidkiGroup);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubgroup(g,GrigorchukGroup);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Random(g);</span>
<Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(FullSCGroup([1,2],3));</span>
128
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FullSCMonoid([1..2]);</span>
FullSCMonoid([ 1 .. 2 ])
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset(g,AsTransformation(FullSCGroup([1..2])));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset(g,AsTransformation(GrigorchukGroup));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g := FullSCSemigroup([1..3]);</span>
FullSCSemigroup([ 1 .. 3 ])
<span class="GAPprompt">gap></span> <span class="GAPinput">h := FullSCSemigroup([1..3],Semigroup(Transformation([1,1,1])));</span>
FullSCSemigroup([ 1 .. 3 ], Semigroup( [ [ 1, 1, 1 ] ] ))
<span class="GAPprompt">gap></span> <span class="GAPinput">Size(h);</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubset(g,h);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">g=FullSCMonoid([1..3]);</span>
true
</pre></div>

<p><a id="X7DB92C34827D513F" name="X7DB92C34827D513F"></a></p>

<h5>7.1-6 FRMachineFRGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FRMachineFRGroup</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">‣ FRMachineFRMonoid</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">‣ FRMachineFRSemigroup</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">‣ MealyMachineFRGroup</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">‣ MealyMachineFRMonoid</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">‣ MealyMachineFRSemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A machine describing all generators of <var class="Arg">g</var>.</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="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FRMachineFRGroup(GuptaSidkiGroup);</span>
<FR machine with alphabet [ 1 .. 3 ] on Group( [ f11, f12 ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
 G   |     1          2        3
-----+--------+----------+--------+
 f11 | <id>,2     <id>,3   <id>,1
 f12 |  f11,1   f11^-1,2    f12,3
-----+--------+----------+--------+
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FRMachineFRMonoid(I4Monoid);</span>
<FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m11, m12 ], ... )>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
 M   |     1        2
-----+--------+--------+
 m11 | <id>,2   <id>,1
 m12 |  m11,1    m12,1
-----+--------+--------+
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">FRMachineFRSemigroup(I2Monoid);</span>
<FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s11, s12, s1 ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
 S   |    1       2
-----+-------+-------+
 s11 | s11,1   s11,2
 s12 | s12,2   s12,1
  s1 |  s1,2   s12,2
-----+-------+-------+
</pre></div>

<p><a id="X7BF4AC9F830A8E1A" name="X7BF4AC9F830A8E1A"></a></p>

<h5>7.1-7 IsomorphismFRGroup</h5>

<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>This function 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="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := IsomorphismFRSemigroup(I2Monoid);</span>
MappingByFunction( I2, <self-similar semigroup over [ 1 .. 2 ] with
3 generators>, <Operation "AsSemigroupFRElement"> )
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(GeneratorsOfSemigroup(I2Monoid)[3]);</span>
   |  1     2
---+-----+-----+
 a | a,2   b,2
 b | b,2   b,1
---+-----+-----+
Initial state: a
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(GeneratorsOfSemigroup(I2Monoid)[3]^phi);</span>
 S  |   1      2
----+------+------+
 s1 | s1,2   s2,2
 s2 | s2,2   s2,1
----+------+------+
Initial state: s1
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := IsomorphismFRMonoid(I4Monoid);</span>
MappingByFunction( I4, <self-similar monoid over [ 1 .. 2 ] with
2 generators>, <Operation "AsMonoidFRElement"> )
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(GeneratorsOfMonoid(I4Monoid)[1]);</span>
   |  1     2
---+-----+-----+
 a | b,2   b,1
 b | b,1   b,2
---+-----+-----+
Initial state: a
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(GeneratorsOfMonoid(I4Monoid)[1]^phi);</span>
 M  |     1        2
----+--------+--------+
 m1 | <id>,2   <id>,1
----+--------+--------+
Initial state: m1
</pre></div>

<p><a id="X7DE1CAE981F2825B" name="X7DE1CAE981F2825B"></a></p>

<h5>7.1-8 IsomorphismMealyGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsomorphismMealyGroup</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">‣ IsomorphismMealyMonoid</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">‣ IsomorphismMealySemigroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An isomorphism towards a group/monoid/semigroup all of whose elements are Mealy machines.</p>

<p>This function constructs a new FR group/monoid/semigroup, such that all elements of the resulting object are Mealy machines.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>");</span>
<self-similar group over [ 1 .. 2 ] with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">phi := IsomorphismMealyGroup(G);</span>
[ <2|a>, <2|b>, <2|c> ] ->
[ <Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>,
  <Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>,
  <Mealy element on alphabet [ 1, 2 ] with 4 states, initial state 1> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(G.3);</span>
   |     1        2
---+--------+--------+
 a | <id>,2   <id>,1
 b |    a,1      b,2
 c |    c,1      b,2
---+--------+--------+
Initial state: c
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(G.3^phi);</span>
   |  1     2
---+-----+-----+
 a | a,1   b,2
 b | c,1   b,2
 c | d,2   d,1
 d | d,1   d,2
---+-----+-----+
Initial state: a
</pre></div>

<p><a id="X7BB8DDEA83946C73" name="X7BB8DDEA83946C73"></a></p>

<h5>7.1-9 FRGroupByVirtualEndomorphism</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FRGroupByVirtualEndomorphism</code>( <var class="Arg">hom</var>[, <var class="Arg">transversal</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A new self-similar group.</p>

<p>This function 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>. This function 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>

<p><a id="X79D75A7D80DD9AD1" name="X79D75A7D80DD9AD1"></a></p>

<h5>7.1-10 TreeWreathProduct</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TreeWreathProduct</code>( <var class="Arg">g</var>, <var class="Arg">h</var>, <var class="Arg">x0</var>, <var class="Arg">y0</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The tree-wreath product of groups <var class="Arg">g,h</var>.</p>

<p>The tree-wreath product of two FR groups is a group generated by a copy of <var class="Arg">g</var> and of <var class="Arg">h</var>, in such a way that many conjugates of <var class="Arg">g</var> commute.</p>

<p>More formally, assume without loss of generality that all generators of <var class="Arg">g</var> are states of a machine <code class="code">m</code>, and that all generators of <var class="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 <var class="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>

<p><a id="X85840A047C04BFC6" name="X85840A047C04BFC6"></a></p>

<h5>7.1-11 WeaklyBranchedEmbedding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WeaklyBranchedEmbedding</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A embedding of <var class="Arg">g</var> in a weakly branched group.</p>

<p>This function constructs a new FR group, on alphabet the square of the alphabet of <var class="Arg">g</var>. It is generated by the canonical copy of <var class="Arg">g</var> and by the tree-wreath product of <var class="Arg">g</var> with an adding machine on the same alphabet as <var class="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 this new 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.



<p><a id="X84E20571841DE1E4" name="X84E20571841DE1E4"></a></p>

<h4>7.2 <span class="Heading">Operations for FR semigroups</span></h4>

<p><a id="X7C6D7BA0818A3A3D" name="X7C6D7BA0818A3A3D"></a></p>

<h5>7.2-1 PermGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermGroup</code>( <var class="Arg">g</var>, <var class="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>( <var class="Arg">g</var>, <var class="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the permutation group of <var class="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 <var class="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 <var class="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>

<p><a id="X8620BEAF7957FA4D" name="X8620BEAF7957FA4D"></a></p>

<h5>7.2-2 PcGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PcGroup</code>( <var class="Arg">g</var>, <var class="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>( <var class="Arg">g</var>, <var class="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the pc group of <var class="Arg">g</var>'s action on level l.



<p>The first function returns a polycyclic group representing the action of <var class="Arg">g</var> on the <var class="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 <var class="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>

<p><a id="X83834FF77F972912" name="X83834FF77F972912"></a></p>

<h5>7.2-3 TransformationMonoid</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TransformationMonoid</code>( <var class="Arg">g</var>, <var class="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>( <var class="Arg">g</var>, <var class="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the transformation monoid of <var class="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 <var class="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 <var class="Arg">g</var> to this transformation monoid.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">i4 := SCMonoid(MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]));</span>
<self-similar monoid over [ 1 .. 2 ] with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := TransformationMonoid(i4,6);</span>
<monoid with 3 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([1..6],i->Size(TransformationMonoid(i4,i)));</span>
[ 4, 14, 50, 170, 570, 1882 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Collected(List(g,RankOfTransformation));</span>
[ [ 1, 64 ], [ 2, 1280 ], [ 4, 384 ], [ 8, 112 ], [ 16, 32 ], [ 32, 8 ], [ 64, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">pi := EpimorphismTransformationMonoid(i4,9);</span>
MappingByFunction( <self-similar monoid over [ 1 .. 2 ] with 3 generators>,
<monoid with 3 generators>, function( w ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">f := GeneratorsOfMonoid(i4){[1,2]};;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">for i in [1..10] do Add(f,f[i]*f[i+1]); od;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Product(f{[3,5,7,9,11]})=f[11]*f[10];</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">Product(f{[3,5,7,9,11]})^pi=(f[11]*f[10])^pi;</span>
true
</pre></div>

<p><a id="X8768C22D859BE75F" name="X8768C22D859BE75F"></a></p>

<h5>7.2-4 TransformationSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TransformationSemigroup</code>( <var class="Arg">g</var>, <var class="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>( <var class="Arg">g</var>, <var class="Arg">l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: [An epimorphism to] the transformation semigroup of <var class="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 <var class="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 <var class="Arg">g</var> to this transformation semigroup.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">i2 := SCSemigroup(MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]));</span>
<self-similar semigroup over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := TransformationSemigroup(i2,6);</span>
<semigroup with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">List([1..6],i->Size(TransformationSemigroup(i2,i)));</span>
[ 4, 14, 42, 114, 290, 706 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Collected(List(g,RankOfTransformation));</span>
[ [ 1, 64 ], [ 2, 384 ], [ 4, 160 ], [ 8, 64 ], [ 16, 24 ], [ 32, 8 ], [ 64, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">pi := EpimorphismTransformationSemigroup(i2,10);</span>
MappingByFunction( <self-similar semigroup over [ 1 .. 2 ] with
2 generators>, <semigroup with 2 generators>, function( w ) ... end )
<span class="GAPprompt">gap></span> <span class="GAPinput">(f1*(f1*f0)^10)=((f1*f0)^10);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">(f1*(f1*f0)^10)^pi=((f1*f0)^10)^pi;</span>
true
</pre></div>

<p><a id="X7BDC634086437315" name="X7BDC634086437315"></a></p>

<h5>7.2-5 EpimorphismGermGroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ EpimorphismGermGroup</code>( <var class="Arg">g</var>, <var class="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">‣ EpimorphismGermGroup</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A homomorphism to a polycyclic group.</p>

<p>This function returns an epimorphism to a polycyclic group, encoding the action on the first <var class="Arg">l</var> levels of the tree and on the germs below. If <var class="Arg">l</var> is omitted, it is assumed to be <span class="SimpleMath">0</span>.</p>

<p>Since the elements of <var class="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 <var class="Arg">g</var>. This function returns the natural homomorphism from <var class="Arg">g</var> to the wreath product of this germ group with the quotient of <var class="Arg">g</var> acting on the <var class="Arg">l</var>th layer of the tree.</p>

<p>The germ group, by default, is abelian. If it is finite, this function 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>

<p><a id="X812242E584462766" name="X812242E584462766"></a></p>

<h5>7.2-6 GermData</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GermData</code>( <var class="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>( <var class="Arg">element</var>, <var class="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>

<p><a id="X87378D53791D0B70" name="X87378D53791D0B70"></a></p>

<h5>7.2-7 StabilizerImage</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StabilizerImage</code>( <var class="Arg">g</var>, <var class="Arg">v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The group of all states at <var class="Arg">v</var> of elements of <var class="Arg">g</var> fixing <var class="Arg">v</var>.</p>

<p>This function constructs a new FR group, consisting of all states at vertex <var class="Arg">v</var> (which can be an integer or a list) of the stabilizer of <var class="Arg">v</var> in <var class="Arg">g</var>.</p>

<p>The result is <var class="Arg">g</var> itself precisely if <var class="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>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfGroup(last);</span>
[ <2|identity ...>, <2|u>, <2|t>, <2|u^-1>, <2|t> ]
</pre></div>

<p><a id="X7B4CD9CA872BA368" name="X7B4CD9CA872BA368"></a></p>

<h5>7.2-8 LevelStabilizer</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LevelStabilizer</code>( <var class="Arg">g</var>, <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The fixator of the <var class="Arg">n</var>th level of the tree.</p>

<p>This function constructs the normal subgroup of <var class="Arg">g</var> that fixes the <var class="Arg">n</var>th level of the tree.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">G := FRGroup("t=<,t>(1,2)","a=(1,2)");</span>
<self-similar group over [ 1 .. 2 ] with 2 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">LevelStabilizer(G,2);</span>
<self-similar group over [ 1 .. 2 ] with 9 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">Index(G,last);</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNormal(G,last2);</span>
true
</pre></div>

<p><a id="X7C5002E683A044C1" name="X7C5002E683A044C1"></a></p>

<h5>7.2-9 IsStateClosed</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsStateClosed</code>( <var class="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 <var class="Arg">g</var> belong to <var class="Arg">g</var>.</p>

<p>This function tests whether <var class="Arg">g</var> is a <em>state-closed</em> group, i.e. a group such that all states of all elements of <var class="Arg">g</var> belong to <var class="Arg">g</var>.</p>

<p>The smallest state-closed group containing <var class="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>

<p><a id="X79246DB482BEAF2D" name="X79246DB482BEAF2D"></a></p>

<h5>7.2-10 StateClosure</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StateClosure</code>( <var class="Arg">g</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The smallest state-closed group containing <var class="Arg">g</var>.</p>

<p>This function computes the smallest group containing all states of all elements of <var class="Arg">g</var>, i.e. the smallest group containing <var class="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

--> --------------------

Messung V0.5
C=92 H=96 G=93

¤ Dauer der Verarbeitung: 0.32 Sekunden  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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 und die Messung sind noch experimentell.