Введение к работе
Актуальность темы. Комбинаторика слов является важным и быстро растущим направлением современной математики. Она изучает различные свойства конечных и бесконечных последовательностей символов. Такие последовательности обычно называют словами, а символы, которые используются для записи слов, — буквами.
В качестве примера источника задач, связанных с изучением таких последовательностей, можно привести молекулярную биологию. Как известно, генетическая информация в любом живом организме зашифрована в молекулах ДНК, которые представляют собой конечные цепочки-слова над алфавитом из четырех букв-нуклеотидов. Важнейшими комбинаторными вопросами в этой области будут расшифровка способов кодирования, хранения, восстановления, считывания и записи генетической информации. Другая, даже более обширная область, которая использует изучение свойств слов, — это компьютерные науки. Вся информация в современных компьютерах организована в виде файлов, а каждый файл в конечном счете представляет собой некоторое слово, состоящее из нулей и единиц. Среди направлений информатики, в которых применяется комбинаторика слов, можно отметить криптографию, сжатие и восстановление данных, теорию формальных языков и теорию автоматов.
Комбинаторика слов имеет много приложений и в математике. Морс и Хедлунд использовали её в своих исследованиях по символической динамике [19]. Также можно отметить применение комбинаторики слов Шют-ценберже в его основополагающих работах по теории кодирования [11].
Особенно важными оказались применения комбинаторики слов в алгебре. Новиков и Адян [1,5] использовали комбинаторный подход для построения бесконечных конечнопорожденных периодических групп (контрпримеров к проблеме Бернсайда для групп). Ширшовым [9] чисто комбинаторными методами была доказана теорема о высоте для ассоциативных колец, удовлетворяющих некоторому полиномиальному тождеству. Из этой теоремы следует положительное решение проблемы Куроша для таких колец. Отметим, что в обоих случаях новый подход привел к решению многих важных алгебраических задач. Например, Зельманов [2] применял комбинаторику слов для исследования проблем бернсайдов-ского типа для йордановых алгебр.
Еще раньше комбинаторика слов нашла свое применение и в теории полугрупп. В работах Морса и Хедлунда [19] и Вина, Эренфойхта
и Макналти [10] в качестве контрпримера для проблем бернсайдовского типа для полугрупп строятся бесконечные конечнопорожденные полугруппы, удовлетворяющие 0-приведенным тождествам. Помимо структурных свойств многообразий полугрупп, комбинаторика слов применялась к исследованиям вопросов конечной базируемости Сапиром [6,21].
Во всех работах, в которых используется комбинаторный подход к решению алгебраических задач, приходится проводить сложные исследования свойств слов, что зачастую приводит к интересным результатам в рамках комбинаторики слов. Поэтому взаимодействие алгебры и комбинаторики слов обогащает обе теории.
В диссертации при помощи комбинаторных методов решается одна алгебраическая задача, связанная с решетками многообразий полугрупп; ее решение потребовало систематического анализа некоторых тонких вопросов, связанных с избегаемостью слов и тождеств.
Целью работы является классификация многообразий полугрупп, у которых решетка подмногообразий обладает некоторым свойством универсальности. Назовем многообразие полугрупп V решеточно универсальным, если в его решетку подмногообразий L(V) можно вложить решетку, дуальную решетке разбиений некоторого счетного множества. Из решеточной универсальности многообразия следует, что его решетка L(V) является сложной в следующем смысле: в нее можно вложить решетку подмногообразий произвольного многообразия универсальных алгебр не более чем счетного типа.
В 1971 году Баррис и Нэльсон [12] показали, что многообразие полугрупп, удовлетворяющее тождеству х2 ~ж3, является решеточно универсальным. Немного позже Ежек [17] доказал, что подмногообразие этого многообразия, заданное тождеством х2 ~0, также решеточно универсально.
В диссертации результаты Барриса-Нэльсон и Ежека обобщаются максимально возможным образом. А именно, устанавливается критерий решеточной универсальности многообразий, заданных произвольной системой тождеств от конечного числа переменных, не выполняющейся ни в какой бесконечной конечнопорожденной периодической группе. В ней приводится доказательство критерия решеточной универсальности многообразий полугрупп в терминах избегаемых тождеств.
Для доказательства основного результата проводятся комбинаторные исследования свойств избегаемых тождеств. Для каждого натурального
числа п строится бесконечная антицепь Мп слов над подходящим конечным алфавитом, каждый элемент которой избегает любой избегаемый шаблон, содержащий не более п переменных. Также доказывается, что каждое слово антицепи Мп является изотермом для пары шаблонов (р, q) такой, что тождество р ~ q избегаемо и содержит не более п переменных.
Научная новизна. Все результаты являются новыми.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в комбинаторике слов и теории полугрупп.
Апробация результатов работы. Основные результаты диссертации докладывались на международных конференциях по комбинаторике слов WORDS (Марсель, 2007; Салерно, 2009); международной школе по алгебраической теории автоматов SATA2008 (Лиссабон, 2008); на семинарах университетов Турку (2009) и Лиссабона (2009); на научном семинаре «Алгебраические системы» под руководством Л.Н. Шеврина (УрГУ, 2010); на семинаре «Компьютерные науки» (УрГУ, 2007-2010); на алгебраическом семинаре под руководством Л.М. Мартынова (ОмГПУ, Омск, 2010).
Публикации
Основные результаты диссертации опубликованы в [25-29]. В совместных работах [26,27] М.В. Волкову принадлежат постановка задачи и общая схема доказательства, а автору диссертации принадлежит реализация и проработка доказательства. В тезисах [29] анонсированы результаты, опубликованные в [25]. Работа [27] опубликована в издании, входящем в перечень, утвержденный ВАК.
Структура и объем диссертации Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации составляет 59 страниц. Библиографический список содержит 61 наименование.