On groups with EDT0L word problem

2025/05/26 by Bishop, Alex, Elder, Murray, Evetts, Alex +2
#20F10 #20F65 #68Q42 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2505.20057

Abstract

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).

Citations

• Using EDT0L systems to solve some equations in the solvable Baumslag-Solitar groups
• EDT0L solutions to equations in group extensions
• The complexity of solution sets to equations in hyperbolic groups
• Applications of L systems to group theory
• Solutions of Word Equations over Partially Commutative Structures
• Solution sets for equations over free groups are EDT0L languages
• Permutations of context-free, ET0L and indexed languages
• Groups of Intermediate Growth: an Introduction for Beginners

Related

• Groups with decidable word problem that do not embed in groups with decidable conjugacy problem
• Elements of uniformly bounded word-length in groups
• A note on Context Sensitive languages and Word Problems
• Non-amenable finitely presented torsion-by-cyclic groups
• The generalised word problem for subgroups of hyperbolic groups