Quelle  chap0.html   Sprache: 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 (IdRel) - Contents</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="chap0"  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="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="chap1.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap0_mj.html">[MathJax on]</a></p>
<p><a id="X7D2C85EC87DD46E5" name="X7D2C85EC87DD46E5"></a></p>
<div class="pcenter">

<h1>idrel</h1>


<h2>Identities among relations</h2>

<p>
    2.49</p>

<p>
    2 October 2025
  </p>

</div>
<p><b>
    Anne Heyworth

  </b>
</p><p><b>
    Chris Wensley



  </b>
<br />Email: <span class="URL"><a href="mailto:cdwensley.maths@btinternet.com">cdwensley.maths@btinternet.com</a></span>
<br />Homepage: <span class="URL"><a href="https://github.com/cdwensley">https://github.com/cdwensley</a></span>
</p>

<p><a id="X7AA6C5737B711C89" name="X7AA6C5737B711C89"></a></p>
<h3>Abstract</h3>
<p><strong class="pkg">IdRel</strong> is a <strong class="pkg">GAP</strong> package originally implemented in 1999, using the <strong class="pkg">GAP</strong> 3 language, when the first author was studying for a Ph.D. in Bangor.</p>

<p>This package is designed to compute a minimal set of generators for the module of the identities among relators of a group presentation. It does this using</p>


<ul>
<li><p>rewriting and logged rewriting: a self-contained implementation of the Knuth-Bendix process using the monoid presentation associated to the group presentation;</p>

</li>
<li><p>monoid polynomials: an implementation of the monoid ring;</p>

</li>
<li><p>module polynomials: an implementation of the right module over this monoid generated by the relators.</p>

</li>
<li><p>Y-sequences: used as a <em>rewriting</em> way of representing elements of a free crossed module (products of conjugates of group relators and inverse relators).</p>

</li>
</ul>
<p><strong class="pkg">IdRel</strong> became an accepted <strong class="pkg">GAP</strong> package in May 2015.</p>

<p>Bug reports, suggestions and comments are, of course, welcome. Please contact the last author at <span class="URL"><a href="mailto:cdwensley.maths@btinternet.com">cdwensley.maths@btinternet.com</a></span> or submit an issue at the GitHub repository <span class="URL"><a href="https://github.com/gap-packages/idrel/issues/">https://github.com/gap-packages/idrel/issues/</a></span>.</p>

<p><a id="X81488B807F2A1CF1" name="X81488B807F2A1CF1"></a></p>
<h3>Copyright</h3>
<p>© 1999-2025 Anne Heyworth and Chris Wensley</p>

<p>The <strong class="pkg">IdRel</strong> package is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.</p>

<p><a id="X82A988D47DFAFCFA" name="X82A988D47DFAFCFA"></a></p>
<h3>Acknowledgements</h3>
<p>This documentation was prepared using the <strong class="pkg">GAPDoc</strong> <a href="chapBib.html#biBGAPDoc">[LN17]</a> and <strong class="pkg">AutoDoc</strong> <a href="chapBib.html#biBAutoDoc">[GH17]</a> packages.</p>

<p>The procedure used to produce new releases uses the package <strong class="pkg">GitHubPagesForGAP</strong> <a href="chapBib.html#biBGitHubPagesForGAP">[Hor14]</a> and the package <strong class="pkg">ReleaseTools</strong>.</p>

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

<div class="contents">
<h3>Contents<a id="contents" name="contents"></a></h3>

