Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind
 [Top of Book]  [Contents]   [Next Chapter] 

Functionally recursive groups

Self-similar groups

Version 2.4.12


Groups generated by automata or satisfying functional recursions

Laurent Bartholdi
Email: laurent dot bartholdi at gmail dot com

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


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

This documentation for FR is available at in PDF format, and may be accessed online at

The latest release of the package may be downloaded as (tar, gzipped). The latest repository version (possibly unstable) may be downloaded as (tar, gzipped), (git repository), or explored at

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.


© 2006-2012 by Laurent Bartholdi


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


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.


1 Licensing
2 FR package
3 Functionally recursive machines
4 Functionally recursive elements
5 Mealy machines and elements
6 Linear machines and elements
7 Self-similar groups, monoids and semigroups
8 Algebras
9 Examples
10 FR implementation details
11 Miscellanea

 [Top of Book]  [Contents]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

generated by GAPDoc2HTML