Quelle chap15.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/chap15.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 (Semigroups) - Chapter 15:
Finitely presented semigroups and Tietze transformations
</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="chap15" 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="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</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="chap14.html">[Previous Chapter]</a> <a href="chap16.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap15_mj.html">[MathJax on]</a></p>
<p><a id="X7F11EF307D4F409B" name="X7F11EF307D4F409B"></a></p>
<div class="ChapSects"><a href="chap15.html#X7F11EF307D4F409B">15 <span class="Heading">
Finitely presented semigroups and Tietze transformations
</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X87CDF7DF7E47F8FB">15.1 <span class="Heading">
Changing representation for words and strings
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7CACE2997C1D243A">15.1-1 WordToString</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7C81FB0F7BF3D4A3">15.1-2 RandomWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7B338B917D72FBED">15.1-3 StandardiseWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7B07470F86FDC7BA">15.1-4 StringToWord</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7BD4785D8488BAD5">15.2 <span class="Heading">
Helper functions
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7C2FCCA487DFC84C">15.2-1 ParseRelations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X847012347856C55E">15.2-2 ElementOfFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X82B7A51B7FE90486">15.2-3 ElementOfFpMonoid</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7C3837FA83BE9CD9">15.2-4 FreeMonoidAndAssignGeneratorVars</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7FF4A1CF79799314">15.2-5 IsSubsemigroupOfFpMonoid</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X8379F50C83FA5088">15.3 <span class="Heading">
Creating Tietze transformation objects
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7B505DA083E2EC0C">15.3-1 StzPresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7B86C70F84BCF8BD">15.3-2 IsStzPresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7F399C5982227D31">15.3-3 GeneratorsOfStzPresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7DCFA5D8834C31BF">15.3-4 RelationsOfStzPresentation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X79D7439679E96F28">15.3-5 UnreducedFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X780769238600AFD1">15.3-6 Length</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X84E3986C7EA62A06">15.4 <span class="Heading">
Printing Tietze transformation objects
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X80F18CED8572886B">15.4-1 StzPrintRelations</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X81837E037DE5ACBF">15.4-2 StzPrintRelation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X846B86477CBA3A2F">15.4-3 StzPrintGenerators</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7D5096807EC939E1">15.4-4 StzPrintPresentation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7EAF8F7A7F7A2A78">15.5 <span class="Heading">
Changing Tietze transformation objects
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7FCA079C7C4D398F">15.5-1 StzAddRelation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X802456968490EE7C">15.5-2 StzRemoveRelation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7F2E7FAF7F899DB9">15.5-3 StzAddGenerator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X85D1304A8461AB59">15.5-4 StzRemoveGenerator</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X85A89C227B8B1A96">15.5-5 StzSubstituteRelation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X7CBD15BC86CC2080">15.6 <span class="Heading">
Converting a Tietze transformation object into a fp semigroup
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7C46AF3A867F273A">15.6-1 TietzeForwardMap</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7F6E26348503DD53">15.6-2 TietzeBackwardMap</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X80142D917E368E46">15.6-3 StzIsomorphism</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X8549F1C87E7BD29A">15.7 <span class="Heading">
Automatically simplifying a Tietze transformation object
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X818403DA85EA82B8">15.7-1 StzSimplifyOnce</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X87B27F5A87103502">15.7-2 StzSimplifyPresentation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap15.html#X817332E27D0406A7">15.8 <span class="Heading">
Automatically simplifying an fp semigroup
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7F9ED6117BA94F01">15.8-1 SimplifyFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X7B32AC2B7D5C74D6">15.8-2 SimplifiedFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X876620BC7BD37EF6">15.8-3 UnreducedFpSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap15.html#X80C4E1757D4F3CE5">15.8-4 FpTietzeIsomorphism</a></span>
</div></div>
</div>
<h3>15 <span class="Heading">
Finitely presented semigroups and Tietze transformations
</span></h3>
<p>In this chapter we describe the functions implemented in <strong class="pkg">Semigroups</strong> that extend the features available in <strong class="pkg">GAP</strong> for dealing with finitely presented semigroups and monoids.</p>
<p>Section <a href="chap15.html#X87CDF7DF7E47F8FB"><span class="RefLink">15.1</span></a> (written by Maria Tsalakou and Murray Whyte) and Section <a href="chap15.html#X7BD4785D8488BAD5"><span class="RefLink">15.2</span></a> (written by Luke Elliott) demonstrate a number of helper functions that allow the user to convert between different representations of words and relations.</p>
<p>In the later sections, written and implemented by Ben Spiers and Tom Conti-Leslie, we describe how to change the relations of a finitely presented semigroup either manually or automatically using Tietze transformations (which is abbreviated to <strong class="button">Stz</strong>.</p>
<p><a id="X87CDF7DF7E47F8FB" name="X87CDF7DF7E47F8FB"></a></p>
<h4>15.1 <span class="Heading">
Changing representation for words and strings
</span></h4>
<p>This section contains various methods for dealing with words, which for these purposes are lists of positive integers.</p>
<p><a id="X7CACE2997C1D243A" name="X7CACE2997C1D243A"></a></p>
<h5>15.1-1 WordToString</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ WordToString</code>( <var class="Arg">A</var>, <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A string.</p>
<p>Returns the word <var class="Arg">w</var>, in the form of a string of letters of the alphabet <var class="Arg">A</var>. The alphabet is given as a string containing its members.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">WordToString("abcd", [4, 2, 3, 1, 1, 4, 2, 3]);</span>
"dbcaadbc"</pre></div>
<p><a id="X7C81FB0F7BF3D4A3" name="X7C81FB0F7BF3D4A3"></a></p>
<h5>15.1-2 RandomWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomWord</code>( <var class="Arg">l</var>, <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A word.</p>
<p>Returns a random word of length <var class="Arg">l</var> over <var class="Arg">n</var> letters.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomWord(8, 5);</span>
[ 2, 4, 3, 4, 5, 3, 3, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomWord(8, 5);</span>
[ 3, 3, 5, 5, 5, 4, 4, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RandomWord(8, 4);</span>
[ 1, 4, 1, 1, 3, 3, 4, 4 ]</pre></div>
<p><a id="X7B338B917D72FBED" name="X7B338B917D72FBED"></a></p>
<h5>15.1-3 StandardiseWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StandardiseWord</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">‣ StandardizeWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of positive integers.</p>
<p>This function takes a word <var class="Arg">w</var>, consisting of <code class="code">n</code> distinct positive integers and returns a word <code class="code">s</code> where the characters of <code class="code">s</code> correspond to those of <var class="Arg">w</var> in order of first appearance.</p>
<p>The word <var class="Arg">w</var> is changed in-place into word <code class="code">s</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">w := [3, 1, 2];</span>
[ 3, 1, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StandardiseWord(w);</span>
[ 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">w;</span>
[ 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">w := [4, 2, 10, 2];</span>
[ 4, 2, 10, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StandardiseWord(w);</span>
[ 1, 2, 3, 2 ]</pre></div>
<p><a id="X7B07470F86FDC7BA" name="X7B07470F86FDC7BA"></a></p>
<h5>15.1-4 StringToWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StringToWord</code>( <var class="Arg">s</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of positive integers.</p>
<p>This function takes a string <var class="Arg">s</var>, consisting of <code class="code">n</code> distinct positive integers and returns a word <code class="code">w</code> (i.e. a list of positive integers) over the alphabet <code class="code">[1 .. n]</code>. The positive integers of <code class="code">w</code> correspond to the characters of <var class="Arg">s</var>, in order of first appearance.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">w := "abac";</span>
"abac"
<span class="GAPprompt">gap></span> <span class="GAPinput">StringToWord(w);</span>
[ 1, 2, 1, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">w := "ccala";</span>
"ccala"
<span class="GAPprompt">gap></span> <span class="GAPinput">StringToWord(w);</span>
[ 1, 1, 2, 3, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">w := "a1b5";</span>
"a1b5"
<span class="GAPprompt">gap></span> <span class="GAPinput">StringToWord(w);</span>
[ 1, 2, 3, 4 ]</pre></div>
<p><a id="X7BD4785D8488BAD5" name="X7BD4785D8488BAD5"></a></p>
<h4>15.2 <span class="Heading">
Helper functions
</span></h4>
<p>This section describes operations implemented in <strong class="pkg">Semigroups</strong> that are designed to interact with standard <strong class="pkg">GAP</strong> methods for creating finitely presented semigroups and monoids (see <a href="../../../doc/ref/chap52_mj.html#X7DE7C52A7C4BDADE"><span class="RefLink">Reference: Finitely Presented Semigroups and Monoids</span></a>).</p>
<p><a id="X7C2FCCA487DFC84C" name="X7C2FCCA487DFC84C"></a></p>
<h5>15.2-1 ParseRelations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ParseRelations</code>( <var class="Arg">gens</var>, <var class="Arg">rels</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A list of pairs of semigroup or monoid elements.</p>
<p><code class="code">ParseRelations</code> converts a string describing relations for a semigroup or monoid to the list of pairs of semigroup or monoid elements it represents. Any white space given is ignored. The output list is then compatible with other <strong class="pkg">GAP</strong> functions. In the below examples we see free semigroups and monoids being directly quotiented by the output of the <code class="code">ParseRelations</code> function.</p>
<p>The argument <var class="Arg">gens</var> must be a list of generators for a free semigroup, each being a single alphabet letter (in upper or lower case). The argument <var class="Arg">rels</var> must be string that lists the equalities desired.</p>
<p>To take a quotient of a free monoid, it is necessary to use <code class="func">GeneratorsOfMonoid</code> (<a href="../../../doc/ref/chap51_mj.html#X83CA2E7279C44718"><span class="RefLink">Reference: GeneratorsOfMonoid</span></a>) as the 1st argument to <code class="code">ParseRelations</code> and the identity may appear as <code class="code">1</code> in the specified relations.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeSemigroup("x", "y", "z");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(f);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ParseRelations([x, y, z], " x=(y^2z) ^2x, y=xxx , z=y^3");</span>
[ [ x, (y^2*z)^2*x ], [ y, x^3 ], [ z, y^3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">r := ParseRelations([x, y, z], " x=(y^2z)^2x, y=xxx=z , z=y^3");</span>
[ [ x, (y^2*z)^2*x ], [ y, x^3 ], [ x^3, z ], [ z, y^3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">f / r;</span>
<fp semigroup with 3 generators and 4 relations of length 23>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 := FreeSemigroup("a");</span>
<free semigroup on the generators [ a ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 / ParseRelations(GeneratorsOfSemigroup(f2), "a = a^2");</span>
<fp semigroup with 1 generator and 1 relation of length 4>
<span class="GAPprompt">gap></span> <span class="GAPinput">FreeMonoidAndAssignGeneratorVars("a", "b")</span>
<span class="GAPprompt">></span> <span class="GAPinput">/ ParseRelations([a, b], "a^2=1,b^3=1,(ab)^3=1");</span>
<fp monoid with 2 generators and 3 relations of length 13>
</pre></div>
<p><a id="X847012347856C55E" name="X847012347856C55E"></a></p>
<h5>15.2-2 ElementOfFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementOfFpSemigroup</code>( <var class="Arg">S</var>, <var class="Arg">word</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An element of the fp semigroup <var class="Arg">S</var>.</p>
<p>When <var class="Arg">S</var> is a finitely presented semigroup and <var class="Arg">word</var> is an associative word in the associated free semigroup (see <code class="func">IsAssocWord</code> (<a href="../../../doc/ref/chap37_mj.html#X7FA8DA728773BA89"><span class="RefLink">Reference: IsAssocWord</span></a>)), this returns the fp semigroup element with representative <var class="Arg">word</var>.</p>
<p>This function is just a short form of the <strong class="pkg">GAP</strong> library implementation of <code class="func">ElementOfFpSemigroup</code> (<a href="../../../doc/ref/chap52_mj.html#X847012347856C55E"><span class="RefLink">Reference: ElementOfFpSemigroup</span></a>) which does not require retrieving an element family.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f := FreeSemigroup("x", "y");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(f);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s := f / [[x * x, x], [y * y, y]];</span>
<fp semigroup with 2 generators and 2 relations of length 8>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := ElementOfFpSemigroup(s, x * y);</span>
x*y
<span class="GAPprompt">gap></span> <span class="GAPinput">b := ElementOfFpSemigroup(s, x * y * y);</span>
x*y^2
<span class="GAPprompt">gap></span> <span class="GAPinput">a in s;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">a = b;</span>
true</pre></div>
<p><a id="X82B7A51B7FE90486" name="X82B7A51B7FE90486"></a></p>
<h5>15.2-3 ElementOfFpMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ElementOfFpMonoid</code>( <var class="Arg">M</var>, <var class="Arg">word</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An element of the fp monoid <var class="Arg">M</var>.</p>
<p>When <var class="Arg">M</var> is a finitely presented monoid and <var class="Arg">word</var> is an associative word in the associated free monoid (see <code class="func">IsAssocWord</code> (<a href="../../../doc/ref/chap37_mj.html#X7FA8DA728773BA89"><span class="RefLink">Reference: IsAssocWord</span></a>)), this returns the fp monoid element with representative <var class="Arg">word</var>.</p>
<p>This is analogous to <code class="func">ElementOfFpSemigroup</code> (<a href="chap15.html#X847012347856C55E"><span class="RefLink">15.2-2</span></a>).</p>
<p><a id="X7C3837FA83BE9CD9" name="X7C3837FA83BE9CD9"></a></p>
<h5>15.2-4 FreeMonoidAndAssignGeneratorVars</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FreeMonoidAndAssignGeneratorVars</code>( <var class="Arg">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">‣ FreeSemigroupAndAssignGeneratorVars</code>( <var class="Arg">arg...</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A free semigroup or monoid.</p>
<p><code class="code">FreeMonoidAndAssignGeneratorVars</code> is synonym with:</p>
<div class="example"><pre>
FreeMonoid(arg...);
AssignGeneratorVariables(last);</pre></div>
<p>These functions exist so that the <code class="code">String</code> method for a finitely presented semigroup or monoid to be valid <strong class="pkg">GAP</strong> input which can be used to reconstruct the semigroup or monoid.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroupAndAssignGeneratorVars("x", "y");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBound(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBound(y);</span>
true</pre></div>
<p><a id="X7FF4A1CF79799314" name="X7FF4A1CF79799314"></a></p>
<h5>15.2-5 IsSubsemigroupOfFpMonoid</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSubsemigroupOfFpMonoid</code>( <var class="Arg">S</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>This property is <code class="keyw">true</code> if the object <var class="Arg">S</var> is a subsemigroup of an fp monoid, and <code class="keyw">false</code> otherwise. This property is just a synonym for <code class="func">IsSemigroup</code> (<a href="../../../doc/ref/chap51_mj.html#X7B412E5B8543E9B7"><span class="RefLink">Reference: IsSemigroup</span></a>) and <code class="code">IsElementOfFpMonoidCollection</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b");</span>
<free semigroup on the generators [ a, b ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(F);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">R := [[a ^ 3, a], [b ^ 2, b], [(a * b) ^ 2, a]];</span>
[ [ a^3, a ], [ b^2, b ], [ (a*b)^2, a ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">S := F / R;</span>
<fp semigroup with 2 generators and 3 relations of length 14>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubsemigroupOfFpMonoid(S);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">map := EmbeddingFpMonoid(S);</span>
<fp semigroup with 2 generators and 3 relations of length 14> ->
<fp monoid with 2 generators and 3 relations of length 14>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubsemigroupOfFpMonoid(Image(map));</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSubsemigroupOfFpMonoid(Range(map));</span>
true</pre></div>
<p><a id="X8379F50C83FA5088" name="X8379F50C83FA5088"></a></p>
<h4>15.3 <span class="Heading">
Creating Tietze transformation objects
</span></h4>
<p>It is possible to use <strong class="pkg">GAP</strong> to create finitely presented semigroups without the <strong class="pkg">Semigroups</strong> package, by creating a free semigroup, then quotienting by a list of relations. This is described in the reference manual (<a href="../../../doc/ref/chap52_mj.html#X7DE7C52A7C4BDADE"><span class="RefLink">Reference: Finitely Presented Semigroups and Monoids</span></a>).</p>
<p>However, finitely presented semigroups do not allow for their relations to be simplified, so in the following sections, we describe how to create and modify the semigroup Tietze (<code class="func">IsStzPresentation</code> (<a href="chap15.html#X7B86C70F84BCF8BD"><span class="RefLink">15.3-2</span></a>)) object associated with an fp semigroup. This object can be automatically simplified, or the user can manually apply Tietze transformations to add or remove relations or generators in the presentation.</p>
<p>This object is analogous to <code class="func">PresentationFpGroup</code> (<a href="../../../doc/ref/chap48_mj.html#X797867B287AD92F8"><span class="RefLink">Reference: PresentationFpGroup</span></a>) implemented for fp groups in the main <strong class="pkg">GAP</strong> distribution (<a href="../../../doc/ref/chap48_mj.html#X782985197BE809BF"><span class="RefLink">Reference: Presentations and Tietze Transformations</span></a>), but its features are semigroup-specific. Most of the functions used to create, view and manipulate semigroup Tietze objects are prefixed with <strong class="button">Stz</strong>.</p>
<p><a id="X7B505DA083E2EC0C" name="X7B505DA083E2EC0C"></a></p>
<h5>15.3-1 StzPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzPresentation</code>( <var class="Arg">S</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A semigroup Tietze (Stz) object.</p>
<p>If <var class="Arg">s</var> is an fp semigroup (<code class="func">IsFpSemigroup</code> (<a href="../../../doc/ref/chap52_mj.html#X8239EF2B853411E9"><span class="RefLink">Reference: IsFpSemigroup</span></a>)), then this function returns a modifiable object representing the generators and relations of <var class="Arg">s</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(F);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := F / [[a * b, c], [b * c, a], [c * a, b]];</span>
<fp semigroup with 3 generators and 3 relations of length 12>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(S);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 12></pre></div>
<p><a id="X7B86C70F84BCF8BD" name="X7B86C70F84BCF8BD"></a></p>
<h5>15.3-2 IsStzPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsStzPresentation</code>( <var class="Arg">stz</var> )</td><td class="tdright">( filter )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Every semigroup Tietze object is an element of the category <code class="code">IsStzPresentation</code>. Internally, each Stz object contains a list of generators (each represented as a string) and a list of relations (each represented as a pair of <code class="code">LetterRep</code> words, see <code class="func">LetterRepAssocWord</code> (<a href="../../../doc/ref/chap37_mj.html#X7BD7647C7B088389"><span class="RefLink">Reference: LetterRepAssocWord</span></a>)). These generator and relation lists can be modified using Tietze transformations (<a href="chap15.html#X7EAF8F7A7F7A2A78"><span class="RefLink">15.5</span></a>).</p>
<p>When a <code class="code">IsStzPresentation</code> object <var class="Arg">stz</var> is created from an fp semigroup <code class="code">s</code> using <code class="code">stz := StzPresentation(s)</code>, the generators and relations of <var class="Arg">stz</var> are initially equal to the generators and relations of <code class="code">s</code>. However, as the Stz object <var class="Arg">stz</var> is modified, these lists may change, and their current state can be viewed using <code class="func">GeneratorsOfStzPresentation</code> (<a href="chap15.html#X7F399C5982227D31"><span class="RefLink">15.3-3</span></a>) and <code class="func">RelationsOfStzPresentation</code> (<a href="chap15.html#X7DCFA5D8834C31BF"><span class="RefLink">15.3-4</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AssignGeneratorVariables(F);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">S := F / [[a * b, c], [b * c, a], [c * a, b]];</span>
<fp semigroup with 3 generators and 3 relations of length 12>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(S);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 12>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsStzPresentation(stz);</span>
true</pre></div>
<p><a id="X7F399C5982227D31" name="X7F399C5982227D31"></a></p>
<h5>15.3-3 GeneratorsOfStzPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GeneratorsOfStzPresentation</code>( <var class="Arg">stz</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of strings.</p>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object, then <code class="code">GeneratorsOfStzPresentation</code> will return (as strings) the generators of the fp semigroup that the presentation was created from. In the <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object, it is only necessary to know how many generators there are, but for the purposes of representing generators and relations of the presentation object and building a new fp semigroup from the object, the strings representing the generators are stored.</p>
<p>As Tietze transformations are performed on <var class="Arg">stz</var>, the generators will change, but the labels will remain as close to the original labels as possible, so that if a generator in the fp semigroup obtained from the presentation is the same as a generator in the original fp semigroup, then they should have the same label.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3]];</span>
<fp semigroup with 3 generators and 2 relations of length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 2 relations
with length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">GeneratorsOfStzPresentation(stz);</span>
[ "a", "b", "c" ]</pre></div>
<p><a id="X7DCFA5D8834C31BF" name="X7DCFA5D8834C31BF"></a></p>
<h5>15.3-4 RelationsOfStzPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RelationsOfStzPresentation</code>( <var class="Arg">stz</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A list of pairs of words in <code class="code">LetterRep</code> (<code class="func">LetterRepAssocWord</code> (<a href="../../../doc/ref/chap37_mj.html#X7BD7647C7B088389"><span class="RefLink">Reference: LetterRepAssocWord</span></a>)) form.</p>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object, then <code class="code">RelationsOfStzPresentation</code> will return in letter rep form the current relations of the presentation object. When the presentation object is first created, these will be the <code class="code">LetterRep</code> forms of the relations of the fp semigroup object that is used to create <var class="Arg">stz</var>. As Tietze transformations are performed on the presentation object, the relations returned by this function will change to reflect the transformations.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3]];</span>
<fp semigroup with 3 generators and 2 relations of length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 2 relations
with length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfStzPresentation(stz);</span>
[ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ],
[ [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ] ]
</pre></div>
<p><a id="X79D7439679E96F28" name="X79D7439679E96F28"></a></p>
<h5>15.3-5 UnreducedFpSemigroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ UnreducedFpSemigroup</code>( <var class="Arg">stz</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: An fp semigroup.</p>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object, then <code class="code">UnreducedFpSemigroup</code> will return the fp semigroup that was used to create <var class="Arg">stz</var> using <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3]];</span>
<fp semigroup with 3 generators and 2 relations of length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 2 relations
with length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">UnreducedFpSemigroup(stz) = T;</span>
true
</pre></div>
<p><a id="X780769238600AFD1" name="X780769238600AFD1"></a></p>
<h5>15.3-6 Length</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Length</code>( <var class="Arg">stz</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A non-negative integer.</p>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object, then the <code class="code">Length</code> of the object is defined as the number of generators plus the lengths of each word in each relation of <var class="Arg">stz</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(stz);</span>
22
</pre></div>
<p><a id="X84E3986C7EA62A06" name="X84E3986C7EA62A06"></a></p>
<h4>15.4 <span class="Heading">
Printing Tietze transformation objects
</span></h4>
<p>Since the relations are stored as flat lists of numbers, there are several methods installed to print the presentations in more user-friendly forms.</p>
<p>All printing methods in this section are displayed as information (<code class="func">Info</code> (<a href="../../../doc/ref/chap7_mj.html#X864E4B6886E2697D"><span class="RefLink">Reference: Info</span></a>)) in the class <code class="code">InfoFpSemigroup</code> at level 1. Setting <code class="code">SetInfoLevevl(InfoFpSemigroup, 0)</code> will suppress the messages, while any higher number will display them.</p>
<p><a id="X80F18CED8572886B" name="X80F18CED8572886B"></a></p>
<h5>15.4-1 StzPrintRelations</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzPrintRelations</code>( <var class="Arg">stz</var>[, <var class="Arg">list</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object and <var class="Arg">list</var> is a list of positive integers, then <code class="code">StzPrintRelations</code> prints for each <var class="Arg">i</var> in <var class="Arg">list</var> the <var class="Arg">i</var>th relation to the console in terms of the stored labels for the generators (that is, as words over the alphabet consisting of the generators of <var class="Arg">stz</var>).</p>
<p>If <var class="Arg">list</var> is not specified then <code class="code">StzPrintRelations</code> prints all relations of <var class="Arg">stz</var> in order.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzPrintRelations(stz, [2, 3]);</span>
#I 2. b^6 = b^3
#I 3. b^2 = b
<span class="GAPprompt">gap></span> <span class="GAPinput">StzPrintRelations(stz);</span>
#I 1. a = b^5*c
#I 2. b^6 = b^3
#I 3. b^2 = b
</pre></div>
<p><a id="X81837E037DE5ACBF" name="X81837E037DE5ACBF"></a></p>
<h5>15.4-2 StzPrintRelation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzPrintRelation</code>( <var class="Arg">stz</var>, <var class="Arg">int</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object, then <code class="code">StzPrintRelation</code> calls <code class="code">StzPrintRelations</code> with parameters <var class="Arg">stz</var> and <code class="code">[<var class="Arg">int</var>]</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzPrintRelation(stz, 2);</span>
#I 2. b^6 = b^3
</pre></div>
<p><a id="X846B86477CBA3A2F" name="X846B86477CBA3A2F"></a></p>
<h5>15.4-3 StzPrintGenerators</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzPrintGenerators</code>( <var class="Arg">stz</var>[, <var class="Arg">list</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object and <var class="Arg">list</var> is a list of positive integers, then <code class="code">StzPrintGenerators</code> for each <var class="Arg">i</var> in <var class="Arg">list</var> the <var class="Arg">i</var>th generator and the number of occurrences of that generator in the relations is printed to the screen.</p>
<p>If <var class="Arg">list</var> is not specified then <code class="code">StzPrintGenerators</code> prints all generators of <var class="Arg">stz</var> in order.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzPrintGenerators(stz, [1, 2]);</span>
#I 1. a 1 occurrences
#I 2. b 17 occurrences
<span class="GAPprompt">gap></span> <span class="GAPinput">StzPrintGenerators(stz);</span>
#I 1. a 1 occurrences
#I 2. b 17 occurrences
#I 3. c 1 occurrences
</pre></div>
<p><a id="X7D5096807EC939E1" name="X7D5096807EC939E1"></a></p>
<h5>15.4-4 StzPrintPresentation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzPrintPresentation</code>( <var class="Arg">stz</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object, then <code class="code">StzPrintPresentation</code> prints a comprehensive overview of <var class="Arg">stz</var>, including the generators and number of occurrences of each generator in the relations, the relations as words over the generators, and the forward and backward maps that indicate how the unreduced semigroup maps to the semigroup currently described by <var class="Arg">stz</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzPrintPresentation(stz);</span>
#I Current generators:
#I 1. a 1 occurrences
#I 2. b 17 occurrences
#I 3. c 1 occurrences
#I
#I Current relations:
#I 1. a = b^5*c
#I 2. b^6 = b^3
#I 3. b^2 = b
#I
#I There are 3 generators and 3 relations of total length 22.
#I
#I Generators of original fp semigroup expressed as
#I combinations of generators in current presentation:
#I 1. a = a
#I 2. b = b
#I 3. c = c
#I
#I Generators of current presentation expressed as
#I combinations of generators of original fp semigroup:
#I 1. a = a
#I 2. b = b
#I 3. c = c
</pre></div>
<p><a id="X7EAF8F7A7F7A2A78" name="X7EAF8F7A7F7A2A78"></a></p>
<h4>15.5 <span class="Heading">
Changing Tietze transformation objects
</span></h4>
<p>Fundamentally, there are four different changes that can be made to a presentation without changing the algebraic structure of the fp semigroup that can be derived from it. These four changes are called Tietze transformations, and they are primarily implemented in this section as operations on an <code class="code">StzPresentation</code> object that will throw errors if the conditions have not been met to perform the Tietze transformation.</p>
<p>However, the checks required in order to ensure that a Tietze transformation is valid sometimes require verifying equality of two words in an fp semigroup (for example, to ensure that a relation we are adding to the list of relations can be derived from the relations already present). Since these checks sometimes do not terminate, a second implementation of Tietze transformations assumes good faith and does not perform any checks to see whether the requested Tietze transformation actually maintains the structure of the semigroup. This latter type should be used at the user's discretion. If only the first type are used, the presentation will always give a semigroup isomorphic to the one used to create the object, but if instead one is not changing the presentation with the intention of maintaining algebraic structure, these no-check functions are available for use.
<p>The four Tietze transformations on a presentation are adding a relation, removing a relation, adding a generator, and removing a generator, with particular conditions on what can be added/removed in order to maintain structure. More details on each transformation and its arguments and conditions is given in each entry below. In addition to the four elementary transformations, there is an additional function <code class="code">StzSubstituteRelation</code> which applies multiple Tietze transformations in sequence.</p>
<p><a id="X7FCA079C7C4D398F" name="X7FCA079C7C4D398F"></a></p>
<h5>15.5-1 StzAddRelation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzAddRelation</code>( <var class="Arg">stz</var>, <var class="Arg">pair</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object and <var class="Arg">pair</var> is a list containing two <code class="code">LetterRep</code> words over the generators of <var class="Arg">stz</var>, then <code class="code">StzAddRelation</code> will perform a Tietze transformation of the first type and add a new relation to <var class="Arg">stz</var>. This only happens if the new relation that would be formed from <var class="Arg">pair</var> can be constructed from the other existing relations; that is, if we can perform elementary operations using the existing relations of <var class="Arg">stz</var> to convert <code class="code"><var class="Arg">pair</var>[1]</code> into <code class="code"><var class="Arg">pair</var>[2]</code>.</p>
<p>If, instead, <var class="Arg">pair</var> is a list containing two elements of the fp semigroup <code class="code">S</code> that was used to create <code class="code">stz</code>, and the two words are equal in that semigroup, then this function will add the <code class="code">LetterRep</code> of these words as a new relation to <var class="Arg">stz</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3]];</span>
<fp semigroup with 3 generators and 2 relations of length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 2 relations
with length 19>
<span class="GAPprompt">gap></span> <span class="GAPinput">pair := [[2, 2, 2, 2, 2, 2, 2, 2, 2], [2, 2, 2]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzAddRelation(stz, pair);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfStzPresentation(stz);</span>
[ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ],
[ [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ],
[ [ 2, 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">pair2 := [[1, 1], [3]];</span>
[ [ 1, 1 ], [ 3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StzAddRelation(stz, pair2);</span>
Error, StzAddRelation: second argument <pair> must list two
words that are equal in the presentation <stz>
</pre></div>
<p><a id="X802456968490EE7C" name="X802456968490EE7C"></a></p>
<h5>15.5-2 StzRemoveRelation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzRemoveRelation</code>( <var class="Arg">stz</var>, <var class="Arg">index</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object and <var class="Arg">index</var> is a positive integer less than or equal to the number of relations of <var class="Arg">stz</var>, then <code class="code">StzRemoveRelation</code> will perform a Tietze transformation of the second type and remove the <var class="Arg">index</var>th relation of <var class="Arg">stz</var> if that relation is such that one side of it can be obtained from the other by a sequence of elementary operations using only the other relations of <var class="Arg">stz</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzRemoveRelation(stz, 2);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfStzPresentation(stz);</span>
[ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ], [ [ 2, 2 ], [ 2 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StzRemoveRelation(stz, 2);</span>
Error, StzRemoveRelation: second argument <index> must point to
a relation that is redundant in the presentation <stz>
</pre></div>
<p><a id="X7F2E7FAF7F899DB9" name="X7F2E7FAF7F899DB9"></a></p>
<h5>15.5-3 StzAddGenerator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzAddGenerator</code>( <var class="Arg">stz</var>, <var class="Arg">word</var>[, <var class="Arg">name</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object and <var class="Arg">word</var> is a <code class="code">LetterRep</code> word over the generators of <var class="Arg">stz</var>, then <code class="code">StzAddGenerator</code> will perform a Tietze transformation which adds a new generator to <var class="Arg">stz</var> and a new relation of the form <code class="code">newgenerator = <var class="Arg">word</var></code>.</p>
<p>If, instead, <var class="Arg">word</var> is a word over the fp semigroup <var class="Arg">S</var> that was used to create <var class="Arg">stz</var>, then this function will add the new generator and a new relation with the new generator equal to the <code class="code">LetterRep</code> of this word as a new relation to <var class="Arg">stz</var>.</p>
<p>A new name for the generator is chosen and added automatically based on the names of the existing generators to <code class="func">GeneratorsOfStzPresentation</code> (<a href="chap15.html#X7F399C5982227D31"><span class="RefLink">15.3-3</span></a>) if the argument <var class="Arg">name</var> is not included. If it is, and if <var class="Arg">name</var> is a string that is not equal to an existing generator, then the string added to the list of generators will be <var class="Arg">name</var> instead.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzAddGenerator(stz, [2, 2, 2]);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfStzPresentation(stz);</span>
[ [ [ 1 ], [ 2, 2, 2, 2, 2, 3 ] ],
[ [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2 ] ], [ [ 2, 2 ], [ 2 ] ],
[ [ 2, 2, 2 ], [ 4 ] ] ]
</pre></div>
<p><a id="X85D1304A8461AB59" name="X85D1304A8461AB59"></a></p>
<h5>15.5-4 StzRemoveGenerator</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzRemoveGenerator</code>( <var class="Arg">stz</var>, <var class="Arg">gen/genname</var>[, <var class="Arg">index</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object and <var class="Arg">gen</var> is a positive integer less than or equal to the number of generators of <var class="Arg">stz</var>, then <code class="code">StzRemoveGenerator</code> will perform a Tietze transformation which removes the <var class="Arg">gen</var>th generator of <var class="Arg">stz</var>.</p>
<p>The argument <var class="Arg">stz</var> must contain a relation of the form <code class="code"><var class="Arg">gen</var> = word</code> or <code class="code">word = <var class="Arg">gen</var></code>, where <code class="code">word</code> contains no occurrences of the generator <var class="Arg">gen</var> being removed. The generator is then removed from the presentation by replacing every instance of <var class="Arg">gen</var> with a copy of <code class="code">word</code>.</p>
<p>If the second argument is a string <var class="Arg">genname</var> rather than a positive integer <var class="Arg">gen</var>, then the function searches the generators of <var class="Arg">stz</var> for a generator with the same name and attempts to remove the generator if the same conditions as above are met.</p>
<p>If the argument <var class="Arg">index</var> is included and is a positive integer less than or equal to the number of relations, then rather than searching the relations for the first to satisfy the necessary conditions, the function checks the <var class="Arg">index</var>th relation to see if it satisfies those conditions, and applies the Tietze transformation by removing this relation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzRemoveGenerator(stz, 1);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfStzPresentation(stz);</span>
[ [ [ 1, 1, 1, 1, 1, 1 ], [ 1, 1, 1 ] ], [ [ 1, 1 ], [ 1 ] ] ]
</pre></div>
<p><a id="X85A89C227B8B1A96" name="X85A89C227B8B1A96"></a></p>
<h5>15.5-5 StzSubstituteRelation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StzSubstituteRelation</code>( <var class="Arg">stz</var>, <var class="Arg">index</var>, <var class="Arg">side</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>If <var class="Arg">stz</var> is an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) object and <var class="Arg">index</var> is a positive integer less than or equal to the number of relations of <var class="Arg">stz</var> and <var class="Arg">side</var> is either <code class="code">1</code> or <code class="code">2</code>, then <code class="code">StzRemoveGenerator</code> will perform a sequence of Tietze transformations in order to replace, for the <var class="Arg">index</var>th relation (say <code class="code">[u, v]</code>), to replace all instances of the <var class="Arg">side</var>th word of the relation in all other relations by the other side (so, for <code class="code"><var class="Arg">side</var>=1</code>, all instances of <code class="code">u</code> in all other relations of <var class="Arg">stz</var> are replaced by <code class="code">v</code>). This requires two Tietze transformations per relation containing <code class="code">u</code>, one to add a new redundant relation with each <code class="code">u</code> replaced by <code class="code">v</code>, and another to remove the original (now redundant) relation.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">F := FreeSemigroup("a", "b", "c");</span>
<free semigroup on the generators [ a, b, c ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">T := F / [[F.1, F.2 ^ 5 * F.3],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [F.2 ^ 6, F.2 ^ 3], [F.2 ^ 2, F.2]];</span>
<fp semigroup with 3 generators and 3 relations of length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">stz := StzPresentation(T);</span>
<fp semigroup presentation with 3 generators and 3 relations
with length 22>
<span class="GAPprompt">gap></span> <span class="GAPinput">StzSubstituteRelation(stz, 3, 1);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfStzPresentation(stz);</span>
[ [ [ 1 ], [ 2, 2, 2, 3 ] ], [ [ 2, 2, 2 ], [ 2, 2 ] ],
[ [ 2, 2 ], [ 2 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StzSubstituteRelation(stz, 3, 1);</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelationsOfStzPresentation(stz);</span>
[ [ [ 1 ], [ 2, 2, 3 ] ], [ [ 2, 2 ], [ 2 ] ], [ [ 2, 2 ], [ 2 ] ] ]
</pre></div>
<p><a id="X7CBD15BC86CC2080" name="X7CBD15BC86CC2080"></a></p>
<h4>15.6 <span class="Heading">
Converting a Tietze transformation object into a fp semigroup
</span></h4>
<p>Semigroup Tietze transformation objects (<code class="func">IsStzPresentation</code> (<a href="chap15.html#X7B86C70F84BCF8BD"><span class="RefLink">15.3-2</span></a>)) are not actual fp semigroups in the sense of <code class="func">IsFpSemigroup</code> (<a href="../../../doc/ref/chap52_mj.html#X8239EF2B853411E9"><span class="RefLink">Reference: IsFpSemigroup</span></a>). This is because their generators and relations can be modified (see section <a href="chap15.html#X7EAF8F7A7F7A2A78"><span class="RefLink">15.5</span></a>). However, an <code class="func">StzPresentation</code> (<a href="chap15.html#X7B505DA083E2EC0C"><span class="RefLink">15.3-1</span></a>) can be converted back into an actual finitely presented semigroup using the methods described in this section.</p>
<p>The intended use of semigroup Tietze objects is as follows: given an fp semigroup <code class="code">S</code>, create a modifiable presentation using <code class="code">stz := StzPresentation(S)</code>, apply Tietze transformations to it (perhaps in order to simplify the presentation), then generate a new fp semigroup <code class="code">T</code> given by <code class="code">stz</code> which is isomorphic to <code class="code">S</code>, but has a simpler presentation. Once <code class="code">T</code> is obtained, it may be of interest to map elements of <code class="code">S</code> over to < | |
