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

• Макаров, Михаил Александрович
• кандидат физико-математических наук
• 2012

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

Введение

Глава 1. Перестановки, порождённые лексикографическим порядком на суффиксах слов

1.1. Конечные лексикографически допустимые перестановки

1.2. Биекция между допустимыми перестановками и регулярными языками

1.3. Бесконечные перестановки, порождённые универсальными словами

Глава 2. Перестановки Штурма

2.1. Определения и предварительные замечания

2.2. Комбинаторная сложность

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

2.4. Обобщение на двумерный случай

2.5. Арифметическая сложность

2.6. Заключительные замечания

Глава 3. Перестановка удвоения периода

3.1. Предварительные определения.

3.2. Знаки и типы вершин.

3.3. Классификация к;-допустимых перестановок.

3.4. Бинарные влево перестановки

3.5. Странные перестановки.

3.6. Комбинаторная сложность

3.7. Технические леммы о «;-допустимых перестановках маленькой длины.

Глава 4. Перестановка Туэ-Морса.

4.1. Два определения.

4.2. Эквивалентность двух определений

4.3. Замечание о последовательностях Т(п) и #щ(п).

Глава 5. Антимонотонные перестановки.

5.1. Определение

5.2. Комбинаторная сложность и графы Рози.

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

5.4. Арифметическая сложность

Введение диссертации (часть автореферата) на тему «Комбинаторика на бесконечных перестановках»

Одним из разделов дискретной математики является комбинаторика на словах. Возникновение этого раздела восходит к работам Акселя Туэ в начале XX века [1], [2], [3]. Исторический очерк может быть найден, например, в статье [4]. Одними из основополагающих книг являются [5], [6].

Объектом исследования в комбинаторике на словах являются символьные последовательности над конечным алфавитом (или слова). Естественным образом определяется конкатенация конечных слов и операция взятия под-слов. Язык всех конечных подслов заданного бесконечного слова является факторным, то есть вместе с любым словом он содержит все его подслова. Среди исследуемых комбинаторных свойств бесконечных слов особенный интерес представляет функция комбинаторной сложности /ш(п), ставящая в соответствие каждому натуральному п количество различных подслов длины п бесконечного слова т. Обзор результатов по комбинаторной сложности слов дан в статье [7]. Классический результат Морса и Хедлунда [8] гласит, что для всякого бесконечного слова и>, являющегося существенно непериодическим (то есть никакой суффикс которого не является периодическим), выполнено /го(п) ^ П + 1.

Помимо исследования общих свойств бесконечных слов, выделяются конкретные классы бесконечных слов или даже отдельные бесконечные слова, которые изучаются более подробно. Таковыми являются слово Туэ-Морса [9], слово удвоения периода [10], слова Штурма [11], слово Фибоначчи [12], слова Роте [13], слово Серпинского, и другие. Приведём несколько определений.

Слово Туэ-Морса т = 0110100110010110. может быть задано рекуррентно условиями ги(0) = 0, и>(2п) = и){п), и>(2п + 1) = 1 — и)(п) при всех п ^ 0. Также слово Туэ-Морса можно определить как неподвижную точку морфизма. А именно, рассмотрим отображение (р: {0,1} —>■ {0,1}2, заданное равенствами <¿>(0) = 01 и <¿>(1) = 10. Для произвольного слова я = ¿(1). з(п) 6 {0,1}п положим ^(й) = </?(з(1)). ^(¿(п)). I

Рассмотрим последовательность -шд = 0, уох = 01, и>2 = 0110, = 01101001, ., где и]п+1 = (р{и)п). Нетрудно доказать, что для любого п слово тп является префиксом слова иип+Следовательно, существует бесконечное слово т = 'ш(0)ъи(1)'ш{2). = 0110100110010110., что иоп = -ш(0). т(2п - 1) для каждого п. Это слово и называется словом Туэ-Морса. Слово удвоения периода ы = 010001010100. может быть задано рекуррентно условиями ио(2п— 1) = 0 и ги(2п) = 1 — т(п) для всех п ^ 1. Также оно является неподвижной точкой морфизма с^: 0 >— 0100,1^0101.

Есть несколько эквивалентных определений слов Штурма. Одно из них следующее. Зафиксируем иррациональное число а Е (0,1) и действительное число ¡3 Е К. Положим ио(п) = [а(п + 1) + /3} - [ап + ¡3}.

Будем говорить, что и] = т(1)ъи(2). — слово Штурма с параметрами а и /3, причём а называется наклоном слова Штурма.

Примером слов Штурма является слово Фибоначчи. Определим последовательность конечных слов рекуррентно: до = 0, = 01, д™ — дп1дп-2. Поскольку каждый член последовательности является префиксом следующего члена, то существует такое бесконечное слово q = 010010100100101001010 что все члены последовательности являются его префиксами. Это слово д и называется словом Фибоначчи. Также его можно определить как неподвижную точку морфизма (р: 0 I—У 01, 1 ь->• 0. Известно, что слово Фибоначчи является словом Штурма с наклоном а. = (3 — л/5)/2.

Актуальным направлением является исследование возможных обобщений результатов комбинаторики на словах, получение аналогов этих результатов для других, схожих с бесконечными словами, объектов. Один из путей попытка исследовать комбинаторные свойства двумерных слов. В этом направлении одной из самых известных проблем является гипотеза Нива [14], утверждающая, что если существует пара чисел (то,щ), что для комбинаторной сложности двумерного слова ии выполнено неравенство ^(то^щ) ^ ШоПо, то слово и> имеет вектор периодичности.

Возможны и другие обобщения. Пусть задано некоторое множество Ы, его элементы будем называть обобщёнными словами, каждому элементу и Е Ы сопоставлено натуральное число £(и), которое мы будем называть длиной и. Пусть задана операция взятия подслова. А именно, пусть для каждого и ЕЫ и для каждых т\,тч ^ Ни) определено обобщённое слово Е Ы.

Постулируем свойства:

• и[1,£(и)] = щ

• £(и[т,1, т2}) =7712—7711 + 1;

