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

• Первухина, Татьяна Вячеславовна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Первухина, Татьяна Вячеславовна

Оглавление

Введение

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

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

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

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

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

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

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

§ 1.2 Теорема 1.1

§ 1.3 Примеры

Глава 2. Псевдомногообразие ГШ

§2.1 Предварительные сведения

§2.2 Разрешимость псевдомногообразия ИН

§ 2.3 Следствия

Глава 3. Инволюторные полугруппы

§3.1 Предварительные сведения

§3.2 Теорема 3.1 и ее приложения

§ 3.3 Регулярные полугруппы

Список литературы

Введение диссертации (часть автореферата) на тему «Многообразия и псевдомногообразия треугольных матричных полугрупп»

Введение

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

Алфавит S — это непустое множество, элементы которого называются буквами. Словом называется произвольная конечная последовательность букв. Обозначение Е+ используется для множества всех непустых слов над алфавитом X. Множество образует свободную полугруппу относительно операции конкатенации. Конкатенация слов и и v записывается как uv. Тождеством над алфавитом £ называется пара слов u, v G которая обозначается посредством формального равенства и = v. Полугруппа S удовлетворяет тождеству и = v, если для любого гомоморфизма (р: Е+ —¥ S выполняется ср(и) = <p(v). Если G — некоторое множество тождеств, то говорят, что тождество и — v следует из 0, если любая полугруппа S, удовлетворяющая всем тождествам из ©, удовлетворяет также тождеству и = v. Множество всех полугрупп, удовлетворяющих заданному набору тождеств, называется многообразием полугрупп. Множество всех полугрупп, удовлетворяющих тем же тождествам, что и данная полугруппа S, называется многообразием полугрупп, порожденным S, и обозначается Var(<S'). В силу классической HSP-теоремы Тарского (1946 г.) Var(S) совпадает с ШР(5), где H, § и Р - это операторы образования гомоморфных образов, подполугрупп и прямых произведений, соответственно. Класс полугрупп, замкнутый относительно операторов 1, S и оператора Р/г-п образования конечных прямых произведений,

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

Многообразия, будучи объектами, которые определяются набором тождеств, являются естественным инструментом для классификации полугрупп. Псевдомногообразия играют аналогичную роль в контексте конечных полугрупп. Основная мотивация к использованию именно таких классов, как псевдомногообразия, для классификации конечных полугрупп исторически проистекает из соответствия Эйленберга, согласно которому существует взаимно однозначное соответствие между псевдомногообразиями моноидов и определенными классами формальных языков, называемыми многообразиями языков [36]. Это соответствие позволяет классифицировать распознаваемые языки, исходя из свойств их синтаксических моноидов. Особую роль здесь играют псевдомногообразия, порожденные моноидами, удовлетворяющими некоторым ограничениям на отношения Грина. В частности, М. Шют-ценберже показал, что псевдомногообразие всех ¿^-тривиальных моноидов соответствует многообразию беззвездных языков [36,40], а И. Саймон доказал, что псевдомногообразие всех ^-тривиальных моноидов соответствует многообразию кусочно-тестируемых языков [36,42]. Подробную информацию о современном состоянии направления, посвященного изучению псевдомногообразий полугрупп, можно найти в монографиях [8,37].

Полугруппа в называется конечно базируемой, если все тождества этой полугруппы следуют из некоторого конечного набора ее тождеств (базиса тождеств полугруппы »9); в противном случае Б называется бесконечно базируемой. Пусть — некоторый класс конечных полугрупп. Проблема конечного базиса для класса состоит в том, чтобы определить, какие полугруппы из являются конечно базируемыми и какие — бесконечно базируемыми.

Решение проблемы конечного базиса известно для класса конечных групп, а именно, как показали Ш. Оутс и М. Пауэлл в работе [32], любая конечная группа является конечно базируемой. Для класса конечных полугрупп это условие может не выполняться. Первый пример бесконечно базируемой конечной полугруппы привел П. Перкинс [34]. Им стал моноид Брандта (В\, •),

где В\ — множество, состоящее из следующих шести 2 х 2-матриц:

/10\ /0 1 \ /0 0\ 0 1 0 ^ у о о у' V о о ; ' V01/' V01/' V00/'

а бинарная операция (А\,А2) у А\ • А2 — обычное матричное умножение. Результаты исследований проблемы конечного базиса тождеств для класса конечных полугрупп по состоянию на 2001 г. систематизированы в обзоре [47]. В теории псевдомногообразий имеется аналог проблемы конечного базиса, основанный на понятии псевдотождества [8]. Однако для класса конечных полугрупп эти проблемы совпадают: конечная полугруппа обладает конечным базисом псевдотождеств тогда и только тогда, когда она обладает конечным базисом тождеств [8, Следствие 4.3.8].

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

Под угшверсальным объектом для некоторого класса полугрупп ¿У мы далее будем понимать набор конкретных полугрупп (например, серию полугрупп, зависящую от одного или нескольких параметров), таких, что каждая полугруппа из У реализуется как подполугруппа или делитель некоторой полугруппы из этого набора. Напомним, что полугруппа Б делит полугруппу Т, если Б является гомоморфным образом некоторой подполугруппы из Т. В теории псевдомногообразий полугрупп однопараметрические серии треугольных матричных полугрупп выступают универсальными объектами для псевдомногообразия всех ^-тривиальных моноидов J и псевдомногообразия всех «^-тривиальных моноидов 11. Приведем соответствующие результаты. Обозначим через моноид всех рефлексивных бинарных отношений на множестве из п элементов. Каждое такое отношение пред ставимо булевой матрицей с единицами на главной диагонали. Обозначим через подмоно-ид состоящий из верхнетреугольных матриц. Назовем преобразование а

частично упорядоченного множества (Смонотонным, если ql ^ влечет ^ о^) для всех ^1,92 € (5, и направленным, если д ^ для всех q ^ Q. Следующая теорема, показывающая, что серии и %'п являются универсальными объектами для псевдомногообразия Л, была доказана Г. Страубингом в 1980 г. [44].

Теорема I. Для конечного моноида М следующие условия равносильны:

• М является ^-тривиальным;

• М делит для некоторого п;

• М делит для некоторого п;

• М делит некоторый моноид монотонных направленных преобразований частично упорядоченного множества.

Обозначим через ¿>п моноид всех направленных преобразований на множестве {1,..., п}. Всякое такое преобразование, очевидно, представимо верхнетреугольной булевой матрицей, каждая строка которой содержит лишь один ненулевой элемент. Следующее утверждение, которое можно найти, например, в [36], показывает, что серия ¿>п является универсальным объектом для псевдомногообразия 11.

Теорема II. Конечный моноид является &-тривиальным тогда и только тогда, когда он изоморфно вкладывается в моноид для некоторого п.

Отметим, что, несмотря на сходные по характеру утверждения теорем I и II, их доказательства опираются на существенно различные идеи. Доказательство теоремы II конструктивно: по данному конечному моноиду £ эффективно вычисляется размер матриц и строится вложение в соответствующий моноид $п. Доказательство же теоремы Страубинга неконструктивно и существенно опирается на упомянутую в предыдущем параграфе теорему Саймона. Более того, можно показать, что эти две теоремы эквивалентны.

На данный момент еще не получено конструктивного доказательства теоремы Страубинга, которое позволяло бы указать конкретный моноид его подмоноид и соответствующий гомоморфизм.

Ввиду теорем I и II представляет интерес дальнейшее изучение возможности классифицировать конечные полугруппы в виде псевдомногообразий, порожденных полугруппами треугольных матриц. Рассмотрим следующую двухпараметрическую серию треугольных матричных полугрупп. Конечную группу С? с присоединенным нулем 0 обозначим через (7 и 0. Назовем матрицу порядка п над (7 и 0 мопомиалъной (по строкам), если каждая строка содержит в точности один ненулевой элемент. Для всех элементов д 6 О и 0 положим дополнительно <7 + 0 = 0 + дг = 0. Обозначим через ТМП((7) моноид всех верхнетреугольных мономиальных матриц порядка п над С и 0. Умножение двух матриц из ТМП((?) с учетом дополнительного условия осуществляется по правилам стандартного матричного умножения.

Моноиды ТМП(С!) интересны тем, что их можно рассматривать как естественное обобщение моноидов £п. В этом случае каждый из моноидов <£п можно считать моноидом всех верхнетреугольных мономиальных матриц порядка п над единичной группой с нулем. Более того, как будет показано в диссертационной работе, на каждом моноиде ТМП(С?) совпадают отношения Грина & и Жчто, в свою очередь, обобщает случай «^-тривиальных моноидов. Возникает предположение, что серия моноидов ТМп{С1) может играть для класса моноидов, удовлетворяющих соотношению & = Ж, роль универсального объекта аналогично роли серии $п для класса «^"-тривиальных моноидов и серии 'п для класса ^-тривиальных моноидов.

Задача 1. Верно ли, что каждый моноид, удовлетворяющий соотношению £% = Ж, делит некоторый моноид ТМп{0) 9

Отметим, что моноиды, на которых совпадают определенные отношения Грина, уже изучались в литературе. Так, например, в [26] Ж. Лаллеман показал соответствие между классом конечных регулярных моноидов, удовлетворяющих соотношению $ = и конечными префиксными кодами. В [33]

М. В. Волков и Ф. Пастэйн охарактеризовали многообразия, полугруппы которых удовлетворяют одному из соотношений & = Ж, = ££, О) = 3% или

Помимо предполагаемого аналога теорем I и II, возникает вопрос о разрешимости псевдомногообразия, порожденного серией моноидов ТМп{С1). Иными словами, необходимо выяснить, существует ли алгоритмически проверяемый критерий, позволяющий определить, принадлежит ли данный конечный моноид этому псевдомногообразию. Для псевдомногообразий Л и II такие критерии, очевидно, существуют.

Задача 2. Определить, является ли псевдомногообразие, порожденное классом всех моноидов ТМп{С), разрешимым, и если да, найти алгоритмически проверяемый критерий.

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

Изучение матричных тождеств, включающих операции умножения и сложения, является классическим направлением исследований, которое было мотивировано несколькими важными проблемами в геометрии и алгебре (см. обзор [12]) и в итоге привело к созданию теории Р1-колец (см., например, [38]). Матричные тождества, включающие наряду с умножением и сложением одну или несколько унарных операций (таких, например, как обычное или сим-плектическое транспонирование) также привлекали большое внимание исследователей, см., например, [15,16,20,38]. Задача классификации матричных тождеств определенного типа естественным образом сводится к проблеме конечного базиса тождеств. Так, например, все тождества полугруппы матриц порядка п над бесконечным полем относительно операции умножения следуют из закона ассоциативности [22]. В противоположность этому, мультипликативная полугруппа матриц порядка п над конечным полем не имеет ко-

нечного базиса тождеств. Этот результат был независимо получен в работах М.В. Волкова [2] и М.В. Сапира [6]. Стоит отметить, что методы, использовавшиеся в этих работах: метод критических полугрупп и метод существенно бесконечно базируемых полугрупп — в значительной степени различны, однако достаточно любого из них, чтоб охватить тождества матриц любого размера над любым конечным полем.

Оба указанных метода были впоследствии реализованы в контексте унарных полугрупп в работе К. Ауингера, И. Долинки и М.В. Волкова [13]. Напомним, что унарной полугруппой называется полугруппа, снабженная дополнительной унарной операцией х н-х* (или несколькими такими операциями). Унарная полугруппа S = (S,-,*) называется инволюторной полугруппой,, если она удовлетворяет тождествам

(ху)* = у*х* и (х*У=х, (1)

или, иными словами, если унарная операция а; х* является инволюторным анти-автоморфизмом полугруппового редукта (S, •). Все понятия, связанные тождествами, переносятся на случай унарных полугрупп. Аналогичным образом формулируется проблема конечного базиса для некорого класса унарных полугрупп. Применение разработанных методов позволило классифицировать с точки зрения конечной базируемости несколько важных классов унарных матричных полугрупп. В частности, в [13] был получен следующий результат.

Теорема III. Следующие унарные матричные полугруппы не имеют конечного базиса тождеств:

• полугруппа п х п-матриц над конечным полем относительно умножения и транспонирования;

• полугруппа 2п х 2п-лштриц над конечным полем относительно умножения и симплектического транспонирования,

• полугруппа 2 х 2-матриц над конечным полем относительно умножения и обращения Мура-Пенроуза или относительно умножения, обращения Мура-Пенроуза и эрмитова сопряжения,

• полугруппа булевых п х п-матриц относительно умножения и транспонирования.

Отметим, что в доказательстве этого результата используются унарные версии обоих методов из работ [2] и [6], и оказывается, что они в некотором смысле дополняют друг друга, поскольку, в отличие от случая мультипликативных тождеств, ни одного из этих методов не достаточно, чтобы охватить, например, тождества матриц любого размера над любым конечным полем относительно умножения и транспонирования.

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

Многообразие (унарных) полугрупп называется локально конечным, если каждая конечно порожденная (унарная) полугруппа из этого псевдомногообразия конечна. Конечная (унарная) полугруппа называется существенно бесконечно базируемой, если она не содержится ни в каком локально конечном конечно базируемом многообразии (унарных) полугрупп. Поскольку многообразие, порожденное конечной (унарной) полугруппой, локально конечно, то существенно бесконечно базируемая (унарная) полугруппа обязательно бесконечно базируема. Фактически, свойство существенной бесконечной базируемое™ намного сильнее, чем свойство бесконечной базируемости.

В 1987 г. М. В. Сапир [7] получил эффективное (в алгоритмическом смысле) описание существенно бесконечно базируемых полугрупп. В частности, согласно нему, упомянутый в первом параграфе моноид Брандта В\ существенно бесконечно базируем. На основании этого результата в 2003 г. И. А. Гольдберг и М. В. Волков в работе [3] классифицировали с точки зрения существенной бесконечной базируемости полугруппы Тп (%) всех верхнетреугольных матриц порядка п над конечным полем %.

Теорема VI. Полугруппа ТП(ЗС) существенно бесконечно базируема тогда и только тогда, когда п ^ 4 и % содерэ/сит не менее трех элементов.

Также из результатов работ [21] и [29] вытекает классификация полугрупп ТВП булевых треугольных матриц порядка п.

Теорема VII. Полугруппа ТВП существенно бесконечно базируема тогда и только тогда, когда п ^ 3.

Существенно бесконечно базируемые унарные полугруппы исследовались в работах [13,17]. В частности, в работе [13] на основании результатов М.В. Сапира были найдены некоторые достаточные и некоторые необходимые условия для существенной бесконечной базируемости конечных инволюторных полугрупп. Приведем необходимое определение.

Пусть х\, Х2, ■ ■ ■, хп,... — последовательность букв. Последовательность {%п}п=1,2,... слов Згшгша определяется индуктивно по правилу ^ = х\, Zn+l = Znxn+lZn. Будем говорить, что инволюторное слово V является инволютор-ным изотермом для унарной полугруппы Б, если единственное инволюторное слово г/, при котором 8 удовлетворяет инволюторному полугрупповому тождеству V = г/, — это само слово V.

Теорема IV. Пусть В — конечная инволюторная полугруппа. Если все слова Зимина являются инволюторными изотермами для $, то 8 существенно бесконечно базируема.

Теорема V. Пусть 8 = (Б,-,*) — конечная инволюторная полугруппа. Если существует такое инволюторное слово и>(х) от одной переменной х, что § удовлетворяет тождеству х = хсо(х)х, то § не является существенно бесконечно базируемой.

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

в качестве инволюции полугруппу ТП(ЗС) можно снабдить операцией ° отражения относительно побочной диагонали. Полученную инволюторную полугруппу обозначим через (ТП(ЗС), Кроме того, для п = 2т полугруппу Т2т(ЗС) можно рассматривать как полугруппу матриц вида

Здесь А, С € Тт(ЗС) и В £ МШ(ЗС), где Мт(ЗС) — полугруппа всех т х т-матриц над полем ОС. Для произвольной инволюции * на полугруппе Мте(ЗС), которая одновременно является инволюцией паТт(%), снабдим Т2Ш(ЗС) следующей унарной операцией 7:

Непосредственная проверка показывает, что эта операция является инволюцией. Обозначим полученную инволюторную полугруппу через (Т2т(ЗС), •,7).

Задача 3. Классифицировать инволюторные полугруппы {ТП(ЗС), и (Т2тп(ЗС), •,7) с точки зрения существенной бесконечной базируемости.

Задачу 3 ввиду упомянутого результата И. А. Гольдберга и М. В. Волкова [3] можно естественным образом рассматривать в контексте более широкого вопроса: в каких случаях инволюция ж н-» х*, определенная на существенно бесконечно базируемой полугруппе (5, •), сохраняет этот вид базируемости в том смысле, что получившаяся инволюторная полугруппа § = (£>, •,*) будет существенно бесконечно базируемой как унарная полугруппа?

Вопрос о взаимосвязи проблемы конечного базиса для данной унарной полугруппы § и для ее полугруппового редукта (5, •) нетривиален. С одной стороны, § обычно удовлетворяет большему количеству тождеств, чем (Б, •), и потому с большей вероятностью может оказаться бесконечно базируемой. С другой стороны, может возникнуть ситуация, когда некоторое тождество в (Б, •) не следовало из системы тождеств Е как обычное полугрупповое тож-

дество, но следует из £ как унарное тождество. Это показывает, что § может иметь конечный базис тождеств, даже если (в, •) была бесконечно базируемой. Итоговый результат от взаимовлияния этих двух эффектов в общем случае сложно предсказать, и, в действительности, оба возможных исхода имеют место. Это означает, что существуют такие унарные полугруппы, даже группы 3 = (С; - ,-1) с операцией обращения, взятой в качестве унарной операции, что 3 является конечно базируемой (бесконечно базируемой) как группа, тогда как редукт ((7; •) бесконечно (соответственно, конечно) базируем как полугруппа. Так, например, базис тождеств группы (а, Ъ \ аЪ2а = 1) состоит из единственного тождества х2у2 = у2х2, но при этом, как показал Дж. Избелл [18], эта группа бесконечно базируема как полугруппа. С другой стороны, сплетение бесконечной относительно свободной группы экспоненты 4 со счетно порожденной свободной абелевой группой бесконечно базируемо как группа, как показал Ю.Г. Клейман [4]. Однако это сплетение конечно базируемо как полугруппа, что следует из результатов В. В. Беляева и Н. Ф. Сесекина [1].

Вопрос о соотношении конечной базируемости унарной полугруппы и ее редукта до сих пор не исследовался систематически в контексте конечных полугрупп. Насколько нам известно, первый пример бесконечно базируемой конечной унарной полугруппы с конечно базируемым редуктом был построен только в 1998 г. в работе Дж. Лоуренса и Р. Уилларда [27]. Унарная операция, использовавшаяся в [27], имела скорее вспомогательное значение, и другие примеры унарных операций с подобными свойствами (включая пример бесконечно базируемой конечной инволюторной полугруппы с конечно базируемым редуктом) появились лишь недавно в статье М. Джексона и М. В. Волкова [24]. Более того, упомянутая выше полугруппа из [27], фактически, существенно бесконечно базируема, и, таким образом, в общем случае существенно бесконечно базируемая унарная полугруппа может обладать конечно базируемым редуктом. Это, тем не менее, невозможно для конечной инволюторной полугруппы. В самом деле, как будет показано в диссертационной

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

Обратное утверждение не верно. Рассмотрим, например, упомянутый в параграфе 1° моноид Брандта (В\, •). Известно [6, следствие 6.1], что моноид Брандта существенно бесконечно базируем (фактически, это был первый пример существенно бесконечно базируемой полугруппы). Моноид Брандта можно снабдить естественной инволюцией, а именно, стандартным матричным транспонированием А 1-4 Ат. Однако инволюторная полугруппа (В\,-,т) уже не будет существенно бесконечно базируемой, как показано в [39]. Другие примеры можно найти в [13]: если % — конечное поле, а МП(ЗС) обозначает множество всех п х п-матриц над ЗС, то полугруппа (МП(ЗС),-) существенно бесконечно базируема для любого п > 2 в соответствии со следствием 6.2 из [6], тогда как инволюторная полугруппа (М2(ЗС), •,т) не будет существенно бесконечно базируемой, если количество элементов ъ% при делении на 4 дает 3 в остатке. Именно это обстоятельство породило указанный выше вопрос о наследовании свойства существенной бесконечной базируемости при добавлении инволюции. Отметим также, что совсем недавно в [28] Э. Ли привел пример конечно базируемой конечной инволюторной полугруппы с бесконечно базируемым редуктом, то есть в общем случае даже обычная бесконечная базируемость не обязана сохраняться при добавлении инволюции.

Задача 4. Найти условия, при которых инволюция х н4 х*, определенная на существенно бесконечно базируемой полугруппе (Б, •), сохраняет этот вид базируемости на инволюторной полугруппе 8 = (Б,-,*).

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

Диссертация состоит, помимо введения, из трех глав и списка литературы. Нумерация теорем, предложений и следствий двойная. Первое число соответствует номеру главы, второе — номеру утверждения. Основные результаты диссертации решают задачи 1-4, поставленные в параграфах 2° и 3°.

В главе 1 рассматривается взаимосвязь между псевдомногообразием, порожденным серией моноидов ТМп{(Т), и классом моноидов, удовлетворяющих соотношению М = Ж'. В §1.1 приводятся вспомогательные понятия и утверждения. В частности, доказывается, что каждый моноид ТМп(С) удовлетворяет соотношению = Ж. Помимо этого, на произвольном моноиде, удовлетворяющем этому соотношению, исследуются свойства конгруэнции порожденной отношением которые необходимы для доказательства основного результата главы. Основным результатом главы 1 является следующая теорема, решающая поставленную задачу 1.

Теорема 1.1. Всякий конечный моноид, удовлетворяющий соотношению & = Ж, делит моноид ТМп(0) для подходящей группы С и подходящего натурального п.

Доказательству теоремы 1.1 посвящен §1.2. Отметим, что доказательство проводится конструктивно: группа С и размер матриц п эффективно вычисляются по данному конечному моноиду Б. Идейная основа для доказательства аналогична доказательству теоремы II: для каждого элемента моноида в рассматривается его направленное действие на определенном частично упорядоченном множестве. В случае «^-тривиальных моноидов конгруэнция совпадает с отношением и в качестве частично упорядоченного множества берется множество одноэлементных ^-классов. Каждый элемент моноида действует на этом множестве умножением справа. В общем случае, рассматриваемом в теореме 1.1, роль частично упорядоченного множества играет фактор-моноид Б/З^. Приведенный алгоритм построения группы (7, подмоноида ТМП(С?) и соответствующего гомоморфизма реализован на серии примеров в §1.3. Теорема 1.1 представляет собой аналог теорем I и II для класса моноидов, удовлетворяющих соотношению = Ж. Из нее следует, что серия моноидов ТМП(С) и класс моноидов, удовлетворяющих соотношению ^ = Ж, порождают одно и то же псевдомногообразие. Обозначим это псевдомногобразие через КН.

В главе 2 исследуется разрешимость псевдомногообразия Г1Н. Первым

результатом главы является следующая теорема, идентифицирующая псевдомногообразие ИН с полупрямым произведением псевдомногообразия всех конечных групп в на псевдомногообразие всех конечных «^-тривиальных моноидов II.

Теорема 2.1. РШ = С * Я.

Изучению полупрямого произведения псевдомногообразий посвящено значительное количество работ, см. [8-11,25,37], в том числе связанных с псевдомногообразиями групп и «^"-тривиальных моноидов. Полученное в теореме 2.1 представление позволяет воспользоваться мощным подходом, который был разработан Б. Тилсоном. В [45] Тилсон рассмотрел категории как алгебраические структуры и обобщил с помощью них многие понятия и операции из теории полугрупп. В частности, он разработал критерий разрешимости псевдомногообразия вида V * Специализируя этот результат для псевдомногообразия С * К, мы получаем алгоритмически проверяемый критерий того, что данный конечный моноид принадлежит псевдомногообразию КН. Для его формулировки приведем необходимые определения.

Определенную выше конгруэнцию назовем «^"-минимальной, если для произвольного фиксированного «^-класса ф любой «^"-класс, лежащий в ф, минимален во множестве всех «^"-классов, лежащих в (5, относительно стандартного частичного порядка ^ на множестве «^"-классов моноида Б: Яа ^ Яь тогда и только тогда, когда аБ С ЬБ, а,Ь е Б. Также для произвольного

класса Н обозначим через Ртг(Н) множество элементов, поточечно стабилизирующих Н при умножении справа: Риог(Н) = {х £ Б | кх = к для любого Н е Н}. Основным результатом главы 2 является следующая теорема, решающая поставленную задачу 2.

Теорема 2.2. Конечный моноид Б принадлежит псевдомногообразию ИН тогда и только тогда, когда конгруэнция является минимальной на Б и для произвольного -класса ф множества Ргиг(Н) совпадают для всех Ж-классов Н С

Доказательству теоремы 2.2 посвящен §2.2. Несколько следствий этой теоремы приводится в §2.3. В частности, следствие 2.6 обобщает результат теоремы 1.1 с класса моноидов, удовлетворяющих соотношению^ = Л?, на все псевдомногообразие RH.

Список литературы диссертационного исследования кандидат наук Первухина, Татьяна Вячеславовна, 2014 год

Литература

[1] Беляев B.B. Свободные подполугруппы в разрешимых группах / В. В. Беляев, Н. Ф. Сесекин // Мат. зап. УрГУ. Исслед. по соврем, алгебре. 1981. Т. 12. № 3. С. 13-18.

[2] Волков М.В. О конечной базируемости многообразий полугрупп / М.В. Волков // Мат. заметки. 1989. Т. 45. С. 12-23.

[3] Волков М.В. Тождества полугрупп треугольных матриц над конечными полями / М.В. Волков, И. А. Гольдберг // Мат. заметки. 2003. Т. 73. № 4. С. 502-510.

[4] Клейман Ю. Г. О базисе произведения многообразий групп / Ю. Г Клейман // Изв. АН СССР. Сер. матем. 1973. Т. 37. № 1. С. 95-97.

[5] Лаллеман Ж. Полугруппы и комбинаторные приложения / Ж. Лалле-ман // М.: Мир. 1985. 440 с.

[6] Сапир М.В. Проблемы бернсайдовского типа и конечная базируемость в многообразиях полугрупп / М. В. Сапир // Изв. АН СССР. Сер. матем. 1987. Т. 51. № 2. С. 319-340.

[7] Сапир М.В. Существенно бесконечно базируемые полугруппы / М.В. Сапир // Мат. Сб. 1987. Т. 133. № 2. С. 154-166.

[8] Almeida J. Finite semigroups and universal algebra / J. Almeida // Singapore: World Scientific. 1994. 511 p.

[9] Almeida J. On iterated semidirect product of finite semilattices / J. Almeida // J. Algebra. 1991. Vol. 142. P. 239-254.

[10] Almeida J. Semidirect product of pseudovarieties from the universal algebraist's point of view / J. Almeida //J- Pure and Applied Alg. 1989. Vol. 60. P. 113-128.

[11] Almeida J. Sintactic and global semigroup theory: a synthesis approach / J. Almeida, B. Steinberg // Algorithmic Problems in Groups and Semigroups. Trends in Mathematics. 2000. P. 1-23.

[12] Amitsur S. A. Polynomial identities / S. A. Amitsur // Israel J. Math. 1974. Vol. 19. P. 183-199.

[13] Auinger K. Matrix identities involving multiplication and transposition / K. Auinger, I. Dolinka, M.V. Volkov // J. Europ. Math. Soc. 2012. Vol. 14. № 3. P. 937-969.

[14] Burris S. A Course in universal algebra / S. Burris, H.P. Sankappanavar// Berlin: Springer. 1981. 276 p.

[15] D'Amour A. ^-Polynomial identites of matrices with the transpose involution: the low degrees /A. D'Amour, M. Racine // Trans. Amer. Math. Soc. 1999. Vol. 351. P. 5089-5106.

[16] D'Amour A. *-Polynomial identites of matrices with the symplectic involution: the low degrees /A. D'Amour, M. Racine // Comm. Algebra. 2004. Vol. 32. P. 895-918.

[17] Dolinka I. On identities of finite involution semigroups / I. Dolinka // Semigroup Forum. 2010. Vol. 80. № 1. P. 105-120.

[18] Isbell J. R. Two examples in varieties of monoids / J. R. Isbell // Proc. Cambridge. Philos. Soc. 1970. Vol. 68. P. 265-266.

[19] Fajtlowicz S. Equationally complete semigroups with involution / S. Fajtlowicz // Alg. Universalis. 1972. Vol. 1. № 1. P. 355-358.

[20] Giambruno A. On ^-polynomial identities for n x n-matrices / A. Giambruno // J. Algebra. 1990. Vol. 133. P. 433-438.

[21] Goldberg I. A. The finite basis problem for monoids of triangular boolean matrices / I. A. Goldberg, M.V. Volkov // In: Algebraic Syst. Formal Lang, and Convent, and Unconvent. Comput. Theory. Research Inst. Math. Sci. Kyoto Univ. Kyoto. 2004. P. 205-214.

[22] Golubchik I. Z. A note on varieties of semiprime rings with semigroup identities / I.Z. Golubchik, A.V. Mikhalev //J. Algebra. 1978. Vol. 54. P. 42-45.

[23] Howie J.M. Fundamentals of Semigroup Theory / J.M. Howie // Oxford: Clarendon Press. 1995. London Mathematical Society Monographs. Vol. 12.

[24] Jackson M. The algebra of adjacency patterns: Rees matrix semigroups with reversion / M. Jackson, M.V. Volkov // In: Fields of Logic and Comput., Lect. Notes in Comput. Sci. 2010. Vol. 6300. P. 414-443.

[25] Karnofsky J. Decidability of complexity one-half for finite semigroups / J. Karnofsky, J. Rhodes // Semigroup Forum. 1992. Vol. 24. P. 55-66.

[26] Lallement G. Regular semigroups with Q) = ^ as syntactic monoids of finite prefix codes / G. Lallement // Theoretical Computer Science. 1997. Vol. 3. P. 35-49.

[27] Lawrence J. On finitely based groups and nonfinitely based quasivarieties / J. Lawrence, R. Willard // J. Algebra. 2008. Vol. 203. № 1. P. 1-11.

[28] Lee E. W. H. Finitely based finite involution semigroups with non-finitely based reducts / E.W. H. Lee // Preprint.

[29] Li J.R. On the finite basis problem for the monoids of triangular boolean matrices / J.R. Li, Y. F. Luo // Alg. Universalis. 2011. Vol. 65. R 353-362.

[30] Lidl R. Finite Fields / R. Lidl, H. Niederreiter // Cambridge: Cambridge University Press. 1997. 755 p.

[31] Nambooripad K. S. S. Regular involution semigroups /K. S. S. Nambooripad, F. Pastijn // In: Semigroups (Szeged, 1981), Colloquia Mathematica Societatis Janos Bolyai. 1985. Vol. 39. P. 199-249.

[32] Oates S. Identical relations in finite groups / S. Oates, M.B. Powell //J. Algebra. 1964. Vol. 1. P. 11-39.

[33] Pastijn F. ^-compatible semigroup varieties / F. Pastijn, M.V. Volkov // J. Algebra. 2006. Vol. 299. P. 62-93.

[34] Perkins P. Bases for equational theories of semigroups / P. Perkins // J. Algebra. 1969. Vol. 13. № 2. P. 298-314.

[35] Pin J.-E. Relational morphisms, transductions and operations on languages / J.-E. Pin // Lecture Notes in Computer Science. 1989. Vol. 386. P. 34-55.

[36] Pin J.-E. Varieties of formal languages / J.-E. Pin // London: North Oxford Academic Publishers. 1986. 148 p.

[37] Rhodes J. The q-theory of finite semigroups / J. Rhodes, B. Steinberg // New York: Springer. 2009. 666 p.

[38] Rowen L. H. Polynomial identities in ring theory / L. H. Rowen // New York-London: Academic Press. 1980. 382 p.

[39] Sapir M.V. Identities of finite inverse semigroups / M.V. Sapir // Internat. J. Algebra Comput. 1993. Vol. 3. № 1. P. 115-124.

[40] Schiitzenberger M. P. On finite monoids having only trivial subgroups / M. P. Schiitzenberger // Inf. Control. 1965. Vol. 8. P. 190-194.

[41] Serre J.-P. Cours d'Arithmetique / J.-P. Serre // Paris: Presses Universitaires de France. 1994. 192 p.

[42] Simon I. Piecewise testable events / I. Simon // Lect. Notes in Comput. Sci (Proc. 2nd GI Conf.) 1975. Vol. 33. P. 214-222.

[43] Stiffler P. Extension of the fundamental theorem of finite semigroups / P. Stiffler // Advances in Math. 1973. Vol. 11. P. 159-209.

[44] Straubing H. On finite ^-trivial monoids / H. Straubing // Semigroup Forum. 1980. Vol. 19. P. 107-110.

[45] Tilson B. Categories as algebra: an essential ingredient in the theory of monoids / B. Tilson //J. Pure and Applied Algebra. 1987. Vol. 48. P. 83-198.

[46] Trotter P. G. The finite basis problem in the pseudovariety joins of aperiodic semigroups with groups / P. G. Trotter, M.V. Volkov // Semigroup Forum. 1996. Vol. 52. P. 83-91.

[47] Volkov M.V. The finite basis problem for finite semigroups / M.V. Volkov // Sci. Math. Jpn. 2001. Vol. 53. № 1. P. 171-199.

Работы автора по теме диссертации

Публикации автора по теме диссертации, опубликованные в ведущих рецензируемых журналах, определенных ВАК

[48] Первухина Т. В. Структура конечных моноидов, удовлетворяющих соотношению Зё = Ж / Т. В. Первухина // Тр. Ин-та математики и механики УрО РАН. 2013. Т. 19. № 4. С. 181-191.

[49] Первухина Т. В. О псевдомногообразии, порожденном всеми конечными моноидами со свойством M = Ж / Т. В. Первухина //Тр. Ин-та математики и механики УрО РАН. 2014. Т. 20. № 1. Р. 215-220.

[50] Pervukhina T.V. Unary enhancements of inherently non-finitely based semigroups / K. Auinger, I. Dolinka, T.V. Pervukhina, M.V. Volkov // Semigroup Forum. 2014. Vol. 89. Issue 1. P. 41-51.

Другие публикации

[51] Первухина Т. В. Тождества инволюторных полугрупп треугольных матриц над конечными полями / М. В. Волков, Т. В. Первухина // Алгебра и линейная оптимизация: Тез. Междунар. конф., посвящ. 100-летию С.Н. Черникова, Екатеринбург, 14-19 мая 2012 г. Екатеринбург: ИММ УрО РАН. 2012. С. 42-43.

[52] Первухина Т. В. О структуре полугрупп, на которых совпадают отношения Грина & и Ж / Т. В. Первухина // Совр. пробл. матем.: Тез. 42-й Всерос. молодеж. школы-конф. Екатеринбург, 30 янв.-б фев. 2011 г. Екатеринбург: ИММ УрО РАН. 2011. С. 231-232.

[53] Pervukhina T.V. On identities of involution semigroups of triangular matrices over a finite field / K. Auinger, I. Dolinka, T.V. Pervukhina, M.V. Volkov // Semigroups and applications: материалы междунар. конф., Уппсала, 30 авг.-1 сент. 2012 г. 2012. Published online: http://www.math.uu.se/digitalAssets/127/127399_pervukhinatv_full.pdf

[54] Pervukhina T.V. Structure of finite monoids satisfying«^ — Ж j T.V. Pervukhina // Материалы 84-го рабоч. совещ. по общ. алгебре ААА84, Дрезден, 8-10 июня 2012 г. 2012. С. 19.

[55] Pervukhina Т. V. Pseudovariety generated by finite monoids satisfying the relation «^ = Ж / Т. V. Pervukhina // Алгебра и комбинаторика: Тез. Междунар. конф., посвящ. 60-летию А. А. Махнева, Екатеринбург, 3-7 июня 2013 г. Екатеринбург: ИММ УрО РАН. 2013. С. 169-170.