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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ЧЕБЫШЕВСКИЙ СБОРНИК Том 11 Выпуск 3 (2010)
УДК 510. 53+512. 53+512. 54
ОБ УРАВНЕНИЯХ С ПОДПОЛУГРУППОВЫМН ОГРАНИЧЕНИЯМИ НА РЕШЕНИЯ В СВОБОДНЫХ ПОЛУГРУППАХ 1
В. Г. Дурнев, О. В. Зеткина (г. Ярославль)
Аннотация
В статье доказывается алгоритмическая неразрешимость проблемы совместности для уравнений с некоторыми ограничениями на решения в свободной полугруппе. Библиография: 24 названия.
Обозначим через Пп свободную полугруппу с пустым словом в качестве нейтрального элемента (свободный моноид) ранга п со свободными образующими й1, …, ап, а черезп — свободную группу с темп же свободными образующими. Вместо а1 и а2 будем писать, а и Ь соответственно.
В 60-ые годы прошлого века А. А. Марков предложил использовать системы уравнений в свободной полугруппе Пп в качестве подхода к отрицательному решению 10-ой проблемы Д. Гильберта. Заметим, что при п ^ 2 система уравнений
т
& amp- = иг
г=1
равносильна одному уравнению
ш1а1ш2а1… а1шт ш1а2ш2а2 … а2шт = и1а1и2а1… а1ит и1а2и2а2 … а2ит.
Системы уравнений в свободных полугруппах также называются системами уравнений в словах. Первые результаты в исследовании систем уравнений в словах были получены А. А. Марковым и 10. 11. Хмелевским [18] в конце 60-ых годов.
В эти же годы было начато изучение систем уравнений в словах и длинах, т. е. систем вида,
т
& amp- = иг & amp- & amp- хг = Хп|,
г=1 {г, Я& amp- А
где через х = |у| обозначен предикат & quot- длины слов х и у равны & quot-.
Первые результаты в исследовании систем уравнений в словах и длинах были получены в начале 70-ых годов в работах Ю. В. Матнясевпча [15] и Н. К. Косовского [6], [7], [8].
1 Работа выполнена при финансовой поддержке гранта Президента Р Ф для ведущих научных школ (НШ-845. 2008. 1).
В 1972−73 годах первый из авторов стал рассматривать системы уравнений в словах и длинах с дополнительным предикатом ха = уа-п проекции слов х у а
году, он, в частности, доказал, что
можно указать такое однопараметрическое семейство систем, уравнений в свободной полугруппе П2,
ш (х, х1, …, хп, а, Ь) = V (х, х1, …, хп, а, Ь) & amp-
& amp- (хг = х^ & amp- хга = х^а)
{., Ле А
с неизвестными, х^ …, хп, с константами, а и Ь и с параметром х, где А
— некоторое подмножество множества М (п) = {{?, з} 1 ^ ^ п}, что
невозможен алгоритм, позволяющий для произвольного натурального числа т определить, имеет ли, решение си, стем, а, уравнений
ш (ат, х1, …, хп, а, Ь) = V (ат, х1, …, хп, а, Ь) & amp-
& amp- (х. = х^ & amp- х. а = х^а).
{",]}? А
В этой же работе отмечалось, что аналогичный результат остается верным, если предикат х = у& amp- ха = уа заменить предикатом хь = уь& amp- ха = уа.
Аналогичный результат содержался в опубликованной в 1988 году работе Л.Е. ВисЫ и Б. Беп§ ег [22].
В 1976 году Г. С. Маканин получил в теории уравнений в словах фундаментальный результат, который был опубликован в 1977 году в работах [10] и [11],
— он построил алгоритм, позволяющий по произвольной системе уравнеий в свободной полугруппе Пп определить, имеет ли она решение. Несколько позже в работе [12] Г. С. Маканин построил алгоритм, позволяющий по произвольной системе уравнеий в свободной группе Еп определить, имеет ли она решение.
После фундаментальных результатов Г. С. Маканина особый интерес стал представлять вопрос о существовании аналогичных алгоритмов для уравнеий в свободных полугруппах и группах с различными & quot-не слишком сложными & quot-и & quot-достаточно еетеетвенными& quot-ограничениями на решения.
В работе [2] была доказана алгоритмическая неразрешимость позитивной ЗУ33-теорпн любой конечно порожденной нециклической свободной полугруппы. Вопрос о разрешимости позитивной теории свободной полугруппы счетного ранга им был сведен к следующей проблеме существует ли алгоритм, позволяющий для, произвольного уравнения
Ш (х1 ,.. , хп, а1'-}…) ат) и (х1, …, хп, а1).. , ат)
в свободной полугруппе счетного ранга определить, имеет ли, оно такое решение дъ …, дп, что
91? Пт1, д2? п т2, …, 9 ^ п ть ,
где т1 ^ т2 ^ … ^ ти Пт. — свободная полугруппа с образующими аъ … ,
ат1. Ю. М. Важенин и Б, В, Розенблат [1] используя результат Г. С. Маканина доказали, что для решения последней задачи алгоритм существует, это позволило им установить разрешимость позитивной теории свободной полугруппы счетного ранга.
Вопрос о разрешимости позитивной теории свободной группы был сведен Ю. И, Мерзляковым [17] к следующей проблеме
существует ли алгоритм, позволяющий для, произвольного уравнения
Ш (xl}.. , хп, а1, …, ат) 1
в свободной группе счетного ранга определить, имеет ли оно такое решение дъ …, дп, что
д1?П1, д2?, …, дЬ? Р'-ть ,
где т1 ^ т2 ^ … ^ т^ - свободная, группа с образующими а^ …, ат1.
Г. С, Маканнным [10] построил искомый алгоритм, и тем самым доказал разрешимость позитивной теории свободной группы.
Обобщая эти ситуации Г. С, Маканин поставил в & quot-Коуровской тетради& quot- [9] следующую проблему для уравнений в свободных группах: —
I!
9. 25. Указать алгоритм, который по уравнению
Ш (xl} …, хт, а1, …, ап) 1
в свободной группе Еп и списку конечно порожденных подгрупп Н1-…, Нт группы, Еп позволял, бы, узнать, существует ли решение этого уравнения с условием,
х1? Н1,.. , хт? Нт.
I!
Первые положительные результаты в направлении решения этой проблемы получил А. Ш. Малхасян [14].
К. Шульц [24] рассмотрел аналогичную проблему для уравнений в свободных полугруппах с регулярными ограничениями на решения и доказал, что существует алгоритм, который по уравнению
Ш (х1 ,.. , xm} а1,.. , ап) и (х1 ,.. , xm} а1,.. , ап)
в свободной полугруппе Пп и списку регулярных подмножеств (языков) Н1,…, Нт Пп
ния, с условием
х1? Н1, …, хт? Нт.
Так как каждая конечно порожденная подполугруппа свободной полугруппы
Пп
проблема для уравнений е ограничениями на решения в свободных полугруппах является естественным аналогом проблемы Г. С. Маканина,
V. Б1екей [19], [20], [21] построил алгоритм, позволяющий по произвольному уравнению
т (х1}. .) хт) а1) …) ап) 1
в свободной группе Еп и списку регулярных подмножеств (языков) Н1-…, Нт группы Еп узнать, существует ли решение этого уравнения с условием
х1 е Н1, …, хт е Нт.
Так как конечно порожденные подгруппы являются регулярными подмножествами, то тем самым решена и проблема Г. С. Маканина.
Сказанное дает основания считать, что представляет интерес дальнейшее исследование различных обобщений проблемы Г. С. Маканина для свободных групп и полугрупп, получающихся путем ослабления ограничений, налагаемых на подгруппы (подполугруппы, языки) Н^, Нп.
В силу теоремы К. Шульца для получения алгоритмически неразрешимых проблем для уравнеий в свободных полугруппах с подполугрупповыми ограничениями на решения необходимо рассматривать, в первую очередь, бесконечно порожденные свободные подполугруппы, среди которых имеются как нерегулярные, так и регулярные языки, например, подполугруппа, порожденная всевозможными словами вида, аЬпа (и = 1, 2,…) свободно ими порождаетя и является регулярным языком.
В литературе по формальным языкам и грамматикам достаточно часто встречается следующий рекурсивный язык в алфавите {а, Ь} - Ь1, который задается следующим, весьма простым способом. Для слова т в алфавите Е и буквы, а этого алфавита через 1т1а будем обозначать число вхождений буквы, а в слово т. В этих обозначениях Ь1 состоит го всех слов т в алфавите {а, Ь}, для которых 1т1а = 1т1ъ-, а Ь2 — из всех слов т в том же алфавите, для которых 1т1ь = 2|ш|а. Ясно, что пересечение этих двух языков состоит лишь из пустого слова. Пользуясь известным критерием свободности для подполугрупп свободной полугруппы, легко доказать, что Ь1 и Ь2 — свободные подполугруппы счетного ранга. Конечно, рекурсивные языки Ь1 и Ь2 не являются регулярными, однако с точки зрения сложности разрешимости для них алгоритмических проблем они скорее & quot-ближе"-к регулярным языкам, чем к произвольным рекурсивным.
Поэтому представляют интерес, на наш взгляд, следующие две теоремы.
Теорема 1. Можно указать такое однопараметрическое семейство урав-
П2
т (х, х1, …, хп, а, Ь) = V (х, х1, …, хп, а, Ь) & amp-
р
& amp- (хг е 1/1) & amp- |х1 | = 1×21
г=3
с неизвестными х^ …, хп, с константами, а и Ь и с параметром х, что невозможен алгоритм, позволяющий для, произвольного натурального числа т определить, имеет ли, решение уравнение с ограничениями на решения
т (ат, х1, …, хп, а, Ь) = V (ат, х1, …, хп, а, Ь) & amp-
р
& amp- (хг е Ь1) & amp- |х1 | = 1×21.
г=3
Теорема 2. Можно указать такое однопараметрическое семейство уравнений с ограничениями на решения в свободной полугруппе П2
т (х, х1, …, хп, а, Ь) = V (х, х1, …, хп, а, Ь) & amp-
р
& amp- (хг е ^1) & amp- х1 е Е2
г=2
с неизвестными, х1} …, хп, с констант ами, а и Ь и с параметром, х, что невозможен алгоритм, позволяющий для, произвольного натурального числа т
т (ат, х1, …, хп, а, Ь) = V (ат, х1, …, хп, а, Ь) & amp-
р
& amp- (хг е ^1) & amp- х1 е Е2.
г=2
Доказательство. Прежде всего покажем, что в позитивной 3-теории полугруппы П2 с использованием только предиката х е Ь1 выразим ряд вспомогательных предикатов.
Пусть, а — это буква «и Ь.
N (х) ^ (ха = ах).
Если X — элемент полугруппы П2, то формула Ма, (X) истинна на, полугруппе П2 тогда и только тогда, когда, X — степень буквы а.
Рассмотрим предикат Я (х, у) истинный тогда и только тогда, когда найдется такое неотрицательное число Ь, что х = а ну = Ьь.
Справедлива эквивалентность
Я (х, у) (ха = ах & amp- уЬ = Ьу) & amp-
(3 г)(г = ху & amp- г е Ь1),
Введем необходимый для дальнейшего предикат делимости 0(х, у), истинный, тогда, и только тогда, когда, найдутся такие неотрицательные целые числа $ и Ь, что х = ая, у = а* и $ делит Ь.
Справедлива эквивалентность
Б (х, у) ((ха = ах & amp- уа = ау)& amp-
((3v)(3u)(3w)(u (xaЬ) = (хаЬ)и & amp- Я (у^)& amp- т = ш & amp- т е Ь1))).
Введем основной для дальнейшего предикат М (х, у, г) истинный тогда и только тогда, когда, найдутся такие натуральные числа в, Ь и г, что х = а3, у = а*, г = аг и вЬ = г.
Имеют место эквивалентности:
М (х, у, г)
(3 V)(3 и)(3 ш)(3 р)(3 д)(и (Ьх) = (Ьх)и & amp- Я (у^)& amp-р = vz & amp-
Я (г, т)& amp- д = иут & amp- д е Ь1 & amp-
|и| =
М (х, у, г) ^
(3 V)(3 и)(3 ш)(3р)(3 д)(3 /)(3 д) (Я (х, V) & amp- Я (у, т) & amp- Я (г, д) & amp- u (av) = (ау)и & amp- / = итг & amp-
& amp- г = ру & amp- д = идр & amp- / е Ь1 & amp-
д е Ь2)).
Покажем, что для произвольных натуральных чисел $ Ь и г имеет место эквивалентность:
П2 = 5 (а3, а1, аг) вЬ = г.
Рассмотрим лишь второй случай.
Если формула Б (а3, а*, аг) истинна та полугруппе П2, то возьмем такие и, V, Р, Q, Г и С, чтобы па полугруппе П2 была истинна формула
(Т (а3, V) & amp- Т (а*, Ш) & amp- Т (аг, Q) & amp-
и^) = ^)и & amp- Г = UWZ & amp-
& amp- Z = РУ & amp- С = UQP & amp- Г е Ь1 & amp- С е Ь2)).
Тогда при некотором к выполняются равенства V = Ь3, и = (аЬ3)к, Ш = Ь*, Р = аг-*, Q = Ьг, Г = (аЬ3)кЬ*аг и С = (аЬ3)кЬгаг-*.
Из условий Г е ^ и С е Ь2 получаем равенства вк + Ь = к + г и вк + 2Ь = 2к + г, го которых получаем Ь = к и г = вк = вЬ.
Для доказательства обратного утверждения достаточно взять V = Ь3, и = (аЬ3) Ш = Ь Р = аг-*, Q = Ьг, Г = (аЬ3)*Ь*аг и С = (аЬ3)*Ьгаг-*.
Воспользуемся следующим вариантом непосредственного следствия фундаментальной теоремы Ю. В. Матиясевича [15] о диофантовоети рекурсивно перечислимых множеств: для, произвольного рекурсивно перечислимого множества, А натуральных чисел можно построить такую формулу ФА (х1) вида
3
(3×2) … (3 хт) Ф, где Ф = & amp- 1? г
г=1
и каждая формула имеет один из следующих видов:
XI + хз = хг, хз = XI, XI хз = хг, хз = с,
где с — натуральное число, что для, произвольного натурального числа п имеем: п € А тогда, и только тогда, когда, формула Фа (п) истинна на, множестве натуральных чисел.
Воспользовавшись хорошо известной эквивалентностью
ху = г (х + у)2 = х2 + 2 г + у2,
можно считать, что в формулу Фа (х1) подформулы вила, хг хз = хг входят лишь при I = т. е. они имеют вил х2 = хг.
Воспользуемся следующим утверждением, принадлежащим Дж, Робинсон, если, т ^ п и Ь & gt- п2, то (Ь + т) | Ь2 — п тогда, и только тогда, п = т2. Условие Ь & gt- п2 можно заменить следующим условием
(п + 1) | Ь & amp- (п + 2) | Ь.
Это позволяет в формуле Фа (х1) заменить подформулу
р
& amp- х2. = хг.
г=1 г г
на подформулу
р
и = У2 & amp- 2 = ^ хг, & amp- (2 + 1) | У & amp- (2 + 2) | У & amp-
г=1
рр
& amp- хк = хг, + иг & amp- & amp- (У + хк) | (и — хи).
г=1 г=1
Поэтому можно считать, что в формуле Фа (х1) лишь одна подформула, имеет вид х2 = хг, а, все остальные подформулы имеют один, из следующих видов:
/V» I /V" , — /V" /V" , — /у' 7 /V" /V", /V" , — Г
1 з г) з 1) / | з) з ^
с
По формуле Фа (х1) построим формулу Ф^ (х1) следующим образом: фА (х1) ^ (з х2)… (3 хт) (Ф1 & amp- (& amp- N (хг))),
г=2
где Ф1 получается из Ф заменой каждой подфо рмулы & lt-^г гад, а хг + хз = хк на хг хз = хк, гада хг | х^ - на Б (хг, х^), гада хз = хк — на хз = хк, вида хз = с — на хз = П и вида, х2 = хк — на М (хг, хг, хк). Напомним, что подформула последнего вила, лишь одна и только в нее, причем лишь один раз входит предикат |х| = |у| или предикат х € Ь2.
Подходящим образом переименовав переменные в формуле фА (х1), можем считать, что в формулу Ф^ (х) входят лишь переменные х, х1, …, хп.
Удалим из формулы фА^ (х) конъюнкцию & amp-, приведем полученную формулу к виду
Ш (х, х1,…, хп, п, Ь) = V (х, х1,…, хп, п, Ь) & amp-
& amp- | & amp-
{г, з}& amp- А
ИЛИ ВИДУ
Ш (х, х1,…, хп, п, Ь) = V (х, х1,…, хп, п, Ь) & amp-
& amp- | & amp- х1 € Ь1.
{г, з}& amp- А
Полученную формулу обозначим через ФА (х).
Тогда: к € А тогда и только тогда, когда формула фА (пк) истинна на полугруппе П2,
А
курсивно перечислимое, но нерекурсивное множество. ?
Выражаем глубокую благодарность анонимному рецензенту нашей заметки, представленной на ('-ЯН-07. указавшему на возможность замены нескольких возведений в квадрат одним таким возведением с использованием предиката делимости.
Выражаем глубокую благодарность Сергею Ивановичу Адяну за внимание к работе и поддержку, благодарим всех участников его семинара за заинтересованное обсуждение.
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
[1] Важенин Ю. М., Розенблат Б. В. Разрешимость позитивной теории свободной счетнопорожденной полугруппы // Матем. сборник. 1981. Т. 116. № 1. С. 120 — 127.
[2] Дурнев В. Г. Позитивная теория свободной полугруппы// Докл. АН СССР. 1973. Т. 211. № 4. С. 772 — 774.
[3] Дурнев В. Г. Об уравнениях на свободных полугруппах и группах// Матем. заметки. 1974. Т. 16. № 5. С. 717 — 724.
[4] Дурнев В. Г. О позитивных формулах на свободных полугруппах// Сиб, матем. журн. 1974. Т. 25. № 5. С. 1131 — 1137.
[5] Дурнев В. Г. Неразрешимость позитивной У33-теории свободной полугруппы// Сиб. матем. журн. 1995. Т. 36. № 5. С. 1067 — 1080.
[6] Косовский Н, К, Некоторые свойства решений уравнений в свободной полугруппе // Записки научи, семинаров Ленингр. отд. Матем, ин-та. АН СССР. Л. 1972. Т. 32. С. 21 — 28.
[7] Косовский Н. К. О множествах, представимых в виде решений уравнений в словах и длинах // Вторая всесоюзная конфер. по матем. логике. Тезися кратких сообщений. М. 1972. С. 23.
[8] Косовский Н. К. О решении систем, состоящих одновременно из уравнений в словах и неравенств в длинах слов// Записки научи, семинаров Ленингр. отд. Матем. ин-та. АН СССР. Л. 1973. Т. 33. С. 24 — 29.
[9] Коуровекая тетрадь. 11-е изд., доп. Новосибирск. 1990.
[10] Маканин Г. С. Проблема разрешимости уравнений в свободной полугруппе// ДАН СССР. 1977. Т. 233. № 2. С. 287 — 290.
[11] Маканин Г. С. Проблема разрешимости уравнений в свободной полугруппе// Матем. сбор. 1977. Т. 103 (145). № 2 (6). С. 147 — 236.
[12] Маканин Г. С. Уравнения в свободных группах// Изв, АН СССР. Сер. матем. 1982. Т. 46. № 6. С. 1199 — 1274.
[13] Маканин Г. С. Разрешимость универсальной и позитивной теорий свободной группы // Изв. АН СССР. Серия матем. 1984. № 4. С. 735 — 749.
[14] Малхасян А. Ш. О разрешимости в подгруппах уравнений в свободной группе // Сб. Прикладная математика. 1986. Вып. 2. С. 42 — 47.
[15] Матиясевич Ю. В. Диофантовоеть перечислимых множеств // ДАН СССР. 1970. Т. 130. № 3. С. 495 — 498.
[16] Матиясевич Ю. В. Связь систем уравнений в словах и длинах с 10-ой проблемой Гильберта / / Исследования по конструктивной математике и математической логике. Записки научи, семинаров Ленингр. отд. Матем. ин-та. АН СССР. Л. 1968. Т. 8. С. 132 — 143.
[17] Мерзляков K).I I. Позитивные формулы на свободных группах // Алгебра и логика. 1966. Т. 5. № 4. С. 25 — 42.
[18] Хмелевский Ю. П. Уравнения в свободной полугруппе. М.: Наука. 1971. (Тр. МИАН.) Т. 107).
[19] Diekert V. Makanin’s Algorithm for Solving Word Equations with Regular Constraints. (Preliminitarv version of the chapter in M. Lothaire, Algebraic Combinatorics on Words) Report Nr. 1998/02. Fakultat Informatik. Universitat Sttutgart. 1998.
[20] Diekert V., Gutierrez С., Hagenah С. The existential theory of equations with rational constraints in free groups is PSPACE-complete. In A. Ferreira and H Reiehel, editors, Proc. 18-th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01), Dresden (Germany), 2001, number 2010 in Leture Notes in Computer Science, pages 170 — 182. Springer-Verlag, 2001.
[21] Diekert V., Gutierrez C, Hagenah C. The existential theory of equations with rational constraints in free groups is PSPACE-complete // Informatiion and Computation. V. 202. 2005. P. 105 — 140.
[22] 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.
[23] Buchi J. R, Senger S. Coding in the existential theory of concatenation // Arch. Math. Logik. 1986/87. Bd. 26. P. 101 — 106.
[24] Schulz K.U. Makanin’s Algprithm for Word Equations — Two Improvements and a Generalization // Lecture Notes in Computer Science. 1990. V. 572. P. 85 -150.
Ярославский государственный университет имени П. Г. Демидова
Поступило 18. 02. 10

ПоказатьСвернуть
Заполнить форму текущей работой