Проблема равенства слов для некоторых классов групп и подгрупп

• Автор: Саркисян, Осанна Ашотовна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 68 c. : ил

Введение стр. ,3

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

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

§3. Алгоритмические проблемы в полугруппе и ее ми

нимальном групповом расширении.

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

равенства.
Литература

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

ковского т , М.Д. Гриндлингера [22] и Р. Линдона [23], В которых доказывается разрешимость проблемы равенства слов для групп, в которых различные определяющие слова имеют малую ( по сравнению с их длинами ) общую часть. Аналогичный результат для полугрупп получен В. Осиповой 2] . Доказана также разрешимость проблемы равенства слов в нильпотентных группах М.
С.И. Адян в работе [|] доказал разрешимость проблеш равенства слов в полугруппах с одним несократимым соотношением, а также с одним соотношением вида Д - { .
В этой же работе С.И. Адян ввел понятие системы соотношений, не содержащей левых (правых) циклов, которое является обобщением понятия одного несократимого соотношения на системы, состоящие из более чем одного соотношения.
Пусть дана система соотношений
А,- В., п. (і)
где А; А - непустые слова в алфавите ССьОг>
Пусть слова А- И 6; начинаются с букв ось и ОС соответет-венно. Левым графом системы (I) называется граф, содержащий ПХ вершин 0І, ОС,. .... а^ и П неориентированных ребер (ос ОС при
*) 7 I £ * і *
с Г-/2 * Если вместо и ОС5 в этом определении взять последние буквы слов Д; И В; , то получим определение правого
с с
графа системы (I) . Если левый /правый) граф системы /I) не имеет циклов, то мы говорим, что система (I) не имеет левых (соответственно, правых) циклов.
В [•/] доказано также, что полугруппа, система определяющих соотношений которой не содержит ни левых, ни правых циклов, изоморфно вкладывается в группу.
Пусть в последовательности
ХгХ.-'А-X»-* ХД*У

Продолжим преобразования следующим образом:
х, с с... сх, в/с;гх'"

" I - і
..-Х,с-'сА ... с^еАЧ^'ГЛ
хаса... с:і^6л
•А ,х<(
Рассмотрев последовательно всю цепочку определяющих соотношений, связывающих с , мы получим следующее представление слова X :
/// г ■
л-хлЧ’ ... с; вДТх.
Сократим С* с и рассмотрим слово . Согласно второму пункту условия В) , длина Я» і • не меньше двух, следова-тельно, ^ можно представить в виде
Вм_. - ^ в ,
где ь не пусто.
Заметим, что все слова и С- , а также слово £> являются собственными концами определяющих слов, а потому они не могут содержать вхождений определяющих слов и внутри слова £>0^ &2.Сі &ХО^нельзя произвести никакого нетривиального преобразования.
Если слово X, делится справа на слово С2_сі ... Ск , то будем считать приведение законченным. Если же не делится на
это слово, то рассотрим пару букв и Сг . Если они не связаны, то слово X не равно никакому положительному слову. В самом деле, отрицательное слово (сгСь ... Ск) не может в этом случае сократиться ни слева, ни справа. Если же оі^ и Ог свя-