• К¡777,1, ^2] ¡7^15 т^] — и[т'1 + 777,1 — 1, 777,2 + — 1].

Если выполнено всё вышеизложенное, то структуру (Ы-[7771,7772]) будем называть обобщённым факторным языком. Через Ы{п) будем обозначать множество обобщённых слов длины п. Количество всех обобщённых слов фиксированной длины п обозначим через /(77) = \Ы{п)\. Последовательность {Лп)}^=1 назовём комбинаторной сложностью языка Ы.

Под такое общее определение подпадают как обычные слова, так и ряд других объектов, в том числе бесконечные перестановки, которым и посвящена настоящая диссертация.

Бесконечные перестановки (в нашем смысле) были введены в 2005 году в [15], [16]. Однако некоторые проблемы, связанные с ними, исследовались ранее. Например, в статье [17] 1977 года рассматриваются перестановки, избегающие длинных монотонных арифметических паттернов. Краткий обзор результатов и направлений исследования по бесконечным перестановкам дан в статье [18].

Под перестановкой мы понимаем линейный порядок -<ж на некотором множестве X (обычно на конечном множестве {1,., п}, на множестве натуральных чисел N = {1,2,3,4,.} или на множестве целых неотрицательных чисел Ми {0}) по отношению к «обычному» линейному порядку ^ на X. Более точно, каждая перестановка — это упорядоченная тройка 7Г = (X, ^т,.), где ^ и ^тг — линейные порядки на X. Вместо записи х у для х, у 6 X мы используем более удобную запись к{х) ^ 7Г(у). Множество X мы будем называть носителем перестановки, а его элементы по отношению к перестановке 7Г мы будем называть вершинами перестановки, через 7г(ж) будем обозначать вершину перестановки 7Г, соответствующую элементу X € X.

Нетрудно понять, что любую биекцию р: {1,., п} —> {1,., п} можно мыслить как линейный порядок ^р на {1,. ,п}. В самом деле, положим, что х у тогда и только тогда, когда р(х) ^ р(у)- Легко проверяется, что это действительно линейный порядок. Обратно, имея некоторый линейный порядок ^ на множестве {1,. ,п}, можем построить по нему биекцию р: {1,., п} —>• {1,., п} следующим образом: р(1) положим равным минимальному элементу из множества {1,., п} по линейному порядку далее р(2) положим равным второму по величине элементу, и так далее, р(п) положим равным максимальному элементу по линейному порядку Очевидно, что р — действительно биекция.

Тем самым, классическое определение конечных перестановок как би-екций эквивалентно нашему определению через линейные порядки. Этим, в частности, оправдывается такое название. Конечная перестановка 7Г, соотвест-вующая биекции р: {1,., п} —> {1,., п}, в алгебре часто записывается в виде / 1 2 . п \ * р(2) . р(п) )> мы же будем записывать лишь нижнюю строку: тг =р(1)р(2). .р(та).

При этом число п мы будем называть длиной перестановки 7Г. Множество всех конечных перестановок длины п обозначаем через <5П.

Отметим, что в отличие от конечного случая, для бесконечного множества X наше определение бесконечной перестановки через пару линейных порядков на X вовсе не эквивалентно существованию соответствующей биекции X на себя. В самом деле, приведём пример бесконечной перестановки на N, которой не соответствует никакая биекция N на себя. Положим 7г(гс) > 7г(у) при любом чётном х и нечётном у, а также положим 7г(1) < 7г(3) < 7г(5) < . и 7г(2) > 7г(4) > 7г(6) >Если допустить, что найдётся биекция р: N N такая, что р(х) ^ р(у) тогда и только тогда, когда тт(х) ^ к (у), то тогда мы бы имели строго возрастающую бесконечную последовательность натуральных чисел р(1) < р(3) < р(5) < ., ограниченную сверху (например числом р(2)), что невозможно.

Вместо биекций X на себя бесконечным перестановкам соответствуют классы эквивалентности отображений из X в У, где У ЭХ. Эквивалентность определим следующим образом. Будем считать, что отображения /: X —> Y и д: X ^ Y эквивалентны, если для всех х,у € X выполнено f{x) ^ f(y) тогда и только тогда, когда д{х) ^ д(у)- Легко проверить, что таким образом определённая эквивалентность отображений рефлексивна, симметрична и транзитивна, то есть в самом деле является отношением эквивалентности. Каждый класс эквивалентности задаёт перестановку 7Г на X такую, что 7г(ж) ^ 7Г{у) тогда и только тогда, когда f(x) ^ /(у), где отображение / — представитель нашего класса эквивалентности. Обратно, всегда ли перестановке будет соответствовать какой-то класс эквивалентности отображений — зависит от выбора Y.

Нетрудно понять, что для X = N всегда можно взять Y = К, то есть любой перестановке на N соответствует класс эквивалентности последовательностей действительных чисел. При этом, как мы видели выше, Y = N можно взять не всегда, то есть далеко не всякая перестановка может быть реализована как биекция N на себя. Соответственно, возникает интересная задача: для заданной перестановки (или класса перестановок) определить, какие множества Y для неё годятся. В частности, интересно исследовать случаи Y = N и Y = Z.

В статье [17] рассматривается как раз задача такого типа. Там исследуются перестановки, избегающие монотонных подпоследовательностей вершин с номерами, образующими арифметическую прогрессию. Более точно, для заданного к ^ 3 рассматриваются перестановки 7г для которых не существует такой арифметической прогрессии т^ ., т^, что 1г(т\) < . < 7г(т^) или 7г(т1) > . > 7г(т^). В статье [17] показано, что такие перестановки существуют для к ^ 3, а также что при к = 5 существует такая перестановка, реализующаяся последовательностью натуральных чисел (то есть что для неё годится У = М), а при к = 4 существует такая перестановка, которая реализуется последовательностью целых чисел (то есть годится У = Z). До сих пор нерешённым остаётся вопрос, существует ли при к = 4 такая перестановка, реализующаяся последовательностью натуральных чисел. В недавней статье [19] сделано частичное продвижение: там построен пример такой перестановки для к = 4, реализующейся последовательностью натуральных чисел, но где требование избегаемости монотонных подпоследовательностей вершин с номерами, образующими арифметическую прогрессию, ослаблено до требования избегаемости монотонных подпоследовательностей вершин с номерами, образующими арифметическую прогрессию с нечётной разностью.

