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

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

ФРИД Анна Эдуардовна

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

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

-8 НОЯ 2012

Новосибирск - 2012

005054677

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения РАН

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

Д. С, Кротов

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

Ведущая организация: Федеральное государственное

бюджетное учреждение науки Санкт-Петербургское отделение Математического института им. В. А. Стеклова Российской академии наук.

Защита состоится 19 декабря 2012 г. в 15 час. 00 мин. на заседании диссертационного совета Д 003.015.01 при Учреждении Российской академии наук Институте математики им. С. Л. Соболева Сибирского отделения РАН по адресу: 630090 г. Новосибирск, пр. Академика Коптюга 4, к. 417.

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

Автореферат разослан " 2012 г.

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

д.ф.-м.н. - Ю. В. Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Все эти вопросы, а следовательно, и результаты диссертации относятся к комбинаторике на словах — области, тесно связанной как с классической комбинаторикой и алгеброй, так и с символической динамикой. История комбинаторики на словах начинается с работ Туэ [36, 35], а также Морса и Хедлунда [29]. Туэ задался вопросом: существует ли бесконечное слово над конечным алфавитом, в котором никогда не встречаются квадраты, то есть слова, состоящие из двух последовательных вхождений одинаковых под-слов: например, квадратом является слово abcabc, представляющее собой два подряд идущих вхождения подслова abc? Нетрудно проверить, что над бинарным алфавитом таких слов не бывает, но Туэ удалось построить первый пример такого слова над алфавитом из трех символов. Со временем его результаты стали основой теории избегаемости [2, 3, 12, 17, 19, 21, 26], тесно связанной с классической комбинаторикой и алгеброй. Так, существование слова, избегающего квадратов, было использовано Новиковым и Адяном в решении проблемы Бернсайда. [1, 7].

С другой стороны, Морс и Хедлунд [29] занимались символической динамикой и рассматривали слова как коды траекторий точки в динамической системе. Их интересовало, в частности, возможное число pw(n) иодслов заданной длины п в бесконечном слове w, которое можно интерпретировать как одну из возможных мер

сложности бесконечного слова — его комбинаторную, или подслов-ную сложность. К их классическим результатам относятся лемма о том, что сложность Рги(п) ограничена тогда и только тогда, когда рш(п) < п для некоторого п, или когда слово т периодично (возможно, с предпериодом). Они же описали непериодические слова с наименьшей сложностью рги(п), равной п + 1 для всех п. Эти слова, названные Морсом и Хедлундом словами Штурма, в настоящий момент хорошо изучены и представляют собой одно из классических семейств бесконечных слов [14].

Теория подсловной сложности активно развивается по сей день. Совершенствуются как методы подсчета комбинаторной сложно- . сти конкретных примеров слов (которым была посвящена, в частности, кандидатская диссертация автора), так и методы, позволяющие получать более общие результаты о том, какой может или не может быть сложность бесконечного слова [15]. Как пример одного из лучших результатов такого рода можно привести теорему Кассе-ня [16], утверждающую, что если подсловная сложность бесконечного слова растет линейно, то ее первые разности рш(п + 1) — рт(п) ограничены сверху константой. Тем не менее, в теории подсловной сложности существует множество нерешенных задач: в частности, до сих пор неизвестна удобная характеризация слов с линейной сложностью. Одно из последних продвижений в этом направлении принадлежит Ж. Леруа [28].

Известный нерешенный вопрос теории чисел о том, любая ли последовательность цифр встречается в д-ичном разложении данного иррационального числа (например, в десятичном разложении числа тт), также является вопросом о подсловной сложности: равна ли подсловная сложность соответствующего слова д"? Самым сильным из известных результатов о комбинаторной сложности д-ичных разложений чисел является результат Адамчевского и Бю-жо [9], утверждающий, что комбинаторная сложность всякого спичного разложения алгебраического иррационального числа растет быстрее, чем линейно.

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

подслов. Факторными являются как языки подслов бесконечного слова или семейства бесконечных слов, так и языки всех слов, избегающих подслов заданного вида; изучается их подсловная сложность [4, 11, 13, 34] и другие свойства, например, возможная частота символов [31].

В последние годы развиваются также направления, основанные на модификациях определений комбинаторной сложности. Оставаясь в рамках подхода, при котором оценивается не сложность построения последовательности символов, а количество фрагментов заданного размера в этой последовательности, можно вводить и исследовать разнообразные функции, родственные комбинаторной сложности, но не равные ей. Так, Иваный в 1987 г. ввел понятие ¿-сложности [23]; Рестиво и Салеми в 2002 г. ввели шаблонную сложность [32] как количество слов над алфавитом переменных, вхождения которых появляются в данном бесконечном слове; На-кашима, Тамура и Ясутоми ввели еще одно понятие модифицированной сложности [30]. Лучше всего исследованы и наиболее перспективны в данный момент две нестандартных комбинаторных функции сложности: максимальная шаблонная сложность, введенная в 2002 г. Камаэ и Замбони [24, 25] и арифметическая сложность, введенная в 2000 г. С. В. Августиновичем, Д. Г. Фон-Дер-Флаассом и автором [41].

Свойствам арифметической сложности полностью посвящена глава 2 диссертации. Удалось получить нетривиальные результаты об этой функции сложности. Так, наименьшую арифметическую сложность среди равномерно рекуррентных непериодических слов имеют не слова Штурма, как чаще всего бывает, а специфические слова, порожденные схемами Теплица. С помощью схем Теплица полностью описываются и все равномерно рекуррентные слова, арифметическая сложность которых растет линейно, сложность же слов Штурма оказывается равной 0(п3). Заметим, что арифметическая сложность является в своем роде продолжением исследований, начатых классическими теоремами Ван дер Вардена и Семереди. О других известных исследованиях арифметических прогрессий молено прочесть в обзоре [8].

Новым научным направлением, развиваемым в диссертации, является установление комбинаторных сложностных характеристик бесконечных слов и родственных им объектов, наиболее ярко де-

монстрирующих нетривиальность свойств слов, перестановок и языков, дающих красивые и нетривиальные результаты о низкой или линейной сложности и предоставляющих новые техники для работы с соответствующими объектами. Кроме арифметической сложности бесконечных слов, к новым понятиям, описываемым и изучаемым в диссертации, относится понятие бесконечной перестановки, которому посвящена глава 3. Бесконечная перестановка определяется аналогично бесконечному слову, но роль ее «подслов» играют обычные конечные перестановки. Представляет интерес изучение свойств перестановок, аналогичных свойствам слов, и установление тех из них, которые наиболее органично описывают их структуру. Одновременно с автором и ее соавторами изучение бесконечных перестановок в данном контексте начали М. А. Макаров [5, 6] и Уидмер [37]. Среди более ранних работ, сходных по тематике, стоит отметить статью Дэвиса и др. [20].

Наконец, глава 4 диссертации посвящена свойствам произведений факторных языков и решению уравнений над ними. В отличие от уравнений над словами, решение которых возможно с помощью алгоритма Маканина [22], уравнения над языками в общем случае демонстрируют множество неожиданных свойств [18, 27, 33] и крайне редко могут быть решены полностью. Однако если ограничить рассматриваемый класс факторными языками, ситуация резко меняется, и уравнения над языками в большой степени начинают сводиться к уравнениям над словами. Таким образом, в работе разработана новая методика, позволяющая решать над факторными языками уравнения, решение которых над произвольными языками весьма сложно.

Цели работы: исследовать новые комбинаторные сложност-ные характеристики бесконечных слов; распространить как известные, так и новые функции от бесконечных слов на родственные им объекты, в частности, факторные языки и бесконечные перестановки, и исследовать, какие именно из этих функций являются естественными и важными для этих объектов; выработать новые методы исследования факторных языков слов и перестановок.

Методы исследования. В диссертации применяются как классические комбинаторные методы, в частности, методы комбинаторики на словах, так и методы алгебры, теории чисел, дискретной

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

Хочется отметить, что многие методы исследования, применяемые в данной работе, разработаны автором и применены впервые. К самым нетривиальным из них можно отнести, прежде всего,

• метод бесконечных специальных ветвей, применяемый в главе 2 для характеризации слов с низкой арифметической сложностью;

• все примененные в главе 3 методы работы с бесконечными перестановками;

• метод выжимок до канонического разложения, применяемый в главе 4 для решения уравнений над факторными языками.

Научная новизна. Все результаты, представленные в диссертации, носят теоретический характер и являются новыми.

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

Основными результатами работы являются следующие.

1. Охарактеризованы равномерно рекуррентные бесконечные слова, арифметическая сложность которых растет линейно.

2. Описаны равномерно рекуррентные бесконечные слова, арифметическая сложность которых минимальна для непериодических слов.

3. Найдены верхняя и нижняя оценки, а в некоторых случаях (включая случай слова Фибоначчи) точные формулы для арифметической сложности слов Штурма: оказалось, что она

растет как 0(п3). Этот же результат может быть переформулирован следующим образом: найдены оценки, а в некоторых случаях точные формулы для количества всех вращательных слов с фиксированной шириной интервала.

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

5. Охарактеризованы бесконечные перестановки, максимальная шаблонная сложность которых минимальна для непериодичных перестановок и равна тг; как оказалось, они порождаются тем же способом, что и слова Штурма, и поэтому названы перестановками Штурма.

6. Доказана теорема существования и единственности канонического разложения факторного языка в конкатенацию факторных языков.

7. Полностью решено уравнение коммутирования XV = УХ на множестве бинарных факторных язьжов.

