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

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?)

  • 1. R. C. Lyndon, Equations in free groups, Trans. Amer. Math. Soc. 96 (1960), 445-457. MR 27:1488
  • 2. -, Groups with parametric exponents, Trans. Amer. Math. Soc. 96 (1960), 518-533. MR 27:1487
  • 3. Yu. V. Matiyasevich, Enumerable sets are diophantine, (Russian), Dokl. Akad. Nauk SSSR 191 (1970), 279-282; Improved English transl., Soviet Math. Dokl. 11 (1970), 354-357. MR 41:3390
  • 4. Yu. J. Khmelevskii, Equations in free semigroups, Trudy Mat. Inst. Steklov. 107 (1971); English transl., Proc. Steklov Inst. Math., No. 107 (1971), Amer. Math. Soc., Providence, RI, 1976. MR 51:5808
  • 5. -, Systems of equations in a free group. I, II, Izv. Akad. Nauk SSSR Ser. Mat. 35 (1971), 1237-1268, 36 (1972), 110-179; English transl. in Math. USSR Izv. 5 (1971), 6 (1972). MR 47:1949
  • 6. G. S. Makanin, System of standard word equations in n-layer alphabet unknowns, Sibirsk. Math. Zh. 13 (1972), 587-597; English transl. in Siberian Math. J. 13 (1972). MR 47:6861

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

American Mathematical Society