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

• Михайлова, Инна Анатольевна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Михайлова, Инна Анатольевна

Введение

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

1.1 Избегаемые шаблоны.

1.2 Свободные стирания и морфизмы.

1.3 Последовательность, которая избегает все избегаемые шаблоны над п-буквенным алфавитом.

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

2 Шаблоны, избегаемые палиндромами

2.1 Последовательность палиндромов.

2.2 Лемма о маркерах.

2.3 Последовательности свободных стираний.

2.4 Основная теорема.

2.5 Индексы избегаемое™.

3 Избегаемые тождества и антицепи слов

3.1 Антицепи слов и избегаемые шаблоны

3.2 Решеточная универсальность многообразий полугрупп, заданных О-приведенными тождествами.

3.3 Изотермы и избегаемые тождества.

3.4 Антицепи слов и избегаемые тождества.

4 Классификация решеточно универсальных многообразий 49 Предметный указатель 53 Список литературы

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

В данной работе под алфавитом понимается непустое множество. Как правило, мы рассматриваем конечные алфавиты; в случае, когда возникает бесконечный алфавит, это будет оговариваться особо. Элементы алфавита называются буквами. Основным объектом наших исследований будут слова, которые мы рассматриваем, с одной стороны, как конечные последовательности букв некоторого алфавита Е, а с другой — как элементы свободной полугруппы Е+ над этим алфавитом. В качестве примера источника задач, связанных с изучением таких последовательностей, можно привести молекулярную биологию. Как известно, генетическая информация в любом живом организме зашифрована в молекулах ДНК, которые представляют собой конечные (хотя и очень длинные) цепочки-слова над алфавитом из четырех букв-нуклеотидов. Важнейшими (но не единственными) комбинаторными вопросами в этой области будут расшифровка способов кодирования, хранения, восстановления, считывания и записи генетической информации. Другая, даже более обширная область, которая использует изучение свойств слов, — это компьютерные науки. Вся информация в современных компьютерах организована в виде файлов, а каждый файл в конечном счете представляет собой некоторое слово, состоящее из нулей и единиц. Среди направлений информатики, в которых применяется комбинаторика слов, можно отметить криптографию, сжатие и восстановление данных, теорию формальных языков и теорию автоматов.

Норвежский математик Аксель Туэ (1863-1922), который одним из первых начал изучать свойства последовательностей букв, считается основателем современной комбинаторики слов. В своих работах 1906 года [53] и 1912 года [54] он исследовал выразительные возможности алфавитов из двух и трех символов (в первую очередь на выбор размера алфавитов повлияло появление таких средств коммуникации, как телеграф и радио). Туэ принадлежит ряд крупных достижений в различных разделах математики, однако его статьи по комбинаторике слов оставались незамеченными в течение почти полувека после публикации, поэтому многие результаты из этих статей переоткрывались иногда не по одному разу. В качестве примера такого «открытия» можно привести наиболее известное множество слов во всей комбинаторике — это слова Туэ-Морса. Туэ в [53] построил эти слова и показал, что они не содержат трех последовательно входящих одинаковых блоков. Почти через 40 лет

Морс и Хедлунд [45], ничего не зная о работах Туэ, переоткрыли этот результат в своих исследованиях по динамическим системам.1

Туэ считал, что развитие комбинаторики слов приведет к появлению интересных результатов не только внутри самой теории, но и в различных ее приложениях. Как оказалось позднее, эти ожидания более чем подтвердились. В последние несколько десятков лет комбинаторика слов разрослась в самостоятельную математическую дисциплину, содержащую большое количество разделов (подробнее с ними можно ознакомиться, например, в монографиях [31,42,43]). Свидетельством определенной зрелости этой дисциплины является выделение ей отдельного кода 68Д15 в широко используемой в математической литературе классификации М5С2010.

