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

DOI:
https://doi.org/10.1090/S0002-9947-96-01670-4

MathSciNet review:
1360227

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

**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**

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:
https://doi.org/10.1090/S0002-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