Алгоритмические проблемы для многообразий полугрупп, моноидов, групп и колец

• Автор: Попов, Владимир Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2002
• Место защиты: Екатеринбург
• Количество страниц: 270 с.

Оглавление
Введение

Глава 1. Марковские свойства

§1. Конструкция полугруппы Б(М,ф)

§2. Распознавание марковских свойств для полугрупп

Глава 2. Эквациональная рекурсивность и границы разрешимости

§1. Распознавание эквациональной рекурсивности

для полугрупп и колец

§2. Распознавание границы разрешимости для полугрупп с

перестановочным тождеством

§3. Позитивные теории классов полугрупп и колец

§4. Расположение многообразий полугрупп и колец с разрешимой эквациональной теорией в решетке
подмногообразий
§5. Проблема равенства для свободных полугрупп и колец
Глава 3. Выводимость тождеств и конечная базируемость
§1. Общая проблема выводимости тождеств
§2. Распознавание конечной базируемости для полугрупп,
групп и колец
Глава 4. Независимая базируемость и относительная покрываемость .. .151 §1. Распознавание независимой базируемости для полугрупп,
моноидов и колец
§2. Независимость систем тождеств полугрупп, групп и колец .. 199 §3. Независимо разбиваемые системы тождеств
§4. Распознавание относительной покрываемое
для полугрупп
§5. Распознавание относительной конечной покрываемое
для полугрупп
Литература

Введение
Первые алгоритмические проблемы для групп и полугрупп были поставлены еще в начале XX века: проблема равенства для групп М.Деном в 1911 г., [129], проблема равенства для полугрупп А.Туэ в 1914 г., [162]. В 30-50-х годах XX века были разработаны и исследованы различные математические версии понятия алгоритма (см. библиографию в [5], [71], [74], [107]). В результате этого в математике оформилось новое направление — исследование алгоритмических проблем, то есть вопросов существования алгоритмов для решения массовых задач из того или иного класса. Среди таких проблем стали различать разрешимые (соответствующий алгоритм существует) и неразрешимые (такого алгоритма нет) алгоритмические проблемы.
Первый пример неразрешимой алгоритмической проблемы в алгебре был найден А.Тарским: в 1943 году он построил многообразие универсальных алгебр с неразрешимой эквациональной теорией (см. [128], [159], [161]). В 1947 году А.А.Маркови, независимо, Э.Пост доказали неразрешимость проблемы равенства в многообразии всех полугрупп [67], [68], [153]. Дальнейшее развитие исследований по проблеме равенства и другим тесно, связанным с ней алгоритмическим вопросам отражено в обзорах [4], [16], [79], [87], [135], [138], [155].
В работах [69], [70] А.А.Марков предложил весьма общий подход к изучению алгоритмических проблем на языке распознаваемости свойств, впоследствии получивших название марковских. Абстрактное свойство алгебраических систем из класса К называется марковским, если существуют две конечно определенные в К системы, одна из которых обладает этим свойством, а другая не вложима изоморфно ни в какую конечно определенную в К систему с этим свойством [18]. Рассматриваемую здесь алгоритмическую проблему, будем называть проблемой распознавания марковских свойств:
Существует ли алгоритм, который по конечному заданию алгебраической системы из класса К отвечает на вопрос, обладает ли она некоторым наперед заданным марковским свойством ?
Важные алгоритмические проблемы, связаны с рассмотрением тождеств. Фундаментальное исследование таких проблем для универсальных алгебр проведено в работах Г.Мак Нал-ти [143], [144]. Тождествам полугрупп, групп и колец посвящены книги и обзоры [3], [9], [10], [12], [44], [59], [114]. Тождества решеток подмногообразий и подалгебр рассматривались в [33], [51], [83], [112], [113], [156]. Среди проблем, связанных с тождествами, мы выделим как наиболее важные проблемы распознавания эквациональной рекурсивности, границы разрешимости, конечной и независимой базируемости и близкие к ним проблемы.
Всякий пример конечно определенной универсальной алгебры с неразрешимой проблемой равенства слов легко можно модифицировать в пример конечно базируемого многообразия универсальных алгебр с неразрешимой эквациональной теорией. Используя это, А.И.Мальцев в работе [65] построил конечно базируемое многообразие квазигрупп с неразрешимой эквациональной теорией и поставил в [61] вопрос о существовании конечно базируемых многообразий полугрупп, групп и колец с неразрешимой эквациональной теорией. Положительный ответ на этот вопрос для полугрупп получен в [77]. Пример конечно базируемого многообразия групп с неразрешимой эквациональной теорией построен в работе [57]. В [117] анонсировано утверждение о том, что произвольное конечно базируемое многообразие ассоциативных колец имеет разрешимую эквациональную теорию. В связи с перечисленными результатами актуальной становится проблема распознавания экващюнальной рекурсивности:
Существует ли алгоритм, определяющий по произвольной конечной системе тождеств данной сигнатуры, разрешима ли эквациональная теория многообразия, заданного этой системой тождеств?
К 90-м годам XX века было получено большое количество результатов по разрешимости теорий первого порядка классов алгебраических систем (см. книги [42], [142], обзоры
[2], [5], [16], [21], [43], [64], [74], [87], работы [46] - [49] и библиографию к ним). Это позволило Ю.М.Важенину поставить в статье [19] проблему описания всех, в рамках некоторой иерархии, разрешимых теорий данного класса алгебраических систем и для решения ее развить в работах [19], [20], [22] - [25] продуктивную концепцию критических теорий и границ разрешимости. Указанная проблема в случае схемно-альтернативной иерархии решена для многообразия всех полугрупп и периодических многообразий коммутативных полугрупп в работах [19], [116], для многообразия йсех групп, нильпотентных и разрешимых многообра-

