Проблема равенства слов для некоторых классов групп и подгрупп тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Введение стр. „

§1. Проблема делимости в полугруппах без циклов. стр. II

§2. Проблема равенства слов в группах без циклов. стр.

§3. Алгоритмические проблемы в полугруппе и ее ми- стр. 52 нимальном групповом расширении.

§4. Один пример группы с неразрешимой проблемой стр. 60 равенства.

Проблема распознавания равенства слов (которую часто называют проблемой равенства слов или проблемой тождества) для групп была впервые сформулирована Дэном в I9II г. Им же получено решение этой проблемы для свободных групп и для фундаментальных групп некоторых многообразий [2 i] . Аналогичная проблема для конечно-определенных полугрупп была поставлена в 1914 г. Туэ £25] .

В 1932 г. В. Магнус [Ч] доказал разрешимость проблемы равенства слов для групп с одним определяющим соотношением. Интерес к такого рода проблемам особенно возрос после того, как в результате уточнения понятия алгоритма, достигнутого в 30-х годах, появилась возможность устанавливать неразрешимость тех или иных алгоритмических проблем. В 1947 г. A.A. Марков [?] и Э. Пост[2^J независимо доказали неразрешимость проблемы равенства слов для полугрупп, а в 1952 г. П.С. Новиков [5, 40] построил первый пример группы с неразрешимой проблемой равенства слов. Примеры A.A. Маркова, Э. Поста и П.С. Новикова содержали большое количество определяющих соотношений. Впоследствии были построены более простые примеры полугрупп ( Г.С. Цейтин£^ б] , Г.С. Маканин [5] » Ю.В. Матиясевич [&] ) и групп ( В.В. Бун [20] , В.В. Борисов [3>] ) с неразрешимой проблемой равенства слов. Построенная в т полугруппа содержит три определяющих соотношения, а группа из [3] - 12 определяющих соотношений.

Ввиду того, что общая проблема равенства слов в полугруппах и группах алгоритмически неразрешима, представляет интерес нахождение таких классов полугрупп и групп, в которых эта проблема может быть решена.

Среди результатов такого рода следует упомянуть кроме вышеуказанного результата В. Магнуса , также работы В.А. Тартаковского [4?] , М.Д. Гриндлингера [22] и Р. Линдона [23] , в которых доказывается разрешимость проблемы равенства слов для групп, в которых различные определяющие слова имеют малую ( по сравнению с их длинами ) общую часть. Аналогичный результат для полугрупп получен В. Осиповой 2] . Доказана также разрешимость проблемы равенства слов в нильпотентных группах [ •

С.И. Дцян в работе доказал разрешимость проблемы равенства слов в полугруппах с одним несократимым соотношением, а также с одним соотношением вида А ~ 1 •

В этой же работе С.И. Дцян ввел понятие системы соотношений, не содержащей левых (правых) циклов, которое является обобщением понятия одного несократимого соотношения на системы, состоящие из более чем одного соотношения» Пусть дана система соотношений

А, - В-, ¿-а,:.,* (1) где А; Е>1 - непустые слова в алфавите

Пусть слова А- и 6- начинаются с букв 0СЬ и ОС соответст

С С венно. Левым графом системы (I) называется граф, содержащий 1П вершин СИ4)ОСг,ОС^ и ГЪ неориентированных ребер (бС^. > (Х&.) при ¿-4 2. гъ . Если вместо ¿^ и СС9 в этом определении взять последние буквы слов и В» » то получим определение правого ь с графа системы (I) . Если левый ¿правый) граф системы (I) не имеет циклов, то мы говорим, что система (I) не имеет левых (соответственно, правых) циклов.

В [•/] доказано также, что полугруппа, система определяющих соотношений которой не содержит ни левых, ни правых циклов, изоморфно вкладывается в группу. Пусть в последовательности выделены два элементарных преобразования

PRQ*X-= PSQ (3)

WEVxX; -Xj^ * UDV f4) где с < j . будем говорить, что преобразование (3) происходит правее преобразования (4) , если имеем Рлгр£Р, где слово Е л * непусто и в последовательности

Xu„ ^ R, Е Рг S Q . =UEV буквы отрезка £ , выделенного в Х- »не затрагиваются и переходят по индивидуальности в соответствующие буквы отрезка Е слова Х- , либо имеем V $V,i где слово S непусто и в

J HZ последовательности Х- & PSQ-+ . Х- И Е V, S № буквы

V » Hf ^ отрезка S * вццеленного в Xt" ^ > не затрагиваются и переходят по индивидуальности в соответствующие буквы отрезка, выделенного в ХJ

Два преобразования последовательности ( 2) назовем независимыми, если одно из них происходит правее другого.

