<p>This manual describes the <strong class="pkg">FGA</strong> (<em>Free Group Algorithms</em>) package, a <strong class="pkg">GAP</strong> package for computations with finitely generated subgroups of free groups.</p>
<p>This package allows you to (constructively) test membership and conjugacy, and to compute free generators, the rank, the index, normalizers, centralizers, and intersections where the groups involved are finitely generated subgroups of free groups. In addition, it provides generators and a finite presentation for the automorphism group of a finitely generated free group and allows to write any such automorphism as word in these generators.</p>
<p>See Chapter <a href="chap2.html#X7B92AEAE7ACBE77D"><span class="RefLink"><span class="Heading">Functionality of the FGA package</span></span></a> for details.</p>
<p>Chapter <a href="chap3.html#X7FB71438871FB3B7"><span class="RefLink"><span class="Heading">Installing and loading the FGA package</span></span></a> explains how to install and load the <strong class="pkg">FGA</strong> package.</p>
<h4>1.2 <span class="Heading">Implementation and background</span></h4>
<p>The methods which are used work mainly with inverse finite automata, a variation of an idea known from theoretical computer science. An inverse finite automaton is a finite state automaton over a symmetric alphabet, i.e. one in which every letter has an inverse, such that each transition between two states for a letter corresponds to a transition in the opposite direction for the inverse letter.</p>
<p>Most of these techniques are described in Chapter 4 of <a href="chapBib.html#biBSims94">[Sim94]</a>, where the same concept is called coset automaton. The method to obtain this automaton is called basic coset enumeration, and in fact it is coset enumeration where only important cosets are defined. Here a coset <var class="Arg">Gg</var> is called important when there are words <var class="Arg">w</var> and <var class="Arg">v</var> such that <var class="Arg">wv</var> is reduced and denotes an element of <var class="Arg">G</var> and <var class="Arg">w</var> denotes an element of <var class="Arg">Gg</var>.</p>
<p>In <a href="chapBib.html#biBBirgetEtAl00">[BMMW00]</a>, the connection between finitely generated subgroups of free groups and inverse finite automata is used to transfer results about the space complexity of problems concerning inverse finite automata to analogous results about finitely generated subgroups of free groups.</p>
<p>Chapter 6 of <a href="chapBib.html#biBSims94">[Sim94]</a> describes the Reidemeister-Schreier procedure and a variant called extended coset enumeration which yields a presentation in the given generators. The <strong class="pkg">FGA</strong> package uses a variation thereof for its constructive membership test: it leaves out the part of the algorithm that fills in relations and interprets the resulting extended coset table differently. This algorithm might be called extended basic coset enumeration.</p>
<p>Some word oriented algorithms in the <strong class="pkg">FGA</strong> package use basic facts about free groups. These can, for example, be found in <a href="chapBib.html#biBLyndonSchupp77">[LS77]</a>.</p>
<p>The presentation of the automorphism groups follows <a href="chapBib.html#biBNeumann33">[Neu33]</a>. The algorithm for writing an automorphism in the generators works first at the level of Nielsen generators and uses relations from <a href="chapBib.html#biBNielsen">[Nie24]</a>.</p>
<p>The theoretical background for most of this implementation is explained in <a href="chapBib.html#biBSievers03">[Sie03]</a>.</p>
<h4>1.3 <span class="Heading">Integration of the package</span></h4>
<p>The <strong class="pkg">FGA</strong> package mainly installs new methods for operations that are already known to <strong class="pkg">GAP</strong>. They overlap with methods in the <strong class="pkg">GAP</strong> library in the case of groups of finite index. In this case, <strong class="pkg">GAP</strong>s methods are usually faster, and the <strong class="pkg">FGA</strong> package tries to recognize such cases and to refer to <strong class="pkg">GAP</strong>.</p>
<p>The methods of the <strong class="pkg">FGA</strong> package will only be selected when the groups involved know they are finitely generated. This may not always be the case for groups that were not created by methods of the <strong class="pkg">FGA</strong> package. In such a case you will get a <code class="code">no method found</code> error, or <strong class="pkg">GAP</strong> may try a coset enumeration that stops with the message <code class="code">the coset enumeration has defined more than 256000 cosets</code>. You may then call <code class="code">GeneratorsOfGroup</code>, and try again.</p>
<p>Please inform the package author if you observe any remaining problems.</p>
<p>Like the <strong class="pkg">GAP</strong> system itself, the <strong class="pkg">FGA</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>This package is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.</p>
<p>You can find the GNU General Public License in the file <code class="code">COPYING</code> of the <strong class="pkg">FGA</strong> package, and also in the file <code class="code">GPL</code> in the <code class="code">etc</code> directory of the main <strong class="pkg">GAP</strong> distribution, or see <span class="URL"><a href="http://www.gnu.org/licenses/gpl.html">http://www.gnu.org/licenses/gpl.html</a></span>.</p>
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.
