Functionally recursive groups

Groups generated by automata or satisfying functional recursions

Laurent Bartholdi
Email: laurent dot bartholdi at gmail dot com
Homepage: http://www.uni-math.gwdg.de/laurent/

Address:
Mathematisches Institut
Bunsenstraße 3-5
D-37073 Göttingen
Germany

Abstract

This document describes the package FR, which implements in GAP the basic objects of Mealy machines and functional recursions; and handles groups that they generate.

The computer algebra system GAP is available at http://gap-system.org.

This documentation for FR is available at http://www.gap-system.org/Manuals/pkg/fr-2.4.3/doc/manual.pdf in PDF format, and may be accessed online at http://gap-packages.github.io/fr/.

The latest release of the package may be downloaded as https://github.com/gap-packages/fr/archive/2.4.3.tar.gz (tar, gzipped) and https://github.com/gap-packages/fr/archive/2.4.3.zip (zip). The latest repository version (possibly unstable) may be downloaded as https://github.com/gap-packages/fr/tarball/master (tar, gzipped), https://github.com/gap-packages/fr.git (git repository), or explored at https://github.com/gap-packages/fr/tree/master/.

Groups defined by a recursive action on a rooted tree can be defined in GAP via their recursion. Various algorithms are implemented to manipulate these groups and their elements.

For comments or questions on FR please contact the author; this package is still under development.

Copyright

© 2006-2012 by Laurent Bartholdi

Acknowledgements

Part of this work is/was supported by the "Swiss National Fund for Scientific Research" and the "German Science Foundation".

Colophon

This project started in the mid-1990s, when, as a PhD student I did many calculations with groups generated by automata, and realized the similarities between all calculations; it quickly became clear that these calculations could be done much better by a computer than by a human.

The first routines I wrote constructed finite representations of the groups considered, so as to get insight from fast calculations within GAP. The results then had to be proved correct within the infinite group under consideration, and this often involved guessing appropriate words in the infinite group with a given image in the finite quotient.

Around 2000, I had developed quite a few routines, which I assembled in a GAP package, that dealt directly with infinite groups. This package was primitive at its core, but was extended with various routines as they became useful.

I decided in late 2005 to start a new package from scratch, that would encorporate as much functionality as possible in a uniform manner; that would handle semigroups as well as groups; that could be easily extended; and with a complete, understandable documentation. I hope I am not too far from these objectives.

generated by GAPDoc2HTML