Апробация: результаты диссертации докладывались, в частности, на четырех приглашенных докладах на международных конференциях, а именно на Рабочей встрече об избегаемости слов, сложности и морфизмах (Турку, Финляндия, 2004); на Летней сессии Канадского математического общества (Ватерлоо, Канада, 2005); на Международной алгебраической конференции (Екатеринбург, 2005); на конференции WORDS 2011 (Прага, Чехия).

Кроме того, результаты были доложены на Международном конгрессе по словам, языкам и комбинаторике (Киото, Япония, 2000); на конференциях WORDS 2003 (Турку, Финляндия), WORDS 2005 (Монреаль, Канада), WORDS 2009 (Салерно, Италия); на. Европейской конференции по комбинаторике (Берлин, Гер-

мания, 2005); на Конференции по комбинаторике, автоматам и теории перечисления (Льеж, Бельгия, 2006); на Международном симпозиуме по теоретической информатике в России (Санкт-Петербург, 2006); на Международной конференции по теории формальных языков (Турку, Финляндия, 2007); на Школе rio комбинаторике на словах (Монреаль, Канада, 2007); на Монсовских днях (Амьен, Франция, 2010); на Рабочей группе по комбинаторике на словах (Банфф, Канада, 2012); на Мальцевских чтениях (Новосибирск, 2006); на Лаврентьевских чтениях (Новосибирск, 2003 и 2007); в Санкт-Петербургском Computer Science Club (2011); на семинарах в университетах Марселя, Лиона, Нанси и Турку (20092012); на семинарах «Факторные языки», «Теория кодирования», «Теория графов» в Институте математики им. С. Л. Соболева СО РАН (1999-2011).

Публикации и личный вклад. По теме диссертации опубликовано 17 работ [38-54], из них 12 (все, кроме [39], [41], [43], [48,49]) — в изданиях из списка ВАК. Работы [40-43,45,46,54] написаны в неразделимом соавторстве с С. В. Августиновичем, Ж. Кассенем, Д. Г. Фон-Дер-Флаассом, Л. Замбони. В статьях [38] и [44] присутствуют леммы из математического анализа и символической динамики, полностью принадлежащие соавторам автора, в диссертации они приводятся без доказательств.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы (105 наименований, включая 17 работ автора по теме диссертации, приведенных в конце списка). Текст работы изложен на 245 страницах и содержит 27 рисунков.

Содержание работы

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

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

Глава 2 посвящена определению и свойствам арифметической сложности бесконечных слов. Эта функция, введенная в работе С. В. Августиновича, Д. Г. Фон-Дер-Флаасса и автора в 2000 г. [41], определяется как количество всех слов данной длины, встречающихся в бесконечном слове и> = ■ по арифметическим прогрессиям:

аш{п) = ■ • • 1Ю(п_1)(1+к\к, й > 1}.

Свойства арифметической сложности оказываются весьма нетривиальными и дают новую, часто неожиданную информацию о свойствах известных классов слов. Так, в разделе 2.2 найдена арифметическая сложность неподвижных точек симметрических морфиз-мов — стандартного семейства, слова из которого часто используются как примеры бесконечных слов с заданными свойствами. В частности, именно в нем содержится слово Туэ-Морса, классический пример бинарного слова, появляющегося в самых разных контекстах и строящегося как неподвижная точка 0110100110010110 • • • морфизма 0 |—> 01,1 1—10. Комбинаторная сложность таких слов растет линейно, а арифметическая, как устанавливается в разделе 2.2, растет экспоненциально (теорема 2.2.3). В частности, сложность слова Туэ-Морса оказывается равна 2", то есть является максимально возможной.

Этот результат позволяет задаться следующим вопросом: а существуют ли бесконечные слова, арифметическая сложность которых растет достаточно медленно, например, линейно? Положительный ответ на этот вопрос дается в разделе 2.3, где описываются равномерно рекуррентные слова с наименьшей арифметической сложностью. Оказывается, что для непериодичных равномерно рекуррентных слов медленнее всего растет арифметическая сложность слов Теплица, порожденных чередованием схем Ра%р = ар~1о и РЬр — Ьр~1о, где число р простое, а а и Ь — различные символы алфавита. Эти слова строятся как предел следующей итеративной конструкции: начав со слова, состоящего из одних пробелов, то есть из символов о, мы последовательно заменяем все оставшиеся пробелы сначала на слово Р£р, потом на слово потом снова на

Ра,р, и так далее. В частности, при р = 3 это последовательно дает слова ооооооооооо---; ааоааоааоаа-■ ааЪааЬаа о аа ■ ■ ■; aabaabaaaaa

Арифметическая сложность ар(п) слова, порождаемого таким образом с помощью схем Раф и Р1кр, удовлетворяет неравенствам

2/> + 2 < ар(п) - 2 6р — 2 Р ~ п _ 2р - 1'

а арифметическая сложность всех других равномерно рекуррентных непериодических слов не может расти медленнее, чем одна из функций ар(п). В этом и состоит основной результат раздела 2.3, совместный с С. В. Августиновичем и Ж. Кассенем и впервые опубликованный в [40].

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

