Multiplication of natural number parameters and equations in a free semigroup
HTML articles powered by AMS MathViewer
- by Gennady S. Makanin PDF
- Trans. Amer. Math. Soc. 348 (1996), 4813-4824 Request permission
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
- Roger C. Lyndon, Equations in free groups, Trans. Amer. Math. Soc. 96 (1960), 445–457. MR 151503, DOI 10.1090/S0002-9947-1960-0151503-8
- Roger C. Lyndon, Groups with parametric exponents, Trans. Amer. Math. Soc. 96 (1960), 518–533. MR 151502, DOI 10.1090/S0002-9947-1960-0151502-6
- Ju. V. Matijasevič, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279–282 (Russian). MR 0258744
- Ju. I. Hmelevskiĭ, Equations in a free semigroup, Trudy Mat. Inst. Steklov. 107 (1971), 286 (Russian). MR 0369575
- 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
- G. S. Makanin, Systems of equations in free groups, Sibirsk. Mat. Ž. 13 (1972), 587–595 (Russian). MR 0318314
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
- © Copyright 1996 American Mathematical Society
- 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