<div class="ContChap"><a href="chap1.html#X7DFB63A97E67C0A1">1 <span class="Heading">Introduction</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap1.html#X80F39D77788BD099">1.1 <span class="Heading">An illustrative example</span></a>
</span>
</div>
</div>
<div class="ContChap"><a href="chap2.html#X7CA8FCFD81AA1890">2 <span class="Heading">Rewriting Systems</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X7875619E84157FC1">2.1 <span class="Heading">Monoid Presentations of FpGroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X868422B878B0C380">2.1-1 FreeRelatorGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7CBE13927DFF4446">2.1-2 MonoidPresentationFpGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X78301362834E55AB">2.1-3 PrintLnUsingLabels</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7EBBA6A284CC7918">2.1-4 InitialRulesOfPresentation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X7A1F10597D8FC9A9">2.2 <span class="Heading">Rewriting systems for FpGroups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X858ECE3E807C7363">2.2-1 RewritingSystemFpGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X83BD6C0A80D88C2C">2.2-2 OnePassReduceWord</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7F0CD1EB7C220D40">2.2-3 OnePassKB</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X844BF013780A746D">2.2-4 RewriteReduce</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8412C40B7B2DC8E0">2.2-5 KnuthBendix</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X83CBF2BE8478A728">2.3 <span class="Heading">Enumerating elements</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7EDA50068207339D">2.3-1 ElementsOfMonoidPresentation</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap3.html#X7B8D727485966AF8">3 <span class="Heading">Logged Rewriting Systems</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X797732E87F1FE197">3.1 <span class="Heading">Logged Knuth-Bendix Completion</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7F47FE67829B962A">3.1-1 InitialLoggedRulesOfPresentation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X80075D5180A8F1A5">3.1-2 LoggedOnePassKB</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7E550C0078AEDC45">3.1-3 LoggedRewriteReduce</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X87D1E3A578AAAFCB">3.1-4 LoggedKnuthBendix</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8652CEEF7802DA46">3.1-5 LoggedRewritingSystemFpGroup</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X831A93087918AA5D">3.2 <span class="Heading">Logged reduction of a word</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7C5094AF784A8BA7">3.2-1 LoggedReduceWordKB</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap4.html#X83B25026816C87CE">4 <span class="Heading">Monoid Polynomials</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7E8CE44085FE959D">4.1 <span class="Heading">Construction of monoid polynomials</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7DE231F282DB8660">4.1-1 MonoidPolyFromCoeffsWords</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X84B1F4CC79983A94">4.2 <span class="Heading">Components of a polynomial</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X810C636178EA42D0">4.2-1 Terms</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X85C78946877C1FF5">4.2-2 Monic</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X82E04F1086DAAA43">4.2-3 AddTermMonoidPoly</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X832341AB7A04BA45">4.3 <span class="Heading">Monoid Polynomial Operations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X86C2C49080691991">4.3-1 Length</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X7A80EA5C7AEA68B1">4.4 <span class="Heading">Reduction of a Monoid Polynomial</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7979DE308676398D">4.4-1 ReduceMonoidPoly</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap5.html#X7B5CEEDF82747121">5 <span class="Heading">Module Polynomials</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X86625AB980F24AA5">5.1 <span class="Heading">Construction of module polynomials</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7A03D1D881B9976E">5.1-1 ModulePoly</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X7BA4DEB7865F82E5">5.1-2 PrintLnModulePoly</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X83ECC2D5781DE850">5.2 <span class="Heading">Components of a module polynomial</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X79E2DD9879D9182C">5.2-1 Terms</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5.html#X7E57DFF4791C4CAA">5.3 <span class="Heading">Module Polynomial Operations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap5.html#X811C7964873E4062">5.3-1 AddTermModulePoly</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chap6.html#X78038BF07E998E21">6 <span class="Heading">Identities Among Relators</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X788AFE547F49A8AF">6.1 <span class="Heading">Constructing identities</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7BEE0DBB78F9355E">6.1-1 RootIdentities</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7933DDE27D5254A4">6.1-2 IdentityRelatorSequences</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7D9664267BC57E09">6.1-3 LogSequenceLessThan</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X84E1E018809BE464">6.1-4 ExpandLogSequence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X79EE179E7AD81F44">6.2 <span class="Heading">Identities for <span class="SimpleMath">S_3</span></span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X8064D8CE783CB70A">6.2-1 ReduceLogSequences</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X82CCDCDF7BE58F35">6.2-2 ConjugateByWordLogSequence</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X8220EF3585706C00">6.2-3 ChangeStartLogSequence</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7E3DACB581C67E3C">6.2-4 InverseLogSequence</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X8325D1257B791ABC">6.2-5 CancelImmediateInversesLogSequence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X82CE16C9788F883A">6.3 <span class="Heading">Reducing identities</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X80F769D9796954FC">6.3-1 LogSequenceRewriteRules</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X82F66A16877FCDFE">6.3-2 OnePassReduceLogSequence</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X85814EFA81FE864F">6.3-3 MoveRightLogSequence</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7EE8CE5E79598779">6.3-4 SubstituteLogSubsequence</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7D428F9B8054F5FB">6.4 <span class="Heading">The original approach</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7FD998C87BF9AAC9">6.4-1 IdentitiesAmongRelators</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X78A94CB77B98ACAA">6.4-2 IdentityYSequences</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X8448909D82CF6FE9">6.5 <span class="Heading">Partial lists of elements</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7FCEF03E7A57C331">6.5-1 PartialElementsOfMonoidRepresentation</a></span>
</div></div>
</div>
<div class="ContChap"><a href="chapBib.html"><span class="Heading">References</span></a></div>
<div class="ContChap"><a href="chapInd.html"><span class="Heading">Index</span></a></div>
<br />
</div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.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="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>