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

Functionally recursive groups

Self-similar groups


$Date: 2012/06/03 14:48:36 $

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 source of the package may be downloaded as (tar, gzipped), or explored at

The last source compatible with GAP 4.4.12 may be downloaded as (tar, gzipped).

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-2010 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 Iterated monodromy groups
10 Examples
11 FR implementation details
12 Miscellanea

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

generated by GAPDoc2HTML