Algorithms in abstract free groups and monoids

The first section of this chapter contains algorithms about subgroups of finite index of an abstract free group of finite rank, e.g., how to decide whether an element of the free group belongs to a given subgroup of finite index or whether a subgroup of finite index is open in a certain topology. Given a prime number p, a free abstract group Φ (with an explicit basis B= { b1, …, bn}) endowed with the pro- p topology, and a finitely generated subgroup H (whose generators are given in terms of B), the second section of this chapter describes an algorithm to find a finite set of generators (written in terms of B) of the closure of H in that topology. The main result in that section presents a general approach to describing the closure of H in a pro- C topology of Φ (when C is an extension-closed pseudovariety of finite groups); one deduces from this theorem what are the main difficulties that arise when trying to make such a description algorithmic. The third part of the chapter contains several algorithms of interest in the theory of formal languages on a finite alphabet and in finite monoids; in particular, there is an algorithm that describes how to construct the kernel of a finite monoid, a problem posed by J. Rhodes