Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0002-9947-96-01670-4
PII: S 0002-9947(96)01670-4
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