<?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>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (SgpViz) - Chapter 2: Basics</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="chap2"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Previous Chapter]</a>    <a href="chap3_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap2.html">[MathJax off]</a></p>
<p><a id="X868F7BAB7AC2EEBC" name="X868F7BAB7AC2EEBC"></a></p>
<div class="ChapSects"><a href="chap2_mj.html#X868F7BAB7AC2EEBC">2 <span class="Heading">Basics</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X7A489A5D79DA9E5C">2.1 <span class="Heading">Examples </span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X85134313846D1A8A">2.2 <span class="Heading">Some attributes</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7F7FAED380682973">2.2-1 HasCommutingIdempotents</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X83F1529479D56665">2.2-2 IsInverseSemigroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X78CA2A0D869C51DC">2.3 <span class="Heading">Some basic functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7A65787A83C0F8EF">2.3-1 PartialTransformation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7EEED52C7D38E1CA">2.3-2 ReduceNumberOfGenerators</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7BBEBEE885D05208">2.3-3 SemigroupFactorization</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X7FB7633483A45209">2.3-4 GrahamBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2_mj.html#X789D5E5A8558AA07">2.4 <span class="Heading">Cayley graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X822983CD7F01B5EA">2.4-1 RightCayleyGraphAsAutomaton</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2_mj.html#X82F7D3E485D615D8">2.4-2 RightCayleyGraphMonoidAsAutomaton</a></span>
</div></div>
</div>

<h3>2 <span class="Heading">Basics</span></h3>

<p>We give some examples of semigroups to be used later. We also describe some basic functions that are not directly available from <strong class="pkg">GAP</strong>, but are useful for the purposes of this package.</p>

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

<h4>2.1 <span class="Heading">Examples </span></h4>

