Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Multiplication of natural number parameters
and equations in a free semigroup

Author: Gennady S. Makanin
Journal: Trans. Amer. Math. Soc. 348 (1996), 4813-4824
MSC (1991): Primary 20M05; Secondary 03D40, 20F10
MathSciNet review: 1360227
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 20M05, 03D40, 20F10

Retrieve articles in all journals with MSC (1991): 20M05, 03D40, 20F10

Additional Information

Gennady S. Makanin
Affiliation: Steklov Mathematical Institute, Vavilova 42, 117 966, Moscow GSP-1, Russia

Received by editor(s): November 2, 1994
Additional Notes: Supported by the American Mathematical Society and Russian Foundation for Fundamental Research
Article copyright: © Copyright 1996 American Mathematical Society