Context-sensitive decision problems in groups

The seemingly distinct areas of group theory, formal language theory and complexity theory interact in an important way when one considers decision problems in groups, such as the question of whether a word in the generators of the group represents the identity or not. In general, these problems are known to be undecidable. Much work has been done on the solvability of these problems in certain groups, however less has been done on the resource bounds needed to solve them, in particular with regard to space considerations. The focus of the work presented here is that of groups with (deterministic) context-sensitive decision problems, that is those that have such problems decidable in (deterministic) linear space. A classification of such groups (similarly to the way that the groups with, for example, regular or context-free word problem, have been classified) seems untenable at present. However, we present a series of interesting results with regard to such groups, with the intentions that this will lead to a better understanding of this area. Amongst these results, we emphasise the difficulty of the conjugacy problem by showing that a group may have unsolvable conjugacy problem, even if it has a subgroup of finite index with context-sensitive conjugacy problem. Our main result eliminates the previously-considered possibility that the groups with context-sensitive word problem could be classified as the set of groups which are subgroups of automatic groups, by constructing a group with context-sensitive word problem which is not a subgroup of an automatic group. We also consider a range of other issues in this area, in an attempt to increase the understanding of the sort of groups under consideration.