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)

 
 

 

Functions for parametrization of solutions
of an equation in a free monoid


Authors: Gennady S. Makanin and Tatiana A. Makanina
Journal: Trans. Amer. Math. Soc. 352 (2000), 1-54
MSC (1991): Primary 20M05; Secondary 03D40, 20F10
DOI: https://doi.org/10.1090/S0002-9947-99-02287-4
Published electronically: March 29, 1999
MathSciNet review: 1491869
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we introduce recursive functions

\begin{align*}&{}^{\mathbf{Fi}}(x_1,x_2)^{\lambda _1,\dotsc,\lambda _s}\qquad(s\ge 0),\\ &{}^{\mathbf{Th}}(x_1,x_2,x_3)_i^{\lambda _1,\dotsc,\lambda _{2s}} \qquad(i=1,2,3;s\ge 0),\\ &{}^{\mathbf{Ro}}(x_1,x_2,x_3)_i^{\mu _1,\dotsc,\mu _s}\qquad(i=1,2,3;s\ge 0) \end{align*}

of the word variables $x_1,x_2,x_3$, natural number variables $\lambda _k$ and variables $\mu _k$ whose values are finite sequences of natural number variables. By means of these functions we give finite expressions for the family of solutions of the equation

\begin{displaymath}x_1x_2x_3x_4=\zeta(x_1,x_2,x_3)x_5,\end{displaymath}

where $\zeta(x_1,x_2,x_3)$ is an arbitrary word in the alphabet $x_1,x_2,x_3$, in a free monoid.


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. I. Khmelevski[??]i, Solution of word equations in three unknowns, Dokl. Akad. Nauk SSSR 177 (1967), 1023-1025; English transl., Soviet Math. Dokl. 8 (1967), 1554-1556. MR 36:3899
  • 4. -, Equation in free semigroups, Trudy Mat. Inst. Steklov. 107 (1971); English transl., Proc. Steklov Inst. Math. 107 (1971) (1976). MR 51:5808; MR 52:14094
  • 5. G. S. Makanin and P. Goralcik, Structure of the solutions of one parametric equation, Report of research, LIR, INSA of Rouen, April 1996.
  • 6. G. S. Makanin and H. Abdulrab, Functions for the general solution of parametric word equations, Report of research, LIR, INSA of Rouen, June 1996.
  • 7. G. S. Makanin, Systems of standard equations in words of an $n$-layer alphabet with unknowns, Sibirsk. Mat. Zh. 19 (1978), 637-645; English transl., Siberian Math. J. 19 (1978), 448-454. MR 80a:20039
  • 8. -, Recognition of the rank of equations in a free semigroup, Izv. Akad. Nauk SSSR Ser. Mat. 43 (1979), 547-602; English transl., Math. USSR Izv. 14 (1980), 499-545. MR 80h:20084
  • 9. M. Lothaire, Combinatorics on words, Addison-Wesley, 1983. MR 84g:05002

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

Tatiana A. Makanina
Affiliation: Steklov Mathematical Institute, Vavilova 42, 117 966, Moscow GSP-1, Russia

DOI: https://doi.org/10.1090/S0002-9947-99-02287-4
Received by editor(s): April 14, 1997
Published electronically: March 29, 1999
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society