MAGMA Computational Algebra System

Introduction

Automatic groups provide a Magma level interface to Derek Holt's KBMAG programs, and specifically to KBMAG's automatic groups program autgroup. Much of the material in this chapter is based on the KBMAG documentation [Hol97]. Familiarity with the Knuth--Bendix completion procedure and the automata associated with a short-lex automatic group is assumed. Some familiarity with KBMAG would be beneficial.

Subsections

• Terminology
• The Category of Automatic Groups
• The Construction of an Automatic Group

Terminology

An automatic group G is a finitely presented group in which various group operations, notably equality between words of G and word enumeration, are decidable through the use of various automata. The words in the automatic group G that can be computed in Magma are ordered using the short-lex ordering on words (shorter words come before longer, and for words of equal length lexicographical ordering is used, based on the given ordering of the generators).

The Category of Automatic Groups

The family of all automatic groups forms a category. The objects are the automatic groups and the morphisms are group homomorphisms. The Magma designation for this category of groups is GrpAtc. Elements of a automatic group are designated as GrpAtcElt.

The Construction of an Automatic Group

An automatic group G is constructed in a three-step process:

(i)

We construct a free group FG.

(ii)

We construct a quotient F of FG.

(iii)

We create a monoid presentation for F and then run procedures which attempt to construct the automata associated with G and to prove them correct.