Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/groupoids/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 11.8.2025 mit Größe 47 kB image not shown  

SSL chap7.html   Sprache: HTML

 
 products/sources/formale Sprachen/GAP/pkg/groupoids/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 (groupoids) - Chapter 7: Graphs of Groups and Groupoids</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="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="X78063DC8847554B4" name="X78063DC8847554B4"></a></p>
<div class="ChapSects"><a href="chap7.html#X78063DC8847554B4">7 <span class="Heading">Graphs of Groups and Groupoids</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X7D554C5D7FDC3D02">7.1 <span class="Heading">Digraphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X85BD6D2584D8A22F">7.1-1 FpWeightedDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X7BAFCA3680E478AE">7.2 <span class="Heading">Graphs of Groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8130246E854BC5D9">7.2-1 GraphOfGroups</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X847464677F641527">7.2-2 IsGraphOfFpGroups</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7B036C2B84E48BB1">7.2-3 RightTransversalsOfGraphOfGroups</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X7BD9DCF87FB3E0AF">7.3 <span class="Heading">Words in a Graph of Groups and their normal forms</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X87937AE47C5B1018">7.3-1 GraphOfGroupsWord</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X78FA7C3F831AA6E4">7.3-2 ReducedGraphOfGroupsWord</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X7D99A7B37B36BAA8">7.4 <span class="Heading">Free products with amalgamation and HNN extensions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X795AB71F7E370119">7.4-1 FreeProductWithAmalgamation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X86F5F9787E3644FD">7.4-2 ReducedImageElm</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7CB0F120804A8DED">7.4-3 HnnExtension</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7.html#X78108FB4814AE887">7.5 <span class="Heading">GraphsOfGroupoids and their Words</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X8739267678808E85">7.5-1 GraphOfGroupoids</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap7.html#X7EC1A9067FC91255">7.5-2 GraphOfGroupoidsWord</a></span>
</div></div>
</div>

<h3>7 <span class="Heading">Graphs of Groups and Groupoids</span></h3>

<p>This package was originally designed to implement <em>graphs of groups</em>, a notion introduced by Serre in <a href="chapBib.html#biBSerre">[Ser80]</a>. It was only when this was extended to <em>graphs of groupoids</em> that the functions for groupoids, described in the previous chapters, were required. The methods described here are based on Philip Higgins' paper [Hig76]. For further details see Chapter 2 of [Moo01]. Since a graph of groups involves a directed graph, with a group associated to each vertex and arc, we first define digraphs with edges weighted by the generators of a free group.



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

<h4>7.1 <span class="Heading">Digraphs</span></h4>

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

