Title:
Compression techniques in group theory
Abstract:
The study of algorithmic problems in group theory and their decidability/complexity has a long tradition and can be traced back to the work of Max Dehn from 1910. Certainly the most important algorithmic problem in this context is the word problem for a (usually fixed) finitely generated group: the input is a finite word over the group generators and the
question is whether this word evaluates to the group identity. Although in general undecidable (even for finitely presented group), there are many known classes of groups for which the word problem can be solved quite efficiently, e.g. finitely generated linear groups (deterministic logspace),hyperbolic groups (LogCFL) and automatic groups (polynomial time).
In recent years, compression techniques have been shown to useful in getting efficient algorithms for word problems and related algorithmic problems. For instance, the first polynomial time algorithm for the word problem of the automorphism group of a free group F exploits a reduction to the so-called
compressed word problem of F. The latter is the variant of the word problem, where the input word is given succinctly by a so-called straight-line program (a context-free grammar that produces a single word; such grammars received a lot of attention in data compression and string algorithms).
The compressed word problem for a free group can be solved in polynomial time using a result of Plandowski according to which equivalence of straight-line programs can be tested in polynomial time. In the meantime, the complexity of the compressed word problem has been studied for various classes of groups. Moreover, other compressed representations haven been used successfully
in group theory (e.g. power circuits and power words). The talk will give an overview on these techniques.