<p>These are some examples of semigroups that will be used through this manual</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeMonoid("a","b");</span>
<free monoid on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := GeneratorsOfMonoid( f )[ 1 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := GeneratorsOfMonoid( f )[ 2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">r:=[[a^3,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[a^2*b,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[b*a^2,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[b^2,a^2],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[a*b*a,a],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[b*a*b,b] ];</span>
[ [ a^3, a^2 ], [ a^2*b, a^2 ], [ b*a^2, a^2 ], [ b^2, a^2 ], [ a*b*a, a ], 
  [ b*a*b, b ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">b21:= f/r;</span>
<fp monoid on the generators [ a, b ]>
      </pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g0:=Transformation([4,1,2,4]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g1:=Transformation([1,3,4,4]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">g2:=Transformation([2,4,3,4]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">poi3:= Monoid(g0,g1,g2);</span>
<monoid with 3 generators>
     </pre></div>

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

<h4>2.2 <span class="Heading">Some attributes</span></h4>

<p>These functions are semigroup attributes that get stored once computed.</p>

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

<h5>2.2-1 HasCommutingIdempotents</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; HasCommutingIdempotents</code>( <var class="Arg">M</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Tests whether the idempotents of the semigroup <var class="Arg">M </var>commute.</p>

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

<h5>2.2-2 IsInverseSemigroup</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsInverseSemigroup</code>( <var class="Arg">S</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Tests whether a finite semigroup <var class="Arg">S </var>is inverse. It is well-known that it suffices to test whether the idempotents of <var class="Arg">S </var>commute and <var class="Arg">S </var>is regular. The function <code class="code">IsRegularSemigroup </code>is part of <strong class="pkg">GAP</strong>.</p>

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

<h4>2.3 <span class="Heading">Some basic functions</span></h4>

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

<h5>2.3-1 PartialTransformation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PartialTransformation</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A partial transformation is a partial function of a set of integers of the form <span class="SimpleMath">\(\{1,\dots, n\}\)</span>. It is given by means of the list of images <var class="Arg">L</var>. When an element has no image, we write 0. Returns a full transformation on a set with one more element that acts like a zero.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">PartialTransformation([2,0,4,0]);</span>
Transformation( [ 2, 5, 4, 5, 5 ] )
      </pre></div>

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

<h5>2.3-2 ReduceNumberOfGenerators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ReduceNumberOfGenerators</code>( <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Given a subset <var class="Arg">L</var> of the generators of a semigroup, returns a list of generators of the same semigroup but possibly with less elements than <var class="Arg">L</var>.</p>

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

<h5>2.3-3 SemigroupFactorization</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SemigroupFactorization</code>( <var class="Arg">S</var>, <var class="Arg">L</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">L</var> is an element (or list of elements) of the semigroup <var class="Arg">S</var>. Returns a minimal factorization on the generators of <var class="Arg">S</var> of the element(s) of <var class="Arg">L</var>. Works only for transformation semigroups.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">el1 := Transformation( [ 2, 3, 4, 4 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">el2 := Transformation( [ 2, 4, 3, 4 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f1 := SemigroupFactorization(poi3,el1);</span>
[ [ Transformation( [ 1, 3, 4, 4 ] ), Transformation( [ 2, 4, 3, 4 ] ) ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f1[1][1] * f1[1][2] = el1;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SemigroupFactorization(poi3,[el1,el2]);</span>
[ [ Transformation( [ 1, 3, 4, 4 ] ), Transformation( [ 2, 4, 3, 4 ] ) ],
  [ Transformation( [ 2, 4, 3, 4 ] ) ] ]
</pre></div>

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

<h5>2.3-4 GrahamBlocks</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GrahamBlocks</code>( <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><var class="Arg">mat</var> is a matrix as displayed by <code class="code">DisplayEggBoxOfDClass(D);</code> of a regular D-class <code class="code">D</code>. This function outputs a list <code class="code">[gmat, phi]</code> where <code class="code">gmat</code> is <var class="Arg">mat</var> in Graham's blocks form and <code class="code">phi</code> maps H-classes of <code class="code">gmat</code> to the corresponding ones of <var class="Arg">mat</var>, i.e., <code class="code">phi[i][j] = [i',j']</code> where <code class="code">mat[i'][j'] = gmat[i][j]</code>. If the argument to this function is not a matrix corresponding to a regular D-class, the function may abort in error.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">p1 := PartialTransformation([6,2,0,0,2,6,0,0,10,10,0,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p2 := PartialTransformation([0,0,1,5,0,0,5,9,0,0,9,1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p3 := PartialTransformation([0,0,3,3,0,0,7,7,0,0,11,11]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">p4 := PartialTransformation([4,4,0,0,8,8,0,0,12,12,0,0]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">css3:=Semigroup(p1,p2,p3,p4);</span>
<transformation semigroup of degree 13 with 4 generators>
<span class="GAPprompt">gap></span> <span class="GAPinput">el := Elements(css3)[8];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">D := GreensDClassOfElement(css3, el);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRegularDClass(D);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">DisplayEggBoxOfDClass(D);</span>
[ [  1,  1,  0,  0 ],
  [  1,  1,  0,  0 ],
  [  0,  0,  1,  1 ],
  [  0,  0,  1,  1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">mat := [ [  1,  0,  1,  0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [  0,  1,  0,  1 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [  0,  1,  0,  1 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">  [  1,  0,  1,  0 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">res := GrahamBlocks(mat);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintArray(res[1]);</span>
[ [  1,  1,  0,  0 ],
  [  1,  1,  0,  0 ],
  [  0,  0,  1,  1 ],
  [  0,  0,  1,  1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PrintArray(res[2]);</span>
[ [  [ 1, 1 ],  [ 1, 3 ],  [ 1, 2 ],  [ 1, 4 ] ],
  [  [ 4, 1 ],  [ 4, 3 ],  [ 4, 2 ],  [ 4, 4 ] ],
  [  [ 2, 1 ],  [ 2, 3 ],  [ 2, 2 ],  [ 2, 4 ] ],
  [  [ 3, 1 ],  [ 3, 3 ],  [ 3, 2 ],  [ 3, 4 ] ] ]
</pre></div>

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

<h4>2.4 <span class="Heading">Cayley graphs</span></h4>

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

<h5>2.4-1 RightCayleyGraphAsAutomaton</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RightCayleyGraphAsAutomaton</code>( <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Computes the right Cayley graph of a finite monoid or semigroup <var class="Arg">S</var>. It uses the <strong class="pkg">GAP</strong> buit-in function <code class="code">CayleyGraphSemigroup</code> to compute the Cayley Graph and returns it as an automaton without initial nor final states. (In this automaton state <code class="code">i</code> represents the element <code class="code">Elements(S)[i]</code>.) The <strong class="pkg">Automata</strong> package is used to this effect.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">rcg := RightCayleyGraphAsAutomaton(b21);</span>
< deterministic automaton on 2 letters with 6 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(rcg);</span>
   |  1  2  3  4  5  6
-----------------------
 a |  2  4  6  4  2  4
 b |  3  5  4  4  4  3
Initial state:   [ ]
Accepting state: [ ]
      </pre></div>

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

<h5>2.4-2 RightCayleyGraphMonoidAsAutomaton</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RightCayleyGraphMonoidAsAutomaton</code>( <var class="Arg">S</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>This function is a synonym of <code class="func">RightCayleyGraphAsAutomaton</code> (<a href="chap2_mj.html#X822983CD7F01B5EA"><span class="RefLink">2.4-1</span></a>).</p>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap1_mj.html">[Previous Chapter]</a>    <a href="chap3_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.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>