Уже в пионерских работах по комбинаторике слов рассматривается одно из важнейших свойств слов — избегаемость. Будем говорить, что непустое слово ги над алфавитом Е содержит слово V над (возможно другим) алфавитом Д, если существует такой морфизм к : Д+ н-> Е+, что слово Н{у) является подсловом и). Слово у е Д+ избегаемо, если найдется такой конечный алфавит Е и бесконечная последовательность слов {шг}{е/ С Е+ таких, что все слова ги$ не содержат v. Например, как следует из упомянутых выше результата Туэ, слово х3 избегаемо, а соответствующее множество слов — это последовательность Туэ-Морса. С последними достижениями в теории избегаемых слов можно ознакомиться, например, по обзору [35]. Именно феномен избегаемости и его алгебраические приложения играют ключевую роль а данной работе.

Как и предсказывал Туэ, новые идеи постепенно нашли применение в различных областях математики. Так с 50-х годов прошлого века Шют-ценберже (см. [24]) начал использовать комбинаторику слов в своих основополагающих работах по теории кодирования.

Особенно важными оказались приложения комбинаторики слов и, в частности, теории избегаемости в алгебре. В 1902 году Бернсайд сформулировал следующую проблему: верно ли, что любая конечнопорожден-ная группа, в которой у каждого элемента конечный порядок, конечна? Проблема Бернсайда и связанные с ней задачи во многом определили развитие алгебры в двадцатом веке. Долгое время усилия были направ

1 Справедливости ради следует отметить, что сами слова, называемые теперь сло-вами-Туэ-Морса, впервые появились в работе Пруэ [47] по теории чисел, но отмеченное выше ключевое свойство этих слов обнаружил именно Туэ. лены на положительное решение данной проблемы, но затем Голод и Ша-фаревич [4] построили контрпример. В работе Новикова и Адяна [1,10] был предложен другой способ нахождения контрпримеров, развитие которого в дальнейшем привело к решению целого ряда важных проблем теории групп. В [10] описывалось построение некоторых групп, удовлетворяющих тождеству хп ~ 1 для нечетных п больших 4381, а бесконечность этих групп выводилась в конечном итоге из существования бесконечной последовательности слов над трехбуквенным алфавитом, не содержащей квадратов. (Новиков и Адян наличие такой последовательности обосновывали ссылкой на статью Аршона [2] — еще одну работу, в которой были переоткрыты результаты Туэ)

Еще раньше комбинаторика слов нашла свое применение и в теории полугрупп. Естественность связи между полугруппами и словами можно проиллюстрировать следующей конструкцией, принадлежащей Дилвор-ту.

Зафиксируем некоторое непустое слово и и обозначим через IV множество слов над некоторым алфавитом Е, которые избегают слово и. Рассмотрим множество всех подслов ¿"(ТУ) слов из IV и добавим к этому множеству новый элемент, который обозначим через 0.

Для произвольных элементов г>1, г^ из множества 5° (ТУ) = 5(Ил)и{0} определим новую операцию г^ * г>2 по следующему правилу:

Ы * 0 = 0 * VI = 0, VI = г>1г>2, если г^г € <5'(Т/^'), У\ * У2 = 0, если У\У2 £ Э(И^).

Очевидно, что (Ж) относительно этой операции является полугруппой. Легко показать, что эта полугруппа удовлетворяет тождеству и т 0. Кроме того, заметим, что множество Б0(IV) будет бесконечным тогда и только тогда, когда слово и избегаемо над алфавитом Е. В частности, если рассмотреть слово ж3, а в качестве \¥ взять множество слов из последовательности Туэ-Морса, то мы получим бесконечную конеч-нопорожденную полугруппу, которая удовлетворяет тождеству Именно такой контрпример привели Морс и Хедлунд в [45] для полугруппового аналога обсуждавшейся выше проблемы Бернсайда: верно ли, что если в некоторой конечнопорожденной полугруппе Э для каждого элемента х € 5 существуют натуральные числа тх и пх такие, что Хт1 длл^+пх^ т0 полугруппа 5 конечна?

