Characterization of groups with EDT0L and ET0L word problems
Statement
Let be a finitely generated group, and let a finite generating set for be fixed. The word problem of 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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.