Многообразия и псевдомногообразия треугольных матричных полугрупп

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

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

1° Многообразия, псевдомногообразия и проблема конечного базиса тождеств

2° Псевдомногообразия, порожденные матричными полугруппами

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

4° Содержание диссертации

5° Апробация и публикации

Глава 1. Аналог теоремы Страубинга

§ 1.1 Вспомогательные понятия и утверждения

§1.2 Теорема 1.1

§ 1.3 Примеры

Глава 2. Псевдомногообразие ИН
§2.1 Предварительные сведения
§ 2.2 Разрешимость псевдомногообразия Г1Н
§ 2.3 Следствия
Глава 3. Инволюторные полугруппы
§3.1 Предварительные сведения
§3.2 Теорема 3.1 и ее приложения
§ 3.3 Регулярные полугруппы
Список литературы

Введение
1° Многообразия, псевдомногообразия и проблема конечного базиса тождеств
Алфавит £ — это непустое множество, элементы которого называются буквами. Словом называется произвольная конечная последовательность букв. Обозначение £+ используется для множества всех непустых слов над алфавитом £. Множество £+ образует свободную полугруппу относительно операции конкатенации. Конкатенация слов и и и записывается как иг). Тооюде-ством над алфавитом £ называется пара слов и, V 6 £+, которая обозначается посредством формального равенства и = V. Полугруппа Б удовлетворяет тождеству и = V, если для любого гомоморфизма <р: £+ —> Б выполняется 1р(и) = <р(н). Если 0 — некоторое множество тождеств, то говорят, что тождество и = V следует из 0, если любая полугруппа Б, удовлетворяющая всем тождествам из 0, удовлетворяет также тождеству и = и. Множество всех полугрупп, удовлетворяющих заданному набору тождеств, называется многообразием полугрупп. Множество всех полугрупп, удовлетворяющих тем же тождествам, что и данная полугруппа Б, называется многообразием полугрупп, порожденным Б, и обозначается Уаг(5'). В силу классической НБР-теоремы Тарского (1946 г.) Уаг(Д) совпадает с Н8Р(5), где Н, § и Р — это операторы образования гомоморфных образов, подполугрупп и прямых произведений, соответственно. Класс полугрупп, замкнутый относительно операторов И, В и оператора Робразования конечных прямых произведений,

ВВЕДЕНИЕ

называется псевдомногообразием полугрупп.
Многообразия, будучи объектами, которые определяются набором тождеств, являются естественным инструментом для классификации полугрупп. Псевдомногообразия играют аналогичную роль в контексте конечных полугрупп. Основная мотивация к использованию именно таких классов, как псевдомногообразия, для классификации конечных полугрупп исторически проистекает из соответствия Эйлеиберга, согласно которому существует взаимно однозначное соответствие между псевдомногообразиями моноидов и определенными классами формальных языков, называемыми многообразиями языков [36]. Это соответствие позволяет классифицировать распознаваемые языки, исходя из свойств их синтаксических моноидов. Особую роль здесь играют псевдомногообразия, порожденные моноидами, удовлетворяющими некоторым ограничениям на отношения Грина. В частности, М. Шют-ценберже показал, что псевдомногообразие всех ^-тривиальных моноидов соответствует многообразию беззвездных языков [36,40], а И. Саймон доказал, что псевдомногообразие всех ^-тривиальных моноидов соответствует многообразию кусочно-тестируемых языков [36,42]. Подробную информацию о современном состоянии направления, посвященного изучению псевдомногообразий полугрупп, можно найти в монографиях [8,37].
Полугруппа Б называется конечно базируемой, если все тождества этой полугруппы следуют из некоторого конечного набора ее тождеств (базиса тождеств полугруппы 5); в противном случае Б называется бесконечно базируемой. Пусть У — некоторый класс конечных полугрупп. Проблема конечного базиса для класса «У состоит в том, чтобы определить, какие полугруппы из У являются конечно базируемыми и какие — бесконечно базируемыми.
Решение проблемы конечного базиса известно для класса конечных групп, а именно, как показали Ш. Оутс и М. Пауэлл в работе [32], любая конечная группа является конечно базируемой. Для класса конечных полугрупп это условие может не выполняться. Первый пример бесконечно базируемой конечной полугруппы привел П. Перкинс [34]. Им стал моноид Брандта (В, •),
ГЛАВА 1. АНАЛОГ ТЕОРЕМЫ СТРАУБИНГА
Рис 1.2: ^-структура моноида &з.
Соответствующие классы моноида ТМз(О) по конгруэнции 3$ также будем обозначать через А, В, С, Я, Е, Б. Легко видеть, что правый стабилизатор б'Я(Х) класса X Е {А, В, С, I), Е, Я} состоит из матриц, обладающих ненулевыми диагональными элементами в строках, номера которых совпадают с номерами ненулевых столбцов матриц из класса X. Каждый из этих диагональных элементов независимо пробегает группу (С, и фиксированный набор этих элементов полностью определяет действие матрицы х Е вГ^Х) на класс X. Перечислим теперь группы Шютцеиберже, соответствующие всем ^-классам: Г1 = ГГ(Я) = О х С х С?, Г2 = ГГ(Л) =бхб, Г3 = ГГ(Я) = в х С, Г4 = Гг(С) = С х й, Г5 = ГГ(Я) = (7 х С, Г6 = ГГ(Я) = С. Итак, каждой матрице из моноида ТМз(С) в соответствии с результатами главы будет соответствовать набор матриц из моноида ТМа(Н), где Я = Г1 х Г2 х Г3 х Г4 х Г5 х Г(;. Через е,- будем далее обозначать единицу группы Гг.
Перейдем к построению подмоноида М моноида ТМ§{Н) и соответствующего ему гомоморфизма <р: М -4- ТМз((7). Для этого необходимо определить плотные разложения для каждого .^-класса при действии этого класса справа на моноиде <э3. Выпишем таблицу действий (попарных произведений) в моноиде <§3, за исключением очевидных действий вида ХЕ = X, где
X 6 {А,В,С,Б,Е, Я}.