При изучении свойств полугрупп, удовлетворяющих определенным тождествам, естественно рассматривать не отдельные полугруппы, а классы полугрупп, каждая из которых удовлетворяет этим тождествам. Такие классы называются многообразиями полугрупп.2 В частности, в связи с предыдущим примером можно рассматривать локально конечные многообразия полугрупп, т.е. многообразия, в которых каждая конеч-нопорожденная полугруппа конечна. Бин, Эренфойхт и Макналти [23] установили следующую связь между избегаемыми словами и многообразиями. Пусть V — многообразие полугрупп, заданное (возможно бесконечным) набором тождеств {щ «0 | г G /} от конечного числа переменных. Многообразие V не является локально конечным тогда и только тогда, когда каждое слово щ избегаемо.

Таким образом, избегаемость оказалась полезным инструментом для исследования многообразий полугрупп, заданных О-приведенными тождествами. В 80-х годах прошлого века комбинаторика слов была применена Сапиром для решения аналогичных задач в произвольных многообразиях полугрупп. Аналогом избегаемого слова стало введенное им понятие избегаемого тождества. Будем говорить, что слово w е является изотермом для пары (р, q) слов над алфавитом Д, если для любого морфизма h : Д+ £+ из того, что h(p) — подслово слова w, следует h(p) = h(q). Соответственно, ТОЖДвСТВО J) ^ а называется избегаемым, если существует бесконечная последовательность слов {ги*}^/ над некоторым алфавитом такая, что каждое слово ги* является изотермом для пар>(р, q) и (q;p). В[13]Сапир нашел следующую связь между избегаемыми тождествами и многообразиями полугрупп. Пусть V — многообразие-полугрупп, заданное (возможно бесконечным) набором тождеств {Pi~4i | i G 1} от конечного.числа переменных. В многообразии V существует ниль-полугруппа, не являющаяся локально конечной, тогда и только тогда, когда каждое тождество Pi ~ qi избегаемо.

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

2Теория многообразий полугрупп активно развивается с 60-х годов прошлого века. Обзор ее достижений можно найти в статьях [3,16,17], посвященных соответственно эквациональным, структурным и решеточным аспектам теории. нечно базируемых конечных полугрупп. Эта классификация является, по-видимому, наиболее ярким алгебраическим приложением теории избегаемых тождеств. Дальнейшее использование этой теории применительно к вопросам конечной базируемости см. в недавней работе [21].

Мы видим, что комбинаторное свойство (избегаемость) тождеств, задающих многообразие, оказывается тесно связано с эквациональными и структурными свойствами этого многообразия. Естественно ожидать, что избегаемость увязана также с решеточными свойствами многообразий. Основным результатом настоящей работы является прояснение связей между избегаемостью тождеств и определяемым ниже свойством решеточной универсальности многообразия.

Назовем многообразие V решеточно универсальным, если в его решетку подмногообразий Ь(у) можно вложить решетку, дуальную решетке разбиений некоторого счетного множества. Из решеточной универсальности многообразия следует, что его решетка ¿(V) является сложной, в частности, в нее можно вложить решетку подмногообразий произвольного многообразия универсальных алгебр не более чем счетного типа. В 1971 году Баррис и Нэльсон [26] показали, что многообразие полугрупп, удовлетворяющее тождеству х2 та ж3, является решеточно универсальным. Немного позже Ежек [38] доказал, что подмногообразие этого многообразия, заданное тождеством х2 та 0, также решеточно универсально. Нетрудно убедиться, что тождество х2 та х3 избегаемо. Также, как было отмечено ранее, слово х2 избегаемо. Возникает следующий вопрос:

Верно ли, что если многообразие полугрупп задано избегаемыми тождествами от конечного числа переменных, то оно решеточно универсально ?

В диссертации дается положительный ответ на этот вопрос.

Структура диссертации такова. Глава 1 носит вводный характер, в ней приводятся основные понятия и факты из комбинаторики слов и теории полугрупп, которые будут использованы в остальных главах данной работы.

Главы 2 и 3 излагают результаты автора по комбинаторике слов. Эти результаты необходимы для ответа на поставленный выше вопрос, но, на наш взгляд, представляют и самостоятельный интерес. В главе 2 вводится один новый вид избегаемости и рассматривается его связь с классической избегаемостью. Для обсуждения этих связей напомним две задачи, которые естественным образом возникают в рамках теории избегаемости и являются наиболее близкими к вопросам, рассматриваемым в диссертации.

