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 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.**Roger C. Lyndon,*Equations in free groups*, Trans. Amer. Math. Soc.**96**(1960), 445–457. MR**0151503**, 10.1090/S0002-9947-1960-0151503-8**2.**Roger C. Lyndon,*Groups with parametric exponents*, Trans. Amer. Math. Soc.**96**(1960), 518–533. MR**0151502**, 10.1090/S0002-9947-1960-0151502-6**3.**Ju. V. Matijasevič,*The Diophantineness of enumerable sets*, Dokl. Akad. Nauk SSSR**191**(1970), 279–282 (Russian). MR**0258744****4.**Ju. I. Hmelevskiĭ,*Equations in a free semigroup*, Trudy Mat. Inst. Steklov.**107**(1971), 286 (Russian). MR**0369575****5.**Ju. I. Hmelevskiĭ,*Systems of equations in a free group. I, II*, Izv. Akad. Nauk SSSR Ser. Mat.**35**(1971), 1237–1268; ibid. 36 (1972), 110–179 (Russian). MR**0313395****6.**G. S. Makanin,*Systems of equations in free groups*, Sibirsk. Mat. Ž.**13**(1972), 587–595 (Russian). MR**0318314**

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

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