Ещё одно обобщение результатов статьи [17] рассмотрено в другой недавней статье [20]. Там исследуются линейные порядки на множестве рациональных чисел и на множестве действительных чисел, избегающие монотонных арифметических прогрессиий.

Для каждой перестановки 7г (конечной или бесконечной) и х,у £ X, X у, определим СИМВОЛ 7ж(х,у) £ {0,1} (или просто 7(х,у), если ясно, о какой перестановке идёт речь) следующим образом:

Ясно, что перестановка 7г полностью определяется символами ^уп(х, у). В частности, если щ и 7Г2 — перестановки на одном и том же носителе X, то 7Г1 = 7Г2 тогда и только тогда, когда 77Т1(х^у) = "уП2(х,у) при всех х,у 6 X, х^у.

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

0, если 7г(х) < 7г(г/),

1, если 7г(х) > 7т(у). линейному порядку Имеется в виду, что если, например, X < у и 1г(х) > 7г(у), то точка, соответствующая вершине 7г(х), на диаграмме должна находится левее и одновременно выше, чем точка, соответствующая вершине 7т(у). Соседние по горизонтали точки соединяются отрезками (для красоты).

Пример 1. Конечная перестановка 7Г = 2431 длины 4 изображена на рисунке 1. Имеем 7.(1,2) = 0, 7.(2,3) = 1, 7.(3,4) = 1, 7.(1,3) = 0, 7.(2,4) = 1, 7.(1,4) = !.

Пример 2. На рисунке 2 изображён начальный кусок бесконечной перестановки 7Г, заданной равенствами 7п(х,у) = 0 для всех нечётных х и чётных у, а также 7^(24, £2) — 0 при всех нечётных Х2, Х\ < Х2, и 7^(2/1,2/2) = 1 при всех чётных 2/1, 2/2, У\ < У2• Выше мы использовали эту перестановку в качестве примера бесконечной перестановки, для которой не существует соответствующей биекции N на себя.

