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

российская академия наук

уральское отделение "".7.гитут математики и механики

На правах рукописи

Михайлова Инна Анатольевна

ШАБЛОНЫ, ИЗБЕГАЕМЫЕ АНТИЦЕПЯМИ СЛОВ, И ИХ АЛГЕБРАИЧЕСКИЕ ПРИЛОЖЕНИЯ

01.01.06 — математическая логика, алгебра И теория чисел

автореферат

диссертации на соискание учёной степени кандидата физико-математических наук

2 7 ЯНЗ 2011

Екатеринбург, 2010

4842930

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета им. A.M. Горького.

Научный руководитель:

доктор физико-математических наук, профессор М. В. Волков

Официальные оппоненты: доктор физико-математических

наук, профессор А. В. Тищенко

кандидат физико-математических наук, доцент Е. А. Перминов

Ведущая организация:

Омский государственный педагогический университет

Защита диссертации состоится " 01 " февраля 2011 года в 1530 часов на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан «гл " декабря 2010 г.

Учёный секретарь диссертационного совета

Д 004.006.03, кандидат физ.-мат. наук

И. Н. Белоусов

Общая характеристика работы

Актуальность темы. Комбинаторика слов является важным и быстро растущим направлением современной математики. Она изучает различные свойства конечных и бесконечных последовательностей символов. Такие последовательности обычно называют словами, а символы, которые используются для записи слов, — буквами.

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

Комбинаторика слов имеет много приложений и в математике. Морс и Хедлупд использовали её в своих исследованиях по символической динамике [19]. Также можно отметить применение комбинаторики слов Шют-ценберже в его основополагающих работах по теории кодирования [11].

Особенно важными оказались применения комбинаторики слов в алгебре. Новиков и Адян [1,5] использовали комбинаторный подход для построения бесконечных конечнопорожденных периодических групп (контрпримеров к проблеме Бернсайда для групп). Ширшовым [9] чисто комбинаторными методами была доказана теорема о высоте для ассоциативных колец, удовлетворяющих некоторому полиномиальному тождеству. Из этой теоремы следует положительное решение проблемы Куроша для таких колец. Отметим, что в обоих случаях новый подход привел к решению многих важных алгебраических задач. Например, Зельманов [2] применял комбинаторику слов для исследования проблем бернсайдов-ского типа для йордановых алгебр.

Еще раньше комбинаторика слов нашла свое применение и в теории полугрупп. В работах Морса и Хедлунда [19] и Вина, Эренфойхта

и Макналти [10] в качестве контрпримера для проблем бернсайдовского типа для полугрупп строятся бесконечные конечнопорожденные полугруппы, удовлетворяющие О-приведенным тождествам. Помимо структурных свойств многообразий полугрупп, комбинаторика слов применялась к исследованиям вопросов конечной базируемости Сапиром [6,21].

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

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

Целью работы является классификация многообразий полугрупп, у которых решетка подмногообразий обладает некоторым свойством универсальности. Назовем многообразие полугрупп V решеточно универсальным, если в его решетку подмногообразий Ь(У) можно вложить решетку, дуальную решетке разбиений некоторого счетного множества. Из решеточной универсальности многообразия следует, что его решетка ¿(V) является сложной в следующем смысле: в нее можно вложить решетку подмногообразий произвольного многообразия универсальных алгебр не более чем счетного типа.

В 1971 году Баррис и Нэльсон [12] показали, что многообразие полугрупп, удовлетворяющее тождеству х2 ~ ж3, является решеточно универсальным. Немного позже Ежек [17] доказал, что подмногообразие этого многообразия, заданное тождеством 7? « 0, также решеточно универсально.

В диссертации результаты Барриса-Нэльсон и Ежека обобщаются максимально возможным образом. А именно, устанавливается критерий , решеточной универсальности многообразий, заданных произвольной системой тождеств от конечного числа переменных, не выполняющейся ни ^ в какой бесконечной конечнопорожденной периодической группе. В ней приводится доказательство критерия решеточной универсальности многообразий полугрупп в терминах избегаемых тождеств.

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

