We study algorithmic problems for equations in free monoids and semigroups (equations in words and lengths) with additional restrictions on the solutions. It is proved that it is impossible to construct an algorithm that solves an arbitrary system of equations in words and lengths in a free monoid (free semigroup) of rank 2 with an additional constraint on the solution in the form that one of its components belongs to the language of balanced words or the equality of the projections of two components of the solution into a distinguished free generator to determine whether it has a solution. A similar result is obtained for systems of inequalities in words.
Download file
Counter downloads: 7
- Title On equations in free monoids and semigroups with restrictions on solutions
- Headline On equations in free monoids and semigroups with restrictions on solutions
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 59
- Date:
- DOI 10.17223/20710410/59/1
Keywords
equations with restrictions on solutions, equations in words and lengths, systems of equations in free monoids and free semigroupsAuthors
References
Матиясевич Ю. В. Диофантовость перечислимых множеств // ДАН СССР. 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.
On equations in free monoids and semigroups with restrictions on solutions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 59. DOI: 10.17223/20710410/59/1
Download full-text version
Counter downloads: 536