Если при преобразование (3) происходит правее преобразования (4) , то мы можем переставить в (1) порядок этих преобразований, сохранив порядок остальных элементарных преобразований. Повторив такую перестановку нужное число раз, мы получим новую последовательность, переводящую X в У > в которой для любых двух независимых преобразований сначала производится то, которое происходит левее. Такие последовательности элементарных преобразований будем называть направленными вправо.

Аналогично определяется понятие последовательности элементарных преобразований, направленной влево.

Пусть полугруппа П задана системой определяющих соотношений. без левых циклов.

Для любой пары различных букв («, алфавита полугруппы П и любого слова а Z введем понятие левого разложения слова а 7 относительно буквы I

Определение понятия левого разложения слова ос 2 относительно буквы I Я^ (а2} I) проведем индукцией по длине слова а ? . Разложение будет существовать не для всякой пары Ш).

Если же такое разложение существует, то в общем случае оно должно иметь вид

Н<*Нг* . Нк*я*2', где а.2 ж Н„Нг. НКИ2[ слова Н1)Иг} Нк, называемые левыми компонентами,суть непустые собственные начала определяющих слов, /2 называется головкой, 2 - правым крылом этого разложения. При этом с головкой обязательно связывается некоторое определяющее соотношение, имеющее вид I?. = Б с точностью до перестановки местами левой и правой части.

Иногда в разложениях звездочки будем опускать. Если разложение существует, то оно определяется однозначно.

Если в левом графе системы определяющих соотношений нет пути, ведущего от буквы ОС к ^ , то будем считать, что левое разложение ^ не существует. Если такой путь в левом графе есть, то он единственный, так как в левом графе нет циклов. Пусть С -смежная с ОС буква, лежащая на пути, соединяющем а с / , и я £ -- с V а) есть соответствующее определяющее соотношение с точностью до перестановки левой и правой части. Тогда положим, по определению,

Для определения R^ (а? с) рассмотрим максимальное общее начало a,F слов О-Е и oJi . Пусть аЕ* Cl F Еч и aZsapZ, . Если F , то положим, по определению,

RffeZ.c) - a£*2v (в)

При этом вццеленное вхождение слова a Е назовем головкой разложения (6) и будем говорить, что с этой головкой связано определяющее соотношение ( 5 ) .

Пусть Ej непусто. Если Z^ пусто, то положим

Rt(a2,c) ^ a F * (7)

При этом будем говорить, что разложение (7) ке имеет головки, а dF есть первая компонента разложения.

Пусть оба слова £ и 7, непусты, т. е.

Л 1

Так как 2г) <1 Э 2) , то по индуктивному предположению определено разложение (oL?2q)• Если не существует, то будем говорить, что и не существует. Пусть существует и имеет вид н., * нг *. * где Н, Н2, . . Нк ~ левые компоненты этого разложения, R, - его головка, связанная с некоторым соотношением R.- S » а Z - его правое крыло. Тогда положим, по определению,

Rf(aZ,c)^ лР*Ия*Иг*. * Н„ (8) и будем называть слово a F и все Hi левыми компонентами разложения (8) , слово Я - его головкой, связанной с тем же со

-jl отношением R,- S , а ¿£ - его правым крылом.

Понятие направленной вправо (влево) последовательности преобразований и левого (правого) разложения слова X относительно буквы С были введены С.И. Адяном в работе [2] , в которой был построен некоторый алгоритм ОЬ , который по слову X и букве I в случае, когда X делится слева (справа) на ^ , указывает кратчайшую напрвленную вправо (влево) последовательность, переводящую слово А в слово вида ШУЯ).

Для удобства читателя мы приведем определение этого алгоритма.

Алгоритм ОЬ : Пусть полугруппа П задана системой соотношений без левых циклов. Рассмотрим произвольное слово X и букву I .

Если X начинается с буквы ^ , то X делится на & слева.

Если X начинается с буквы ¿С , отличной от ^ , то п проверим существует ли левое разложение слова X относительно буквы $ или нет. Если такое разложение не существует, то X не делится на Ч> . Если же это разложение существует, то оно имеет вид: ,

Яе(Х,1)*Н4*Нг*.*

Если это разложение не имеет головки, то X не делится на ^ слева. Пусть /?- есть головка разложения Я.^К^) и она соответствует определяющему соотношению ^ > тогда слово

X, х Н1 • Нг ;. Н^Х' назовем результатом применения одного шага алгоритма и т»

Д.

Проблемы равенства и делимости в полугруппах без левых циклов (правых)циклов были в работе [2] сведены к проблеме остановки алгоритма ОЬ •

В §1 настоящей работы с помо1цыо этого алгоритма доказывается разрешимость проблем левой и правой делимости (и проблемы равенства) в полугруппе, система определяющих соотношений которой не содержит ни левых, ни правых циклов. Этот результат изложен в статье •

