Word problems of groups: Formal languages, characterizations and decidability

摘要

Let G be a group and let phi : Sigma* - G be a monoid homomorphism from the set of all strings Sigma* over some finite alphabet Sigma onto the group G. The set Sigma is then called a generating set for G and the language [1] phi(-1) subset of Sigma* is called the word problem of G with respect to the generating set Sigma (via the homomorphism phi) and is denoted by W(G, Sigma). We consider nine conditions that hold in each such language of the form W(G, Sigma) and determine which combinations of these conditions are equivalent to the property of the language in question being the word problem of a group. We show that each of these nine conditions is decidable for the family of regular languages but that each is undecidable for the family of one-counter languages (the languages accepted by one-counter pushdown automata). We also show that the property of a language being the word problem of a group is undecidable for the family of one-counter languages but is decidable for the family of deterministic context-free languages (the languages accepted by deterministic pushdown automata). (C) 2018 Elsevier B.V. All rights reserved.