числа п строится бесконечная антицепь Л1п слов над подходящим конечным алфавитом, каждый элемент которой избегает любой избегаемый шаблон, содержащий не более п переменных. Также доказывается, что каждое слово антицепи Мп является изотермом для пары шаблонов (р, q) такой, что тождество p~q избегаемо и содержит не более п переменных.

Научная новизна. Все результаты являются новыми.

Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в комбинаторике слов и теории полугрупп.

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

Публикации

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

Структура и объем диссертации Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации составляет 59 страниц. Библиографический список содержит 61 наименование.

Краткое содержание работы

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

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

Воспроизведем здесь определения нескольких понятий, необходимых для формулировки основных результатов. Пусть Е — некоторое непустое множество, тогда словом над алфавитом Е называется произвольный элемент свободной полугруппы Е+. (Иногда для упрощения изложения результатов для термина слово используют синоним — шаблон). Будем говорить, что слово содержит шаблон р Е Д+, если существует

морфизм свободных полугрупп Л : Д+ 1-» Е+ такой, что h(p) — некоторое подслово слова w. Шаблон р называется избегаемым, если существует конечный алфавит Е и бесконечная последовательность слов {wj С Е+ таких, что каждое слово iu, не содержит шаблон р. Основным инструментом исследования в диссертации являются избегаемые шаблоны.

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

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

В параграфе 2.1 для каждого натурального числа п строится последовательность слов J?™' над конечным алфавитом из 22—1)1 +2 букв. Каждое слово этой последовательности может быть представлено в виде ffi = cfccm'¿2<1\, где d\,di — некоторые фиксированные буквы, a cr'"' — некоторый палиндром. Основным результатом второй главы является следующая теорема1:

Теорема 2.1. Последовательность {77m^}m>o избегает все избегаемые шаблоны, содержащие не более п переменных.

^десь и далее формулировки утверждений приведены в том виде, который не требует введения дополнительных сведений, но в форме, эквивалентной той, которой они даны в диссертации. Нумерация утверждений совпадает с используемой в диссертации.

Из теоремы 2.1 получается следующая связь между введенным выше и классическим видами избегаемости:

Следствие 2.1. Шаблон избегаем тогда и только тогда, когда он избегаем палиндромами.

Впервые бесконечный набор слов, который одновременно избегает все избегаемые шаблоны над данным алфавитом, был построен Бином, Эренфойхтом и Мак-Налти в [10] для доказательства критерия избегаемости шаблонов. Более экономичная по размеру алфавита конструкция бесконечного множества слов с таким свойством описана Кассенем в [18]. Однако вопрос о том, какой минимальный размер к должен иметь алфавит, над которым можно избежать фиксированный шаблон р, остается открытым. Тахое число к называется индексом избегаелюсти шаблона и обозначается через ц(р). Еще из первых статьей по комбинаторике слов Туэ [23,24] известно, что [¿(х3) = 2, а ц{х2) = 3. В параграфе 2.5 получен следующий результат, являющийся следствием более общего утверждения.

Следствие 2.2. Пусть р — избегаемый палиндром над произвольным алфавитом. Тогда ц(р) < 16.

Мы определяем индекс избегаемости .палиндромами шаблона /^(р) как наименьшее число к такое, что над алфавитом из к букв существует последовательность палиндромов, избегающих р. Из определения немедленно следует, что /^¡(р) > ц{р). С другой стороны, известно [20), что нельзя построить бесконечное множество бинарных слов, которые избегали бы одновременно оба шаблона д — хугхгу и V = угхгух. В то же время ¡х{ц) = ц(*с[) = 2 и, следовательно, р.ры(д) > р(я)- В параграфе 2.5 получены границы для введенного индекса для различных классов слов: для полных слов, для слов, в которых каждая буква встречается дважды, а также для класса всех избегаемых шаблонов. Вероятнее всего, что взаимодействие между феноменом избегаемости и симметрией гораздо глубже и его дальнейшее изучение может привести к другим интересным результатам.

В третьей главе рассматривается другой вид избегаемости — избе-гаемость антицепями слов. Множество слов М называется антицепью, если любые два различных слов из М избегают друг друга. Впервые этот вид избегаемости возникает в статье Ежека [17], в работах [13,14] были построены антицепи слов, избегающие некоторые особые шаблоны.

В параграфе 3.1 упомянутые выше частные результаты обобщены для произвольных избегаемых шаблонов: ,

Теорема 3.1. Для каждого натурального числа п множество слов Мп = {Пт I т > 22Г,ог(6п_Ч1} является антицепью. Каждый элемент этой антицепи избегает произвольный избегаемый шаблон, содержащий не более п переменных.

Бесконечная антицепь слов, избегающая шаблон х2, возникает в работе Ежека [17], который доказал, что многообразие полугрупп, определенное тождеством х2 га 0, является решеточно универсальным. Следующее утверждение является следствием теоремы 3.1, обобщающим результат Ежека на случай многообразий, заданных 0-приведенными тождествами.

Предложение 3.1. Многообразие полугрупп, заданное тождествами вида 0 от конечного числа переменных таких, что каждый шаблон Рг избегаем, является решеточно универсальным.

Для того, чтобы классифицировать решеточно универсальные многообразия, заданные произвольными тождествами, в параграфе 3.4 используется принадлежащее Сапиру [22] понятие избегаемого тождества, аналогичное понятию избегаемого шаблона. Назовем слово и € Е+ изотер-мом для упорядоченной пары шаблонов (р, <?) над алфавитом А, если для произвольного морфизма Л : Д+ Е+ такого, что слово Л(р) содержится в и выполняется равенство Л(р) = Л(?). Тождество р~д называется избегаемым если существует бесконечная последовательность слов над некоторым конечным алфавитом таких, что каждое слово щ является изотермом для обеих пар (р,д) и (?,р). Отметим, что теорема 3.1 не может быть автоматически перенесена на случай избегаемых тождеств, так как существуют избегаемые тождества, у которых и правая и левая части являются неизбежными шаблонами. В качестве примера приведем тождество Мальцева [4] ахЬ у Ьха г Ьха у ахЬ^Ьха у ахЪ г ахЬ у Ьха, обе части которого, очевидно, содержатся в слове Зимина

Zi = х\хгх\ 1з Х\Х1Х\ х4 х^ях ^з Х1Х2Х1

и поэтому неизбежны. Тем не менее, можно показать, что само тождество Мальцева избегаемо.

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

Теорема 3.2. Для любого избегаемого тождества р ~ q, содержащего не более п переменных, каждый элемент антицепи слов Мп является изотермом для (р, д) и (<?,р).

Четвертая глава посвящена изложению основных алгебраических результатов диссертации. В качестве следствия теоремы 3.2 получено следующее утверждение которое обобщает результат Барриса и Нэль-сон [12] на случай многообразий полугрупп, заданных произвольными избегаемыми тождествами.

Предложение 4.1. Пусть многообразие полугрупп V задано набором избегаемых тождеств от конечного числа переменных. Тогда V является решеточно универсальным. ■

Отметим, что многообразие, заданное тождеством Мальцева является решеточно универсальным по предложению 4.1 несмотря на то, что никакое его подмногообразие, заданное О-приведенными тождествами, не является решеточно универсальным.

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

Теорема 4.2. Пусть V — многообразие полугрупп, заданное множеством тождеств Ы от конечного числа переменных, и такое, что все его конечнопорожденные периодические группы конечны. Многообразие V решеточно универсально тогда и только тогда, когда все тождества из Ы являются избегаемыми.

Основные результаты диссертации

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

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

• Доказано, что многообразие полугрупп, заданное тождествами от конечного числа переменных, имеющими вид ~ 0, где все шаблоны p¡ избегаемы, является решеточно универсальным.

• Доказано, что многообразие полугрупп, заданное множеством тождеств Id от конечного числа переменных, и такое, что все периодические группы в нем локально конечны, является решеточно универсальным тогда и только тогда, когда все тождества в Id избегаемы.

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

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

[2] Зельманов Е. И. Абсолютные делители нуля в йордановых парах и алгебрах Ли/ Е.. И. Зельманов// Матем. сб. 1980. Т. 112. № 4. С. 611-629.

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

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

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

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

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

[8] Шеврин. Л. Н. Решетки многообразий полугрупп/ Л. Н. Шеврин, Б. М. Берников, М. В. Волков// Изв. вузов. Матем. 2009. № 3. С. 3-36.

[9] Ширшов А. И. О некоторых неассоциативных ниль-кольцах и алгебраических алгебрах/ А. И. Ширшов// Матем. сб. 1957. Т. 41. № 3. С. 381-394.

[10] Bean D.R. Avoidable patterns in strings of symbols/ D.R. Bean, A. Ehrenfeucht, G.F. McNulty// Pacific J. Math. 1979. V. 85. P. 261-294.

[11] Berstel J. Theory of Codes/ J. Berstel, D. Perrin. Academic Press. 1985.

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

[13] Cassaigne J. Words strongly avoiding fractional powers/ J. Cassaigne, J.D. Currie//Eur. J. Comb. 1999. V. 20. № 8. P. 725-737.

[14] Crochemore M. Mutually avoiding ternary words of small exponent/ M. Crochemore, P. Goralêik// Internat. J. Algebra Comput. 1991. V. 1. P. 407-410.

[15] Currie J.D. Pattern avoidance: themes and variations/ J.D. Currie// Theoret. Comp. Sei. 2005. V. 339. P. 7-18.

[16] Currie J.D. [Эл. ресурс] A note on antichains of words / J.D. Currie// Electr. J. Comb. 1995. V. 2. № 21.

[17] Jezek J. Intervals in the lattice of varieties/ J. Jezek// Algebra Universalis. 1976. V. 6. P. 147-158.

[18] Lothaire M. Algebraic Combinatorics on Words/ M. Lothaire. Cambridge University Press, 2002.

[19] 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.

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

[21] 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.

[22] Sapir M. V. [Эл. ресурс] 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

[23] Thue A. Über unendliche Zeichenreihen/ A. Thue//' Kra. Vidensk. Selsk. Skrifter. I, Mat.-Nat. Kl. Christiana, 1906, Vol. 7, P. 1-22. Reprinted in: Eds. T. Nagell, A. Seiberg, S. Seiberg, K. Thalberg. Selected Mathematical Papers of Axel Thue. Oslo, Norway. Universitetsforlaget, 1977. P. 139-158.

[24] Thue A. Uber die gegebseitige Lage gleicher Teile gewisser Zeichenreihen/A. Thue// Kra. Vidensk. Selsk. Skrifter. I, Mat.-Nat. Kl. Christiana, 1912, Vol. 10, P. 1-67. Reprinted in: Eds. T. Nagell, A. Seîberg, S. Seiberg, К. Thalberg. Selected Mathematical Papers of Axel Thue. Oslo, Norway. Universitetsforlaget, 1977, P. 413-478.

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

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

[26] 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.

[27] Mikhailova I. A. Pattern avoidance by palindromes/ I.A. Mikhailova, M.V. Volkov// Theoret. Сотр. Sci. 2009. V. 410. P. 2992-2998.

[28] Mikhailova I. А. [Эл. ресурс] Pattern avoidance by antichains/ I. A. Mikhailova// Proc. 7th Int. Conf. on Words, Salerno, Italy. 2009. №. 139.

[29] Mikhailova I. Lattice universal semigroup varieties/ I. Mikhailova, M. Sapir, M. Volkov// International Conference on Algebras and Lattices'on the occasion of the 65th birthday of Jaroslav Jezek. Abstract of Talks, Charles University, Prague. 2010.-P. 28-29......................... ......................

Подписано в печать 14.12.2010. Формат 60 х 84 1/16. Бумага офсетная. Усл. печ. л. 1,0. Тираж 100. Заказ 418 Издатеш>ство Уральского университета. 620083, Екатеринбург, пр. Ленина, 51.

Введение

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), на научном семинаре «Алгебраические системы» под руководством Л.Н. Шеврина (УрГУ), алгебраическом семинаре под руководством Л.М. Мартынова (ОмГПУ, Омск).

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

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.