Search

In this paper we introduce recursive functions (Xi,X2)I' (S > O), Th(X1, X2, X3).A2 (i -1, 2,3; s > 0), Ro(X 1, X2, x3) z (i1, 2,3; s > O) of the word variables xI, X2, X3, natural nuniber variables Ak and variables Pk whose values are finite sequences of natural number variables. By means of these functions we give finite expressions for the family of solutions of the equation X1X2X3X4 = ((xi, X2, X3)x5, where ((x1, X2, x3) is an arbitrary word in the alphabet xi, X2, X3, iri a free monoid.

This paper deals with the problem of describing the set M M of all solutions of an equation over a free semigroup S S . The standard way to do this involves the introduction of auxiliary equations containing polynomials in natural number parameters of arbitrarily high degree. Since S S has a solvable word problem, M M must be computable. However, M M cannot necessarily be computed from the standard description of M M . The present paper shows that the only polynomials needed to describe M M are just products of one parameter by a linear combination of some other parameters. The resulting simplification of the standard description of M M clearly can be used to compute M M .