Characterization of groups with EDT0L and ET0L word problems

From papers

Let GG be a finitely generated group, and let a finite generating set for GG be fixed. The word problem of GG is the language of words over the generators and their inverses that represent the identity element. The language classes EDT0L and ET0L are standard classes of formal languages.

EDT0L and ET0L word-problem conjecture. A group has EDT0L word problem if and only if it is finite, and a group has ET0L word problem if and only if it is virtually free.

The first assertion is motivated by the fact that free groups of rank at least two do not have EDT0L word problem, while the status of the word problem for the infinite cyclic group is posed separately. The ET0L assertion would imply that the only groups with ET0L word problem are virtually free, and is presented as a reasonable conjecture in connection with the open problem of finding a non-virtually free group with indexed word problem.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Laura Ciobanu, Murray Elder and Michal Ferov, “Applications of L systems to group theory”, arXiv:1705.02809 (2018).

Solutions 0

No solutions have been posted yet.