On groups with EDT0L word problem

Alex Bishop
UTS

Abstract

The word problem is a fundamental concept in group theory that asks us to decide if a given product of elements evaluates to the group identity. A recurring theme in geometric group theory is to classify groups based on the computational difficulty of solving their word problems. For example, Anisimov showed in 1971 that a group is finite if and only if its word problem can be described by a machine known as a finite-state automaton. In this talk, we are interested in the class of groups whose word problem can be decided by an EDT0L system (which we will define and motivate within the talk). We note here that the class of EDT0L systems has gained much popularity in group theory within recent years, as they seem to provide the perfect descriptive complexity in several areas of research.