On groups with EDT0L word problem

Alex Bishop; Murray Elder; Alex Evetts; Paul Gallot; Alex Levine

On groups with EDT0L word problem

Alex Bishop
, Murray Elder
, Alex Evetts
, Paul Gallot
, Alex Levine

Research output: Contribution to journal › Article › peer-review

1 Downloads (Pure)

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

Original language	English
Number of pages	40
Journal	International Journal of Algebra and Computation
Early online date	27 Feb 2026
Publication status	E-pub ahead of print - 27 Feb 2026

Keywords

word problems
EDT0L
language
finite-index EDT0L
grammar

Access to Document

rba13-Levine_On_Groups_with_EDTAccepted author manuscript, 2.24 MBLicence: CC BY

https://www.worldscientific.com/doi/10.1142/S0218196726500165

Cite this

@article{192b5535889f4c1cb090dfc89925ae70,

title = "On groups with EDT0L word problem",

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

keywords = "word problems, EDT0L, language, finite-index EDT0L, grammar",

author = "Alex Bishop and Murray Elder and Alex Evetts and Paul Gallot and Alex Levine",

year = "2026",

month = feb,

day = "27",

language = "English",

journal = "International Journal of Algebra and Computation",

issn = "0218-1967",

publisher = "World Scientific Publishing",

}

TY - JOUR

T1 - On groups with EDT0L word problem

AU - Bishop, Alex

AU - Elder, Murray

AU - Evetts, Alex

AU - Gallot, Paul

AU - Levine, Alex

PY - 2026/2/27

Y1 - 2026/2/27

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

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

KW - word problems

KW - EDT0L

KW - language

KW - finite-index EDT0L

KW - grammar

M3 - Article

SN - 0218-1967

JO - International Journal of Algebra and Computation

JF - International Journal of Algebra and Computation

ER -