ОБ УРАВНЕНИЯХ И НЕРАВЕНСТВАХ В СЛОВАХ И ДЛИНАХ
https://doi.org/10.22405/2226-8383-2016-17-2-137-145
Аннотация
Доказывается алгоритмическая неразрешимость проблемы совместности для систем уравнений и неравенств в словах и длинах.
Об авторах
В. Г. Дурнев
Ярославский государственный университет имени П.Г. Демидова
Россия
Россия
доктор физико-математических наук, профессор, заведующий кафедрой компьютерной безопасности и математических методов обработки информации, математический факультет,
150014 Ярославль, ул. С.-Щедрина, дом 59, кв. 18
О. В. Зеткина
Ярославский государственный университет имени П.Г. Демидова
Россия
Россия
кандидат экономических наук, доцент, доцент кафедры мировой экономики и статистики, экономический факультет,
150014 Ярославль, проспект Толбухина, дом 17-а, кв. 59
А. И. Зеткина
Ярославский государственный университет имени П.Г. Демидова
Россия
Россия
магистрант кафедры мировой экономики и статистики, экономический факультет,
150014 Ярославль, проспект Толбухина, дом 17-а, кв. 59
Список литературы
1. Дурнев В. Г. Об уравнениях на свободных полугруппах и группах // Математические заметки. 1974. Т. 16, №5. С. 717 - 724.
2. Косовский Н.К. Некоторые свойства решений уравнений в свободной полугруппе // Записки научных семинаров Ленинградского отделения Математического института АН СССР. Ленинград. 1972. Т. 32. С. 21 - 28.
3. Косовский Н.К. О множествах, представимых в виде решений уравнений в словах и длинах // Вторая всесоюзная конференция по математической логике. Тезисы кратких сообщений. Москва. 1972. С. 23.
4. Косовский Н.К. О решении систем, состоящих одновременно из уравнений в словах и неравенств в длинах слов // Записки научных семинаров Ленинградского отделения Математического института АН СССР. Ленинград. 1973. Т. 33. С. 24 - 29.
5. Маканин Г.С. Проблема разрешимости уравнений в свободной полугруппе // Доклады АН СССР. 1977. Т. 233, №2. С. 287 - 290.
6. Маканин Г.С. Проблема разрешимости уравнений в свободной полугруппе // Математический сборник. 1977. Т. 103(145), №2(6). С. 147 - 236.
7. Матиясевич Ю.В. Диофантовость перечислимых множеств // Доклады АН СССР. 1970. Т. 130, №3. С. 495 - 498.
8. Матиясевич Ю.В. Связь систем уравнений в словах и длинах с 10-ой проблемой Гильберта // Исследования по конструктивной математике и математической логике. Записки научных семинаров Ленинградского отделения Математического института АН СССР. Ленинград. 1968. Т. 8. С. 132-143.
9. Хмелевский Ю.И. Уравнения в свободной полугруппе // Труды Математического института АН СССР. Т. 107. М.: Наука. 1971.
10. Buchi 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. Buchi J. R., Senger S. Coding in the existential theory of concatenation // Arch. Math. Logik. 1986/87. V. 26. P. 101 - 106.
12. J. Karhumaki, 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.
Рецензия
Для цитирования:
Дурнев В.Г., Зеткина О.В., Зеткина А.И. ОБ УРАВНЕНИЯХ И НЕРАВЕНСТВАХ В СЛОВАХ И ДЛИНАХ. Чебышевский сборник. 2016;17(2):137-145. https://doi.org/10.22405/2226-8383-2016-17-2-137-145
For citation:
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
Просмотров:
516
Послать статью по эл. почте 