An introduction to counter groups

Abstract

In this thesis we consider the generalization of automatic groups to a larger class called counter groups. A counter group is an automatic group with deterministic counter languages substituted for regular languages.

Automatic groups were introduced by David Epstein et al in 1985. They attracted the interest of many mathematicians because of their connection with the problem of classifying compact three dimensional manifolds. This problem includes as a special case the famous Poincar'e Conjecture. A solution was announced by Grigori Perelman a few years ago.

Automatic groups are defined in terms of formal languages. A formal language is a subset of a finitely generated free monoid. We present the definition of automatic groups, main theorems and some examples of automatic groups.

Counter groups are defined by counter machines and counter languages. We investigate counter languages in their own right. Counter groups resemble automatic groups. They have solvable word problem and under certain conditions solvable conjugacy problem. On the other hand, counter groups need not be finitely presented, and their word problems are more difficult than the word problems of automatic groups. The definition of counter groups encompasses more groups, like Heisenberg group and Lamplighter group that are not automatic groups. The two counter groups are presented in detail.