зий групп в работах [19], [24], [26], [27]. Критические теории многообразий всех колец, ассоциативных, коммутативных, антикоммутативных, нильпотентных, лиевых, йордановых и альтернативных колец найдены в работах [19], [22], [23], [168], [167], [118], [86]. Типы границ разрешимости над-коммутативно-ассоциативных многообразий колец указаны в [85], [173]. В работе [29] найдены границы разрешимости для некоторых псевдомногообразий колец. Эти результаты позволяют сформулировать проблему распознавания границы разрешимости:
Существует ли алгоритм, определяющий по произвольной конечной системе тождеств данной сигнатуры, какова граница разрешимости многообразия, заданного этой системой тождеств ?
В [60] Л.А.Бокуть поставил общую проблему выводимости тождеств для групп: ’’Существует ли алгоритм, который по любой системе групповых слов Д,..., fm (от фиксированного множества переменных *г, 22, ...) и отдельному слову / выяснял бы, следует ли тождество / = 1 из тождеств /1 = 1,..., /т = 1.” Отрицательное решение этого вопроса получено в [56]. Общую проблему выводимости тождеств можно сформулировать и для произвольных алгебраических систем:
Существует ли алгоритм, который по любой системе тождеств данной сигнатуры <р17 ■■■: бт от фиксированного множества переменных х, %2, и отдельному тождеству -р выяснял бы, следует ли тождество <р из тождеств р,..., (рт.
Ниже мы будем говорить об алгоритмической распознаваемости таких свойств бесконечных систем тождеств, как конечная и независимая базируемость и др. Соответствующие постановки задач будут корректны лишь в том случае, когда в рассматриваемом классе бесконечных систем тождеств каждая система задана эффективно. Поэтому в нижеследующих формулировках проблем предполагается, что рассматриваемые системы тождеств принадлежат семейству Т бесконечных систем тождеств такому, что существует конечный автомат, распознающий принадлежит ли система тождеств Е семейству Т .
Первые примеры многообразий полугрупп, не имеющих конечного базиса, были приведены в работах [17], [122]. Примеры многообразий групп с тем же свойством построены в
[3], [80], [163]. В [75] доказано существование многообразия альтернативных алгебр над полем характеристики 2, не имеющего конечного базиса. Многообразие алгебр Ли простой характеристики р с этим же свойством найдено в [38]. Примеры многообразий полугрупп и колец, порожденных конечной алгеброй и не имеющих конечного базиса, построены в работах [149], [84]. Целый ряд работ посвящен проблеме конечной базируемости многообразий универсальных алгебр (см. обзор [83]). В частности, в работе [123] доказано, что любое конгруэнц-дистрибутивное многообразие конечной сигнатуры, порожденное конечной алгеброй, конечно базируемо. Более того, в ней показано, что по порождающей алгебре можно эффективно выписать конечную систему тождеств, задающую соответствующее многообразие. К настоящему времени накоплена весьма обширная информация о конечно базируемых многообразиях (см. обзоры [10], [114] и книгу [9]). Основной вопрос, возникающий в исследованиях этого направления, заключается в следующем: по данной бесконечной системе тождеств определить, является ли многообразие, заданное этой системой, конечно базируемым? Этот вопрос позволяет сформулировать проблему распознавания конечной базируемости:
Существует ли алгоритм, определяющий по произвольной бесконечной системе тождеств данной сигнатуры, является ли многообразие, заданное этой системой тождеств, конечно базируемым?
Первый пример многообразия полугрупп, не имеющего независимого базиса, построен в работе [104]. Другие примеры многообразий полугрупп с этим свойством указаны в работах [95], [105], [152]. В [152] приведен пример системы тождеств моноидов, в [55] — инверсных полугрупп, в [58] — групп, не имеющих независимого базиса. В [95] доказано, что существует многообразие полугрупп, порожденное конечной полугруппой и не имеющее независимого базиса. В работе [35] доказано, что любая двуэлементная алгебра, конечной сигнатуры порождает конечно базируемое квазимногообразие и следовательно все квазимногообразия, порожденные двуэлементными алгебрами, независимо базируемы. В [34] построено квазимногообразие, порожденное трехэлементной алгеброй и не имеющее независимого базиса. Эти результаты стимулируют постановку проблемы распознавания независимой базируемости:
Существует ли алгоритм, определяющий по произвольной бесконечной системе тождеств данной сигнатуры, является ли многообразие, заданное этой системой тождеств, независимо базируемым?

щнущ-ну,... и£УЖ*+ІУ’+1
и,+,+1 = и1+і+2 = ... = ит = Ш2,
где "IV — слово, полуденное из слова заменой слова х^іУіХіімоУі на
Ь(. При этом очевидно, что
г>№) + щи2) +... + щи,-2) + з(сл,-і)+ ци^1щу2...щ_1ті^+2.. .н;%и;+1;+
Ф(Пі+171и|+11?а.. .и£1'1?и;+2у$.. .ІС“+^?И;+})+
5)(иї+2^иі+272.. .щхіші’+^хі...щ+^щхь +...+ зод+^и^а.. .Щ+_^ЩХ^ХІ.. .ид%и;+;)+
Ш+,+1) + ь(щ+,+2) +... + циг) < чиї) + чи2) +... + циг).
Это противоречит нашему предположению о том, что для цепочки равенств ИЛ = Су = (У2 = ... = 11г — ИЛ число ї)(С7і) + Ъ{1}2) + ... + 5(Уг) является минимальным.
Таким образом мы рассмотрели случай, когда Ну — иц и Ну+у = Шо, и убедились в том, что Ну ф ці,- или 1Х|+1 ф и:о- Следовательно нам нужно рассмотреть три случая: 11| ф иц и Ну+1 ф гго, Ну = ш,- и и;+1 Ф “»о. Щ ф Щ я и;+1 = шо- Мы рассмотрим только случай Щ ф и Щ+1 ф №о, поскольку остальные случаи можно получить несложной комбинацией конструкций для случаев Ну ф ьц ж Иу+1 Ф и>о, Ну = иіі и Щ+1 = п>0. Так как 1Х| ф ад и 1[у+і ф п>і, очевидно, что в последовательности слов Щ,Щ+ • • ■ і Ну+< не все слова равны между собой. Выделим из последовательности Ну ,Иу+1,... ,Н|+І максимальную подпоследовательность Ну"1, Ну“2,..., її/1' такую, что ни одно слово из этой последовательности не равно последующему. Совершенно аналогично, из последовательности Н|+1, Иу^, • -., Ну Д можно выделить максимальную подпоследовательность Ну^, Ну^,..., Ну^'у такую, что ни одно слово из этой последовательности не равно последующему. В силу того, что если для некоторых г и } имеет место соотношение Иу Ф Н}+1, то для любого I Ф і имеет место соотношение Н; = ИД1, числа «г,,, ■ і ^а,і, , • • •> ®д,;/ попарно различны. Следовательно
если г < то цепочку равенств ИЛ = 11 = 1}2 — ■ ■ ■ = Й- = ИЛ можно заменить цепочкой
ил = их = и2 =... = и,= и,_ г =
Н^уЩ72... идуїу.нд^
Ul_1Vy_1u;-VyU)+yVy+1llj+2Vy+2. ..щудщ+1 = Н>у7ІН^2...и?_у"И?уи?+2Уі+2... и|_у7у_іН;-^и;+уУу+уиі+л+2.. .щу„щ+у
и|_1'7у_1иу"‘"УуНу+1'Уу+уНу+2'Уу+2.. .Н;У,Н;+1 = и?7уН5У2... Ш_у'У1и!+2'Ун.2
и;--М-1и?'ъи%1ушии№+3.. .ида‘+1 =
и;_у^_1н;-«'^и;?у7я.1и;+2^+а.. .и;%Н;+1 -... ида^2...иг_у"^іН?+2^+2
нд17у_уи;<*"^и;;-;'^+1н*+2^+2.. .и;%и;+1 = и^хЩУ2... иищиі+2У!+2... щщ+2уі+2... и^„щ+1 =
и?уде2.. .Н|_у^_1Н^уН*+у^+1Н|+2^+2... Н|_12Н|+2Уу+2...ида;+1 =