There has been considerable interest in exploring the connections between the word problem of a finitely generated group as a formal language and the algebraic structure of the group. However, there are few complete characterizations that tell us precisely which groups have their word problem in a specified class of languages. We investigate which finitely generated groups have their word problem equal to a language accepted by a Petri net and give a complete classification, showing that a group has such a word problem if and only if it is virtually abelian.
|Name||Lecture Notes in Computer Science|
|Workshop||International Workshop on Descriptional Complexity of Formal Systems|
|Period||16/06/15 → …|
The final authenticated version is available online at https://doi.org/10.1007/978-3-319-19225-3_21