В статье [16] дано определение периодичности перестановок. Будем говорить, что бесконечная перестановка 7г периодична с периодом если 7. (х, у) = 7.(х + + £) для всех х. у. Будем говорить, что бесконечная перестановка 7г существенно периодична с периодом t, если существует число N0, что 7.(а:,2/) = 7тг(ж + + ПРИ всех х ^ Мь У ^ ЛЬ, то есть, другими словами, если периодичен какой-то её суффикс. Заметим, что перестановка из примера 2 является периодической с периодом 2. В статье [16] доказано, что

Рис. 1. тг = 2431.

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

Линейные порядки на X индуцируют линейные порядки на подмножествах X, следовательно естественным образом можно определить понятие подперестановки. Дадим формальное определение. Для перестановки 7Г = (ЛГ, ^тг) (конечной или бесконечной) и конечного набора у1,.,уп Е X, где у\ < . < уп, обозначим через тг{у\,., уп} перестановку на {1,., п}, определённую равенством Ъ{У1,.,Уп}(ь з) = 1ж{уь Уз) при 1 ^ г ^ п, 1 ^ з ^ п, ъф 3- Особенно интересен случай, когда ., уп — последовательные целые числа (и соответственно когда X = N или X = {1,., А/"}). Итак, пусть заданы числа 777,1 И Ш2, причём 777,1 < 777,2- Тогда перестановку 7г{777,1, 7721 + 1, • • • , ™>2} будем обозначать через 7г[777,1,777,2]. Иными словами, 7г[777,1, ^2] ~ это такая перестановка длины 7772—777,1 + 1, ЧТО При 1 ^ % ^ 7772 — 777,1 + 1 И 1 ^ ] ^ 7772—7771 + 1 выполнено 77Г[тьТО2)(г,3) = + г - 1,т1 + 3 - 1). Будем говорить, что конечная перестановка £ € ¿>п является подперестановкой конечной или бесконечной перестановки 7Г, если £ = 7г[7771,7772] ДЛЯ некоторых 7771 И 7772- Для каждой бесконечной перестановки 7г и конечной перестановки £ € с>п определим множество = = 7г[т + 1,т + п]}.

Пример 3. Перестановка 321 является подперестановкой перестановки 7г = 2431, так как 7г[2,4] = 321. А для бесконечной перестановки тг из примера 2 имеем тг[1, 8] = 18273645 и £„(18273645) = {0, 2,4, 6,.}.

Аналогичное обозначение мы будем применять для слов над конечным алфавитом, то есть для слова и (конечного или бесконечного) запись и[т1,7772] будет означать его подслово и[гп\). 7/(7772).

Через Л будем обозначать пустое слово.

Пусть у нас имеется бесконечная перестановка 7Г. Множество всех её под-перестановок обозначим через Тж и будем называть языком всех подпереста-новок перестановки 7г. Легко видеть, что этот язык является факторным, то есть вместе с любой перестановкой содержит все её подперестановки. Множество перестановок из Т^ длины п обозначим через ^(п) = П ¿>п, а его мощность обозначим через ^(п) = Другими словами, /„(п) — это количество различных подперестановок длины п в бесконечной перестановке 7Г. Последовательность называется комбинаторной сложностью бесконечной перестановки 7г (и самого языка Комбинаторная сложность бесконечных перестановок (/тг(^))п>2 является аналогом комбинаторной сложности бесконечных слов которая активно исследовалась ранее (см. например обзорную статью [7]).

Пример 4. Для перестановки 7г из примера 2 имеем /ж(п) = 2 при всех тг ^ 2, так как

Поскольку перестановок длины п существует ровно 77,!, то для любой бесконечной перестановки 7Г имеет место верхняя оценка /„ (п) ^ 77,!. Покажем, что она может достигаться. Сделаем это по аналогии с примером бесконечного слова над двухсимвольным алфавитом с комбинаторной сложностью 2П, который строится выписыванием (для определённости, в лексикографическом порядке) всех слов длины 1, потом в лексикографическом порядке — слов длины 2, потом — длины 3, и так далее. По аналогии, построим такую бесконечную перестановку 7Го, что 7Го[1, 2] = 12 и 7Го[3,4] = 21, то есть что перестановки 7Го[1, 2], 7Го[3,4] — это все перестановки длины 2, далее 7Го[5, 7] = 123, тг0[8,10] = 132, тг0[11,13] = 213, тг0[14,16] = 231, тг0[17,19] = 312, тг0[20, 22] = 321, то есть по порядку все перестановки длины 3 (в порядке, соответствующем лексикографическому порядку слов над алфавитом {1, 2, 3}, представляющих эти перестановки), далее проделываем то же с перестановками длины 4, и так далее. Указанные условия ещё не задают полностью бесконечную перестановку 7Го, ведь конкатенация для перестановок не определена однозначно, но они задают символы 7тг0(ж, у), когда вершины к(х) и 7г(у) попадают в один и тот же блок (то есть когда х и у попадают в одно и то же множество из

1, 2}, {3, 4}, {5, 6, 7}, {8, 9,10}, {И, 12,13}, и т.д.). В остальных случаях, то есть когда 7г(х) и тг(у) попадают в разные блоки, положим 7^0{х,у) — 0 для х < у, и тПо(х,у) = 1 для х > у. Нетрудно убедиться, что такое определение

7Г[1, 77,] При чеТНЫХ 777,;

7Г[2, 72 + 1] При НечётНЫХ 777. корректно. Префикс ДЛИНЫ 34 получившейся бесконечной перестановки 7Го изображён на рисунке 3.

Таким образом, верхние оценки для комбинаторной сложности бесконечных слов и бесконечных перестановок аналогичны. По-иному обстоят дела с нижними оценками. Напомним, что для бесконечных слов имеется следующий известный результат [8]: комбинаторная сложность существенно периодического слова ограничена, а для всякого бесконечного слова являющегося существенно непериодическим, выполнено /ш(п) ^ п + 1, причём эта нижняя оценка достигается на словах Штурма. Отметим, что этот результат верен не только для случая бесконечных вправо слов, но и для случая бесконечных в обе стороны слов. Аналогичный вопрос о низкой комбинаторной сложности бесконечных перестановок исследовался в статье [16]. Оказывается, случаи перестановок на N и перестановок на Ъ различаются. А именно, в статье [16] доказано следующее:

• комбинаторная сложность перестановки на N ограничена тогда и только тогда, когда эта перестановка существенно периодична, а комбинаторная сложность существенно непериодичных перестановок на N может

Рис. 3. Префикс перестановки с комбинаторной сложностью п!. расти сколь угодно медленно;

• комбинаторная сложность перестановки на Z ограничена тогла и только тогда, когда эта перестановка периодична, а для комбинаторной сложности непериодичной перестановки 7Г на Z выполнена нижняя оценка fn(ri) ^ п — С, где С — некоторая константа (которая не зависит от п, но зависит от 7Г и может быть произвольно большой), причём эта нижняя оценка неуточняемая.

Кроме того, отметим, что комбинаторная сложность некоторых бесконечных перестановок исследовалась в статьях [21], [22], [23].

При исследовании структуры конечных подслов бесконечного слова w иногда рассматривают последовательность графов (Gw(n)): называемых графами Рози [24], [25]. Для бесконечного слова w обозначим через Gw(n) граф,

В КОТОРОМ fw(n) ВерШИН, Помеченных ПОДСЛОВамИ W ДЛИНЫ П, И /ur(7l-f-l) дуг, помеченных подсловами w длины 71+1. Каждому слову и длины п + 1, являющемуся подсловом w, соответствует дуга, помеченная словом и и ведущая из вершины, помеченной словом w[l,n], в вершину, помеченную словом и[2,п+1].

Мы предлагаем ввести аналог графов Рози для бесконечных перестановок. Для бесконечной перестановки тт и п ^ 2 обозначим через Gn(n) ориентированный мультиграф, в котором fn(n) вершин, помеченных подпереста-новками 7Г ДЛИНЫ 71, И /л-(п +- 1) дуг, помеченных подперестановками 7Г длины п + 1. Каждой г/ G Fn(n + 1) соответствует дуга, помеченная г] и ведущая из вершины, помеченной 7/[1,п] в вершину, помеченную ту[2,п+ 1]. Граф Стг(п) будем называть графом Рози перестановки 7г порядка п.

В отличии от графов Рози для слов, графы Рози для перестановок могут иметь параллельные дуги. Например, вершины, помеченные перестановками 312 и 123, могут быть соединены двумя параллельными дугами, помеченными перестановками 4123 и 3124. Однако, покажем, что для каждой пары вершин г>1, г>2 количество дуг, ведущих из v\ в г>2, меньше либо равно 2. В самом деле, допустим, что существует три попарно различных перестановки Т?1,772, 77з е Sn+l, ЧТО 7?i[l,n] = 772(1, та] = 7?3[l,n] И 771 [2 ,n+ 1] = 772 [2, п + 1] =

77з[2,п+ 1]. Тогда имеем 7т(г^) = 7%(г,]) = 7т?з(м) Для {^Л Ф {1,п + 1};

И ТОЛЬКО ЛИШЬ СИМВОЛЫ 7^(1,77, + 1), 7^(1,71 + 1), 7^(1,77, + 1) могут быть разными. По принципу Дирихле среди этих трёх символов найдутся два одинаковых: 7^(1, п + 1) = 7^(1, п + 1) для некоторых £ {1,2,3}, р ф д. Тогда г)р = щ, противоречие.

Пример 5. На рисунке 4 показаны графы Рози 6^(2) (слева) и С7Г(3) (справа) для периодической перестановки тг из примера 2. Все графы Рози Сп(п) для этой перестановки изоморфны между собой.

132 1423

Рис. 4. Графы Рози £¡>(2) и £¡>(3) периодической перестановки тс.

На рисунке 5 представлен граф Рози 6^(3) для перестановки щ с комбинаторной сложностью п\, которую мы описывали выше и префикс которой был показан на рисунке 3. В графе 0^(3) присутствуют параллельные дуги.

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

Максимальная шаблонная сложность для слов была введена в статье [26] и далее исследовалась в статьях [27], [28], [29], [30], [31], [32], [33]. Последовательность целых положительных чисел (I = (<¿1,., 1) условимся называть окном длины п с дистанциями ., с£пх- Будем говорить, что конечное слово и длины п встречается в бесконечном слове ги по окну б, = (¿¿х,., с£пх), если существует такое ттг, что и = ъи(т 4- Д). .ги(т + Д-х), то есть что и{г) = и){т + Дх) при всех г € {1,., п}, где Д = О, Д = при

1 ^ к ^ п — 1. Количество слов, встречающихся в и) по окну й обозначим через /ш(сГ). в частности, если (1 — ОКНО С дистанциями = . . . = = 1, то получаем комбинаторную сложность: /^(сГ) = 1ги(п). Обозначим к^п) = йир^ где супремум берётся по всем окнам (1 длины п. Последовательность (/чу(п)) будем называть максимальной шаблонной сложностью (или максимальной оконной сложностью, или сложностью Камаэ) бесконечного слова ио.

Аналогичным образом максимальную шаблонную сложность можно определить и для бесконечных перестановок. Будем говорить, что конечная перестановка £ длины п встречается в бесконечной перестановке 7Г по окну (I = ((¿1, . . . , Йпх), если существует такое 772, ЧТО £ = 7г{тп +Д, . . . , 777 +Дх}, то есть что = 7^(777, + Дх, т + Д-х) при всех г, ,7 £ {1,., п}, г ф где Д = О, Д = ^ ПРИ 1 ^ ^ ^ ^ — 1- Количество перестановок, встречающихся В 7Г ПО окну (1 обозначим через /тг(^). В частности, если д, — окно с дистанциями = . = (¿пх = 1, то получаем комбинаторную сложность: /тг(^) = /ж{п). Обозначим кж(п) = эир^ /^(с?), где супремум берётся по всем окнам (1 длины п. Последовательность {кж{п))п^2 будем называть максимальной шаблонной сложностью (или максимальной оконной сложностью, или сложностью Камаэ) перестановки 7г.

Ясно, что максимальная шаблонная сложность всегда не меньше, чем комбинаторная сложность (как для бесконечных слов, так и для бесконечных перестановок), то есть кт(п) ^ 1и){п) и ^(п) ^ /-п-(п). По аналогии с комбинаторной сложностью, интересен вопрос о том, насколько медленно может расти максимальная шаблонная сложность. Для существенно непериодических бесконечных слов в статье [26] доказана нижняя оценка кш{п) ^ 2п. В статье [34] доказано, что кж(п) ^ п для любой существенно непериодической перестановки 7г.

Пример 6. Нетрудно видеть, что для периодической перестановки 7г из примера 2 имеем кж(п) = 2 при всех п ^ 2. Кроме того, для перестановки 7Го с комбинаторной сложностью п\, которую мы описывали выше и префикс которой изображён на рисунке 3, имеем кЖо(п) = п\.

Арифметическая сложность для бесконечных слов была введена в работе [35] и далее исследовалась в статьях [36], [37], [38], [39], [40], [41], [42]. Будем говорить, что слово и длины п встречается в бесконечном слове ии по арифметической прогрессии, если существует такие числа т и что и = ъи(т+с1)и1(т + 2с1). и>(т+пеГ), то есть и(г) = w(m+id), 1 ^ г ^ п. Обозначим через количество слов длины п встречающихся в бесконечном слове %и по арифметической прогрессии. Последовательность (а^п)) называется арифметической сложностью бесконечного слова и).

Аналогичным образом можно определить арифметическую сложность для бесконечных перестановок. Будем говорить, что перестановка £ длины п встречается в бесконечной перестановке 7Г по арифметической прогрессии, если существуют такие числа т и с/, что £ = тг{т + (1,т-\- 2с£,., га + п(1}. Обозначим через аж(п) количество перестановок длины п, встречающихся в бесконечной перестановке 7г по арифметическим прогрессиям. Последовательность (аж(п))п^2 будем называть арифметической сложность бесконечной перестановки 7г. Ясно, что арифметическая сложность всегда не меньше, чем комбинаторная сложность (как для бесконечных слов, так и для бесконечных перестановок), то есть аю(п) ^ /ш(п) и аж(п) ^ /тг(п).

Кроме того, через аж(га, д) будем обозначать бесконечную перестановку, соответствующую линейному порядку, индуцированному -<ж на арифметической прогрессии {га + с1, га + 2т + Зс£,.}. А именно,

В частности, при т = 0 и с! = 1 получаем аДО, 1) = 7Г. Кроме того, обозначим через Аж{п) множество перестановок длины п, встречающихся в 7г по арифметическим прогрессиям: з) = ъ{т + id,m + 3 п

Имеем аж(п) = \Аж(п)\.

Пример Т. Нетрудно видеть, что для периодической перестановки 7Г из примера 2 имеем аж(п) — 4 при всех п ^ 3. Кроме того, для перестановки 7Го с комбинаторной сложностью п!, которую мы описывали выше и префикс которой изображён на рисунке 3, имеем аж0(п) = п\.

Ещё одним направлением исследований являются автоматные перестановки [43] (по аналогии с автоматными словами [44]). Бесконечное слово т над алфавитом £9 называется к-автоматным, если существует детерминированный конечный автомат, состояния которого помечены символами алфавита Ед и для каждого г символ т(г) совпадает с символом, которым помечено состояние, где автомат остановится, после того как на вход было подано /с-ичное представление (г)^ числа г. Известно, например, что слово Туэ-Морса является 2-автоматным.

По аналогии, бесконечная перестановка 7г называется А-/с-автоматной, если существует детерминированный конечный автомат (ф, ()2,5, б/о, {<, > , =}, т) с функцией перехода 6 : С} х Е| —> (и её естественным расширением до функции 5 : х (£|)* —> С}) и пометкой состояний автомата г : —> {< , >, такой, что т(6(д0,^)к х и)к)) = < если 7г(г) < >, если 7г(г) > 7г(7'); =, если % = у. то есть после того как на вход автомата подаётся к-ичное представление пары чисел г и автомат должен выдавать символ В статье [43], помимо прочего, показано, что перестановка Туэ-Морса, о которой годробно будет идти речь в главе 4 данной диссертации, является А-2-автоматной.

В целях сравнения свойств бесконечных слов и бесконечных перестановок, представляло бы интерес иметь некую схему, которая каждому бесконечному слову сопоставляла бы бесконечную перестановку с похожими свойствами. Одна из таких схем следующая. Для заданного бесконечного слова ъи над алфавитом {0,1} определим бесконечную перестановку 7г, положив

7тг (ж, у) = 0, если (ги(ж) = 0 и го (у) = 1) или (у)(х) = и)(у) = 0 и х < у) или (ги(ж) = у)(у) = 1 и х > у); а также 7^(2, у) = 1, если (т(х) = 1 и т(у) = 0) или (ъи(х) = и){у) = 1 и х < у) или (гу(ат) = т(у) — 0 и х > у). Несложно проверить, что такое определение корректно. Заметим, что для случая х < у всегда выполнено 7ж(х,у) = т(х).

