In this paper we consider reduced word problems of groups. We explain the relationship between the word problem and the reduced word problem, and we give necessary and sufficient conditions for a language to be the word problem (or the reduced word problem) of a group. In addition, we show that the reduced word problem is recursive (or recursively enumerable) precisely when the word problem is recursive. We then prove that the groups which have context-free reduced word problem with respect to some finite monoid generating set are exactly the context-free groups, thus proving a conjecture of Haring-Smith. We also show that, if a group G has finite irreducible word problem with respect to a monoid generating set X, then the reduced word problem of G with respect to X is simple; this is a generalization of one direction of a theorem of Haring-Smith. References: 13
展开▼