×

zbMATH — the first resource for mathematics

Parametrization of the solutions of the equation \(x_1x_2\cdots x_{n-1}x_n=x_nx_{n-1}\cdots x_2x_1\) in a free monoid. (English. Russian original) Zbl 1230.20055
Math. Notes 89, No. 6, 839-844 (2011); translation from Mat. Zametki 89, No. 6, 879-884 (2011).
Summary: A parametrizing function \(\mathbf{Sm}\) is introduced. The parametrizing function is a recursive function depending on lexicographic variables, natural variables, and variables whose values are finite sequences of natural variables. Using the function \(\mathbf{Sm}\), we construct formulas that provide all the solutions of the equation \(x_1x_2\cdots x_{n-1}x_n=x_nx_{n-1}\cdots x_2x_1\) in a free monoid \(\langle a_1,a_2,\dots,a_\omega\rangle\) and only them.

MSC:
20M05 Free semigroups, generators and relations, word problems
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] G. S. Makanin, ”On the general solution of equations in a free semigroup,” in Lecture Notes in Comput. Sci., Vol. 677: Word Equations and Related Topics, Rouen, 1991 (Springer-Verlag, Berlin, 1993), pp. 1–5. · Zbl 0784.20017
[2] G. S. Makanin, H. Abdulrab, and M. N. Maksimenko, ”Formal parametric equations,” in in Lecture Notes in Comput. Sci., Vol. 965: Fundamentals of Computation Theory, Dresden, 1995 (Springer-Verlag, Berlin, 1995), pp. 353–362.
[3] G. S. Makanin, ”Multiplication of natural number parameters and equations in a free semigroup,” Trans. Amer. Math. Soc. 348(12), 4813–4824 (1996). · Zbl 0862.20043
[4] G. S. Makanin, H. Abdulrab, and P. Goralcik, ”Functions for the general solution of parametric word equations,” in Lecture Notes in Comput. Sci., Vol. 1234: Logical Foundations of Computer Science, Yaroslavl, 1997 (Springer-Verlag, Berlin, 1997), pp. 189–202. · Zbl 0892.20034
[5] G. S. Makanin and T. A. Makanina, ”Functions for parametrization of solutions of an equation in a free monoid,” Trans. Amer. Math. Soc. 352(1), 1–54 (2000). · Zbl 0943.20056
[6] G. S. Makanin and T. A. Makanina, ”A parametrization of the solutions of some equations of squares in a free monoid,” Diskretn. Mat. 11(3), 133–148 (1999) [Discrete Math. Appl. 9 (4), 419–435 (1999)]. · Zbl 0976.20041
[7] G. S. Makanin and T. A. Makanina, ”Parametrization of solutions of parametric equation in a free monoid,” Theoret. Comput. Sci. 242(1–2), 403–475 (2000). · Zbl 0944.68147
[8] G. S. Makanin, ”Parametrization of the solutions of the x -1 y -1 xyz -1 v -1 zv = 1 equation in a free group,” Diskretn. Mat. 13(2), 35–88 (2001) [Discrete Math. Appl. 11 (3), 235–290 (2001)]. · Zbl 1062.20026
[9] G. S. Makanin and A. G. Savushkina, ”An equation in a free group that defines colored braids,” Mat. Zametki 70(4), 591–602 (2001) [Math. Notes 70 (4), 535–544 (2001)]. · Zbl 1033.20036
[10] G. S. Makanin, ”Finite parametrization of solutions of equations in a free monoid. I,” Mat. Sb. 195(2), 41–90 (2004) [Russian Acad. Sci. Sb. Math. 195 (2), 187–235 (2004)]. · Zbl 1073.20049
[11] G. S. Makanin, ”Finite parametrization of solutions of equations in a free monoid,” Mat. Sb. 195(4), 65–96 (2004) [Russian Acad. Sci. Sb. Math. 195 (4), 521–552 (2004)]. · Zbl 1073.20049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.