Вопрос о разрешимости проблемы делимости и даже проблемы равенства слов для полугрупп, системы определяющих соотношений которых не содержат циклов только с одной стороны, пока является открытым даже для полугрупп с одним определяющим соотношением, несмотря на то, что для групп с одним соотношением разрешимоеть проблемы равенства слов доказана В. Магнусом еще в 1932 г. Г.У. Оганесян [}Н1 используя результат, содержащийся в §1, доказал разрешимость проблемы делимости для полугрупп с одним определяющим соотношением вида а А (о » гДе А - произвольное слово.

В §2 доказывается разрешимость проблемы равенства слов для групп, заданных системой определяющих соотношений в положительном алфавите, не содержащей циклов.

В §3 иссдедуется связь между алгоритмическими проблемами в полугруппе, изоморфно вложимой в группу, и в ее минимальном групповом расширении. Указывается пример полугруппы, для которой проблемы левой и правой делимости, а также проблемы равенства слов разрешимы, в то время как в ее минимальном групповом расширении проблема равенства слов неразрешима.

Содержание §§ 2 и 3 изложено в работах [/4] и

В работе 9] С.И. Адян доказал разрешимость проблемы равенства слов в случае, когда все определяющие слова группы имеют вид

Ап г 4 » где П - достаточно велико, и группа не содержит элементов второго порядка. Возникает естественный вопрос о том, разрешима ли проблема равенства слов при малык значениях гь .

В §4 настоящей работы строится пример группы с неразрешимой проблемой равенства слов, все определяющие соотношении которой имеют вид А ' i • Зтот результат имеется в .

Все понятия и обозначения, не оговоренные особо, понимаются так же, как в .

Нумерация теорем в работе сплошная, леммы и формулы нумеруются в пределах каждого параграфа.

1. Дцян С.И., Определяющие соотношения и алгоритмические проблемы для групп и полугрупп, Труды Матем. ин-та им. В.А. Стекло-ва АН СССР, 85, 1966.

2. Дцян С.И., О преобразовании слов в полугруппе, заданной системой определяющих соотношений, Алгебра и логика, 1976, т.15, № 6, 611-621.

3. Борисов В.В., Простые примеры групп с неразрешимой проблемой тождества, Матем. заметки, 6, Р 5, 1965, 521-532.

4. Магнус В., Проблема идентичности для групп с одним определяющим соотношением, УМН, вып.З, 1941.

5. Маканин Г.С., К проблеме тождества в конечно-определенных полугруппах, Доклады АН СССР, т.171, (Р 2, 1966, 285-287.

6. Мальцев А.И., Два замечания о нильпотентных группах, Матем. сб., нов.сер., 1955, т.37, вып.З, 567-572.

7. Марков А.А., Невозможность некоторых алгорифмов в теории ассоциативных систем, I, ДАН СССР, т.55, № 7, 1947.

8. Матиясевич Ю.В., Простые примеры неразрешимых канонических исчислений. Труды Матем. ин-та им. В.А. Стеклова, т.93, 1967.

9. Новиков П.С., Об алгоритмической неразрешимости проблемы тождества, ДАН СССР, 85, 1952, 709-772.

10. Новиков П.С., Об алгоритмической неразрешимости проблемы тождества слов в теории групп, Тр. МИАН СССР, 44, 1955, 3-143.

11. Оганесян Г.У., О полугруппах с одним соотношением и полугруппах без циклов, Изв. АН СССР, сер. матем., т.46, № I, 1982, 88-94.

12. ОсиповаВ.А., К проблеме тождества для конечно-определенных полугрупп, ДАН СССР, т.178, № 5, 1968, I0I7-I020.

13. Саркисян O.A., К проблеме равенства слов для конечно-определенных: групп, Всесоюзный алгебраический симпозиум, Гомель, тезисы докладов 4.1, 1975.

14. Саркисян O.A., О связи между алгоритмическими проблемами в группах и полугруппах, ДАН СССР, т.227, Р 6, 1976, 1305-1307.

15. Саркисян O.A., Некоторые соотношения между проблемами тождества и делимости в группах и полугруппах, Изв. АН СССР, сер. матем., т.43, Г- 4, 1979 , 909-921.

16. Саркисян O.A., О проблемах тождества и делимости в полугруппах и группах без циклов, Изв. АН СССР, сер. матем., т.45,№ 6, 1981, I424-1440.

17. Тартаковский В.А., Метод решета в теории групп, Матем. сб., 25, 1979, 3-50.

18. Lyndon R.C., 0* Derm's aL^or »ft^, McfHa,1.>é>, I9é>é>, 208-SE8.