Покажем, что при таком определении 7г{гг1,., хп, хп+1} = тг{у1?., уп, уп+1} тогда и только тогда, когда и/^х) = у){у\), ., го(жп) = Уо(уп). В самом деле, если 7г{ж1, ., хт жп+1} = 7г{у1,., уп, Уп+1}, ТО при каждом 3, 1 ^ 3 ^ п5 имеем = ^^{х^.х^^х) = = Обратно, если ш(х 1) = IV(У1), . . . , ъи^п) = IV(уп), то при любых i, 1 ^ г < j ^ п + 1, имеем = Ъи(Хг) = Уо(Уг) = ОТКуда 7г{х1, . . . , Хп, Хп+1} =

Как частный случай доказанного свойства, мы получаем, что i:\mi + 1, 7П\ + п + 1] = 7г[т2 + 1, 777,2 + П + 1] ТОГДа И ТОЛЬКО ТОГДа, когда т[гП1 + 1, 777,1 + п) = т[гП2 + 1, 7712 + п].

Доказанное свойство означает, что слово и> и перестановка 7Г изоморфны в том смысле, что между подпоследовательностями СИМВОЛОВ ДЛИНЫ 77 слова IV и подпоследовательностями вершин длины 77 + 1 перестановки 7Г существует взаимно-однозначное соответствие. Из этого вытекает, что все свойства слова ги, определяемые через подпоследовательности символов, могут быть перенесены на перестановку 7г (с увеличением длины подпоследовательности на единицу). В частности, все свойства слова го, определяемые через операцию взятия подслова, могут быть перенесены на перестановку 7Г. Таковыми свойствами являются, в том числе, комбинаторная сложность и графы Ро-зи (а также ещё ряд свойств, в том числе, частоты подслов и функции рекуррентности, определения которых мы здесь не приводим), то есть имеем /ш(п) = /тг(77 + 1) и = Сж(п + 1). Больше того, то же верно для максимальной шаблонной сложности и для арифметической сложности, то есть кт{п) = кж(п + 1) и аю(п) = аж{п + 1).

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