Назовем слово и канонически р-регулярным, если для всех к > О и г € {1,... ,р' — 1} его арифметические подпоследовательности и\. периодичны. Канонически р-регулярные слова также могут быть определены с помощью схем Теплица, подобных описанным выше схемам Рар.

Основным результатом раздела 2.4 является следующая

Теорема 2.4.1. Арифметическая сложность непериодического равномерно рекуррентного слова растет линейно тогда и только тогда, когда это слово принадлежит орбите некоторого канонически р-регулярного слова w, где число р просто, и wC = иК для

р рь

некоторых а фо.

В 2007-м г. автор работы получил за этот результат Третью премию Эйлера в номинации "Молодые исследователи".

В следующих двух разделах, 2.5 и 2.6, с помощью схем Теплица строятся семейства примеров бесконечных слов, арифметическая сложность которых растет как ns для какой-либо степени s > 1. Основными результатами соответствующих разделов являются следующие две теоремы.

Теорема 2.5.1. Для всякого бесконечного слова и над конечным алфавитом Е, комбинаторная сложность которого обозначается через ри(п), и для всякого простого р > 3 существует бесконечное слово над алфавитом Е, арифметическая сложность которого растет как Э(при([к^рп])).

Теорема 2.6.1. Пусть <2 = {<?ь - произвольное конеч-

ное множество простых чисел, к < 2. Тогда для любого с? > 1 существует бесконечное слово ги = и>(<3, й) над (1-буквенным алфавитом,, для арифметической сложности аш(п) = Рс]4{п) которого выполняется свойство

2Я^^Сприп-> оо,

П

где С — некоторая положительная константа, а а((Э,<Г) — единственный положительный корень уравнения

¿=1

В обеих теоремах соответствующее слово строится с помощью схем Теплица, но если в доказательстве теоремы 2.5.1 применяются чисто комбинаторные методы, в том числе уже ставшая классической техника биспециальных слов, то в доказательстве теоремы 2.6.1, совместного результата с Ж. Кассенем и Ф. В. Петровым, для оценки асимптотики арифметической сложности используются, кроме комбинаторных, аналитические методы. Две используемые для этой оценки леммы принадлежат соавторам автора и поэтому приводятся в тексте диссертации без доказательства.

Из вышеописанных результатов следует, в частности, что у слов Штурма — слов с наименьшей комбинаторной сложностью, равной п + 1, — арифметическая сложность растет быстрее, чем линейно. Верхняя оценка и в ряде случаев точные формулы для комбинаторной сложности слов Штурма приводятся в разделе 2.7. Результаты этого раздела получены совместно с Ж. Кассенем [45]. Основной используемый в разделе метод впервые применен Бер-стелем и Поккьолой [13], нашедшими с помощью него совокупное

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

— например, всякому арифметическому подслову слова Штурма

— можно поставить в соответствие точку в двумерном пространстве, координаты которой равны этим двум параметрам, причем при правильном выборе параметров точки из некоторой связной области будут соответствовать одному и тому же слову. Таким образом, верхняя оценка количества всех арифметических подслов слова Штурма может быть получена как число таких связных областей. В данном случае, как и в задаче, рассмотренной Берстелем и Поккьолой, области являются гранями некоторого плоского графа, и их количество может быть найдено по формуле Эйлера.

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

Лемма 2.7.8. Для всех п и для всякого слова Штурма и/ верно неравенство

агс{п) < -'-Л-1 + _ рЫр) + 2,

Р=1

где (р(р) — функция Эйлера, то есть количество натуральных чисел, не превосходящих р и взаимно простых с ним.

Заметим, что правая часть вышеприведенного неравенства растет как (1/6 + 1/тг2)п3 + 0(п2), то есть полученная оценка растет как 0(тг3). Точные значения арифметической сложности зависят от того, какое слово Штурма рассматривается, а точнее, от наклона этого слова. Путем подробного рассмотрения случаев, когда разные грани соответствуют одному и тому же слову, удается найти точные значения арифметической сложности слов Штурма с наклонами, близкими к 1/2, а точнее, с наклонами из интервала

[1/3; 2/3]. В частности, в этот интервал попадает наклон слова Фибоначчи - самого известного из всех слов Штурма, неподвижной точки аЪааЪаЪа ■ ■ • морфизма а ^ ab, b н-> а. Наклон слова Фибоначчи равен а = (3 - л/5)/2 = 0,381966 • • •, и потому оно попадает в зону действия следующей теоремы.

Теорема 2.7.15. Для всякого иррационального a € (0.375,0.4) верны равенства аа( 1) = 2, оа(2) = 4, оа(3) = 8, аа(4) = 16, ав(5) = 30, аа(6) - 52, аа(7) = 83, оа(8) = 128 и

( д(п) — 8, при четном п, аа{п + 1) = < _ g^ npU нечетпн0м п

дляп + 1 > 9, где 9(п) = +±(п-Р + 1 Мр) + 2.

р=1

Заметим, что для наклонов, не входящих в интервал [1/3; 2/3], неизвестно, ограничена ли разность между имеющейся верхней оценкой арифметической сложности соответствующего слова Штурма и самой арифметической сложностью. Однако, как показывает основной результат раздела 2.8, арифметическая сложность всякого слова Штурма тем не менее растет как ©(п3). Справедлива следующая теорема, впервые опубликованная в [39].

Теорема 2.8.1. Для всех п > 0 арифметическая сложность слова Штурма с наклоном а < 1/2 удовлетворяет неравенству

1 L2/o-j х Li/oJ

аа(2п - 2) > ¿MP) - J - 2 ^ Р<Р(р)'

p=i p=i p=1

где (р{р) — функция Эйлера.

Заметим, что для а > 1/2 имеем аа(п) = ai_a(n), и потому данная теорема фактически дает верхнюю оценку арифметической сложности любого слова Штурма. Эта оценка удовлетворяет неравенству аа(п) >^2+ 0{п2) -J^ + O , а значит, меньше

верхней примерно в 10,58 раз. В отличие от верхней оценки она не претендует на точность, поскольку получена достаточно грубыми методами.

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

Глава 3 посвящена свойствам новых объектов, впервые введенных в работе [46], — бесконечных перестановок. Бесконечная перестановка может быть описана как множество натуральных или целых чисел, на которых, кроме стандартного линейного порядка, определен еще один, или, что равносильно, как последовательность (пронумерованная натуральными или целыми числами) попарно различных действительных чисел, в которой нас интересует порядок между элементами, но не их значения. Строгое определение бесконечной перестановки приводится в разделе 3.1. Важно, что аналогично подслову бесконечного слова, можно определить фактор длины п бесконечной перестановки, представляющий собой конечную перестановку длины п. Таким образом, бесконечные перестановки занимают промежуточное положение между классическими конечными перестановками и бесконечными словами.

В данной работе рассматриваются свойства бесконечных перестановок, аналогичные свойствам бесконечных слов, и демонстрируется, что, несмотря на сходство определений и структуры, свойства бесконечных перестановок часто оказываются более сложными и менее предсказуемыми, чем свойства бесконечных слов. Так, в разделе 2.2 устанавливается, что, в отличие от периодических слов, насчитывается счетное, а не конечное, число периодических перестановок с данным периодом. В разделе 2.3 рассматривается аналог для перестановок известной теоремы Файна. — Уилфа:

Теорема (Файн, Уилф). Если слово длины не меньше рЛ-д — (р, д) периодично с периодалш р ид, то оно периодично с периодом (Р^Я)- Длина р + <7 - (р, д) оптимальна для всех слов, кроме как над однобуквенным алфавитом, поскольку существуют бинарные слова длины р + д - (р, д) - 1, периодичные с периодалш р и д, но не (р,д).

Оказывается, что теорема Файна — Уилфа может быть перенесена на перестановки лишь частично, а именно в случаях, когда периоды р и <1 взаимно просты.

Теорема 3.3.1. Если перестановка а длины не меньше р + ц периодична с периодами р и <7, где (р, (?) = 1, то а периодична с периодом 1, то есть монотонна. Длина р + ц здесь наименьшая, поскольку всегда существуют перестановки длины р + q — периодичные с периодами р и ц, но не монотонные.

Для произвольных периодов перестановок теорема Файна — Уилфа неверна, поскольку при (р, д) ф 1 всегда можно построить перестановку, периодическую с периодами р, д, но не (р, с/). Тем не менее в качестве аналога теоремы Файна — Уилфа для перестановок общего вида доказана

Теорема 3.3.5. Если перестановка а длины п является р- и д-периодической, то всякий ее фактор длины не более п — р — д + 2(р, <?) + 1 является, (р, <7)-периодическим.

В разделе 3.4 аналогично комбинаторной сложности слов определяется комбинаторная сложность бесконечных перестановок и доказывается, что, как и для слов, комбинаторная сложность перестановки ограничена константой тогда и только тогда, когда перестановка со временем периодична. Тем не менее, в отличие случая слов, комбинаторная сложность перестановки, определенной на натуральных числах, может расти сколь угодно медленно. Еще одно отличие от слов состоит в том, что сложность ведет себя по-разному в случае перестановок, бесконечных в одну или в обе стороны: если непериодическая перестановка определена на множестве то ее сложность ограничена снизу функцией п — С для некоторой константы С.

Во всех вышеперечисленных результатах свойства перестановок оказывались более разнообразны, менее очевидны и несколько менее изящны, чем свойства слов. Ярким исключением оказываются результаты раздела 3.5, где на бесконечные перестановки переносится понятие максимальной шаблонной сложности. Известно [24], что максимальная шаблонная сложность непериодического бесконечного слова не может быть меньше, чем 2п. Известно также, что сложность равна 2п как минимум для слов Штурма, слов Теплица, порожденных простыми схемами, и некоторых нере-

куррентных слов особого вида [25]. Однако до сих пор неизвестно, существуют ли другие примеры слов со сложностью 2п. В то же время для непериодичных перестановок, как удалось установить в работе [44], совместной с С. В. Августиновичем, Т. Камаэ и П. В. Салимовым, наименьшая максимальная шаблонная сложность равна га, и, в отличие от слов, перестановки с максимальной шаблонной сложностью п удалось естественно охарактеризовать.

Теорема 3.5.2. Максимальная шаблонная сложность р*(га) бесконечной перестановки а равна п для всех п тогда и только тогда, когда а — перестановка Штурма.

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

Наконец, в разделе 3.6 произведена попытка обобщить на бесконечные перестановки понятие автоматности бесконечных слов: слово называется ¿-автоматным, если его символ номер п может быть вычислен с помощью конечного автомата, на вход которого поступает Личное разложение числа п. Существует также по меньшей мере три других эквивалентных определения автоматного слова [10]. Оказывается, что эквивалентные определения автоматного слова при переносе на перестановки перестают быть эквивалентными. Основными результатами пункта 3.6 являются утверждения, описывающие строгую вложенность соответствующих классов. Самым нетривиальным из них является лемма 3.6.8, утверждающая, что всякая перестановка, порожденная автоматным словом, может быть порождена конечным автоматом.

Наконец, глава 4 посвящена свойствам моноида факторных языков и решению уравнений над факторными языками. Напомним, что язык X называется факторным, если он замкнут относительно операции Fac взятия подслов всякого элемента: X =Fac(X).

Назовем факторный язык X разложимым, если X = YZ для некоторых факторных языков Y и Z, ни один из которых не равен X; в противном случае язык X называется неразложимым. Разложение факторного языка X в произведение факторных языков Х\,... ,Хп, X = Х\ ■ ■ ■ Хп, назовем минимальным, если все языки Xi не равны {Л}, где Л пустое слово, и ни один из языков А", не может быть без изменения результата заменен на свое собствен-

ное подмножество: X ф Х\ ■ • • Х[ ■ ■ • Хп, где Х[ С Х1. Минимальное разложение факторного языка в произведение неразложимых языков называется каноничестм разложением языка X.

Важнейшим результатом главы 4 является следующая

Теорема 4.1.3. У всякого факторного языка существует единственное каноническое разложение.

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

Несмотря на неконструктивность доказательства, теорема 4.1.3 предоставляет технику, позволяющую сводить уравнения над факторными языками к уравнениям над словами. Метод решения уравнений основан на том, каким может быть каноническое разложение конкатенации факторных языков, каноническое разложение которых известно. Возможные варианты описаны в разделе 4.2. В разделе 4.4 описанная техника применена к решению над бинарными факторными языками уравнений Хп — У11, ХУ = УХ (коммутирование) и XZ = ZУ (сопряжение). Первое из них выполняется, только если X = У; решения третьего слишком разнообразны, чтобы легко записываться; наконец, решения уравнения коммутирования ХУ = УХ над бинарными факторными языками полностью описаны и попадают в одну из пяти категорий. Чтобы перечислить их, для каждого факторного языка X введем подалфавиты

Про ={х£ Е|Хж С X} и Д(Х) = {х е Е\хХ С X}.

Как нетрудно проверить, два бинарных факторных языка коммутируют в каждом из следующих пяти случаев. Словесное коммутирование. ХУ = УХ, если X = Zrn и У = Zn для некоторого факторного языка Z и неотрицательных целых п и т.

Поглощение. Пусть Ех — подалфавит всех букв, входящих в факторный язык X. Если УЕХ С У, Ед-У С У,"то ХУ = УХ = У = УЕ у = Е*\У' язык У поглощает язык X.

В бинарном случае поглощение значит, что либо X = {Л}, либо X С х* для некоторой буквы х и П(У) = Д(У) = {ж}, либо У = {а,Ъ}*.

Неожиданное коммутирование I. Пусть 2 — бинарный факторный язык с А(2) = {ж} и Щ2) = {у}, х ф у. Тогда для всех г,р > О язык 2Т' коммутирует со всяким языком X, для которого верны вложения

ггас ггх* п у*гг.

Пример. Пусть ^ =Еас({а,а6}*) и ^ =¥ж({Ь,аЬ}*), т.е. язык -^а содержит все слова, не содержащие двух стоящих рядом Ь, а язык ^ — все слова, не содержащие двух стоящих рядом а. Рассмотрим £ = ^ • Тогда всякий язык X = 2 + 5, где 5 является факторным подмножеством языка а*Ь*, коммутирует со всякой степенью 2Р языка 2.

Неожиданное коммутирование II. Рассмотрим символ х алфавита {а, 6} и бинарный факторный язык С¡>, для которого ЬХ{Я) = Кх(Я) = Я и Д(<2),П(<2) равны 0 или {у}, у ф х. Тогда для всех р > 0 и г > 1 язык (х*Я)рх* коммутирует со всяким языком А, удовлетворяющим включениям

(х*ЯУ + (Ях*у ас (хчэух*.

Пример. Языки А = а*Ъ* + Ъ*а* и В = а* коммутируют, поскольку АВ = В А = а*Ь*а*. Здесь х = а и С? = Ь*, так что в действительности В коммутирует со всяким языком, являющимся одновременно надмножеством языка а*Ъ* + Ь*а* и подмножеством языка а*Ъ*а*. Неожиданное коммутирование III. Рассмотрим бинарный факторный язык ¿Г, для которого верно равенство 22 = 2 2, и А(2) = {ж}. Пусть В — факторный язык, для которого 2п С В С 2пх*, тг > 0. Тогда для всех пг > 0 язык В коммутирует с 2тВ.

__Симметрично, для всякого бинарного факторного 2 с 22 =

гги П (2) = {ж} и для всякого бинарного факторного языка В с 2п С В С х*2п, язык В коммутирует с В2т, каковы бы ни были п,т > 0.

Пример.Рассмотрим языки 2 = а*Ь* и В =¥&с(а*(ЬЬ)*а*Ь*+ а*Ъ(ЪЪ)*а*Ь*а*).^Здесъ Л(2) = {а} и = а*Ъ*а*Ъ* С В С а*Ь*а*Ь*а* = 2 а*. Таким образом, В коммутирует со всеми множествами А вида А = 2тВ: АВ = В А = 2т+2В.

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

Теорема 4.4.9. Два бинарных факторных языка коммутируют тогда и только тогда, когда возникает одна из вышеописанных ситуаций: либо словесное коммутирование, либо поглощение, либо неожиданное коммутирование I, II или III.

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

[1] С. И. Адян. Проблема Бернсайда и связанные с ней вопросы // Успехи мат. наук. 2010. Т. 65. № 5. С. 5-60.

[2] А. А. Евдокимов. О сильно асимметричных последовательностях, порожденных конечным числом символов // Докл. АН СССР. 1968. Т. 179. № 6. С. 1268-1271.

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

[4] Е. П. Липатов. Об одной классификации двоичных наборов и свойствах классов однородности // Проблемы кибернетики. 1982. М.: Наука. Т. 39. С. 67-84.

[5] М. А. Макаров. О перестановках, порожденных бесконечными бинарными словами // Сиб. электрон, матсм. изв. 2006. Т. 3. С. 304311.

[6] М. А. Макаров. Антимонотонные перестановки /'/' Сиб. электрон, матем. изв. 2012. Т. 9. С. 346-359.

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

[8] И. Д. Шкредов. Теорема Семереди и задачи об арифметических прогрессиях // Успехи мат. наук. 2006. Т. 61. № 6. С. 111-179.

[9] В. Adamczewski, Y. Bugeaud. On the complexity of algebraic numbers I. Expansions in integer bases // Annals of Math. 2007. V. 165. P. 547-565.

[10] J.-P. Allouche, J. Shallit. Automatic sequences — theory, applications, generalizations. Cambridge University Press, 2003.

[11] P. Ambroz, A. Frid, Z. Masakova, E. Pelantova. On the number of factors in codings of three interval exchange // Discr. Math. Theoret. Comput. Sci. 2011. V. 13. P. 51-66.

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

13] J. Bcrstel, M. Pocchiola. A geometric proof of the enumeration formula for Sturmian words // Int. J. Algebra and Comput. 1993. V 3 P 349355.

14] J. Berstel, P. Sécbold. Sturmian words, in: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002. P. 40-97.

15] J. Cassaigne. Complexité et facteurs spéciaux // Bull. Belg. Math Soc Simon Stevin. 1997. V. 4. P. 67-88.

16] J. Cassaigne. Special factors of sequences with linear subword complexity // Developments of Language Theory II. Singapore: World Sci Publishing. 1996. P. 25-34.

17] J. Cassaigne. Unavoidable patterns. In: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press. 2002.

18] C. Choffrut, J.Karhumaki. On Fatou proper-ties of rational languages // C. Martin-Vide and V. Mitrana, Eds. Where Mathematics, Computer Science, Linguistics and Biology Meet. Dordrecht: Kluvver. 2000 P 227235.

19] J. D. Currie. Open problems in pattern avoidance /'/ Amer. Mathem Monthly 1993. V. 100. P 790-793.

20] J. A. Davis, R. C. Entringer, R. L. Graham, and G. J. Simmons. On permutations containing no long arithmetic progressions // Acta Arithmetica 1977. V. 34. P. 81-90.

21] F. Dejean. Sur un théorème de Time /'/ J. Combin. Theory Ser. A 1972 V. 12. P. 90-99.

22] V. Diekert. Makanin's Algorithm, in: M. Lothaire, Algebraic combinatorics on words, Cambridge Univ. Press, 2002. P. 387-442.