<h5>7.1-1 FpWeightedDigraph</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FpWeightedDigraph</code>( <var class="Arg">verts</var>, <var class="Arg">arcs</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">‣ IsFpWeightedDigraph</code>( <var class="Arg">dig</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">‣ InvolutoryArcs</code>( <var class="Arg">dig</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>A <em>weighted digraph</em> is a record with two components: <em>vertices</em>, which are usually taken to be positive integers (to distinguish them from the objects in a groupoid); and <em>arcs</em>, which take the form of 3-element lists <code class="code">[weight,tail,head]</code>. The <em>tail</em> and <em>head</em> are the two vertices of the arc. The <em>weight</em> is taken to be an element of a finitely presented group, so as to produce digraphs of type <code class="code">IsFpWeightedDigraph</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">V1 := [ 5, 6 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fg1 := FreeGroup( "y" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := fg1.1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A1 := [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ];</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">D1 := FpWeightedDigraph( fg1, V1, A1 );</span>
weighted digraph with vertices: [ 5, 6 ]
and arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">inv1 := InvolutoryArcs( D1 );</span>
[ 2, 1 ]

</pre></div>

<p>The example illustrates the fact that we require arcs to be defined in involutory pairs, as though they were inverse elements in a groupoid. We may in future decide just to give <code class="code">[y,5,6]</code> as the data and get the function to construct the reverse edge. The attribute <code class="code">InvolutoryArcs</code> returns a list of the positions of each inverse arc in the list of arcs. In the second example the graph is a complete digraph on three vertices.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">fg3 := FreeGroup( 3, "z" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">z1 := fg3.1;;  z2 := fg3.2;;  z3 := fg3.3;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ob3 := [ 7, 8, 9 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A3 := [[z1,7,8],[z2,8,9],[z3,9,7],[z1^-1,8,7],[z2^-1,9,8],[z3^-1,7,9]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">D3 := FpWeightedDigraph( fg3, ob3, A3 );</span>
weighted digraph with vertices: [ 7, 8, 9 ]
and arcs: [ [ z1, 7, 8 ], [ z2, 8, 9 ], [ z3, 9, 7 ], [ z1^-1, 8, 7 ],
  [ z2^-1, 9, 8 ], [ z3^-1, 7, 9 ] ]
[gap> inob3 := InvolutoryArcs( D3 );
[ 4, 5, 6, 1, 2, 3 ]

</pre></div>

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

<h4>7.2 <span class="Heading">Graphs of Groups</span></h4>

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

<h5>7.2-1 GraphOfGroups</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphOfGroups</code>( <var class="Arg">dig</var>, <var class="Arg">gps</var>, <var class="Arg">isos</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">‣ DigraphOfGraphOfGroups</code>( <var class="Arg">gg</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">‣ GroupsOfGraphOfGroups</code>( <var class="Arg">gg</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">‣ IsomorphismsOfGraphOfGroups</code>( <var class="Arg">gg</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">‣ IsGraphOfGroups</code>( <var class="Arg">dig</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>A graph of groups is traditionally defined as consisting of:</p>


<ul>
<li><p>a digraph with involutory pairs of arcs;</p>

</li>
<li><p>a <em>vertex group</em> associated to each vertex;</p>

</li>
<li><p>a group associated to each pair of arcs;</p>

</li>
<li><p>an injective homomorphism from each arc group to the group at the head of the arc.</p>

</li>
</ul>
<p>We have found it more convenient to associate to each arc:</p>


<ul>
<li><p>a subgroup of the vertex group at the tail;</p>

</li>
<li><p>a subgroup of the vertex group at the head;</p>

</li>
<li><p>an isomorphism between these subgroups, such that each involutory pair of arcs determines inverse isomorphisms.</p>

</li>
</ul>
<p>These two viewpoints are clearly equivalent.</p>

<p>In this implementation we require that all subgroups are of finite index in the vertex groups.</p>

<p>The three attributes provide a means of calling the three items of data in the construction of a graph of groups.</p>

<p>We shall be representing free products with amalgamation of groups and HNN extensions of groups in Section <a href="chap7.html#X7D99A7B37B36BAA8"><span class="RefLink">7.4</span></a>. So we take as our first example the trefoil group with generators <span class="SimpleMath">a,b</span> and relation <span class="SimpleMath">a^3=b^2</span>. For this we take digraph <code class="code">D1</code> above with an infinite cyclic group at each vertex, generated by <span class="SimpleMath">a</span> and <span class="SimpleMath">b</span> respectively. The two subgroups will be generated by <span class="SimpleMath">a^3</span> and <span class="SimpleMath">b^2</span> with the obvious isomorphisms.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">## free vertex group at 5</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fa := FreeGroup( "a" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := fa.1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( fa, "fa" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hy := Subgroup( fa, [a^3] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( hy, "hy" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## free vertex group at 6</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fb := FreeGroup( "b" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := fb.1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( fb, "fb" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hybar := Subgroup( fb, [b^2] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( hybar, "hybar" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## isomorphisms between subgroups</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">homy := GroupHomomorphismByImagesNC( hy, hybar, [a^3], [b^2] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">homybar := GroupHomomorphismByImagesNC( hybar, hy, [b^2], [a^3] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## defining graph of groups G1</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G1 := GraphOfGroups( D1, [fa,fb], [homy,homybar] );</span>
Graph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( G1 );</span>
Graph of Groups with :-
    vertices: [ 5, 6 ]
        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
      groups: [ fa, fb ]
isomorphisms: [ [ [ a^3 ], [ b^2 ] ], [ [ b^2 ], [ a^3 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfGroups( G1 );</span>
true

</pre></div>

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

<h5>7.2-2 IsGraphOfFpGroups</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGraphOfFpGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGraphOfPcGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGraphOfPermGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>This is a list of properties to be expected of a graph of groups. In principle any type of group known to <strong class="pkg">GAP</strong> may be used as vertex groups, though these types are not normally mixed in a single structure.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfFpGroups( G1 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismsOfGraphOfGroups( G1 );</span>
[ [ a^3 ] -> [ b^2 ], [ b^2 ] -> [ a^3 ] ]


</pre></div>

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

<h5>7.2-3 RightTransversalsOfGraphOfGroups</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightTransversalsOfGraphOfGroups</code>( <var class="Arg">gg</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">‣ LeftTransversalsOfGraphOfGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Computation with graph of groups words will require, for each arc subgroup <code class="code">ha</code>, a set of representatives for the left cosets of <code class="code">ha</code> in the tail vertex group. As already pointed out, we require subgroups of finite index. Since <strong class="pkg">GAP</strong> prefers to provide right cosets, we obtain the right representatives first, and then invert them.</p>

<p>When the vertex groups are of type <code class="code">FpGroup</code> we shall require normal forms for these groups, so we assume that such vertex groups are provided with Knuth Bendix rewriting systems using functions from the main <strong class="pkg">GAP</strong> library, (e.g. <code class="code">IsomorphismFpSemigroup</code>).</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">RTG1 := RightTransversalsOfGraphOfGroups( G1 );</span>
[ [ <identity ...>, a, a^2 ], [ <identity ...>, b ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LTG1 := LeftTransversalsOfGraphOfGroups( G1 );</span>
[ [ <identity ...>, a^-1, a^-2 ], [ <identity ...>, b^-1 ] ] 

</pre></div>

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

<h4>7.3 <span class="Heading">Words in a Graph of Groups and their normal forms</span></h4>

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

<h5>7.3-1 GraphOfGroupsWord</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphOfGroupsWord</code>( <var class="Arg">gg</var>, <var class="Arg">tv</var>, <var class="Arg">list</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">‣ IsGraphOfGroupsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphOfGroupsOfWord</code>( <var class="Arg">w</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">‣ WordOfGraphOfGroupsWord</code>( <var class="Arg">w</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">‣ TailOfGraphOfGroupsWord</code>( <var class="Arg">w</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">‣ HeadOfGraphOfGroupsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>If <code class="code">G</code> is a graph of groups with underlying digraph <code class="code">D</code>, the following groupoids may be considered. First there is the free groupoid or path groupoid on <code class="code">D</code>. Since we want each involutory pair of arcs to represent inverse elements in the groupoid, we quotient out by the relations <code class="code">y^-1 = ybar</code> to obtain <code class="code">PG(D)</code>. Secondly, there is the discrete groupoid <code class="code">VG(D)</code>, namely the union of all the vertex groups. Since these two groupoids have the same object set (the vertices of <code class="code">D</code>) we can form <code class="code">A(G)</code>, the free product of <code class="code">PG(D)</code> and <code class="code">VG(D)</code> amalgamated over the vertices. For further details of this universal groupoid construction see <a href="chapBib.html#biBemma-thesis">[Moo01]</a>. (Note that these groupoids are not implemented in this package.)</p>

<p>An element of <code class="code">A(G)</code> is a graph of groups word which may be represented by a list of the form <span class="SimpleMath">w = [g_1,y_1,g_2,y_2,...,g_n,y_n,g_n+1]</span>. Here each <span class="SimpleMath">y_i</span> is an arc of <code class="code">D</code>; the head of <span class="SimpleMath">y_i-1</span> is a vertex <span class="SimpleMath">v_i</span> which is also the tail of <span class="SimpleMath">y_i</span>; and <span class="SimpleMath">g_i</span> is an element of the vertex group at <span class="SimpleMath">v_i</span>.</p>

<p>So a graph of groups word requires as data the graph of groups; the tail vertex for the word; and a list of arcs and group elements. We may specify each arc by its position in the list of arcs.</p>

<p>In the following example, where <code class="code">gw1</code> is a word in the trefoil graph of groups, the <span class="SimpleMath">y_i</span> are specified by their positions in <code class="code">A1</code>. Both arcs are traversed twice, so the resulting word is a loop at vertex <span class="SimpleMath">5</span>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">L1 := [ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gw1 := GraphOfGroupsWord( G1, 5, L1 );</span>
(5)a^7.y.b^-6.y^-1.a^-11.y.b^9.y^-1.a^7(5)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfGroupsWord( gw1 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[ TailOfGraphOfGroupsWord(gw1), HeadOfGraphOfGroupsWord(gw1) ];</span>
[ 5, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GraphOfGroupsOfWord(gw1);</span>
Graph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ]
<span class="GAPprompt">gap></span> <span class="GAPinput">WordOfGraphOfGroupsWord( gw1 );</span>
[ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ]

</pre></div>

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

<h5>7.3-2 ReducedGraphOfGroupsWord</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReducedGraphOfGroupsWord</code>( <var class="Arg">w</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">‣ IsReducedGraphOfGroupsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>A graph of groups word may be reduced in two ways, to give a normal form. Firstly, if part of the word has the form <code class="code">[yi, identity, yibar]</code> then this subword may be omitted. This is known as a length reduction. Secondly there are coset reductions. Working from the left-hand end of the word, subwords of the form <span class="SimpleMath">[g_i,y_i,g_i+1]</span> are replaced by <span class="SimpleMath">[t_i,y_i,m_i(h_i)*g_i+1]</span> where <span class="SimpleMath">g_i = t_i*h_i</span> is the unique factorisation of <span class="SimpleMath">g_i</span> as a left coset representative times an element of the arc subgroup, and <span class="SimpleMath">m_i</span> is the isomorphism associated to <span class="SimpleMath">y_i</span>. Thus we may consider a coset reduction as passing a subgroup element along an arc. The resulting normal form (if no length reductions have taken place) is then <span class="SimpleMath">[t_1,y_1,t_2,y_2,...,t_n,y_n,k]</span> for some <span class="SimpleMath">k</span> in the head group of <span class="SimpleMath">y_n</span>. For further details see Section 2.2 of <a href="chapBib.html#biBemma-thesis">[Moo01]</a>.</p>

<p>The reduction of the word <code class="code">gw1</code> in our example includes one length reduction. The four stages of the reduction are as follows:</p>

<p class="pcenter">
a^7b^{-6}a^{-11}b^9a^7 ~\mapsto~
a^{-2}b^0a^{-11}b^9a^7 ~\mapsto~
a^{-13}b^9a^7 ~\mapsto~
a^{-1}b^{-8}b^9a^7 ~\mapsto~
a^{-1}b^{-1}a^{10}.
</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">nw1 := ReducedGraphOfGroupsWord( gw1 );</span>
(5)a^-1.y.b^-1.y^-1.a^10(5)

</pre></div>

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

<h4>7.4 <span class="Heading">Free products with amalgamation and HNN extensions</span></h4>

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

<h5>7.4-1 FreeProductWithAmalgamation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeProductWithAmalgamation</code>( <var class="Arg">gp1</var>, <var class="Arg">gp2</var>, <var class="Arg">iso</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">‣ FreeProductWithAmalgamationInfo</code>( <var class="Arg">fpa</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">‣ IsFreeProductWithAmalgamation</code>( <var class="Arg">fpa</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphOfGroupsRewritingSystem</code>( <var class="Arg">fpa</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">‣ NormalFormGGRWS</code>( <var class="Arg">fpa</var>, <var class="Arg">word</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>As we have seen with the trefoil group example in Section <a href="chap7.html#X7BAFCA3680E478AE"><span class="RefLink">7.2</span></a>, graphs of groups can be used to obtain a normal form for free products with amalgamation <span class="SimpleMath">G_1 *_H G_2</span> when <span class="SimpleMath">G_1, G_2</span> both have rewrite systems, and <span class="SimpleMath">H</span> is of finite index in both <span class="SimpleMath">G_1</span> and <span class="SimpleMath">G_2</span>.</p>

<p>When <code class="code">gp1</code> and <code class="code">gp2</code> are fp-groups, the operation <code class="code">FreeProductWithAmalgamation</code> constructs the required fp-group. When the two groups are permutation groups, the <code class="code">IsomorphismFpGroup</code> operation is called on both <code class="code">gp1</code> and <code class="code">gp2</code>, and the resulting isomorphism is transported to one between the two new subgroups.</p>

<p>The attribute <code class="code">GraphOfGroupsRewritingSystem</code> of <code class="code">fpa</code> is the graph of groups which has underlying digraph <code class="code">D1</code>, with two vertices and two arcs; the two groups as vertex groups; and the specified isomorphisms on the arcs. Despite the name, graphs of groups constructed in this way <em>do not</em> belong to the category <code class="code">IsRewritingSystem</code>. This anomaly may be dealt with when time permits.</p>

<p>The example below shows a computation in the the free product of the symmetric <code class="code">s3</code> and the alternating <code class="code">a4</code>, amalgamated over a cyclic subgroup <code class="code">c3</code>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">## set up the first group s3 and a subgroup c3=<a1></span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fg2 := FreeGroup( 2, "a" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rel1 := [ fg2.1^3, fg2.2^2, (fg2.1*fg2.2)^2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s3 := fg2/rel1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gs3 := GeneratorsOfGroup(s3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( s3, "s3" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1 := gs3[1];;  a2 := gs3[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H1 := Subgroup(s3,[a1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## then the second group a4 and subgroup c3=<b1></span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 := FreeGroup( 2, "b" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rel2 := [ f2.1^3, f2.2^3, (f2.1*f2.2)^2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a4 := f2/rel2;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ga4 := GeneratorsOfGroup(a4);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( a4, "a4" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b1 := ga4[1];  b2 := ga4[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H2 := Subgroup(a4,[b1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## form the isomorphism and the fpa group</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">iso := GroupHomomorphismByImages(H1,H2,[a1],[b1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">inv := InverseGeneralMapping(iso);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fpa := FreeProductWithAmalgamation( s3, a4, iso );</span>
<fp group on the generators [ f1, f2, f3, f4 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelatorsOfFpGroup( fpa );</span>
[ f1^2, f2^3, (f2*f1)^2, f3^3, f4^3, (f4*f3)^2, f2*f3^-1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gg1 := GraphOfGroupsRewritingSystem( fpa );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( gg1 );</span>
Graph of Groups with :- 
    vertices: [ 5, 6 ]
        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
      groups: [ s3, a4 ]
isomorphisms: [ [ [ a1 ], [ b1 ] ], [ [ b1 ], [ a1 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftTransversalsOfGraphOfGroups( gg1 );</span>
[ [ <identity ...>, a2^-1 ], [ <identity ...>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ] 
 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gfpa := GeneratorsOfGroup( fpa );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">w2 := (gfpa[1]*gfpa[2]*gfpa[3]^gfpa[4])^3;</span>
(f1*f2*f4^-1*f3*f4)^3
<span class="GAPprompt">gap></span> <span class="GAPinput">n2 := NormalFormGGRWS( fpa, w2 );</span>
f2*f3*(f4^-1*f2)^2*f4^-1*f3

</pre></div>

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

<h5>7.4-2 ReducedImageElm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ReducedImageElm</code>( <var class="Arg">hom</var>, <var class="Arg">eml</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">‣ IsMappingToGroupWithGGRWS</code>( <var class="Arg">map</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Embedding</code>( <var class="Arg">fpa</var>, <var class="Arg">num</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>All fpa-groups are provided with a record attribute, <code class="code">FreeProductWithAmalgamationInfo(fpa)</code> which is a record storing the groups, subgroups and isomorphism involved in their construction. This information record also contains the embeddings of the two groups into the product. The operation <code class="code">ReducedImageElm</code>, applied to a homomorphism <span class="SimpleMath">h</span> of type <code class="code">IsMappingToGroupWithGGRWS</code> and an element <span class="SimpleMath">x</span> of the source, finds the usual <code class="code">ImageElm(h,x)</code> and then reduces this to its normal form using the graph of groups rewriting system.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">fpainfo;</span>
rec( embeddings := [ [ a2, a1 ] -> [ f1, f2 ], [ b1, b2 ] -> [ f3, f4 ] ], 
  groups := [ s3, a4 ], isomorphism := [ a1 ] -> [ b1 ], 
  positions := [ [ 1, 2 ], [ 3, 4 ] ], 
  subgroups := [ Group([ a1 ]), Group([ b1 ]) ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">emb2 := Embedding( fpa, 2 );</span>
[ b1, b2 ] -> [ f3, f4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ImageElm( emb2, b1^b2 );       </span>
f4^-1*f3*f4
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedImageElm( emb2, b1^b2 );</span>
f4*f3^-1

</pre></div>

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

<h5>7.4-3 HnnExtension</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ HnnExtension</code>( <var class="Arg">gp</var>, <var class="Arg">iso</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">‣ HnnExtensionInfo</code>( <var class="Arg">gp</var>, <var class="Arg">iso</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">‣ IsHnnExtension</code>( <var class="Arg">hnn</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>For <em>HNN extensions</em>, the appropriate graph of groups has underlying digraph with just one vertex and one pair of loops, weighted with <code class="code">FpGroup</code> generators <span class="SimpleMath">z,z^-1</span>. There is one vertex group <code class="code">G</code>, two isomorphic subgroups <code class="code">H1,H2</code> of <code class="code">G</code>, with the isomorphism and its inverse on the loops. The presentation of the extension has one more generator than that of <code class="code">G</code> and corresponds to the generator <span class="SimpleMath">z</span>.</p>

<p>The functions <code class="code">GraphOfGroupsRewritingSystem</code> and <code class="code">NormalFormGGRWS</code> may be applied to hnn-groups as well as to fpa-groups.</p>

<p>In the example we take <code class="code">G=a4</code> and the two subgroups are cyclic groups of order 3.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">H3 := Subgroup(a4,[b2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">i23 := GroupHomomorphismByImages( H2, H3, [b1], [b2] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hnn := HnnExtension( a4, i23 );</span>
<fp group on the generators [ fe1, fe2, fe3 ]> 
<span class="GAPprompt">gap></span> <span class="GAPinput">phnn := PresentationFpGroup( hnn );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">TzPrint( phnn );</span>
#I  generators: [ fe1, fe2, fe3 ]
#I  relators:
#I  1.  3  [ 1, 1, 1 ]
#I  2.  3  [ 2, 2, 2 ]
#I  3.  4  [ 1, 2, 1, 2 ]
#I  4.  4  [ -3, 1, 3, -2 ] 
<span class="GAPprompt">gap></span> <span class="GAPinput">gg2 := GraphOfGroupsRewritingSystem( hnn );</span>
Graph of Groups: 1 vertices; 2 arcs; groups [ a4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftTransversalsOfGraphOfGroups( gg2 );</span>
[ [ <identity ...>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ],
  [ <identity ...>, b1^-1, b1, b2^-1*b1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gh := GeneratorsOfGroup( hnn );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">w3 := (gh[1]^gh[2])*gh[3]^-1*(gh[1]*gh[3]*gh[2]^2)^2*gh[3]*gh[2];</span>
fe2^-1*fe1*fe2*fe3^-1*(fe1*fe3*fe2^2)^2*fe3*fe2
<span class="GAPprompt">gap></span> <span class="GAPinput">n3 := NormalFormGGRWS( hnn, w3 );</span>
(fe2*fe1*fe3)^2

</pre></div>

<p>As with fpa-groups, hnn-groups are provided with a record attribute, <code class="code">HnnExtensionInfo(hnn)</code>, storing the group, subgroups and isomorphism involved in their construction.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">hnninfo := HnnExtensionInfo( hnn );</span>
rec( embeddings := [ [ b1, b2 ] -> [ fe1, fe2 ] ], group := a4, 
  isomorphism := [ b1 ] -> [ b2 ], 
  subgroups := [ Group([ b1 ]), Group([ b2 ]) ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">emb := Embedding( hnn, 1 );</span>
[ b1, b2 ] -> [ fe1, fe2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ImageElm( emb, b1^b2 );       </span>
fe2^-1*fe1*fe2
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedImageElm( emb, b1^b2 );</span>
fe2*fe1^-1

</pre></div>

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

<h4>7.5 <span class="Heading">GraphsOfGroupoids and their Words</span></h4>

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

<h5>7.5-1 GraphOfGroupoids</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphOfGroupoids</code>( <var class="Arg">dig</var>, <var class="Arg">gpds</var>, <var class="Arg">subgpds</var>, <var class="Arg">isos</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">‣ IsGraphOfPermGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsGraphOfFpGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GroupoidsOfGraphOfGroupoids</code>( <var class="Arg">gg</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">‣ DigraphOfGraphOfGroupoids</code>( <var class="Arg">gg</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">‣ SubgroupoidsOfGraphOfGroupoids</code>( <var class="Arg">gg</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">‣ IsomorphismsOfGraphOfGroupoids</code>( <var class="Arg">gg</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">‣ RightTransversalsOfGraphOfGroupoids</code>( <var class="Arg">gg</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">‣ LeftTransversalsOfGraphOfGroupoids</code>( <var class="Arg">gg</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">‣ IsGraphOfGroupoids</code>( <var class="Arg">dig</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Graphs of groups generalise naturally to graphs of groupoids, forming the class <code class="code">IsGraphOfGroupoids</code>. There is now a groupoid at each vertex and the isomorphism on an arc identifies wide subgroupoids at the tail and at the head. Since all subgroupoids are wide, every groupoid in a connected constituent of the graph has the same number of objects, but there is no requirement that the object sets are all the same.</p>

<p>The example below generalises the trefoil group example in subsection 4.4.1, taking at each vertex of <code class="code">D1</code> a two-object groupoid with a free group on one generator, and full subgroupoids with groups <span class="SimpleMath">⟨ a^3 ⟩</span> and <span class="SimpleMath">⟨ b^2 ⟩</span>.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">Gfa := SinglePieceGroupoid( fa, [-2,-1] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ofa := One( fa );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Gfa, "Gfa" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Uhy := Subgroupoid( Gfa, [ [ hy, [-2,-1] ] ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Uhy, "Uhy" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gfb := SinglePieceGroupoid( fb, [-4,-3] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ofb := One( fb );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Gfb, "Gfb" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Uhybar := Subgroupoid( Gfb, [ [ hybar, [-4,-3] ] ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Uhybar, "Uhybar" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfGroupoid( Uhy );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gensbar := GeneratorsOfGroupoid( Uhybar );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mory := GroupoidHomomorphismFromSinglePiece( </span>
<span class="GAPprompt">></span> <span class="GAPinput">               Uhy, Uhybar, gens, gensbar );</span>
groupoid homomorphism : Uhy -> Uhybar
[ [ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ], 
  [ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">morybar := InverseGeneralMapping( mory );</span>
groupoid homomorphism : Uhybar -> Uhy
[ [ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ], 
  [ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gg3 := GraphOfGroupoids( D1, [Gfa,Gfb], [Uhy,Uhybar], [mory,morybar] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( gg3 );</span>
Graph of Groupoids with :- 
    vertices: [ 5, 6 ]
        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
   groupoids: 
fp single piece groupoid: Gfa
  objects: [ -2, -1 ]
    group: fa = <[ a ]>
fp single piece groupoid: Gfb
  objects: [ -4, -3 ]
    group: fb = <[ b ]>
subgroupoids: single piece groupoid: Uhy
  objects: [ -2, -1 ]
    group: hy = <[ a^3 ]>
single piece groupoid: Uhybar
  objects: [ -4, -3 ]
    group: hybar = <[ b^2 ]>
isomorphisms: [ groupoid homomorphism : Uhy -> Uhybar
    [ [ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ], 
      [ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ] ], 
  groupoid homomorphism : Uhybar -> Uhy
    [ [ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ], 
      [ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfGroupoids( gg3 );</span>
true

</pre></div>

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

<h5>7.5-2 GraphOfGroupoidsWord</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphOfGroupoidsWord</code>( <var class="Arg">gg</var>, <var class="Arg">tv</var>, <var class="Arg">list</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">‣ IsGraphOfGroupoidsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphOfGroupoidsOfWord</code>( <var class="Arg">w</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">‣ WordOfGraphOfGroupoidsWord</code>( <var class="Arg">w</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">‣ ReducedGraphOfGroupoidsWord</code>( <var class="Arg">w</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">‣ IsReducedGraphOfGroupoidsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Having produced the graph of groupoids <code class="code">gg3</code>, we may construct left coset representatives; choose a graph of groupoids word; and reduce this to normal form. Analogous to the word <span class="SimpleMath">a^7b^-6a^-11b^9a^7</span> in subsection <code class="func">ReducedGraphOfGroupsWord</code> (<a href="chap7.html#X78FA7C3F831AA6E4"><span class="RefLink">7.3-2</span></a>) we shall consider</p>

<p class="pcenter">
(a^7 : -1 \to -2)~(b^{-6} : -4 \to -4 )~(a^{-11} : -2 \to -1)~
(b^9 : -3 \to -4)~(a^7 : -2 \to -1).
</p>

<p>Compare the normal form <code class="code">nw3</code> below with the normal form <code class="code">nw1</code> above.</p>


<div class="example"><pre>

<span class="GAPprompt">gap></span> <span class="GAPinput">f1 := Arrow( Gfa, a^7, -1, -2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 := Arrow( Gfb, b^-6, -4, -4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f3 := Arrow( Gfa, a^-11, -2, -1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f4 := Arrow( Gfb, b^9, -3, -4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f5 := Arrow( Gfa, a^7, -2, -2 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">L3 := [ f1, 1, f2, 2, f3, 1, f4, 2, f5 ];</span>
[ [a^7 : -1 -> -2], 1, [b^-6 : -4 -> -4], 2, [a^-11 : -2 -> -1], 1, 
  [b^9 : -3 -> -4], 2, [a^7 : -2 -> -2] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gw3 := GraphOfGroupoidsWord( gg3, 5, L3);</span>
(5)[a^7 : -1 -> -2].y.[b^-6 : -4 -> -4].y^-1.[a^-11 : -2 -> -1].y.[b^9 : 
-3 -> -4].y^-1.[a^7 : -2 -> -2](5)
<span class="GAPprompt">gap></span> <span class="GAPinput">nw3 := ReducedGraphOfGroupoidsWord( gw3 );</span>
(5)[a^-1 : -1 -> -1].y.[b^-1 : -3 -> -3].y^-1.[a^10 : -1 -> -2](5)

</pre></div>

<p>The reduction proceeds as follows.</p>


<ul>
<li><p><span class="SimpleMath">[a^7 : -1 -> -2] = [a^-2 : -1 -> -1]*[a^9 : -1 -> -2] stackrely-> [a^-2 : -1 -> -1]*[b^6 : -3 -> -4]</span></p>

</li>
<li><p><span class="SimpleMath">[b^6 : -3 -> -4]*[b^-6 : -4 -> -4] = [mathrmid : -3 -> -4] stackrelbary}-> [mathrmid : -1 -> -2]</span></p>

</li>
<li><p><span class="SimpleMath">[a^-2 : -1 -> -1]*[mathrmid : -1 -> -2]*[a^-11 : -2 -> -1] = [a^-13 : -1 -> -1]</span></p>

</li>
<li><p><span class="SimpleMath">[a^-13 : -1 -> -1] = [a^-1 : -1 -> -1]*[a^-12 : -1 -> -1] stackrely-> [a^-1 : -1 -> -1]*[b^-8 : -3 -> -3]</span></p>

</li>
<li><p><span class="SimpleMath">[b^-8 : -3 -> -3]*[b^9 : -3 -> -4] = [b^-1 : -3 -> -3]*[b^2 : -3 -> -4] stackrelbary}-> [b^-1 : -3 -> -3]*[a^3 : -1 -> -2]</span></p>

</li>
<li><p><span class="SimpleMath">[a^3 := -1 -> -2]*[a^7 : -2 -> -2] = [a^10 : -1 -> -2]</span></p>

</li>
</ul>
<p>So the resulting word is <span class="SimpleMath">~(a^-1 : -1, -1)(b^-1 : -3, -3)(a^10 : -1, -2)</span>. Notice that all the arrows except the final one are loops.</p>


<div class="chlinkprevnextbot"> <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>


<div class="chlinkbot"><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="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

99%


¤ Dauer der Verarbeitung: 0.34 Sekunden  (vorverarbeitet)  ¤

*© 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 ist noch experimentell.