On groups with EDT0L word problem

Bishop, A; Elder, M; Evetts, A; Gallot, P; Levine, A

On groups with EDT0L word problem

Bishop, A Elder, M

Evetts, A Gallot, P Levine, A

Permalink

Publisher:: World Scientific Publishing
Publication Type:: Journal Article
Citation:: International Journal of Algebra and Computation

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (546.67 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Bishop, A
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945
dc.contributor.author	Evetts, A
dc.contributor.author	Gallot, P
dc.contributor.author	Levine, A
dc.date.accessioned	2026-02-26T12:36:30Z
dc.date.available	2026-02-26T12:36:30Z
dc.identifier.citation	International Journal of Algebra and Computation
dc.identifier.issn	0218-1967
dc.identifier.issn	1793-6500
dc.identifier.uri	http://hdl.handle.net/10453/193745
dc.description.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).
dc.language	en
dc.publisher	World Scientific Publishing
dc.relation	http://purl.org/au-research/grants/arc/DP210100271
dc.relation	http://purl.org/au-research/grants/arc/DP210100271
dc.relation.ispartof	International Journal of Algebra and Computation
dc.relation.isbasedon	10.1142/s0218196726500165
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0101 Pure Mathematics, 0103 Numerical and Computational Mathematics, 0802 Computation Theory and Mathematics
dc.subject.classification	General Mathematics
dc.subject.classification	4613 Theory of computation
dc.subject.classification	4901 Applied mathematics
dc.subject.classification	4904 Pure mathematics
dc.title	On groups with EDT0L word problem
dc.type	Journal Article
utslib.for	0101 Pure Mathematics
utslib.for	0103 Numerical and Computational Mathematics
utslib.for	0802 Computation Theory and Mathematics
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Science
pubs.organisational-group	University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access	*
dc.date.updated	2026-02-26T12:36:29Z
pubs.publication-status	Published online

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

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/193745