Задача 1. Для заданного слова ги выяснить, является ли гу избегаемым.

Ответ на этот вопрос дали Бин, Эренфойхт и Макналти в [23] и Зимин в [7], которые независимо доказали два эффективных критерия избегаемости слов.

Задача 2. Пусть гю — избегаемое слово. Найти индекс избегаемости слова ю, т.е. наименьшее число к такое, что слово ъи избегаемо над алфавитом Е мощности к.

Эта задача оказалось сложной и в общем случае ответа на нее нет до сих пор, хотя можно отметить некоторые продвижения: Кассень [28,29], Рот [49], Горальчик и Ваничек [37], Шмидт [52] указали индекс избегаемости для каждого слова над двухбуквенным алфавитом; Петров в [11] показал, что индекс избегаемости любого полного слова не превосходит четырех.

Кроме описанной выше «классической» избегаемости слов в литературе рассматриваются такие модификации как, например, избегаемость в абелевом смысле [36,39], р-адическая избегаемость [40,48]. Возникновение этих модификаций связано с возможным их применением в алгебре. Напомним, что палиндромом называется слово, которое одинаково читается как слева направо, так и справа налево. В главе 2 вводится новый вид избегаемости, а именно, слово ъи называется избегаемым палиндромами, если существует некоторый конечный алфавит и бесконечная последовательность палиндромов над этим алфавитом, каждый элемент которой избегает (в обычном смысле) данное слово. Палиндромы как объект исследований часто возникают в комбинаторике слов (см. например [19,20]), так как представляют собой простейший пример симметрии. В главе 2 доказывается критерий избегаемости палиндромами (аналог задачи 1). Оказывается, что каждое избегаемое слово можно избежать последовательностью палиндромов над подходящим конечным алфавитом. Кроме того, найден новый класс слов (а именно, класс избегаемых палиндромов над произвольным алфавитом), для каждого слова из которого мы можем дать оценку индекса избегаемости в задаче 2. Показано, что любой избегаемый палиндром избегается (в обычном смысле) бесконечной последовательностью слов над 16-буквенным алфавитом. Также в главе 2 приводятся оценки мощности алфавита, над которым данное слово можно избежать палиндромами (аналог задачи 2).

В главе 3 рассматривается еще один вид избегаемости. Будем называть множество слов М над некоторым алфавитом антицепью, если любые два различных слова из множества М избегают друг друга. Впервые этот вид избегаемости возникает в статье Ежека [38], где он строит антицепь слов, избегающих слово ж2. Кассень в [30] называл этот вид сильной избегаемостью, Крошмор и Горальчик в [33] использовали термин «взаимная избегаемость». Термин «антицепь» впервые использовал Карри в своей статье [34], в которой он построил бесконечную антицепь слов, избегающих кубы. В пункте 3.1 обобщаются результаты этих авторов: для любого избегаемого слова и строится бесконечная антицепь слов, избегающих слово и. Для построения этой антицепи используется последовательность палиндромов, избегающих слово и, существование которой доказано в главе 2.

В работе Ежека [38] антицепь слов, избегающих слово х2, используется для того, чтобы показать, что многообразие полугрупп, заданное тождеством х2 и 0 является решеточно универсальным. Аналогично, используя антицепь слов, построенную в пункте 3.1, мы получили- следующее утверждение, обобщающее результат Ежека: все многообразия, которые заданы О-приведенными тождествами от конечного числа переменных, у которых левая часть — избегаемое слово, являются решеточно универсальными.

Только что сформулированный результат, хотя и представляет самостоятельный интерес, является промежуточным шагом на пути к решению основной задачи настоящего исследования — классификации.решеточно универсальных многообразий. Поясним на примере возникающие здесь трудности. Рассмотрим многообразие полугрупп V, удовлетворяющих тождеству Мальцева [9] ахЪ у Ьха г Ъха у ахЬ Ъха у ахЪ г ахЬ у Ьха. Несмотря на то, что обе части' этого тождества являются неизбежными словами, легко показать, что само оно является избегаемым. Его подмногообразие, удовлетворяющее тождеству ахЪ у Ьха г Ьха у ахЬ ~ 0, не является решеточно универсальным, но само многообразие V будет решеточно универсальным. Таким образом, для дальнейших продвижений пришлось изучить избегаемость тождеств антицепями. В пункте 3.4 для каждого натурального числа п строится бесконечная антицепь слов, которая является изотермом для любой пары шаблонов (р, q) таких, что pmq — избегаемое тождество, содержащее не более п переменных.