В настоящей диссертации рассматривается ещё одна, другая, схема, сопоставляющая каждому бесконечному слову над алфавитом {0,1} бесконечную перестановку. Первоначально она возникла в связи с практическими задачами поиска подслова в слове и, в частности, с так называемыми суффиксными массивами. Так, в статье [45] в качестве открытого вопроса сформулирована проблема комбинаторной характеризации перестановок, соответствующих суффиксным массивам. Эта проблема была решена в работе [46]. Однако в обоих указанных статьях, во-первых, рассматривались конечные перестановки, которые порождались конечными словами (которые притом заканчивались на особый символ, отличный от 0 и 1, то есть по существу, там бесконечное слово обрывалось особым символом), что существенно упрощает задачу, а, во-вторых, в них акцент сделан прежде всего на поиск оптимальных алгоритмов определения принадлежности перестановки рассматриваему классу и другие практические задачи. А чисто комбинаторные свойства остались практически неисследованными.

Итак, пусть w = w(l)w(2). w(n). — произвольное существенно непериодическое (никакой суффикс которого не является периодическим) бесконечное вправо слово над алфавитом {0,1}. Каждому п G N может быть сопоставлено действительное число в двоичной системе счисления

Rw{n) = 0, w(n)w(n + l)w{n + 2). = ^2w(n + k)2~{к+1). к^О

В силу непериодичности суффиксов слова w все эти действительные числа будут различны. Поэтому эти числа порождают некоторую бесконечную перестановку 7Гц, такую, что для любых г, j, г j, неравенство itw{i) < 7t№(j) выполнено тогда и только тогда, когда выполнено неравенство Rw{%) < Rw(j). Другими словами, перестановка irw определяется лексикографическим порядком на суффиксах слова u>, то есть irw = (N, где -<w — лексикографический порядок на суффиксах w(i)w(i + 1).

Пример 8. Для слова Туэ-Морса w = 01101001. имеем Rui 1) = 0,01101001., Ящ(2) = 0,1101001.Я№(3) = 0,101001.Яад(4) = 0,01001. Ясно, что Яш(4) < Rw(l) < Яад(З) < Rw{2). Поэтому слово w порождает перестановку irw такую, что 7Пш[1,4] = 2431, первые четыре вершины которой 7Пш[1,4] = 2431 схематично изображены на рис. 7 слева. Л

