Word problems
Trevor Evans · Bulletin of the American Mathematical Society · 1978
Introduction.In studying fundamental groups of manifolds, Dehn [4] in 1911 investigated some special cases of a problem which is now known as the word problem for groups.Let G be a group generated by a finite set of elements a, b, c,....Each element in G is a product of these generators and their inverses, for example, a~xbacb~xc.We call such expressions w(a, b, c,... ) words in the generators.G is assumed to ge given by a finite set of equations or defining relations r(a, b, c,... ) = 1 which the generators satisfy.The question Dehn proposed was to find a uniform test or mechanical procedure (i.e. an algorithm) which enables us to decide whether w * 1 for an arbitrary word w(a, b, c,... ) in G.We say that the word problem is solvable for the group G if there is such an algorithm.A different version of the same kind of problem was posed by Thue a year or two later [35].Consider an "abstract language" L having a finite alphabet 0, 6, c,....A word in L is a finite sequence of symbols from the alphabet, for example, baabecba.A language L (usually called a Thue system) is defined on the alphabet a, b, c,... by a dictionary, a finite set of pairs of words.If a word w is of the form usv, where u, v are words and s is a word which occurs in the dictionary paired with a word /, then we say that w can be transformed by the dictionary into the word utv and we write usv -» utv.If there is a finite sequence of transformations w -» • • • -» w' connecting two words w, w', then we say that w, w' are equivalent in L. Thue's problem, which we may call the word problem for the language L, asks for an algorithm for deciding whether two words in the language are equivalent.We say that the word problem is solvable for L if there is such an algorithm.These two problems are examples of the same general situation.We have an algebra & which is generated by elements a,b,c,....The elements of the algebra are represented by expressions (words) involving the generators and the operations.The algebra satisfies certain axioms and is characterized by certain basic relations r = r' where the r, r' are words.We wish to find some effective test for deciding whether two words w(a, b, c,... ), w'(a, b, c,... ) represent the same element of the algebra, i.e. whether w * w' follows from the axioms and the relations r * r'.The question of the existence of such an algorithm is called the word problem for the algebra.Obviously the word problem for groups is of this type.The word problem for the language L becomes such a question if we view L as a semigroup given by generators An invited address delivered to the American Mathematical Society in Nashville, Tennessee,