Глава 4 посвящена изложению основных алгебраических результатов диссертации. В ней показано, что любое многообразие, заданное избегаемыми тождествами от конечного числа переменных, является решеточно универсальным. Более того, если многообразие полугрупп удовлетворяет одному достаточно слабому дополнительному условию, а именно, все периодические группы в нем локально конечны, то выполняется и обратное утверждение. Это и завершает решение поставленной выше задачи.

Публикации по теме диссертации

Основные результаты диссертации опубликованы в [57-61]. В совместных работах [58, 59] М.В. Волкову принадлежат постановка задачи и общая схема доказательства, а автору диссертации принадлежит реализация и проработка доказательства. В тезисах [61] анонсированы результаты, опубликованные в [57]. Работа [59] опубликована в издании, входящем в перечень утвержденный ВАК.

Апробация результатов

Основные результаты диссертации докладывались на международной конференции WORDS 2007 (Марсель, Франция, 2007), международной школе по алгебраической теории автоматов SATA 2008 (Лиссабон, Португалия, 2008), международной конференции WORDS 2009 (Салер-но, Италия, 2009), а также на семинаре «Компьютерные науки» (УрГУ), в университете города Турку (Турку, Финляндия, 2009), в университете Лиссабона (Лиссабон, Португалия, 2009), на научном семинаре «Алгебраические системы» под руководством Л.Н. Шеврина (УрГУ), алгебраическом семинаре под руководством Л.М. Мартынова (ОмГПУ, Омск).

Автор выражает глубокую благодарность своему научному руководителю профессору М. В. Волкову за постановки задач и постоянное внимание к работе.

Список литературы диссертационного исследования кандидат физико-математических наук Михайлова, Инна Анатольевна, 2010 год

1. Адян С. И. Проблема Бернсайда и тождества в группах/ С. И. Адян. М: Наука, 1975.

2. Аршон С. Е. Доказательство существования тг-зпачных бесконечных асимметричных последовательностей/ С. Е. Аршон// Матем. сб. 1937. Т. 2. № 4. С. 769-779.

3. Берников Б. М. Решетки нильпотентных многообразий полугрупп. II/ Б. М. Берников, М. В. Волков // Изв. Урал. гос. ун-та. Матем., механика. 1998. Вып. 1. № 10. С. 13-31.

4. Голод Е. С. О башне полей классов/Е. С. Голод, И. Р. Шафаревич// Изв. АН СССР. Сер. матем. 1964, Т. 28, Вып. 2. С. 261-272.

5. Кострикин А. И. Вокруг Бернсайда/ А. И. Кострикин. М: Мир, 1986.

6. Гретцер Г. Общая теория решеток/Г. Гретдер. М: Мир, 1982.

7. Зимин А. И. Блокирующие множества термов/ А. И. Зимин// Матем. сб. 1982. Т. 119. С. 363-375.

8. Клиффорд А. Алгебраическая теория полугрупп /А. Клиффорд, Г. Престон. М: Мир, 1972. Т. 1.

9. Мальцев А. И. Нильпотентные полугруппы/ А. И. Мальцев// Учен, зап. Ивановск, педин-та, 1953. Т. 4. С. 107-111.

10. Новиков С. И. О бесконечных периодических группах. 1-Ш/ П. С. Новиков, С. И. Адян// Изв. АН СССР. Сер. матем., 1968. Т. 32, С. 212-244; 251-524; 709-731.

11. Петров А. Н. Последовательность, которая избегает любое полное слово/ А. Н. Петров // Матем. заметки. 1988. Т. 44, № 4. С. 517-522.

