ON EQUATIONS AND INEQUALITIES IN WORDS AND WORD LENGTHS
https://doi.org/10.22405/2226-8383-2016-17-2-137-145
Abstract
We prove the algorithmic undecidability of a compatibility problem for some systems of equations and inequalities in words and word lengths.
About the Authors
V. G. Durnev
P. G. Demidov Yaroslavl University
Russian Federation
Russian Federation
Dr.Sci. (Phys&Math), Professor, Chief of Department of Computer security & Mathematical methods in IT, Mathematical Faculty,
150008 Yaroslavl, Soyuznaya Str., 144
O. V. Zetkina
P. G. Demidov Yaroslavl University
Russian Federation
Russian Federation
Cand.Sci. (Economics), dozent, Department of World Economics and Statistics, Economic Faculty,
150008 Yaroslavl, Komsomolskaya Str., 3
A. I. Zetkina
P. G. Demidov Yaroslavl University
Russian Federation
Russian Federation
MS student, Department of World Economics and Statistics, Economic Faculty,
150008 Yaroslavl, Komsomolskaya Str., 3
References
1. Durnev V. G. / On equations in free semigroups and groups // Mat. Zametki. V. 16, no. 5. P. 717 – 724 (in Russian).
2. Kosovski˘i N. K. / Certain properties of the solutions of equations in a free semigroup. Investigations in constructive mathematics and mathematical logic, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI). 1972. Vol. 32. P. 21Џ-28, 154. (in Russian).
3. Kosovski˘i N. K. / On sets represented as solutions of equations in words and lengths // 2nd USSR Conference on mathematical logics. Moscow. 1972. Book of abstracts, P. 23 (in Russian).
4. Kosovski˘i N. K. / The solution of systems that consist simultaneously of word equations and word length inequalities // Investigations in constructive mathematics and mathematical logic, VI (dedicated to A. A. Markov on the occasion of his 70th birthday). Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI). 1974. Vol. 40. P. 24–29, 156 (in Russian).
5. Makanin G. S. / The problem of the solvability of equations in a free semigroup. // Dokl. Akad. Nauk SSSR. 1977. Vol. 233, no. 2. P. 287 – 290 (in Russian) [Translated in: Soviet Math. Dokl,. 18:2 (1977), 330–334 ].
6. Makanin G. S. / The problem of solvability of equations in a free semigroup // Math. Sbornik. 1977. V. 103(145), no. 2(6). P. 147-236 (in Russian) [Translated in: Math. USSR Sb. 1977. Vol. 32. No. 2, P. 129–198, doi:10.1070/SM1977v032n02ABEH002376]
7. Matiyasevich Yu. V. / Diophanticity of enumerable sets // Dokl. AN SSSR 1970, Vol. 191(2), P. 278–282 [Translated in: Soviet Math. Doklady 1970, Vol. 11(2), P. 354–358]
8. Matiyasevich Yu. V. The connection between systems of equations in words and lengths with Hilbert’s 10th problem // Studies on constructive mathematics and mathematical logics. Zap. Nauˇchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI). Vol. 8. 1968. P. 132 – 143 (in Russian).
9. Hmelevski˘ı Ju. I. / Equations in a free semigroup. (Russian) Trudy Mat. Inst. Steklov. 107 (1971), 286 pp. [Translated in: Proceedings of the Steklov Institute of Mathematics, 1971, Vol. 107, P. 1–270]
10. B¨uchi J. R., Senger S. / Definability in the existential theory of concatenation // Z. math. Log. und Grundl. Math. 1988. V. 34, №4. P. 337–342
11. B¨uchi J. R., Senger S. / Coding in the existential theory of concatenation // Arch. Math. Logik. 1986/87. V. 26. P. 101–106
12. J. Karhum¨aki, F. Mignosi, W. Plandowski / On the expressibility of languages by word equations with a bounded number of variables // Bull. Belg. Math. Soc. Simon Stevin. 2001. V. 8, №2. P. 293–305.
Review
For citations:
Durnev V.G., Zetkina O.V., Zetkina A.I. ON EQUATIONS AND INEQUALITIES IN WORDS AND WORD LENGTHS. Chebyshevskii Sbornik. 2016;17(2):137-145. (In Russ.) https://doi.org/10.22405/2226-8383-2016-17-2-137-145
Views:
517
Email this article 