Multiplication of natural number parameters and equations in a free semigroup

Abstract:

This paper deals with the problem of describing the set $M$ of all solutions of an equation over a free semigroup $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$ has a solvable word problem, $M$ must be computable. However, $M$ cannot necessarily be computed from the standard description of $M$. The present paper shows that the only polynomials needed to describe $M$ are just products of one parameter by a linear combination of some other parameters. The resulting simplification of the standard description of $M$ clearly can be used to compute $M$.