12. Саломаа А. Жемчужины теории формальных языков/ А. Саломаа. М: Мир, 1986.

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

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

15. Шеврин JL Н. Тождества полугрупп/ JI. Н. Шеврин, М. В. Волков// Изв. вузов. Матем. 1985. № 11. С. 3-47.

16. Шеврин JI. Н. Структурные аспекты теории многообразий полугрупп/ JI. Н. Шеврин, Е. В. Суханов// Изв. вузов. Матем. 1989. № 6. С. 3-39.

17. Шеврин JI. Н. Решетки многообразий полугрупп/ JI. Н. Шеврин, Б. М. Верников, М. В. Волков // Изв. вузов. Матем. 2009. № 3. С. 336.

18. Шур А. М. Комбинаторика слов: Учеб. пособие /А. М. Шур. Екатеринбург: Изд-во Урал, ун-та, 2003.

19. Alouche J.-P. Palindromic complexity/J.-P. Alouche, M. Baake, J. Cassaigne, D. David// Theoret. Сотр. Sci. 2003. № 1. V. 292, P. 931.

20. Ambros P. Palindromic complexity of infinite words associated with simple Parry numbers/ P. Ambros, Ch. Frougny, Z. Mazakova, E. Pelantova// Annales de L'Institute Fourier. 2006. V. 56, № 7. P. 21312160.

21. Auinger К. Эл. ресурс] Matrix identities involving multiplication and transposition/ K. Auinger, I. Dolinka, M. Volkov// http://arxiv.org/pdf/0902.1155v4

22. Baker K.A. Growth problems for avoidable words/ K.A. Baker, G.F. McNulty, W. Taylor// Theoret. Сотр. Sci. 1989. V. 69. P. 319-345.

23. Bean D.R. Avoidable patterns in strings of symbols/ D.R. Bean, A. Ehrenfeucht, G.F. McNulty// Pacific J. Math. 1979. V. 85. P. 261294.

24. Berstel J. Theory of Codes/ J. Berstel, D. Perrin. Academic Press, 1985.

25. Burris S. Embedding of the dual of Поо in the lattice of equational classes of semigroups/ S. Burris, E. Nelson// Algebra Universalis, 1971. V. 1. P. 248-253.

26. Burris S. Embedding the dual of IIm in the lattice of equational classes of commutative semigroups/ S. Burris, E. Nelson // Proc. Amer. Math. Soc. 1971. V. 30, № 2. P. 37-39.

27. Burris S. A course in universal algebra/ S. Burris, H.P. Sankappanavar. Springer. 1981.

28. Cassaigne J. Unavoidable binary patterns/ J. Cassaigne// Acta Inf. 1993. V. 30, P. 385-295.

29. Cassaigne J. Motifs evitables et regularites dans les mots: These de Doctoral/ J. Cassaigne. Univ. Paris 6, 1994.

30. Cassaigne J. Words strongly avoiding fractional powers/ J. Cassaigne, J.D. Currie//Eur. J. Comb. 1999. № 20. P. 725-737.

31. Choffrut C. Combinatorics on words. Handbook of formal languages/ C. Choffrut, J. Karhumaki// Eds. G. Rosenberg, A. Salomaa, B. 1997. V. 1.

32. Clark R.J. Avoidable formulas in combinatorics on words/ R.J. Clark.// Doctoral Thesis, UCLA, 2001.

33. Crochemore M. Mutually avoiding ternary words of small exponent/ M. Crochemore, P. Goralcik// Internat. J. Algebra Comput. 1991. V. 1. P. 407-410.

34. Currie J. D. 3ji. pecypc] A note on antichains of words / J. D. Currie// Electronic J. Comb. 1995. V. 2. № 21.

35. Currie J. D. Pattern avoidance: themes and variations/ J.D. Currie// Theoret. Comp. Sci. 2005. V. 339. P. 7-18.

36. Erdos P. Some unsolved problems/ P. Erdos// Magyar Tud. Akad. Mat. Kutato. Int. Kozl. 1961. V. 6. P. 221-254.

37. Goralcik P. Binary patterns in binary words/ P. GoralGik, T. Vanicek// Internat. J. Algebra Comput. 1991. V. 1. P. 387-391.

