ГлавнаяАрхивОб уравнениях в свободных моноидах и полугруппах с ограничениями на решения

Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения | Прикладная дискретная математика. 2023. № 59. DOI: 10.17223/20710410/59/1

Изучаются алгоритмические проблемы для уравнений в свободных моноидах и полугруппах (уравнения в словах и длинах) с дополнителвными ограничениями на решения. Доказывается, что невозможно построитв алгоритм, позволяющий по произволвной системе уравнений в словах и длинах в свободном моноиде (свободной полугруппе) ранга 2 с одним дополнителвным ограничением на решение в форме принадлежности одной его компоненты языкѵ сбалансированных слов или равенства проекций двух компонент решения на одну выделенную свободную образующую определитв, имеет ли она решение. Аналогичный резулвтат установлен для систем неравенств в словах.
  • Title Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения
  • Headline Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 59
  • Date:
  • DOI 10.17223/20710410/59/1
Ключевые слова
уравнения с ограничениями на решения, уравнения в словах и длинах, системы уравнений в свободных моноидах и свободных полугруппах
Авторы
Ссылки
Матиясевич Ю. В. Диофантовость перечислимых множеств // ДАН СССР. 1970. Т. 130. №3. С. 495-498.
Robinson J. Existential definability in arithmetic // Trans. Amer. Math. Soc. 1952. V. 72. P. 437-439.
Diekert V., Gutierrez C., and Hagenah C. The existential theory of equations with rational constraints in free groups is PSPACE-complete // Information and Computation. 2005. V. 202. P. 105-140.
Schulz К. U. Makanin's algorithm for word equations - two improvements and a generalization // LNCS. 1990. V.572. P.85-150.
Diekert V., Gutierrez С., and Hagenah С. The existential theory of equations with rational constraints in free groups is PSPACE-complete // LNCS. 2001. V. 2010. P. 170-182.
Малхасян А. Ш. О разрешимости в подгруппах уравнений в свободной группе j j Прикладная математика. 1986. Вып.2. С. 42-47.
Коуровская тетради. 11-е изд., доп. / ред. В. Д. Мазуров и др. Новосибирск, 1990. 126 с.
Мерзляков Ю. И. Позитивные формулы на свободных группах // Алгебра и логика. 1966. Т. 5. №4. С. 25-42.
Маканин Г. С. Разрешимости универсалвной и позитивной теорий свободной группы // Изв. АН СССР. Сер. матем. 1984. №4. С. 735-749.
Важенин Ю. М., Розенблат Б. В. Разрешимости позитивной теории свободной счетно-порожденной полугруппы // Матем. сб. 1981. Т. 116. № 1. С. 120-127.
Дурнев В. Г. О позитивных формулах на свободных полугруппах j j Сиб. матем. жури. 1974. Т. 25. №5. С. 1131-1137.
Дурнев В. Г. Позитивная теория свободной полугруппы // ДАН СССР. 1973. Т. 211. №4. С.772-774.
Маканин Г. С. Уравнения в свободных группах // Изв. АН СССР. Сер. матем. 1982. Т. 46. №6. С. 1199-1274.
Маканин Г. С. Проблема разрешимости уравнений в свободной полугруппе // Матем. сб. 1977. Т. 103 (145). №2 (6). С. 147-236.
Buchi J. R. and Senger S. Definability in the existential theory of concatenation // Z. Math. Log. und Grundl. Math. 1988. V. 31. Xo. 4. P. 337-342.
Маканин Г.С. Проблема разрешимости уравнений в свободной полугруппе // ДАН СССР. 1977. Т. 233. №2. С. 287-290.
Дурнев В. Г. Об уравнениях на свободных полугруппах и группах // Матем. заметки. 1974. Т.16. №5. С. 717-724.
Косовский Н. К. О решении систем, состоящих одновременно из уравнений в словах и неравенств в длинах слов // Записки науч. семинаров Ленингр. отд. Матем. ин-та им. В. А. Стеклова АН СССР. 1973. Т.ЗЗ. С. 24-29.
Косовский Н. К. О множествах, представимых в виде решений уравнений в словах и длинах // Вторая Всесоюз. конф. по матем. логике. Тезисы кратких сообщений. М., 1972. С. 23.
Матнясевнч Ю. В. Связи систем уравнений в словах и длинах с 10-й проблемой Гилвберта // Исследования по конструктивной математике и математической логике. Записки науч. семинаров Ленингр. отд. Матем. ин-та им. В. А. Стеклова АН СССР. 1968. Т. 8. С.132 1 IЗ.
Хмелевский Ю.И. Уравнения в свободной полугруппе. М.: Наука, 1971. 218 с.
Дурнев В. Г. Неразрешимости позитивной ѴЕI3-теории свободной полугруппвi // Сиб. матем. жури. 1995. Т. 36. №5. С. 1067-1080.
Косовский Н. К. Некоторвiе свойства решений уравнений в свободной полугруппе // Записки науч. семинаров Ленингр. отд. Матем. ин-та им. В. А. Стеклова АН СССР. 1972. Т. 32. С. 21-28.
Перязев Н. А. Позитивные теории свободнвiх моноидов // Алгебра и логика. 1993. Т. 32. №2. С. 148-159.
Дурнев В. Г., Зеткина А. И. Алгоритмические проблемы для уравнений в свободных группах и полугруппах с ограничениями на решения // Всерос. науч. конф. "Математические основвi информатики и информационно-коммуникационнвiх систем". Тверв, 3-8 декабря 2021г. Тверв: ТвГУ, 2021. С. 25-41.
Дурнев В. Г., Зеткина А. И. Об уравнениях в свободных моноидах с ограничениями на решения // Актуальные проблемы прикладной математики, информатики и механики: сб. трудов Междунар. науч. конф. Воронеж, 13-15 декабря 2021г. Воронеж: Изд-во "Научно-исследовательские публикации", 2022. С. 1571-1575.
Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения | Прикладная дискретная математика. 2023. № 59. DOI: 10.17223/20710410/59/1
Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения | Прикладная дискретная математика. 2023. № 59. DOI: 10.17223/20710410/59/1