2431 2134

Рис. 7. Допустимая и недопустимая перестановки

Оказывается, что не все конечные перестановки могут быть получены аналогичным образом из некоторого бесконечного слова над алфавитом {0,1}. Например, для перестановки т = 2134 не существует слова w такого, что ^[1,4] = г. В самом деле, если бы такое слово w существовало, то из леммы 2 (которая утверждает, что если w(j) = 0, то irw(j) < 7rw(j + l), и которую мы докажем в главе 1) вытекает, что первый его символ был бы 1, ибо иначе мы бы имели 7гад(1) < 71^(2), что противоречило бы тому, что т(1) > т(2). Аналогично получаем, что и>(3) = 0. Но тогда Ии}( 1) > Иш{3), однако т(1) < т(3), противоречие.

Итак, конечную перестановку назовём лексикографически ъи-допустимой (или, для краткости, просто т-допустимой), если она является подпереста-новкой перестановки 7ГЮ. Конечную перестановку назовём лексикографически допустимой (или допустимой), если она лексикографически ии-допустима для какого-нибудь слова т. Из предыдущих примеров следует, что перестановка 2431 лексикографически допустима, а перестановка 2134 — нет.

В настоящей диссертации исследуются свойства конечных допустимых и и]-допустимых перестановок, а также бесконечных перестановок 71"^, полученных описанным выше способом как лексикографический порядок на суффиксах бесконечного слова, для слов Штурма, слова удвоения периода, слова Туэ-Морса.

Отметим, что лексикографический порядок на подсловах возникает в другой задаче (которая, однако, прямого отношения к нашим результатам не имеет), а именно в задаче факторизации бесконечных слов в конкатенацию слов Линдона [47], [48], [49], [50]. Такой факторизации соответствует убывающая последовательность вершин перестановки, порождённой лексикографическим порядком на суффиксах данного бесконечного слова.

Отметим, что наше определение перестановок допускает следующее обобщение. Зафиксируем натуральное число к ^ 2. Набор 7г = (X, ., будем называть обобщённой перестановкой порядка к, если:

• ^ — линейный порядок на X;

• Гп, • • • ? ^к ~ частичные порядки на X, что для любых х, у £ X, х Ф у, выполнено ровно одно из к условий: х гп У, ■ ■ •, х У (то единственное ]. для которого х у обозначаем ] = '^{х. у)).

Заметим, что при к — 2 определение эквивалентно определению перестановок, данному выше, так как в этом случае частичные порядки ^ и -<2 являются линейными и обратными друг другу (то есть достаточно задать лишь один из них). Для заданной обобщённой перестановки частичные порядки на X индуцируют частичные порядки на подмножествах X, поэтому понятие подперестановки определяется естественным образом. Следовательно, можно определить комбинаторную сложность. Задачи, связанные с комбинаторной сложностью обобщённых перестановок и другими их комбинаторными характеристиками, представляют одно из возможных направлений для дальнейших исследований.

Опишем кратко структуру настоящей диссертации.

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

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

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

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

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

Результаты диссертации опубликованы в статьях [51], [52], [53], [54], [55].

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

1. Thue A. Über unendliche Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. 1. Mat.-Nat. Kl. Christiana, 1906. pp. 1-22.

2. Thue A. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. Christiana, 1912. pp. 1-67.

3. Thue A. Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln // Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. Christiana, 1914. pp. 1-34.

4. Berstel J., Perrin D. The origins of combinatorics on words // European Journal of Combinatorics. 2007. Vol. 28. pp. 996-1022.

5. Lothaire M. Combinatorics on Words. Vol. 17 of Encyclopedia of Mathematics and Its Applications. Addison-Wesley, 1983.

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

7. Ferenczi S. Complexity of sequences and dynamical systems // Discrete Mathematics. 1999. Vol. 206. pp. 145-154.

8. Morse M., Hedlund G.A. Symbolic dynamics II: Sturmian trajectories // Amer. J. Math. 1940. Vol. 61. pp. 1-42.

9. Allouche J.-P., Shallit J. The ubiquitous Prouhet-Thue-Morse sequence // Proceedings of SETA'98 (Sequences and their Applications), DMTCS / Ed. by C. Ding, T. Helleseth, H. Niederreiter. Springer, 1999. pp. 1-16.

10. Damanik D. Local symmetries in the period doubling sequence // Discrete Applied Mathematics. 2000. Vol. 100. pp. 115-121.

11. Berstel J. Recent results on Sturmian words // Developments in language theory II. Magdeburg, 1995. pp. 13-24.12. de Luca A. A Combinatorial Property of the Fibonacci Words // Information Processing Letters. 1981. Vol. 12, no. 4. pp. 193-195.

12. Rote G. Sequences with subword complexity 2n // Journal of Number Theory. 1994. Vol. 46. pp. 196-213.

13. Epifanio C., Koskas M., Mignosi F. On a conjecture on bidimensional words // Theoretical Computer Science. 2003. Vol. 299. pp. 123-150.

14. Fon-Der-Flaass D., Frid A. On periodicity and low complexity of infinite permutations // European Journal of Combinatorics. 2007. Vol. 28, no. 8. pp. 2106-2114.

15. Davis J., Entringer R., Graham R., Simmons G. On permutations containing no long arithmetic progressions // Acta Arithmetica. 1977. Vol. 34. pp. 81-90.

16. Frid A. Infinite permutations vs. infinite words // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. pp. 13-19.

17. LeSaulnier T., Vijay S. On permutations avoiding arithmetic progressions // Discrete Mathematics. 2011. Vol. 311. pp. 205-207.

18. Ardai H., Brown T., Jungic V. Chaotic Orderings of the Rationals and Reals // The American Mathematical Monthly. 2011. Vol. 118, no. 10. pp. 921-925.

19. Widmer S. Permutation complexity of the Thue-Morse word // Advances in Applied Mathematics. 2011. Vol. 47, no. 2. pp. 309-329.

20. Widmer S. Permutation complexity related to the letter doubling map // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. pp. 265-276.

