Events

Algorithmic (or decision) problems is one of the classical subjects of combinatorial group theory, originating in the three fundamental decision problems  posed  by Max Dehn in 1911: the  word problem, the conjugacy problem and the isomorphism problem. This subject has recently been given new impulse by interest in the potential use of group theory as a basis for the development of secure cryptographic systems.   

In the early 80's John Stallings showed that every finitely generated subgroup of a free group is canonically represented by a finite minimal immersion of a bouquet of circles (or, in other words, a finite labeled graph). In terms of the theory of automata, this is a minimal finite inverse automaton. This allows for the deep algorithmic theory of finite automata and finite inverse monoids to be used to answer questions about finitely generated subgroups of free groups.

We review the theory for free groups and discuss a number of algorithmic problems solved by these methods including the membership problem, the finite index problem and the computation of closures of subgroups in various profinite topologies. 

If time permits, we'll look at applying the same methods to other classes of groups. A fundamental new problem is that the Stallings folding algorithm must be modified to allow for "sewing" on relations of non-free groups. We look at the class of groups that are amalgams of finite groups or virtually  free groups. It is known that these groups are locally quasiconvex and thus all finitely generated subgroups are represented by finite automata. We give an algorithm to compute such a finite automaton and use it to solve various algorithmic problems.