[Up] [Next] [Index]

# 1 Introduction

### Sections

1. Overview
2. Implementation and background

## 1.1 Overview

This manual describes the FGA (Free Group Algorithms) package, a GAP package for computations with finitely generated subgroups of free groups.

This package allows you to test membership and conjugacy, and to compute free generators, the rank, the normalizer, centralizer, and index, where the groups involved are finitely generated subgroups of free groups. In addition, it provides a finite presentation for the automorphism group of a finitely generated free group following Neumann33.

See Chapter Functionality of the FGA Package for details.

Chapter Installing and Loading the FGA Package explains how to install and load the FGA package.

## 1.2 Implementation and background

The methods which are used work mainly with inverse finite automata, a variant of a concept known from theoretical computer science.

Most of these techniques are described in Sims94.

In BirgetEtAl00, 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.

Some word oriented algorithms in the FGA package use basic facts about free groups that can for example be found in LyndonSchupp77.

The theoretical background for this implementation is explained in Sievers03.

[Up] [Next] [Index]