23] A. Ivânyi, On the d-complexity of words // Ann. Univ. Sci. Budapest Sect. Comput. 1987. V. 8. P. 69-90.

24] T. Karaae, L. Zamboni. Sequence entropy and the maximal pattern complexity of infinite words // Ergodic Theory Dynam. Systems 2002 V. 22. P. 1191-1199.

25] T. Kamae, L. Zamboni. Maximal pattern complexity for discrete systems // Ergodic Theory Dynam. Systems 2002. V. 22. P. 1201-1214.

V. Kerânen. Abelian squares are avoidable on 4 letters // Automata, Languages and Programming. Berlin: Springer, 1992. P. 41-52. (LNSC V. 623).

M. Kunc. The power of commuting with finite sets of words // Theory Comput. Syst. 2007. V. 40. P. 521-551.

J. Leroy. Some improvements of the S-adic conjecture // Advances in Appl. Math. 2012. V. 48. P. 79-98.

M. Morse, G. A. Hedlund. Symbolic Dynamics II. Sturmian trajectories // Am. J. Math. 1940. V. 62. P. 1-42.

I. Nakashima, J.-I. Tamura, Sh.-I. Yasutomi. *-Sturmian words and complexity // J. Théorie Nombres Bordeaux 2003. V. 15. P. 767-804.

P. Ochem. Binary words avoiding the pattern AABBCABBA // Theoret. Informatics Appl. 2010. V. 44. P. 151-158.

A. Restivo, S. Salemi. Binary patterns in infinite binary words // Formal and Natural Computing. Berlin: Springer, 2002. P. 107-116. (LNCS Vol. 2300).

A. Salomaa, S. Yu. On the decomposition of finite languages // Developments in Language Theory. Foundations, Applications, Perspectives. World Scientific, 2000. P. 22-31.

A. M. Shur. Growth properties of power-free languages // Proc. DLT 2011. Berlin: Springer, 2011. P. 28-43. (LNCS Vol. 6795).

A. Thue. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen // Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1912. V. 10. P. 1-67.

A. Thue. Uber unendliche Zeichenreihen /'/ Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1906. V. 7 P. 1-22.

S. Widmer. Permutation complexity of the Thue-Morse word // Adv. Appl. Math. 2011. V. 47. P. 309-329.

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

Ж. Кассеиь, Ф. В. Петров, А. Э. Фрид. О возможных скоростях роста языков Теплица ,// Снб. мат. журнал 2011. Т. 52. № 1. С. 8194.

А. Фрид. Нижняя оценка на комбинаторную с/южностъ слов Штурма // Сиб. электрон, матсм. изв. 2005. Т. 2. С. 14-22.

[40] S. V. Avgustinovich, J. Cassaigne, A. E. Frid. Sequences of low arithmetical complexity // Theoret. Informatics Appl. 2006. V. 40 P. 569-582.

[41] S. V. Avgustinovich, D. G. Fon-Dcr-Flaass, A. E. Fricl. Arithmetical complexity of infinite words // Proc. Words, Languages and Combinatorics III, 2000. Singapore: World Scientific, 2003. P. 51-62.

[42] S. V. Avgustinovich, A. E. Frid. A unique decomposition theorem for factorial languages // Int. J. Algebra Comput. 2005. V. 15. P. 149-160.

[43] S. V. Avgustinovich, A. E. Frid. Canonical decomposition of a regular factorial language // Proc. CSR 2006. Berlin: Springer, 2006. P. 18-22 (LNCS Vol. 3967).

[44] S. V. Avgustinovich, A. E. Frid, T. Kamae, P. Salimov. Infinite permutations of lowest maximal pattern complexity // Theoret. Comput Sci. 2011. V. 412. P. 2911—2921.

[45] J. Cassaigne, A. E. Frid. On arithmetical complexity of Sturmian words 11 Theoret. Comput. Sci. 2007. V. 380. P. 304-316.

[46] D. G. Fon-Der-Flaass, A. E. Frid. On periodicity and low complexity of infinite permutations // European J. Combinatorics 2007. V. 28 P. 2106-2114.

[47] A. E. Frid. Arithmetical complexity of symmetric D0L words /' / Theoret Comput. Sci. 2003. V. 306. P. 535-542.

[48] A. Frid. Canonical decomposition of a catenation of factorial languages // Sib. Electron. Math. Reports 2007 V. 4. P. 12-19.

[49] A. Frid. Commutation of binary factorial languages //' Proc. DLT 2007 Berlin: Springer, 2007. P. 193-204. (LNCS Vol. 4588).

[50] A. Frid. Fine and Wilf's theorem for permutations // Sib. Electron. Math. Reports 2012. V. 9. P. 377-381.

[51] A. E. Frid. On possible growths of arithmetical complexity // Theoret. Informatics Appl. 2006. V. 40. P. 443-458.

[52] A. E. Frid. Sequences of linear arithmetical complexity // Theoret. Comput. Sci. 2005. V. 339. P. 68-87.

[53] A. Frid. Simple equations on binary factorial languages // Theoret. Comput. Sci. 2009. V. 410. P. 2947-2956.

[54] A. Frid, L. Zamboni. On automatic infinite permutations /7 Theoret. Informatics Appl. 2012. V. 46. P. 77-85.

Фрид Анна Эдуардовна

Комбинаторные сложпостные характеристики бесконечных слов, языков и перестановок

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

Подписано в печать 11.10.12г. Формат 60x84 1/16. Усл. печ. л. 2,0. Уч.-изд. л. 2,0. Тираж 120 экз. Заказ №180

Отпечатано в ООО "Омега Принт" пр. Ак. Лаврентьева, 6, 630090 Новосибирск

0.1 Актуальность темы.

0.2 Обзор.

0.2.1 Теория избегаемое™.

0.2.2 Понятия сложности бесконечных слов и языков.

0.2.3 Бесконечные перестановки

0.2.4 Моноид формальных языков.

0.3 Цели и результаты работы

0.4 Апробация и публикации.

0.5 Содержание работы.

1 Основные понятия

1.1 Вводные определения и обозначения.

1.2 Периодические слова.

1.3 Слова Штурма.

1.4 Вращательные слова.

1.5 Морфизмы и их неподвижные точки.

1.6 Автоматные слова.

1.7 Схемы Теплица.

1.8 Равномерно рекуррентные слова.

1.9 Максимальная шаблонная сложность.

1.10 Факторные языки и операции над ними.

1.11 Специальные слова и сложность.

Арифметическая сложность бесконечных слов

2.1 Определение, обсуждение и примеры

2.2 Сложность неподвижных точек симметрических и квазисимметрических морфизмов.

2.3 Низкая арифметическая сложность равномерно рекуррентных слов.

2.3.1 Бесконечные специальные ветви.

2.3.2 Случай двух ветвей

2.3.3 Наименьшая арифметическая сложность.

2.4 Линейная арифметическая сложность равномерно рекуррентных слов.

2.4.1 Канонически р-регулярные и р-регулярные слова.

2.4.2 Случай конечного числа бесконечных специальных ветвей

2.4.3 Основная лемма

2.4.4 Завершение доказательства.

2.5 Арифметическая сложность обобщенных слов Теплица: схемы фиксированной длины.

2.5.1 Конструкция.

2.5.2 Арифметическое замыкание слова Ьр(и).

2.5.3 Биспециальные слова языка А.

2.5.4 Степени биспециальности и диаграмма первых разностей

2.5.5 Оценки на арифметическую сложность.

2.5.6 Обсуждение.

2.6 Арифметическая сложность обобщенных слов Теплица: схемы разных длин

2.6.1 Конструкция языка ^(<5, (1)

2.6.2 Рекуррентная формула для первых разностей

2.6.3 Рост функции з(п).

2.6.4 Тауберова теорема.

2.6.5 Завершение доказательства.

2.7 Арифметическая сложность слов Штурма: верхняя оценка и точные формулы.

2.7.1 Арифметические подпоследовательности слов Штурма

2.7.2 Геометрический двойственный метод.

2.7.3 Количество граней.

2.7.4 Симметрия.

2.7.5 Наследование граней.

2.7.6 Вычислительный эксперимент

2.7.7 Интервалы Фарея и изоморфизм.

2.7.8 Точные формулы.

2.7.9 Обсуждение.

2.8 Нижняя оценка на арифметическую сложность слов Штурма . 146 2.8.1 Нижняя оценка.

2.8.2 Нижняя оценка для вращательных слов.

3 Периодичность и сложность бесконечных перестановок

3.1 Бесконечные перестановки и бесконечные слова.

3.2 Периодические бесконечные перестановки.

3.3 Периоды конечных перестановок.

3.4 Факторы и факторная сложность

3.5 Максимальная шаблонная сложность перестановок

3.5.1 Определение и неравенство р*(п) > п.

3.5.2 Перестановки Штурма и теорема о максимальной шаблонной сложности.

3.5.3 Максимальная шаблонная сложность перестановок Штурма

3.5.4 Схема доказательства в обратную сторону

3.5.5 Случай последовательности Штурма.

3.5.6 Случай периодической последовательности.

3.6 Автоматные перестановки.

4 Моноид факторных языков

4.1 Канонические разложения.

4.1.1 Подалфавиты и выжимки.

4.1.2 Доказательство существования.

4.1.3 Доказательство единственности.

4.2 Вид канонического разложения катенации

4.3 Свойства факторных языков.

4.4 Уравнения над факторными языками.

4.4.1 Простые уравнения над словами.

4.4.2 Унарные факторные языки.

4.4.3 Уравнение Хп = Уп.

4.4.4 Коммутирование.

4.4.5 Сопряжение.

4.5 Канонические разложения регулярных факторных языков

0.1 Актуальность темы

В диссертации рассматриваются свойства и характеристики бесконечных слов и родственных им объектов, а именно бесконечных перестановок и факторных языков, зависящие только от множества входящих в слово (или в бесконечную перестановку, или в язык) фрагментов — подслое или факторов. Таким образом, результаты диссертации находятся в рамках следующей проблематики: какими свойствами может и какими не может обладать множество подслов данного слова (перестановки)? Сколько определенных заданным образом фрагментов данного размера может содержаться в бесконечном слове (перестановке), как может и как не может расти их количество? Как факторный язык может быть разложен в произведение нескольких факторных языков, и как решать уравнения над факторными языками?

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

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

Результаты диссертации разбиваются на три части: об арифметической сложности бесконечных слов; о бесконечных перестановках и их свойствах; и о разложениях факторных языков. Начнем с обзора предыдущих исследований.

0.2 Обзор

0.2.1 Теория избегаемости

Считается, что начало современной комбинаторики на словах положили работы Акселя Туз, датированные 1906 [84] и 1912 [83] годами; их пересказ содержится также в обзоре Ж. Берстеля [25]. Туэ задался вопросом: существует ли бесконечное слово над конечным алфавитом, в котором никогда не встречаются два одинаковых подслова подряд — то есть, например, не встречается подслово аЬсаЬс, представляющее собой два подряд вхождения подслова аЬс? Нетрудно проверить, что над бинарным алфавитом таких слов не бывает, но Туэ удалось построить первый пример такого слова над алфавитом из трех символов. Конструкция Туэ была довольно тяжеловесна; современный же стандартный пример такого тернарного слова строится как неподвижная точка морфизма а —> аЬс, Ь —> ас,

Начав с символа а, применим к нему последовательно много раз морфизм определяя образ конкатенации символов как конкатенацию их образов. Мы получим последовательность слов а —abc abc acb -> abcacb abcb ас • • • .

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

Это слово и является ответом на вопрос Туэ, поскольку можно доказать, что в нем никогда не содержится двух одинаковых подслов подряд.

Из работ Туэ выросло целое направление исследований — теория избегаемое™. Классическая постановка задачи об избегании звучит так: пусть дано слово W = W\ - ■ ■ Wn над алфавитом переменных {X, У,.}; существует ли слово над конечным алфавитом, избегающих вхождений этого слова, то есть слов вида h(W\) ■ • • h(Wn), где h — нестираю-щий морфизм? Заметим, что вопрос Туэ в этих терминах формулируется как вопрос об избегаемости слова XX.

Зимин [5], а также независимо Бин, Эренфойхт и Мак-Налти [24] привели алгоритм решения этого вопроса, после чего в центр внимания попали сразу несколько смежных задач: если слово над алфавитом переменных избегаемо, то какого алфавита достаточно, чтобы его избежать? Что если определять формат слов, которых мы хотим избежать, каким-либо другим образом — например, требовать избегания слов вида X ■ • • X.Х\ где к слово X' — префикс слова X, или слов вида Х'Х", где слова X' и X" одинаковы по составу, то есть содержат равное количество вхождений каждого из символов. Какие слова над алфавитом переменных избегаются в данном бесконечном слове? Все эти вопросы в настоящий момент достаточно хорошо исследованы; см. обзоры и результаты в работах [34), [42], [74], [62].

Разнообразные вопросы, связанные с избегаемостью, активно изучаются до сих пор. В частности, до сих пор не доказано и не опровергнуто, что если некое слово над алфавитом переменных избегаемо над некоторым алфавитом, то над этим алфавитом существует слово, избегающее его и строящееся как результат применения к неподвижной точке мор-физма какого-то другого морфизма [41].

В главе 1 дается краткий обзор стандартных способов построения непериодических бесконечных слов с нетривиальными свойствами (разделы 1.3-1.7).

0.2.2 Понятия сложности бесконечных слов и языков

Вторым краеугольным камнем комбинаторики на словах является работа Морса и Хед-лунда [70]. среди прочих вопросов задавшихся вопросом о том, каким может быть множество подслов данной длины бесконечного слова. Подсловом конечного или бесконечного слова w называется конечное слово и, такое что w = sut для некоторых (конечных или бесконечных) слов s и i. Количество подслов заданной длины данного бесконечного слова w называется его комбинаторной сложностью и обозначается через pw(n). Морс и Хедлунд доказали, что комбинаторная сложность бесконечного слова ограничена сверху константой тогда и только тогда, когда слово периодично (см. раздел 1.2), и. более того, что комбинаторная сложность непериодического слова не может быть меньше чем n + 1 для всякой длины п.

Слова с комбинаторной сложностью pw(n) = n + 1 называются словами Штурма и прекрасно изучены (см. раздел 1.3). Однако попытки охарактеризовать более широкий класс слов с низкой сложностью приводят к очень громоздким и при этом неполным результатам. Так, на данный момент известно очень сложно формулируемое (и поэтому даже неопубликованное) утверждение о структуре слов со сложностью не больше 2п, принадлежащее Ж. Леруа; однако до сих пор неизвестна характеризация слов, например, с линейной сложностью. Имеющиеся утверждения о словах с линейной сложностью, описывающие их структуру с помощью морфизмов, не являются характеризациями [49, 65).

Кроме того, представляют интерес и активно разрабатываются несколько классов вопросов. Какой может и какой не может быть комбинаторная сложность бесконечного слова? Как оценить комбинаторную сложность слова, построенного заданным образом? Собственно говоря, известная нерешенная проблема теории чисел о том, любая ли последовательность цифр встречается в десятичном разложении числа 7г, также является вопросом о комбинарной сложности, а точнее, о том, верно ли, что комбинаторная сложность десятичного разложения числа 7Г равна 10". Самым сильным из известных результатов о комбинаторной сложности g-ичных разложений чисел является результат Адамчевского и Бюжо [17] о том, что комбинаторная сложность всякого ç-ичного разложения алгебраического иррационального числа растет быстрее, чем линейно.

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

Смежным является вопрос о комбинаторной сложности не бесконечных слов, а языков, то есть о количестве элементов этих языков заданной длины. Так, А. М. Шур (см. докторскую диссертацию [16] и приводимые там ссылки) занимался изучением сложности регулярных языков. Особый интерес представляет случай, когда язык является факторным, то есть замкнут относительно взятия подслов. Факторными являются, например, язык всех слов, избегающих заданного слова над алфавитом переменных, язык всех подслов слов Штурма и другие языки, полученные объединениями языков подслов бесконечных слов какого-либо семейства. К примеру, мощность множества всех слов Штурма данной длины была впервые найдена Липатовым [11], а затем Миньози [69] и Берстелем и Поккьолой [26]. Слова Штурма по-другому могут быть охарактеризованы как слова, порожденные перекладыванием двух отрезков, и их количество для данной длины растет как 0(п3). В работе [22] были установлены верхняя и нижняя оценки на количество слов данной длины, порожденных перекладыванием трех отрезков; из этих оценок следует, в частности, что их количество растет как 0{пА).

Отдельной бурно исследоваемой областью являются оценки на количество слов данной длины, избегающих какого-либо слова над алфавитом переменных или подслов, заданных какими-либо подобными ограничениями. В подобных задачах активно используются вычислительные методы; как результат, в некоторых случаях имеющиеся оценки уже весьма точны. Так, известно, что количество всех тернарных слов, избегающих двух одинаковых слов подряд, то есть слова XX над алфавитом переменных, находится между Cil, 301759" и С21,301761" [80] (см. также [6] и [72]).

Отметим, что рост комбинаторной сложности различных языков, задаваемых вполне естественными ограничениями, или слов, строящихся с помощью не слишком сложных конструкций, может быть достаточно необычным: например, субполиномиальным, но осциллирующим между двумя полиномами разных степеней [32] или промежуточным между полиномиальным и экспоненциальным [31, 81].

В последние годы развиваются также направления, основанные на модификациях определений комбинарной сложности. Оставаясь в рамках подхода, при котором сложность оценивается не как сложность построения последовательности символов, а как количество фрагментов заданного размера в ней, можно ввести и исследовать на естественность свойств несколько определений, родственных комбинаторной сложности, но не равных ей. Так, А. Иваный в 1987 году ввел понятие ¿-сложности [48]; Рестиво и Салеми в 2002 году ввели шаблонную сложность [75] как количество слов данных слов над алфавитом переменных, вхождения которых входят в данное бесконечное слово; Накашима, Тамура и Ясутоми также ввели еще одно понятие модифицированной сложности [71]. Наиболее же исследованы и перспективны в данный момент две нестандартных комбинаторных функции сложности: максимальная шаблонная сложность, введенная в 2002 год}' Т. Камаэ и Л. Замбони [60, 61] (см. раздел 1.9) и арифметическая сложность, введенная в 2000 году Ав-густиновичем, Фон-Дер-Флаассом и автором [92]. Свойствам арифметической сложности полностью посвящена глава 2 данной работы.

Заметим, что в своем роде арифметическая сложность является продолжением направления исследований, начатого классическими теоремами Ван дер Вардена и Семереди. О других известных продолжениях исследований арифметических прогрессий можно прочесть в обзоре [15].

0.2.3 Бесконечные перестановки

Несмотря на обилие литературы как о классических конечных перестановках, бесконечные перестановки, рассматриваемые в главе 3, являются новым объектом, или по крайней мере изучаются с точки зрения, с которой ранее никогда не изучались. Нас интересуют факторы перестановок, структура их множества, их количество и свойства, то есть в точности те же самые параметры, что и для слов. Самым близким по духу из более ранних результатов можно считать работу Дэвиса и пр. [44] о перестановках, в которых не встречается длинных монотонных арифметических подперестановок.

Одновременно и параллельно с автором и соавторами схожие свойства бесконечных перестановок, в особенности перестановок, получаемых с помощью непериодических бесконечных слов, исследовали Макаров [7, 8, 67, 68. 9], Августинович, Валюженич, Китаев и Пяткин [23], Уидмер [87, 88], Валюженич [85].

0.2.4 Моноид формальных языков

Напомним, что языком над алфавитом Е называется произвольное подмножество множества Е* всех слов над Е. Над языками определяются стандартные операции — пересечение (П), объединение (и) или (+), дополнение и конкатенация ХУ, определяемая как язык всех слов вида ху, где х € X и у € У.

Относительно конкатенации множество всех языков представляет собой моноид с единицей {Л}, где Л пустое слово, и нулем 0. В отличие от уравнений над словами, решение которых хорошо исследовано [46], попытки решать уравнения над этим моноидом могут приводить к совершенно неожиданным и плохо классифицируемым результатам. Так, Кунц [64] построил пример конечного языка X. для которого максимальный язык У, коммутирующий с ним, то есть максимальный язык, для которого ХУ = УХ, не является даже рекурсивно перечислимым. Даже оставаясь в рамках рассмотрения конечных унарных языков, можно встретить множество примеров, когда, например, X2 = У2, но X ^ У [78]. Таким образом, исследования моноида языков демонстрируют впечатляющее разнообразие неожиданных сложностей, затрудняющих решение, например, уравнений над языками.

В данной работе рассматривается подмоноид моноида формальных языков, содержащий только фактюрные языки, то есть языки, замкнутые относительно взятия подслова любого элемента. Факторными являются, в частности, все языки, упомянутые выше: языки всех подслов бесконечного слова, языки всех слов, избегающих подслов заданного вида, языки всех слов, полученных определенным образом (например, подслов всех слов Штурма). Кроме того, для каждого формального языка, построенного любым способом, можно определить его факторное замыкание — минимальный факторный язык, содержащий данный; при этом, как нетрудно доказать, факторное замыкание, например, регулярного языка регулярно.

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

0.3 Цели и результаты работы

Цели работы: исследовать новые комбинаторные сложностные характеристики бесконечных слов; распространить как известные, так и новые функции от бесконечных слов на родственные им объекты, в частности, факторные языки и бесконечные перестановки, и исследовать, какие именно из этих функций являются естественными и важными для этих объектов; выработать новые методы работы с факторными языками слов и перестановок.

Методы исследования. В диссертации применяются как классические комбинаторные методы, в частности, методы комбинаторики на словах, так и методы, заимствованные из алгебры, теории чисел, дискретной геометрии и теории графов. В статьях, написанных в соавторстве, соавторы автора диссертации использовали также аналитические и динамические методы; соответствующие результаты, принадлежащие соавторам автора — лемма 2.6.12 и теорема 2.6.13 из [89] и лемма 1.4.1 из [95] — приведены в диссертации без доказательств.

Хочется отметить, что несколько методов исследования, применяемых в данной работе, разработаны специально для ее результатов и применены впервые. К наиболее нетривиальным из них можно отнести, прежде всего, метод бесконечных специальных ветвей, применяемый для характеризации слов с низкой арифметической сложностью (см. разделы 2.3 и 2.4), все примененные в главе 3 методы работы с бесконечными перестановками, и метод выжимок до канонического разложения, применяемый в главе 4 для решения уравнений над факторными языками.

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

Основными результатами работы являются следующие.

1. Охарактеризованы равномерно рекуррентные бесконечные слова, арифметическая сложность которых растет линейно.

2. Описаны равномерно рекуррентные бесконечные слова, арифметическая сложность которых минимальна для непериодических слов (совместно с С. В. Августиновичем и Ж. Кассенем).

3. Найдены оценки, а в некоторых случаях (включая случай слова Фибоначчи) точные формулы на арифметическую сложность слов Штурма; как оказывается, она растет как 0(п3). Этот же результат, совместный с Ж. Кассенем, может быть переформулирован следующим образом: найдены оценки, а в некоторых случаях точные формулы на количество всех вращательных слов с фиксированной шириной интервала.

4. Введено понятие периодичности бесконечных перестановок; установлено, что периодических бесконечных перестановок с данной длиной периода существует бесконечное количество; установлено, что периодичность перестановки эквивалентна ограниченности ее сложности; исследован возможный медленный рост сложности непериодических перестановок (совместно с Д. Г. Фон-Дер-Флаассом).

5. Охарактеризованы бесконечные перестановки, максимальная шаблонная сложность которых минимальна для непериодичных перестановок и равна п; как оказывается, они порождаются тем же способом, что и слова Штурма, и поэтому названы перестановками Штурма (совместно с С. В. Августиновичем, Т. Камаз и П. В. Салимовым).

6. Доказана теорема существования и единственности канонического разложения факторного языка в конкатенацию факторных языков (совместно с С. В. Августинови-чем).

7. Полностью решено уравнение коммутирования XY = YX на множестве бинарных факторных языков.

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

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

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

• на Рабочей встрече об избегаемости слов, сложности и морфизмах (Турку, Финляндия, 2004);

• на Летней сессии Канадского математического общества (Ватерлоо, Канада, 2005);

• на Международной алгебраической конференции (Екатеринбург, 2005);

• на конференции WORDS 2011 (Прага, Чехия). Кроме того, результаты были доложены

• на Международном конгрессе по словам, языкам и комбинаторике (Киото, Япония, 2000);

• на конференциях WORDS 2003 (Турку, Финляндия), WORDS 2005 (Монреаль, Канада), WORDS 2009 (Салерно, Италия);

• на Европейской конференции по комбинаторике (Берлин, Германия, 2005);

• на Конференции по комбинаторике, автоматам и теории перечисления (Льеж, Бельгия, 2006);

• на Международном симпозиуме по теоретической информатике в России (Санкт-Петербург, 2006);

• на Международной конференции по теории формальных языков (Турку, Финляндия, 2007);

• на Школе по комбинаторике на словах (Монреаль, Канада, 2007);

• на Монсовских днях (Амьен, Франция, 2010);

• на Рабочей группе по комбинаторике на словах (Банфф, Канада, 2012);

• на Мальцевских чтениях (Новосибирск, 2006);

• на Лаврентьевских чтениях (Новосибирск, 2003 и 2007);

• в Санкт-Петербургском Computer Science Club (2011);

• на семинарах в университетах Марселя, Лиона, Нанси и Турку (2009-2012);

• на семинарах "Факторные языки", "Теория кодирования", "Теория графов" в Институте математики им. С. Л. Соболева СО РАН (1999-2011).

По теме диссертации опубликовано 17 работ [89]-[105], из них 12 (все, кроме [90], [92], [94], [99], [100]) — в изданиях из списка ВАК. Работы [91, 92, 93, 94, 97] написаны в нераздельном соавторстве с С. В. Августиновичем, Ж. Кассенем, Д. Г. Фон-Дер-Флаассом. В работе [96] Ж. Кассеню принадлежит идея использования в рассматриваемой задаче геометрического метода Берстеля и Поккьолы, а автору — формулировка задачи, детали применения этой техники и оставшаяся часть доказательств; в работе [105] автору принадлежит исходная формулировка задачи и все доказательства. В статьях [89] и [95] присутствуют утверждения, полностью принадлежащие соавторам автора; это соответственно лемма 2.6.12 и теорема 2.6.13 из [89] и лемма 1.4.1 из [95], приводимые в диссертации без доказательств.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы (105 наименований, включая 17 работ автора по теме диссертации, приведенных в конце списка). Текст работы изложен на 245 страницах и содержит 27 рисунков.

1. Ц. Ч.-Д. Батуева. Серия двумерных слов с максимальной оконной сложностью 2к // Дискреты, анализ и исслед. опер. 2010. Т. 17. № 5. С. 3-14.

2. А. А. Бухштаб. Теория чисел. М.: Просвещение, 1966. 385 с.

3. А. А. Евдокимов. О сильно асимметричных последовательностях, порожденных конечным числом символов // Докл. АН СССР. 1968. Т. 179. 6. С. 1268-1271.

4. А. А. Евдокимов. Существование базиса, порождают,его 1-зна.чные бесповторные последовательности // Дискретн. анализ. 1971. Вып. 18. С. 25-30.

5. А. И. Зимин. Блокируючцие множества т,ермов // Мат. Сб. 1982. Т. 119 (161), 3 (11), С. 363-375.

6. Р. М. Колпаков. Об оценке числа бесповторны,х слов // Дискретн. анализ и исслед. опер. 2006. Т. 13. № 2. С. 21-37.

7. М. А. Макаров. О перестановках, порожденных бесконечными бинарными словами // Сиб. электрон, матем. изв. 2006. Т. 3. С. 304-311.

8. М. А. Макаров. О перестановках, порожденных словами Шт,урма // Сиб. матем. журн. 2009. Т. 50. № 4. С. 850-857.

9. М. А. Макаров. Антимонот,онные перестановки //' Сиб. электрон, матем. изв. 2012. Т. 9. С. 346-359.

10. Ж. Лаллеман. Полугруппы и комбинаторные приложения. М.: Мир, 1985. 440 с.

11. Е. П. Липатов. Об одной классификации двоичных наборов и свойствах классов однородности // Проблемы кибернетики. 1982. М.: Наука. Т. 39. С. 67-84.

12. Г. М. Фихтентольд. Курс дифференциального и интегрального исчисления. Т. 1. М.: Физматлит, 2001.

13. А. Э. Фрид. О комбинаторных свойствах бесконечных слов, порожденных итерациями морфизмов. Кандидатская диссертация. Новосибирск. 2001.

14. А. Я. Хинчин. Три жемчужины теории чисел. М.: Наука, 1979. 65 с.

15. И. Д. Шкредов. Теорема Сем,вреди и задачи об арифметических прогрессия,х // Успехи мат. наук. 2006. Т. 61. № 6. С. 111-179.

16. А. М. Шур. Комбинаторные характеризации формальных языков. Докторская диссертация. Екатеринбург. 2010.

17. В. Adamczewski, Y. Bngeaud. On the complexity of algebraic numbers I. Expansions m integer bases // Annals of Math. 2007. V. 165. P. 547-565.

18. J.-P. Allouche. The number of factors m a paperfoldmg sequence // Bull. Austral. Math. Soc. 1992. V. 46. P. 23-32.

19. J.-P. Allouche, J. Shallit. Automatic sequences — theory, applications, generalizations. Cambridge University Press. 2003.

20. J.-P. Allouche, J. Shallit. The nhg of k-regular sequences // Theoret,. Comput. Sci. 1992. V. 98. P. 163-197.

21. J.-P. Allouche, J. Shallit. The ubiquitous Prouhet-Thue-Morse sequence // Proc. SETA'98 (Ed. C. Ding, T. Helleseth, H. Niederreiter). New York: Springer-Verlag. 1999. P. 1-16.

22. P. Ambroz, A. Frid, Z. Masakova, E. Pelantova. On the number of factors in codings of three interval exchange jj Discr. Math. Theoret. Comput. Sci. 2011. V. 13. P. 51-66.

23. S. Avgustinovich, S. Kitaev, A. Pyatkin, A. Valyuzhenich. On square-free permutations // J. Autom. Lang. Comb. 2011. V. 7. P. 3-10.

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

25. J. Berstel. Axel Thue's papers on repetitions in words: a translation // Publications du LaCIM, Montreal, 1995. 85 p.

26. J. Berstel, M. Pocchiola. A geom.et.ric proof of the enumeration form,via for Sturm,ian words /'/ Int. J. Algebra and Comput. 1993. V. 3. P. 349-355.

27. J. Berstel, P. Séébold. Stiirmian words, in: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002. P. 40-97.

28. J. Berstel, L. Vuillon. Coding rotations on intervals // Theoret. Comput. Sci. 2002. V. 281. P. 99-107.

29. A. S. Besicovitch. On the linear independence of fractional powers of integers // J. London Math. Soc. 1940. V. 15. P. 3-6.

30. J. Cassaigne. An algorithm, to test if a given circular HDOL-language a,voids a pattern // Proc. Information Processing'94, Vol. 1, North-Holland, Amsterdam, 1994. P. 4-59-464.

31. J. Cassaigne. Constructing infinite words of intermediate complexity /7 Proc. Developments in Language Theory 2003. Berlin: Springer, 2003. P. 173-184. (LNCS V. 2450).

32. J. Cassaigne. Counting overlap-free binary words // Proc. STACS 1993. Berlin: Springer, 1993. P. 216-225. (LNCS V. 665).

33. J. Cassaigne. Complexité et facteurs spéciaux j j Bull. Belg. Math. Soc. Simon Stevin. 1997. V. 4. P. 67-88.

34. J. Cassaigne. Unavoidable patterns. In: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press. 2002.

35. J. Cassaigne, J. D. Currie, L. Schaeffer, J. Shallit. Avoiding three consecutive blocks of the same size and same sum, jj preprint, arxiv.org/abs/1106.5204.

36. C. Choffrut, .J. Karhumàki. On Fatou properties of rational languages j j C. Martin-Vide and V. Mitrana, Eds. Where Mathematics, Computer Science, Linguistics and Biology Meet. Dordrecht,: Kluwer, 2000. P. 227-235.

37. G. Christol, T. Kamae, M. Mendès France. G. Rauzy. Suites algébriques, automates et substitutions // Bull. Soc. Math. France 1980. V. 108. P. 401-419.

38. A. Cobham. Uniform tag sequences // Math. Systems Theory 1972. V. 6. P. 164-192.

39. J. D. Currie. Open problems in pattern avoidance j j Amer. Mathem. Monthly 1993. V. 100. P 790-793.

40. J. D. Currie, N. Rampersad. A proof of Dejean's conjecture j j Math. Comp. 2011. V. 80. P. 1063-1070.

41. D. Damanik. Local symmetries in the period doubling sequence / / Discrete Appl. Math. 2000. V. 100. P. 115-121.

42. J. A. Davis, R. C. Entringer, R. L. Graham, and G. J. Simmons. On permutations containing no long arithmetic progressions // Acta Arithmetica 1977. V. 34. P. 81-90.

43. F. Dejean. Sur un théorème de Thue // J. Combin. Theory Ser. A 1972. V. 12. P. 90-99.

