On groups with EDT0L word problem
By: Alex Bishop , Murray Elder , Alex Evetts and more
Potential Business Impact:
Groups with simple math problems can't be infinite.
We prove that the word problem for the infinite cyclic group is not EDT0L, and obtain as a corollary that a finitely generated group with EDT0L word problem must be torsion. In addition, we show that the property of having an EDT0L word problem is invariant under change of generating set and passing to finitely generated subgroups. This represents significant progress towards the conjecture that all groups with EDT0L word problem are finite (i.e. precisely the groups with regular word problem).
Similar Papers
On groups with EDT0L word problem
Group Theory
Proves some math problems are too hard for computers.
On finite extensions of lamplighter groups
Group Theory
Answers math puzzles with tricky group rules.
Word equations and the exponent of periodicity
Formal Languages and Automata Theory
Finds patterns in word puzzles with rules.