×

The non-parametrizability of the word equation \(xyz=zvx\): a short proof. (English) Zbl 1079.68081

Summary: Although Makanin proved the problem of satisfiability of word equations to be decidable, the general structure of solutions is difficult to describe. In particular, Hmelevskii proved that the set of solutions of \(xyz=zvx\) cannot be described using only finitely many parameters, contrary to the case of equations in three unknowns. In this paper we give a short, elementary proof of Hmelevskii’s result.

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Appel, K. I., One variable equations in free groups, Proc. Amer. Math. Soc., 19, 912-918 (1968) · Zbl 0159.30502
[2] Choffrut, C., Equations in words, (Lothaire, M., Combinatorics on Words, Chap. 9, Encyclopedia of Mathematics and its Applications, Vol. 17 (1983), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0656.68083
[3] Choffrut, C.; Karhumäki, J., Combinatorics on words, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vol. 1 (1997), Springer: Springer Berlin), 329-438
[4] L.P. Comerford, C.C. Edmunds, Solutions of equations in free groups, Group Theory (Singapore, 1987), Walter de Gruyter, Berlin, 1989, pp. 347-356.; L.P. Comerford, C.C. Edmunds, Solutions of equations in free groups, Group Theory (Singapore, 1987), Walter de Gruyter, Berlin, 1989, pp. 347-356.
[5] J. Karhumäki, E. Petre, On some special equations on words, in: Dixiemes Journees Montoises d’Informatique Theorique, 2004.; J. Karhumäki, E. Petre, On some special equations on words, in: Dixiemes Journees Montoises d’Informatique Theorique, 2004.
[6] Diekert, V., Makanin’s algorithm, (Lothaire, M., Algebraic Combinatorics on Words, Chap. 12, Encyclopedia of Mathematics and its Applications, Vol. 90 (2002), Cambridge University Press: Cambridge University Press Cambridge)
[7] Grigorchuk, R. I.; Kurchanov, P. F., On quadratic equations in free groups, Contemp. Math., 131, 159-171 (1992) · Zbl 0778.20013
[8] J.I. Hmelevskii, Equations in free semigroups, Translated by G.A. Kandall from the Russian original, Trudy Mat. Inst. Steklov. 107, 1971, 1-270, American Mathematical Society, Providence, RI, 1976.; J.I. Hmelevskii, Equations in free semigroups, Translated by G.A. Kandall from the Russian original, Trudy Mat. Inst. Steklov. 107, 1971, 1-270, American Mathematical Society, Providence, RI, 1976.
[9] Karhumäki, J., On cube-free \(\omega \)-words generated by binary morphisms, Discrete Appl. Math., 5, 279-297 (1983) · Zbl 0505.03022
[10] Lentin, A.; Schützenberger, M. P., A combinatorial problem in the theory of free monoids, (Bose, R. C.; Bowlings, T. E., Combinatorial Mathematics (1967)), 112-144 · Zbl 0221.20076
[11] Lorenc, A. A., The solution of systems of equations in one unknown in free groups, Soviet Math. Dokl., 4, 262-266 (1963)
[12] Lorenc, A. A., On the representation of solution sets of systems of equations with one unknown in a free group, Soviet Math. Dokl., 9 (1968)
[13] Lothaire, M., Combinatorics on words, Encyclopedia of Mathematics and its Applications 17 (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[14] Lyndon, R. C., Equations in free groups, Trans. Amer. Math. Soc., 96, 445-457 (1960) · Zbl 0108.02301
[15] Makanin, G. S., The problem of solvability of equations in a free semigroup, Math. USSR-Sb., 32, 129-198 (1977) · Zbl 0396.20037
[16] Makanin, G. S., Equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat., 46, 1199-1273 (1982), (in Russian), English translation in: Math. USSR-Izv. 21 (1983) 483-546 · Zbl 0511.20019
[17] Makanin, G. S., Decidability of the universal and positive theories of a free group, Izv. Akad. Nauk SSSR Ser. Mat., 48, 735-749 (1984), (in Russian), English translation in: Math. USSR-Izv. 25 (1985) 75-88.
[18] Markov, A. A., The theory of algorithms, Trudy Mat. Inst. Steklov, 42 (1954) · Zbl 0056.24901
[19] Mignosi, F.; Pirillo, G., Repetitions in the Fibonacci infinite word, RAIRO Inform. Theor. Appl., 26, 199-204 (1992) · Zbl 0761.68078
[20] Petre, E., An elementary proof for the non-parametrizability of the equation \(xyz = zvx\), (Fiala, J.; Koubek, V.; Kratochvíl, J., Proc. MFCS 2004, Lecture Notes in Computer Science, Vol. 3153 (2004), Springer: Springer Berlin), 807-817 · Zbl 1097.68112
[21] Plandowski, W., Satisfiability of word equations with constants is in NEXPTIME, (Annu. ACM Symposium on Theory of Computing (1999), Association of Computing Machinery: Association of Computing Machinery New York), 721-725 · Zbl 1346.68113
[22] Plandowski, W., Satisfiability of word equations with constants is in PSPACE, (40th Annu. Symposium on Foundations of Computer Science (1999), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA), 495-500, (Final version in Journal of the Association Computing Machinery 51 (2004) 483-496) · Zbl 1192.68372
[23] Razborov, A. A., On systems of equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat., 48, 779-832 (1984), (in Russian), English translation in: Math. USSR-Izv. 25 (1985) 115-162
[24] Razborov, A. A., On the Parameterization of Solutions for Equations in Free Groups, Internat. J. Algebra Comput., 3, 251-273 (1993) · Zbl 0793.20028
[25] Weinbaum, C. M., Word equation \(ABC = CDA, B \neq D\), Pacific J. Math., 1, 213, 157-162 (2004) · Zbl 1047.20045
[26] A. Lentin, Équations dans les monoı¨des libres, Mathmatiques et Sciences de l’Homme, vol. 16, Gauthier-Villars, Paris, 1972.; A. Lentin, Équations dans les monoı¨des libres, Mathmatiques et Sciences de l’Homme, vol. 16, Gauthier-Villars, Paris, 1972. · Zbl 0258.20058
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.