Псевдооперации и псевдосвободные полугруппы

• Автор: Жильцов, Илья Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Екатеринбург
• Количество страниц: 148 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
1. Комбинаторика слов
2. Переписывающие системы
3. Проблема равенства слов в бернсайдовых многообразиях
4. Полугруппы
5. Унарные слова и унарно-полу групповые тождества
6. Псевдосвободные полугруппы
Глава 1. У.П.-ТОЖДЕСТВА НА МНОГООБРАЗИИ §
§1. УНАРНЫЕ СЛОВА ВЫСОТЫ <1
1.1. Связь с бернсайдовыми многообразиями
1.2. О зацеплении подслов
1.3. Нормальные унарные слова высоты <1
1.4. Доказательство теоремы
§2. ПРИМИТИВНЫЕ УНАРНЫЕ СЛОВА
2.1. Факторизации Z-cлoв
2.2. Е-слова, определяемые нормальными унарными словами
2.3. Доказательство критерия примитивности
§3. ВПОЛНЕ ПРИМИТИВНЫЕ УНАРНЫЕ СЛОВА
§4. НОРМАЛЬНЫЕ УНАРНЫЕ СЛОВА ВЫСОТЫ <2
4.1. Леммы о й-образах нормальных унарных слов
4.2. Доказательство предложения
§5. -ПРИВЕДЕННЫЕ ФОРМЫ -ОБРАЗОВ
§6. ПРИВЕДЕННЫЕ ФОРМЫ ГОБРАЗОВ
6.1. Структура Г-образа
6.2. Слова ер и их свойства
6.3. Структура Г-образа
6.4. Доказательство предложения
6.5. Доказательства теорем
Глава 2. АРХИМЕДОВЫ ПОЛУГРУППЫ
§7. СТРОЕНИЕ ПОЛУГРУПП ЩШт
7.1. Конструкция специальной архимедовой полугруппы
7.2. Свойства специальных архимедовых полугрупп
7.3. Комментарии
§8. ПРИЛОЖЕНИЕ
8.1. ЬИт-распозна,ваемые языки
8.2. Псевдосвободные полугруппы ранга
БИБЛИОГРАФИЯ
АЛФАВИТНЫЙ УКАЗАТЕЛЬ
ВВЕДЕНИЕ
1° Псевдомногообразием называется класс конечных универсальных алгебр, замкнутый относительно взятия подалгебр, гомоморфных образов и конечных прямых произведений. Большой интерес к изучению псевдомногообразий полугрупп и моноидов связан с одним из центральных результатов теории автоматов и формальных языков — теоремой Эйленберга [18]. В этой теореме устанавливается взаимно однозначное соответствие между псевдомногообразиями полугрупп (или моноидов) и так называемыми потоками рациональных языков, что позволяет использовать при изучении формальных языков методы теории полугрупп. При этом псевдомногообразия полугрупп [соотв., моноидов] возникают, если формальный язык определяется как подмножество свободной полугруппы [соотв., свободного моноида].
Несмотря на всю схожесть структурных определений псевдомногообразий и многообразий, долгое время методы исследования этих объектов значительно разнились. В первую очередь это связано с тем, что для псевдомногообразий неверен прямой аналог теоремы Биркгофа об аксиоматизируемости тождествами любого многообразия, а также с тем, что псевдомногообразия, как правило, не содержат даже конечнопорожденных (относительно) свободных алгебр. Положение дел начало меняться, когда в 1982 году Я. Рейтерман [29] предложил использовать для задания псевдомногообразий введенные им псевдооперации.
Поскольку в диссертации затрагиваются только псевдомногообразия полугрупп, приведем основные определения, ограничиваясь лишь полугрупповым случаем. Для натурального числа п и псевдомногообразия полугрупп V п-арной псевдооперацией (или неявной операцией) над V называется такое семейство отображений ж = {яя | б'бУ}, что:
• 7Г£ — всюду определенное отображение из 5" в 5;
• 7Г устойчиво относительно гомоморфизмов из V, т. е. для каждой пары 5, Т полугрупп из ¥, любого гомоморфизма <р : Б —* Т и любых элементов ах
ът{ч>(а), , <р(ап)) = <р(1Г3(а1, , «»))
На множестве Пп¥ всех п-арных псевдоопераций над ¥ задают операцию умножения, сопоставляя каждым ж, а € ПЯУ элемент ж о € Пп¥, определяемый следующим условием: для любой полугруппы 5е¥ и любых элементов аг, а2,.. , ап(ЕЗ
(тгсфДах
Отметим, что данная операция ассоциативна. Полугруппу Пп¥ наделяют инициальной топологией относительно семейства всех гомоморфизмов в полугруппы

из V (как в дискретные полугруппы), т. е. наименьшей топологией, при которой все указанные гомоморфизмы непрерывны. После введения такой топологии полугруппа Пге¥ становится топологической полугруппой. Она называется псев-досвободной полугруппой ранга п псевдомногообразия ¥. Псевдотождество.м над ¥ называют формальное равенство псевдоопераций над ¥. (Для обозначения всевозможных формальных равенств всюду далее используется символ =.) Говорят, что конечная полугруппа ,5Д¥ удовлетворяет псевдотождеству ж=а над ¥, если жз=<тз- Множество псевдотождеств П над ¥ называют базисом псевдотомсдеств подпсевдомногообразия Ш в V, если конечная полугруппа из ¥ принадлежит Щ тогда и только тогда, когда она удовлетворяет всем псевдотождествам из П. В своей работе Я. Рейтерман, существенно используя топологию, показал, что любое подпсевдомногообразие произвольного псевдомногообразия ¥ имеет базис псевдотождеств над ¥ ([29, теорема 3.1], см. также [16], [6, теорема 3.5.1.], [22]). Именно этот результат предоставил принципиальную возможность применить к теории псевдомногообразий богатый арсенал синтаксических методов исследования из теории многообразий. Первым успехом можно считать работу Алмейды и Азеве-до [12], в которой вычислено решеточное объединение псевдомногобразий К и I всех конечных 7?.-тривиаль:ных и, соответственно, -тривиальных полугрупп. Отметим также два наиболее ярких последних достижения, полученных при помощи псевдоопераций:
• Марголис, Сапир и Вейль [25] доказали, что псевдомногобразие В всех конечных полугрупп и псевдомногобразие А всех конечных апериодических полугрупп не представимы в виде объединения, прямого произведения и мальцевского произведения собственных подпсевдомногообразий;
• Алмейда [9] нашел способ определения экспоненты неперестановочного апериодического псевдомногообразия, т. е. числа применений оператора степени, достаточного, чтобы получить из исходного псевдомногообразия псевдомногообразие В (под степенью псевдомногообразия мы подразумеваем псев-домногообразие, порожденное глобальными надполугруппами полугрупп исходного псевдомногообразия);
Только что перечисленные, а также многие другие результаты склоняют к мысли, что столь полезные инструменты, как псевдооперации и псевдосвободные полугруппы (и моноиды) достойны изучения сами по себе. Более того, в настоящее время этой проблематике посвящено уже, достаточно много работ. Этой же теме посвящена и данная диссертация.
Конкретно, нас будут интересовать следующие два направления:
• изучение некоторых наиболее часто используемых псевдоопераций псевдомногообразия В, так называемых сэ-псевдоопераций (определение ниже);

а(—3) а(-2) а( —1) а(0) а(1) а(2) н

Подсловом в Ъ-слове а называют слово вида а[г, г2] = а(гі)а(гі + !) <т(г2) для таких целых гх,г2, что Г < г2, и обозначают на диаграмме так:
П Г2
Пусть г — целое число и (ия)я£2, — семейство слов над алфавитом А, содержащее бесконечное подсемейство непустых слов. Будем говорить, что 2-слово а обладает факторизацией (ия)я со сдвигом г, если его диаграмма имеет следующий вид:
4 3 И_ 2 И-1 «0 М1 «2 и3
• С у ' V у у у у у б

т. е. для всех г>1 выполнены равенства
а Г+|мо| + |и1|+ --ui~i |, Г+ |мо| + |и11+ ' ' ' + |ыг-1 | + |ы* | — 1 ] — иг,
а[ г—|а_г|
а[ Г, г+|и0|-1 ] = и0, Г—г-1 ] = и_!.
Скажем, что Z-cлoвo а является и-периодическим. если оно обладает такой факторизацией (и9)?ег5 что ид — и для всех д € Z. Очевидно, что в этом случае 2-слово а является | гг периодическим отображением.
Замечание 2.3. Если для некоторых примитивных слов и и V Ъ-слово является как и-, так и и-периодическим, то, ввиду его “бесконечности”, согласно лемме 0.1 слова и и V сопряжены.
Пусть ( = Що(г)1)'ш1(г’2)и'№2 — непустое унарное слово высоты <
г > 1. Опре диаграммой:
гщ и* го,

и к > 1. Определим Z-cлoвo ( и его факторизацию Ф0 со сдвигом 0 следующей
гоо «Ч ик гщ гоо гої
Обозначим через а единственное примитивное слово, степенью которого является слово Ясно, что Z-cлoвo обладает факторизацией Фх, которая отличается от Ф0 лишь сдвигом, равным длине слова а:

Фо щ0 У{ Ю1
г~ У У У 1
ж К К > к л А
ь; ш, и> о гф гщ
Аналогично, для целого і обозначим через Ф4 факторизацию Z-cлoвa ( , ко-
торая отличается от Ф0 лишь сдвигом, равным і |а|. Отметим, что если а = то все факторизации Фх, Ф2, Фз, и Ф_х, Ф_2, Ф_3