Goto Chapter: Top 1 2 3 4 5 Bib Ind
 Top of Book   Previous Chapter   Next Chapter 

1 Introduction
 1.1 System Requirements and Dependencies
 1.2 Obtaining and Installing SmallOverlap
 1.3 Loading SmallOverlap

1 Introduction

SmallOverlap is a GAP package for computing with monoids and semigroups given by finite presentations satisfying small overlap conditions of the kind introduced by Remmers [Rem71]. It includes routines for testing whether presentations satisfy small overlap conditions, and an implementation of a new, highly efficient algorithm to solve the word problem for monoid and semigroup presentations satisfying the condition C(4) [Kam07].

The purposes of the package are twofold. First, it can be transparently employed by users wishing to make use of faster computations in small overlap monoids and semigroups. And secondly, it will be of use to researchers studying small overlap monoids and semigroups for their own sake.

The package is still at an early development stage, and may well contain bugs. If you find one, or have any comments on the package, the author will be very pleased to hear from you.

This manual comprises five chapters. This introduction contains technical information on installing and loading the package. Chapter 2 contains a very brief introduction to the history and theory of small overlap conditions. Chapter 3 is a short example session to illustrate the most important features of the package. Chapter 4 documents all the functionality of the package in detail. Finally, Chapter 5 discusses some performance issues.

1.1 System Requirements and Dependencies

SmallOverlap is written in pure GAP with no use of external libraries, and so should run happily on any platform supported by GAP. The algorithms implemented are highly efficient, so unless you are working with enormous presentations, you should need no more memory or processor power than is usually required by GAP. The package has been developed and tested with GAP 4.4.10, but is likely to work with any GAP 4 release. The online help requires GAPDoc 1.1 or later.

1.2 Obtaining and Installing SmallOverlap

To install SmallOverlap, download the file smalloverlap.tar from Mark's Homepage and unpack it into the pkg directory of your GAP hierarchy.

1.3 Loading SmallOverlap

This section describes how to load the SmallOverlap package, and how to make GAP use it implicitly and transparently for computations. First load the package in the usual way:

gap> LoadPackage("smalloverlap");
Loading package SmallOverlap (version 0.1)
Mark Kambites, School of Mathematics, University of Manchester
This is an experimental development version and may contain bugs.
All usage is at your own risk.
Please send comments and bug reports to Mark.Kambites@manchester.ac.uk

SmallOverlap routines are now installed for explicit use only; to
enable implicit use call PreferSmallOverlapEqualityTest()

true

Now if you want to make GAP use the new small overlap routines whenever it can, just call the function PreferSmallOverlapEqualityTest:

gap> PreferSmallOverlapEqualityTest();
SmallOverlap routines will now be used (where applicable) for
testing equality in finitely presented semigroups and monoids.

You can now use GAP entirely as normal, forgetting that the package is installed. However, computations with finitely presented semigroups and monoids will now use the small overlap equality tester where applicable, which means that many computations will run faster, or succeed where they would otherwise have failed or not terminated. (In the event that you are performing computations with very large numbers of different finitely presented monoids or semigroups which do not satisfy C(4), you may experience a slight slowdown caused by the process of checking the C(4) condition for each monoid - see 5.2 for a full discussion.) If you just wish to enjoy the fast computation abilities of the small overlap routines, you need read no further!

 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML