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

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

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

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

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

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

0.2 Обзор

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

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

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

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

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

Из работ Туэ выросло целое направление исследований — теория избегаемое&trade-. Классическая постановка задачи об избегании звучит так: пусть дано слово 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, 301 759″ и С21,301 761″ [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. Seebold. 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. Complexite et facteurs speciaux 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. Karhumaki. 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. Mendes France. G. Rauzy. Suites algebriques, 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 theoreme 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. Theorie 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. 30 103 018.

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. Elements de theorie 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. Szemeredi. On sets of integers containing no k elements in arithmetic progression // Acta Arithm. 1975. V. 27. P. 199−245.

81. A. Thue. Uber 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.