44. V. Diekert. Makanin's Algorithm, in: M. Lothaire, Algebraic combinatorics on words, Cambridge Univ. Press, 2002. P. 387-442.

45. S. Eilenberg, Automata, Languages, and Machines, Vol. A. Academic Press, 1974.

46. A. Ivanyi, On the d-complexity of words // Ann. Univ. Sci. Budapest. Sect. Comput,. 1987. V. 8. P. 69-90.

47. S. Ferenczi. Rank and symbolic complexity // Ergodic Theory Dynam. Systems 1996. V. 16. P. 663-682.

48. A. Frid. Applying a uniform m,arked morphism, to a word // Discr. Math. Theoret. Comput. Sci. 1999. V. 3. P. 125-140.

49. A. Frid, S. V. Avgustinovich. On bispecial factors and subword complexity of DOL sequences // Proc. SETA'98. Berlin: Sprtinger, 1999. P. 191-204.

50. A. Frid. On uniform, DOL words // Proc. STACS'98. Berlin: Springer, 1998. P. 544-554. (LNCS V. 1373).

51. N. Gjini, T. Kamae, Tan Bo, Yu-M. Xue. Maximal pattern complexity for Toeplitz words // Ergodic Theory Dynam. Systems 2006. V. 26 P. 1-14.

52. I. Goldstein. Subword complexity of uniform, DOL words over finite groups // Theoret. Comput. Sci. 2011. V. 412. P. 5728-5743.

53. T. Kamae, H. Rao. Maximal pattern, complexity over £ letters // European .J. Combinatorics 2006. V. 27. P. 125-137.

54. T. Kamae, H. Rao, Yu-M. Xue. Maximal pattern complexity of 2-dimensional words /j Theoret. Comput. Sci. 2006. V. 359. P. 15-27.

55. T. Kamae, H. Rao, Bo Tan, Yu-M. Xue. Language structure of pattern sturmian words j I Discr. Math. 2006. V. 306. P. 1651-1668.

56. T. Kamae, P. Salimov. On m,axim,al pattern complexity of some automatic words j j Ergodic Theory Dynam. Systems 2011. V. 31. P. 1463-1470.

57. T. Kamae, Yu-M. Xue. Two-dimensional word with 2k maximal pattern complexity // Osaka J. Math. 2004. V. 41 P. 257-265.

58. T. Kamae, L. Zamboni. Sequence entropy and the m,aximal pattern complexity of infinite words // Ergodic Theory Dynam. Systems 2002. V. 22. P. 1191-1199.

59. T. Kamae, L. Zamboni. Maximal pattern complexity for discrete systems // Ergodic Theory Dynam. Systems 2002. V. 22. P. 1201-1214.

60. V. Keranen. Abelian squares a,re avoidable on 4 letters // Automata, Languages and Programming. Berlin: Springer, 1992. P. 41-52. (LNSC V. 623).

61. M. Koskas. Com,plexites de suites de Toeplitz // Discr. Math. 1998. V. 183. P. 161-183. 161-183.

62. M. Kunc. The power of commuting with finite sets of words // Theory Comput,. Syst. 2007. V. 40. P. 521-551.

63. J. Leroy. Some improvements of the S-adic conjecture // Advances in Appl. Math. 2012. V. 48. P. 79-98.

64. M. Lothaire. Combinatorics on words. Addison-Wesley, 1983.

65. M. A. Makarov. On an infinite permutation similar to the Thue-Morse word // Discr. Math. 2009. V. 309. P. 6641-6643.

66. M. A. Makarov. On the infinite perm,utation generated by the period doubling word // European J. Combinatorics 2010. V. 31 P. 368-378.

67. F. Mignosi. On the num,ber of factors of Sturmian words // Theoret,. Comput. Sci. 1991. V. 82. P. 71-84.

68. M. Morse, G. A. Hedlund. Symbolic Dynamics II. Sturmian trajectories // Am. J. Math. 1940. V. 62. P. 1-42.

69. I. Nakashima, J.-I. Tamura, Sh.-I. Yasutomi. *-Sturm,ian words and complexity // J. Théorie Nombres Bordeaux 2003. V. 15. P. 767-804.

70. P. Ochem, T. Reix. Upper bound on the number of ternary square-free words j j Proc. Workshop on Words and Automata, http://www.lirmm.fr/~ochem/morphisms/wowa.pdf.

71. N. Pytheas Fogg. Substitutions in Dynamics, Arithmetics and Combinatorics. Berlin: Springer, 2002. 402 p. (Lect. Notes Math. Vol. 1794).

72. M. Rao. Last Cases of Dejean's Conjecture /7 Theoret. Compnt. Sri. 2011. V. 412. P. 30103018.

73. A. Restivo, S. Salemi. Binary patterns in infinite binary words j j Formal and Natural Computing. Berlin: Springer, 2002. P. 107-116. (LNCS Vol. 2300).

74. G. Rote. Sequences with subword complexity 2 n j j J. Number Th. 1994. V. 46. P. 196-213.

75. J. Sakarovitch. Éléments de théorie des automates. Vuibert, 2003.

76. A. Salomaa, S. Yu. On the decomposition of finite languages j j Developments in Language Theory. Foundations. Applications, Perspectives. World Scientific, 2000. P. 22-31.

77. P. Salimov. Constructing infinite words of intermediate arithmetical complexity j j Proc. Languages and Automata Theory and Applications. Berlin: Springer, 2009. P. 696-701. (LNCS Vol. 5457).

78. A. M. Shur. Growth properties of power-free languages j j Proc. DLT 2011. Berlin: Springer, 2011. P. 28-43. (LNCS Vol. 6795).

79. A. M. Shur. On intermediate factorial languages j j Discr. Appl. Math. 2009. V. 157. P. 1669-1675.

80. E. Szemerédi. On sets of integers containing no k elements in arithmetic progression // Acta Arithm. 1975. V. 27. P. 199-245.

81. A. Thue. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen j j Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania 1912. V. 10. P. 1-67.

82. A. Thue. Uber unendliche Zeichenreihen j/ Norske Vid. Skrifter I Mat,.- Nat. Kl., Christiania 1906. V. 7 P. 1-22.

83. A. Valyuzhenich. Permutation complexity of the fixed points of som,e uniform binary morphisms j/ El. Proc. Theoret. Comput. Sei. 2011. V. 63. P. 257-264.

84. M. Waldschmidt,. Open Diophantine problems // Mose. Math. J. 2004. V. 4. P. 245-305.

85. S. Widmer. Permutation complexity of the Thue-Morse word j j Adv. Appl. Math. 2011. V. 47. P. 309-329.

86. S. Widmer. Perm,utat,ion complexity related to the letter doubling map j j El. Proc. Theoret,. Comput. Sei. 2011. V. 63. P. 265-276.Публикации автора по теме диссертации

87. Ж. Кассень, Ф. В. Петров, А. Э. Фрид. О возможных скоростях роста, языков Теплица ¡1 Сиб. мат. журнал 2011. Т. 52. № 1. С. 81-94.

88. А. Фрид. Нижняя оценка на комбинаторную сложность слов Штурм,а // Сиб. электрон. матем. изв. 2005. Т. 2. С. 14-22.

89. S. V. Avgustinovich, J. Cassaigne, А. Е. Frid. Sequences of low arithmetical complexity // Theoret,. Informatics Appl. 2006. V. 40. P. 569-582.

90. S. V. Avgustinovich, D. G. Fon-Der-Flaass, A. E. Frid. Arithmetical complexity of infinite words // Proc. Words, Languages and Combinatorics III, 2000. Singapore: World Scientific, 2003. P. 51-62.

91. S. V. Avgustinovich, A. E. Frid. A unique decomposition theorem, for factorial languages // Int. J. Algebra Comput. 2005. V. 15. P. 149-160.

92. S. V. Avgustinovich, A. E. Frid. Canonical decomposition of a regular factorial language 11 Proc. CSR 2006. Berlin: Springer, 2006. P. 18-22. (LNCS Vol. 3967).

93. S. V. Avgustinovich, A. E. Frid, T. Kamae, P. Salimov. Infinite permutations of lowest maximal pattern complexity // Theoret. Comput. Sci. 2011. V. 412. P. 2911—2921.

94. J. Cassaigne, A. E. Frid. On arithmetical complexity of St,urm,ia,n words // Theoret. Comput. Sci. 2007. V. 380. P. 304-316.

95. D. G. Fon-Der-Flaass, A. E. Frid. On periodicity and lovi complexity of infinite permutations I/ European J. Combinatorics 2007. V. 28. P. 2106-2114.

96. A. E. Frid. Arithmetical complexity of symmetric DOL words // Theoret. Comput. Sci. 2003. V. 306. P. 535-542.

97. A. Frid. Canonical decomposition of a catenation of factorial languages // Sib. Electron. Math. Reports 2007 V. 4. P. 12-19.

98. A. Frid. Commutation of binary factorial languages // Proc. DLT 2007. Berlin: Springer, 2007. P. 193-204. (LNCS Vol. 4588).

99. A. Frid. Fine and Wilf's theorem for permutations // Sib. Electron. Math. Reports 2012. V. 9. P. 377-381.

100. A. E. Frid. On possible growths of arithmetical complexity // Theoret. Informatics Appl. 2006. V. 40. P. 443-458.

101. A. E. Frid. Sequences of linear arithmetical complexity // Theoret. Comput. Sci. 2005. V. 339. P. 68-87.

102. A. Frid. Simple equations on binary factorial languages // Theoret. Comput. Sci. 2009. V. 410. P. 2947-2956.

103. A. Frid, L. Zamboni. On automatic infinite permutations // Theoret,. Informatics Appl. 2012. V. 46. P. 77-85.