21. Valyuzhenich A. Permutation complexity of the fixed points of some uniform binary morphisms // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. pp. 257-264.

22. Rauzy G. Suites à termes dans un alphabet fini // Séminaire de Théorie des nombres de Bordeaux, exposé 25. 1983. pp. 2501-2516.

23. Cassaigne J. On a conjecture of J. Shallit // Proceedings of the 24th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science. Vol. 1256. Bologna, Springer, 1997. pp. 693-784.

24. Kamae T., Zamboni L. Sequence entropy and the maximal pattern complexity of infinite words // Ergodic Theory and Dynamical Systems. 2002. Vol. 22, no. 4. pp. 1191-1199.

25. Kamae T., Zamboni L. Maximal pattern complexity for discrete systems // Ergodic Theory and Dynamical Systems. 2002. Vol. 22. pp. 1201-1214.

26. Kamae T., Rao H., Tan Bo, Xue Yu-Mei. Language structure of pattern Sturmian word // Discrete Mathematics. 2006. Vol. 306. pp. 1651-1668.

27. Kamae T., Rao H., Xue Yu-Mei. Maximal pattern complexity of two-dimensional words // Theoretical Computer Science. 2006. Vol. , 359. pp. 15-27.

28. Gjini N., Kamae T., Tan Bo, Xue Yu-Mei. Maximal pattern complexity for Toeplitz words // Ergodic Theory and Dynamical Systems. 2006. Vol. 26. pp. 1073-1086.

29. Kamae T., Rao H. Maximal pattern complexity of words over £ letters // European Journal of Combinatorics. 2006. Vol. 27, no. 1. pp. 125-137.

30. Kamae Т., Salimov P. On maximal pattern complexity of some automatic words // Ergodic Theory and Dynamical Systems. 2011. Vol. 31, no. 5. pp. 1463-1470.

31. Kamae T. Behavior of various complexity functions // Theoretical Computer Science. 2012. Vol. 420. pp. 36-47.

32. Avgustinovich S., Frid A., Kamae Т., Salimov P. Infinite permutations of lowest maximal pattern complexity // Theoretical Computer Science. 2011. Vol. 412. pp. 2911-2921.

33. Avgustinovich S., Fon-Der-Flaass D., Frid A. Arithmetical complexity of infinite words // Words, Languages & Combinatorics III / Ed. by M., Ito, T. Imaoka. World Scientific Publishing, 2003. pp. 51-62.

34. Frid A. Arithmetical complexity of symmetric D0L words // Theoretical Computer Science. 2003. Vol. 306. pp. 535-542.

35. Frid A. Sequences of linear arithmetical complexity // Theoretical Computer Science. 2005. Vol. 309. pp. 68-87.

36. Frid A. On possible growths of arithmetical complexity // Theoretical Informatics and Applications. 2006. Vol. 40, no. 3. pp. 443-458.

37. Avgustinovich S., Cassaigne J., Frid A. Sequences of low arithmetical complexity // Theoretical Informatics and Applications. 2006. Vol. 40, no. 4. pp. 569-582.

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

39. Cassaigne J., Frid A. On arithmetical complexity of Sturmian words // Theoretical Computer Science. 2007. Vol. 380. pp. 304-316.

40. Salimov P. Constructing infinite words of intermediate arithmetical complexity // Language and Automata Theory and Applications, Lecture Notes in Computer Science. Vol. 5457. Springer, Berlin, 2009. pp. 696-701.

41. Frid A., Zamboni L. On automatic infinite permutations // RAIRO Theoretical Informatics and Applications. 2012. Vol. 46, no. 1. pp. 77-85.

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

43. Grossi R., Vitter J. Compressed suffix arrays and suffix trees with applications to text indexing and string matching // Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 2000. pp. 397-406.

44. He M., Munro J., Rao S. A categorization theorem on suffix arrays with applications to space efficient text indexes // Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 2005. pp. 23-32.

45. Siromoney R., Matthew L., Dare V., Subramanian K. Infinite Lyndon words // Information Processing Letters. 1994. Vol. 50, no. 2. pp. 101-104.

46. Melancon G. Lyndon factorization of infinite words // STACS'96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 1046 / Ed. by C. Puech, R. Reischuk. SpringerVerlag, 1996. pp. 147-154.

47. Melancon G. Lyndon factorization of sturmian words // Discrete Mathematics. 2000. Vol. 210. pp. 137-149.

48. Seebold P. Lyndon factorization of the Prouhet words // Theoretical Computer Science. 2003. Vol. 307. pp. 179-197.

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

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

51. Makarov М. On the infinite permutation generated by the period doubling word // European Journal of Combinatorics. 2010. Vol. 31, no. 1. pp. 368-378.

52. Makarov M. On an infinite permutation similar to the Thue-Morse word // Discrete Mathematics. 2009. Vol. 309. pp. 6641-6643.

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

54. Elizalde S. The number of permutations realized by a shift // SI AM Journal of Discrete Mathematics. 2009. Vol. 23. pp. 765-786.

55. Domaratzki M., Kisman D., Shallit J. On the number of distinct languages accepted by finite automata with n states //J. Autom. Lang. Comb. 2002. Vol. 7. pp. 469-486.

56. Seebold P. Fibonacci morphisms and sturmian words // Theoretical Computer Science. 1991. Vol. 88. pp. 365-384.

57. Fraenkel A., Simpson J. The exact number of squares in Fibonacci words // Theoretical Computer Science. 1999. Vol. 218. pp. 95-106.

58. Berstel J., Pocchiola M. A geometric proof of the enumeration formula for Sturmian words // Internat. J. Algebra Comput. 1993. Vol. 3. pp. 349-355.

59. Cassaigne J. Complexité et facteurs spéciaux // Bulletin of the Belgian Mathematical Society. 1997. Vol. 4, no. 1. pp. 67-88.

60. Августинович С. Число различных подслов заданной длины в последовательности Морса-Хедлунда // Сибирский журнал исследования операций. 1994. Т. 1, № 2. С. 3-7.