On groups with EDT0L word problem (Alex Bishop)

27.05.2025 10:30

After demonstrating that the word problem of a group is solvable, one then wonders how difficult it is to describe the associated computation. A common method of categorising the complexity of sets of words is by their formal-language class, that is, the level of complexity required to present such a set. In this talk, we consider the groups whose word problems lie in the family of EDT0L languages. We note that EDT0L languages have recently become of great interest within group theory, in particular, as the solution to equations over hyperbolic groups, and as a method of presenting certain groups.

Our main result is that if a group has an EDT0L word problem, then it must be torsion. This is a generalisation of a recent result which appeared in the PhD thesis of Paul Gallot. It is conjectured by Elder, Ciobanu and Ferov that a group has EDT0L word problem if and only if it is finite: this work is a step towards resolving this conjecture.

This is a joint work with Murray Elder, Alex Evetts, Paul Gallot and Alex Levine.

Lieu

Bâtiment: Conseil Général 7-9

Room 1-05, Séminaire "Groupes et géométrie"

entrée libre