38. Jezek J. Intervals in the lattice of varieties/ J. Jezek// Algebra Universalis. 1976. V. 6, P. 147-158.

39. Justin J. Characterization of the repetitive commutative semigroups/ J. Justin// J. Algebra 1972. V. 21. P. 87-90.

40. Kao J.-Y. Words avoiding repetitions in arithmetic progressions/ J.Y. Kao, N. Rampersad, J. Shallit, M. Silva// Theoret. Comput. Sci. 2008. V. 391. P. 126-137.

41. Korjakov I. O. A sketch of the lattice of commutative nilpotent semigroup varieties/ I. O. Korjakov// Semigroup Forum. 1982. V. 24, № 1, P. 285-317.

42. Lothaire M. Combinatorics on Words/ M. Lothaire. Addison-Wesley, 1983.

43. Lothaire M. Algebraic Combinatorics on Words/ M. Lothaire. Cambridge University Press, 2002.

44. McNulty G. F. Structural diversity in the lattice of equational theories/ G. F. McNulty// Alg. Univ. 1981. V. 13, № 3, P. 271-292.

45. Morse M. Unending chess, symbolic dynamics and a problem in semigroups/ M. Morse, G.A. Hedlund// Duke Math. J. 1944. V. 11. P. 1-7.

46. Ochem P. A generator of morphisms for infinite words/ P. Ochem// Theoret. Informatics Appl. 2006. V. 40. P. 427-441.

47. Prouhet E. Mémoire sur quelques relations entre les puissances des nombres./ E. Prouhet// C. R. Acad. Sci. Paris Sér. I. 1851. V. 33, P. 225.

48. Puzynina S. Эл. ресурс] On p-adic avoidance of words/ S. Puzynina// Proc. 7th Int. Conf. on Words, Salerno, Italy. 2009. № 125.

49. Roth P. Every binary pattern of lenth six is avoidable on the two-letter alphabet/ P. Roth// Act. Inf. 1992. V.29. № 1. P. 95-107.

50. Sapir M. V. Sur la propriété de base finie pour les pseudovariétés de semigroups finie/ M.V. Sapir // C. R. Acad. Scie. Paris. 1988. V. 306. Sér. I. P. 795-797.

51. Sapir M. V. Эл. pecypcj Combinatorics on Words with Applications/ M.V. Sapir IBP-Litp 1995/32: Rapport de Recherche Litp, Université Paris 7, 1995. URL: http://www.math.vanderbilt.edu/ msapir/ftp/course/course.pdf

52. Schmidt U. Avoidable patterns on two letters/ U. Schmidt// Theoret. Comp. Sei. 1989. V. 63. P. 1-17.

53. Volkov M. V. Young diagrams and the structure of the lattice of overcommutative semigroup varieties/ M.V. Volkov// Transformation Semigroups. Proc. Int. Conf. held at the Univ. of Essex. Colchester, 1994. P. 99-110.

54. Whitman P. Lattices, equivalence relations, and subgroups/ P. Whitman// Bull. Amer. Math. Soc. 1946. V. 52. P. 507-512.

55. Михайлова И. А. Шаблоны, избегаемые палиндромами, и их алгебраические приложения/ И. А. Михайлова// Депонир. в ВИНИТИ. 01.07.2010. №687-В2004. 46 с.

56. Mikhailova I. A. Patterns avoidance by palindromes/ I.A. Mikhailova, M.V. Volkov// in P. Arnoux, N.Bédaride, J. Cassaigne (eds.), WORDS 2007. Proc. 6th Int. Conf. on Words, Institute de Mathématiques de Luminy, Marseille. 2007. P. 212-221.

57. Mikhailova I. A. Pattern avoidance by palindromes/ I. A. Mikhailova, M. V. Volkov// Theoret. Comp. Sei. 2009. V. 410. P. 2992-2998.

58. Mikhailova I. A. 9ji. pecypc] Pattern avoidance by antichains/ I. A. Mikhailova// Proc. 7th Int. Conf. on Words, Salerno, Italy. 2009. № 139.