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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С.Л. Соболева

ЦУТ-' -V /4,14. ЛУ.1

САЛИМОВ Павел Вадимович

РЕКУРРЕНТНОСТЬ И РАВНОМЕРНАЯ РЕКУРРЕНТНОСТЬ БЕСКОНЕЧНЫХ СЛОВ И ИХ ПРОИЗВЕДЕНИЙ

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

1 6 СЕН 2010

Автореферат

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

Новосибирск, 2010

004608065

Работа выполнена и Институте математики им. С. Л. Соболева СО РАН

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

А.Э. Фрид.

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

Д.С. Ананичев (УрГУ), доктор физико-математических наук Е.А. Околышшникопа.

Ведущая организация: Московский Государственный Университет.

Защита состоится 22 сентября 2010 в 17 часов на заседании диссертационного сонета Д 003.015.01 при Институте математики им. С. Л. Соболева СО РАН по адресу: ауд. 417, пр. Академика Коп-тюга 4, г. Новосибирск С30090.

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

Автореферат разослан ü/l^oCCv QoíO

Ученый секретарь диссертационного совет, д.ф.-м.п. / fl Ю. В. Шамардин

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

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

Алфавитом называется произвольное конечное множество. Бесконечное слово над алфавитом £ есть элемент множества последовательностей Е^0, где через обозначено множество натуральных чисел с нулем. Конечным словом длины п называется элемент множества Е™. Конечное слово и является подсловом слова х = Х0Х1..., а точнее, имеет вхождение в него на позиции к, если и = хьХк+1■■ ■ хь+п для некоторого п. Слово и входит в слово х равномерно, если оно входит в него бесконечное число раз, и расстояния между соседними позициями его вхождений в х ограничены константой. Бесконечное слово х называют рекуррентным, если всякое его подслово входит в него бесконечное число раз, и равномерно рекуррентным, если всякое его подслово входит в него равномерно. Обзор результатов и проблем, связанных с равномерной рекуррентностью бесконечных слов можно найти, например, в [3]. Произведением слов х = хох\... и у = уоу\... называется слово х <8> у = (жо, Уо){х1: Ух) наД алфавитом пар символов. Слово х называется сильно рекуррентным, если для всякого равномерно рекуррентного слова у произведение х®у равномерно рекуррентно.

Понятие рекуррентности имеет не "дискретное" происхождение: впервые оно возникло в работах Пуанкаре, посвященных механике. В них он изучает свойства траекторий точек топологических пространств под действием непрерывных преобразований. Один из первых полученных им в этом направлении результатов заключается (в формулировке Биркгофа [12]) в том, что для всяких компактного метрического пространства и его непрерывного отображения в себя имеется точка, чья траектория проходит через всякую ее окрестность бесконечное число раз. Такие точки и их орбиты называются рекуррентными. Еще более близкими к периодичным являются траектории, проходящие через всякую окрестность начальной точке в течении всякого интервала времени, зависящей

лишь от окрестности длины. Такие точки также существуют [8] для всяких компактного метрического пространства и его непрерывного отображения в себя и называются равномерно рекуррентными. Определения, приведенные ранее, являются формулировками этих свойств в терминах изучаемых в диссертации объектов. Это же касается и сильной рекуррентности, про которую почти ничего не известно [24, 26, 27], за исключением того, что это — относительно редкое явление [23].

Причина, по которой свойство рекуррентности в настоящее время играет немалую роль в теории факторных языков, заключается в том, что в применении к бесконечным словам оно позволяет получать новые и улучшать имеющиеся результаты Рамсеевского типа (теоремы типа ван дер Вардена, Семереди, Хидмана). Этой теме посвящена монография [24]. Возможно, детальное изучение свойства рекуррентности приведет к получению еще более сильных результатов в этой области.

Еще одним исследуемым в диссертации аспектом бесконечных слов является их сложность. Классической мерой сложности слова х является функция комбинаторной сложности /х(гг), считающая различные подслова длины п слова х. Эта функция очень хорошо изучена, хотя в этом направлении имеется и ряд нерешенных вопросов [18]. Одним из ее обобщений является арифметическая сложность ах(п) слова х, равная количеству различных слов вида хьХк+с! • • • при всевозможных к ^ 0 и <1 ^ 1, которая была

впервые представлена в работе [10]. Как и в случае комбинаторной сложности, множество возможных функций арифметической сложности еще не описано. В этом направлении следует отметить ряд результатов [19, 22, 16]. В диссертацию включен результат о существовании бесконечных слов арифметической сложности, промежуточной между полиномиальной и экспоненциальной.

Для изучения бесконечных слов низкой сложности часто используется аппарат графов Рози [4, 1, 5, 15], представленных в работе [34]. Множество конечных слов, замкнутое относительно операции взятия подслов, называется факторным языком. Граф Рози М/Дп) порядка п факторного языка Ь есть такой орграф на словах длины п языка Ь, что дуга из слова щщ ... ип-\ ведет в слово г>о«1 • • • тогда и только тогда, когда щ ... ип-\ = ... уп-2

(при п — 1 считаем это выполненным), и щщ ... ип-1Ьп-1 6 I. В диссертации приводится метод построения равномерно рекуррентных слов с последовательностью графов Рози, содержащей подпоследовательность гомеоморфов заданной.

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

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

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

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

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

1.1 неподвижные точки антиподальных морфизмов,

1.2 обобщенно вращательные слова,

1.3 слова Теплица.

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

3. Предложен способ построения равномерно рекуррентных слов над ^-буквенным алфавитом, последовательность графов Рози которых содержит подпоследовательность гомеоморфов заданных Р3-орграфов.

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

Апробация работы. Результаты диссертации докладывались на Международном симпозиуме по информатике в России (Екатеринбург, Россия, 2007), Международной конференции по язы-

кам и автоматам ЬАТА2009 (Таррагона, Испания, 2009), Международной конференции по автоматам и комбинаторике на словах А^оМа1ЬА2009 (Льеж, Бельгия, 2009), Международной конференции по дискретной математике и информатике МаЛ1пГо2010 (Марсель, Франция, 2010), на заседаниях семинаров "Факторные языки" (НГУ), "Дискретный анализ" (НГУ), "Теория кодирования" (НГУ), "Синтез и сложность схем" (НГУ), на заседании семинара "Динамические системы" (Центр Математики Морнингсайд Китайской Академии Наук, Пекин, 2009).

Практическая и теоретическая ценность. Работа носит теоретический характер. Методы, представленные в диссертации, имеют ценность в комбинаторике на словах и могут быть использованы в комбинаторной теории чисел и теории дискретных динамических систем. Результаты включены в программу спецкурса "Факторные языки", читаемого на кафедре теоретической кибернетики НГУ.

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

Объем и структура диссертации. Диссертация состоит из введения, четырех глав и списка литературы (42 наименования). Объем диссертации 77 страниц, включая 1 рисунок и 2 таблицы.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

Морфизмом называется отображение <р : —» Д*, удовлетворяющее тождеству ip(uv) = <f(u)cp(v) для всех конечных слов и, v. Морфизм называется (т-)равноблочным, если он отображает буквы в слова одинаковой длины т > 1. Обозначим алфавит {0,1,..., s — 1} через T,s. Равноблочный морфизм </? : £*—>■£* длины т называется симметрическим, если для всех 0 ^ i < т выполнено равенство <p(j)i = ц>(0)i © j, где операция ф есть сложение по модулю s. Симметрический морфизм над алфавитом £2 называется антиподальным.

Неподвижной точкой морфизма у? называется бесконечное слово х, удовлетворяющее соотношению х = <р(х). Неподвижные точки морфизмов (так называемые DOL-послсдовательности) образуют обширный хорошо изученный класс слов. Введенные первоначально в 1968 г. для моделирования развития живых организмов [2], впоследствии они нашли применение во многих областях математики и теоретической кибернетики.

Теорема 1. Неподвижные точки антиподальных морфизмов сильно рекуррентны.

Примером такой неподвижной точки может служить слово Туэ-Морса хтм — 0110100110... для морфизма </?(0) = 01, <р( 1) = 10, впервые введенное А. Туэ [35].

Обозначим через С единичную окружность, отождествляемую с 1R//Z. Вращением называется отображение Ra : С -> С, отображающее точку р в р + a mod 1.

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

Теорема 2. Восстановимые обобщенно вращательные слова сильно рекуррентны.

Частным случаем обобщенно вращательных слов являются слова Штурма, обладающие многими интересными свойствами [30].

Определим операцию вставки бесконечного слова у = Уо'Уг • • • в бесконечное слово х над алфавитом £ и {?} как операцию, которая заменяет г-ое вхождение символа ? в слове х символом уг, и обозначим результат ее применения через х < у. Пусть дано конечное слово и над алфавитом £и{?}, начинающееся с символа, отличного от ?. Определим у = иш и рассмотрим последовательность слов

у,у<у,у<у<у,____Эта последовательность сходится к некоторому

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

Описанный способ построения слов является модификацией, предложенной в [28], способа построения почти периодичных функций на множестве действительных чисел, представленного О. Теп-лицем в [36]. Изучение комбинаторных свойств таких слов началось с работы [33], которая и закрепила за ними название "слова Теплица". В работе [6] описывается интересная связь этих слов с некоторыми известными комбинаторными проблемами. В работе [17] описывается иной способ построения слов Теплица, основанный на итеративном применении морфизмов, и приводится их классификация.

Для бесконечного слова х и множества I = {¿о < Ч < ■ . •} С Щ) обозначим через XI слово хЦ)хп — Арифметической прогрессией А С 1Х0 назовем множество, имеющее вид {к + (с1 : г е 1\"о} для некоторых к ^ 0 и с? > 0.

Теорема 3. Если для слова х существует такое разбиение множества чисел 1Чо на попарно непересекающиеся арифметические

прогрессии Л,, где г € I, что всякое слово хд1 сильно рекуррентно, то и само х сильно рекуррентно.

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

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

Результаты этой главы докладывались на международных конференциях А^оМа^АгООЭ (Льеж, Бельгия, 2009), Ма1±Шо2010 (Марсель, Франция, 2010), на заседании семинара по динамическим системам в Пекине (2009) и изложены в работе [39].

В третьей главе приводятся результаты о графовых структурах на словах - графах Рози.

Напомним, что графом Рози [34] Е/,(п) порядка п факторного языка Ь называется такой орграф на словах длины п языка Ь, что дуга из слова щщ ... ип-\ ведет в слово зд«!... тогда и только тогда, когда щ ... ип-\ = ьоУ\... ип-2 (при п — 1 считаем это выполненным), и щщ . ..ип-\Уп-\ е Ь.

Граф де Брейна можно определить как граф Рози того же порядка языка всех слов над соответствующим алфавитом.

Орграф в — (Ус, Ее) называется частью орграфа Н = (Ун, Ен), если Ус С Ун и Ее С Ец. В этом случае используется запись ОСН. Орграф С? вложим в орграф Н, если найдется такой орграф С С Я, что £ ~ С.

Назовем к-разбиением ребра орграфа операцию замены этого ребра цепью, состоящей из к дуг и проходимой в том же направлении. Результат /г-разбиения всех ребер орграфа С? назовем его /¿-растяжением и обозначим через т^.

Реберный граф тгС орграфа С есть такой орграф на ребрах (3, что ребро (е1,б2) принадлежит -кС тогда и только тогда, когда конечная вершина ребра е\ есть начальная для ребра е-ч-

Орграф называется £8-орграфом, если полустепени исхода и захода его вершин не превосходят я. Орграф, обладающий свойством Ь$, называется Р5-орграфом, если в нем найдутся такие вершины

V, V1, что полустепень исхода V равна полустепени захода V1 и равна е.

В этой главе доказывается следующее утверждение о вложимо-сти.

Лемма 1. Пусть орграф <2 является сильно связным Р8-орграфом. Тогда для всякого Ь3-орграфа Н существуют такие числа тг, к, что растяжение т^Н вложимо в 7г™£?.

На ее основе доказывается теорема для последовательностей графов Рози.

Теорема 4. Для всякой последовательности (С^гелчт0 сильно связных Рв-орграфов существует такой равномерно рекуррентный язык Ь надТ,8> чтоЖ^гц) ~ т^С^ для некоторых последовательностей (Пг)ге^о» (^г)г£Е^о Чисел.

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

Результаты этой главы докладывались на Международном симпозиуме по информатике в России (Екатеринбург, Россия, 2007) и изложены в работе [37].

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

Арифметическая сложность, определенная ранее, была впервые представлена в работе [10] в 2000 году. В работе [19] вычислена арифметическая сложность неподвижных точек симметричных морфизмов. В работе [22] описаны равномерно рекуррентные слова линейной арифметической сложности. Примененный в ней метод получил развитие в работах [9], где приводится конструкция семейства слов низкой арифметической сложности на основе слов Теплица, и [20]. Арифметическая сложность слов Штурма, как доказано в [16], имеет кубический порядок роста.

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

диссертации впервые доказывается похожий результат для арифметической сложности. Обозначим через х(п) мощность множество подслов длины п всех возможных слов Штурма, которая имеет [30] кубический порядок роста.

Теорема 5. Для произвольных числе таких, что 1 < Ь <

т, существует бесконечное слово х над £2, для арифметической сложности которого справедливы оценки

< ах(п) ^ 4ш2пх(тп)242"1огт' .

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

Морфизм р называется морфизмом типа Серпинского, если он удовлетворяет следующим условиям:

у? есть т-равноблочный морфизм; </?(0) начинается с символа 0; у(0) содержит Ь вхождений 0, где 1 < I < т; Ч>{ 1) = 1™

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

ах(п) ^ 4т2пх(гпп)2№т' .

Результаты об арифметической сложности докладывались на международной конференции 1АТА2009 (Таррагона, Испания, 2009) и изложены в работе [38].

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

[1] Белов А.Я., Чернятьев А.Л. Слова медленного роста и перекладывания отрезков // Успехи матем. наук, 63:1 (2008), 159— 160.

[2] Линденмайер А. Биологические аспекты развивающихся систем и языков // Кибернетический сб. нов. сер., вып. 17 (1980), 192-232.

[3] Мучник Ан. А., Притыкин Ю. Л., Семенов А. Л. Последовательности, близкие к периодическим // Успехи матем. наук, 64:5 (2009), 21-96.

[4] Фрид А.Э. О графах подслов DOL-последовательностей // Дискрет, анализ и исслед. операций 6:4 (1999), 92-103.

[5] Aberkane A. Words whose complexity satisfies lim p(n)/n = 1. // Theoret. Comput. Sei. 307:1 (2003), 31-46.

[6] Allouche J.-P., Bacher R. Toeplitz sequences, paperfolding, Hanoi towers and progression-free sequences of integers // Ens. Math. 38 (1992), 315-327.

[7] Allouche J.-P., Shallit, J. Automatic Sequences. Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003).

[8] Auslander J., Furstenberg H. Product recurrence and distal points // Trans. Amer. Math. Soc. 343:1 (1994), 221-232.

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

[10] Avgustinovich S.V., Fon-Der-Flaass D.G., Frid A.E.

Arithmetical Complexity of Infinite Words // Words, Languages & Combinatorics III, World Scientific Publishing, Kyoto (2003), 51-62.

[11] Berstel J. Recent results in Sturmian words // Developments in Language Theory. II, Magdeburg (1996), 13-24.

[12] Birkhoff G.D.Dynamical systems // Amer. Math. Soc. Colloq. Publ. 9 (1927).

[13] Cassaigne J. An Algorithm to Test if a Given Circular HDOL-language Avoids a Pattern // IFIP World Computer Congress'94. Elsevier 1 (1994), 459-464.

[14] Cassaigne J. Constructing Infinite Words of Intermediate Complexity // Developments in Language Theory VI, Lect. Notes Comp. Sci. 2450 (2003), Springer, Berlin, 173-184.

[15] Cassaigne J. Sequences with grouped factors // Developments in Language Theory III, Aristote University of Thessaloniki (1998), 211-222.

[16] Cassaigne J., Frid A.E. On arithmetical complexity of Sturmian words // Theoret. Comput. Sci. 380 (2007), 304-316.

[17] Cassagne J., Karhumaki J. Toeplitz Words, Generalized Periodicity and Periodically Iterated Morphisms // Lect. Notes Comp. Sci. 959 (1995), Springer, Berlin, 244-253.

[18] Ferenczi S. Complexity of Sequences and Dynamical Systems // Discrete Math. 206:1 (1999), 145-154.

[19] Frid A.E. Arithmetical complexity of symmetric D0L words // Theoret. Comput. Sci. 306:1 (2003), 535-542.

[20] Frid A.E. On possible growths of arithmetical complexity // Theoret. Informatics Appl. 40 (2006), 443-458.

[21] Frid A.E. On Uniform DOL Words // STACS'98: Symposium on Theoretical Aspects of Computer Science, Lect. Notes Comp. Sci. 1373 (1998), 544-554.

[22] Frid A.E. Sequences of linear arithmetical complexity // Theoret. Comput. Sci. 339 (2005), 68-87.

[23] Furstenberg H. Poincare Recurrence and Number Theory// The mathematical heritage of Henri Poincare, Proceedings of Symposia in Pure Mathematics, Amer. Math.Soc. 39:2 (1980), 192-216.

[24] Furstenberg H. Recurrence in Ergodic Theory and Combinatorial Number Theory. Princeton Univ. Press, Princeton (1981).

[25] Gjini N., Kamae T., Tan B. and Xue Y.-M. Maximal pattern complexity for Toeplitz words // Ergodic Theory and Dynamical Systems 26 (2006), 1-14.

[26] Haddad K., Ott W.Recurrence in pairs //Ergodic Theory and Dynamical Systems 28 (2008), Cambridge University Press, 1135— 1143.

[27] Hasselblatt B., Katok A.Handbook of Dynamical Systems Vol. IB, Elsevier (2005).

[28] Jacobs K., Keane M. 0-1 sequences of Toeplitz type // Z. Wahr. verw. Geb. 13 (1969), 123-131.

[29] Kamae T., Zamboni L. Sequence entropy and the maximal pattern complexity of infinite words // Ergodic Theory and Dynamical Systems 22:4 (2002), 1191-1199.

[30] Lothaire M. Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002).

[31] Mignosi F., Segbold P.: If a D0L Language is /c-power-free then It Is Circular. // ICALP'93: Automata, Languages and Programming, Lect. Notes Comp. Sci. 700 (1993), Springer, Berlin, 507-518.

[32] Morse M., Hedlund G.A. Symbolic dynamics II. Sturmian trajectories // Amer. J. Math. 62 (1940), 1-42.

[33] Prodinger H., Urbanek F.J. Infinite 0-1 sequences without long adjacent identical blocks // Discrete Math. 28 (1979), 277289.

[34] Rauzy G. Suites a termes dans un alphabet fini // Seminar on Number Theory, 1982-1983. Talence: Univ. Bordeaux I 25 (1983), 16.

[35] Thue A. Uber unendliche Zeichenreihen // Norske vid. Selsk. Skr. Mat. Nat. Kl., V.7 (1906), 1-22.

[36] Toeplitz O. Beispiele zur Theorie der fastperiodischen Funktionen // Math. Ann. 98 (1928), 281-295.

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

[37] Салимов П.В. Существование бесконечного слова, последовательность графов Рози которого содержит подпоследовательность гомеоморфов заданных орграфов // Дискретн. анализ и исслед. опер., 15:5 (2008), 61-75.

[38] Salimov P.V. Constructing Infinite Words of Intermediate Arithmetical Complexity // Language and Automata Theory and Applications, Lect. Notes Сотр. Sci. 5457 (2009), Springer, Berlin, 696-701.

[39] Salimov P.V. On Uniform Recurrence of a Direct Product // AutoMathA2009: from Mathematics to Applications, plenary conference, (University of Liege, 2009), Europian Science Foundation (2009), 1-9.

Салимов Павел Вадимович

Рекуррентность и равномерная рекуррентность бесконечных слов

и их произведений

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

Подписано в печать 06.07.2010. Формат 60x84 1/16. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 75 экз. Заказ N РЬ

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

Введение

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

1.1 Множество слов

1.2 Морфизмы

1.3 Морфизмы и циркулярность.

1.4 Слова Теплица.

1.5 Обобщенные вращательные слова.

2 Равномерная рекуррентность произведений слов

2.1 Класс сильно рекуррентных бесконечных слов.

2.2 Слова типа Туэ-Морса.

2.3 Обобщенно вращательные слова.

2.4 Слова Теплица.

3 Графовые структуры на языках

3.1 Графы Рози, растяжения и графы перекрытия путей

3.2 Вложимость растяжений в графы де Брейна.

3.3 Вложимость растяжений графов де Брейна.

3.4 Конструирование языков.

4 Сложностные функции бесконечных слов

4.1 Арифметическая и максимальная шаблонная сложности

4.2 Конструирование слов промежуточной арифметической сложности

4.3 Максимальная шаблонная сложность некоторых автоматных слов.

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

В диссертации изучаются свойства бесконечных слов - последовательностей элементов конечного множества, называемого алфавитом. Формально, бесконечное слово х над алфавитом £ есть отображение 1Чд —> где !Мо - множество натуральных чисел с нулем.

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

Центральное понятие работы, равномерная рекуррентность, является одним из фундаментальных понятий теории динамических систем. Определим динамическую систему как пару (X, Т), где X есть топологическое пространство с заданным на нем непрерывным отображением Т : X X. Это определение, более узкое по сравнению со стандартным, вполне достаточно для объяснения постановки изучаемых в данной работе вопросов и полученных результатов. Траекторией точки х назовем последовательность точек х, Тх, Т2х,. Определим множество возвращения Я,(х, и) точки х в ее окрестность и С X как множество таких п Е БЧд, что Тпх 6 и. Точку х называют периодичной, если ее траектория периодична: для некоторого т выполнено Ттх = х .

Теория динамических систем начинается с работ Пуанкаре, посвященных механике. В них он отступил от привычного вопроса о выяснении свойств траектории отдельно взятой точки в сторону изучения свойств совокупности траекторий всех точек в целом. Так, одним из первых резулътатов Пуанкаре в этой области является доказательство существования периодичных траекторий для некоторых частных случаев динамических систем. Следующим встал вопрос о существовании траекторий, устойчивых по Пуассону (рекуррентных). Точка х б X динамической системы (X, Т) называется рекуррентной, если для всякой ее окрестности и С. X множество возвращения Я(х, и) бесконечно (или, что эквивалентно, содержит хотя бы два элемента). Изучая этот вопрос, Пуанкаре получил следующий результат: у всякой динамической системы на компактном метрическом пространстве имеется рекуррентная точка (эта формулировка, принадлежащая Биркгофу, носит название "теорема Биркгофа о рекуррентности" и приведена в его трактате от 1927 г. о динамических системах [14]).

Следующий класс точек, еще более близких по свойствам к периодичным, образуют равномерно рекуррентные точки (в некоторых работах называемые почти периодическими). Точка х динамической системы (X, Т) называется равномерно рекуррентной, если для всякой ее окрестности и С X множество возвращения Я(х, II) бесконечно, и разности между его соседними элементами ограничены (другими словами, множество Я(х,и) соединительно). Фольклорная, судя по всему, теорема, доказательство которой можно найти, например, в [26], утверждает, что всякая компактная метрическая динамическая система имеет хотя бы одну равномерно рекуррентную точку. Это изначально "динамическое" понятие оказалось очень полезным в комбинаторной теории чисел при доказательстве теорем типа Семереди (теорема утверждает, что подмножество натурального ряда, имеющее положительную верхнюю плотность, содержит сколь угодно длинный арифметические прогрессии). Подробно о приложении равномерной рекуррентности в комбинаторной теории чисел написано в [26]. Обзор результатов о равномерной рекуррентности бесконечных слов приведен в [3].

Пусть нам даны две динамические системы (Х,Т) и (У, 5"). Назовем их произведением систему (X х У, Т х 51), где оператор Т х Б отображает точку (х,у) е X х У в точку (Тх, Бу).

Точка динамической системы называется сильно рекуррентной, если в паре со всякой рекуррентной точкой она образует рекуррентную точку произведения их систем. Сильная рекуррентность влечет равномерную рекуррентность (обратное, однако, не верно - пример на бесконечных словах приведен в главе 2). Доказательство этого факта можно найти, например, в [25]. Там же приведен пример сильно рекуррентных точек и приведены некоторые соображения, объясняющие, почему сильная ре-курретность должна быть редким явлением.

Две точки х,у динамической системы (Х,Т) на метрическом пространстве X называются близкими, если т\Ы(ЦТпх,Тпу) = 0 . п—» оо

Как доказано в [26], точка является сильно рекуррентной тогда и только тогда, когда она равномерно рекуррентна и не близка ни к какой другой точке из замыкания своей орбиты. Связь понятий сильной рекуррентности и близости изучалась так же в [9]. Некоторые другие результаты о рекуррентности пар точек изложены в [28].

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

Вопрос описания всех сильно рекуррентных точек остается нерешенным по сей день. Основной целью работы являлось изучение этого вопроса в более узкой постановке - постановке для бесконечных слов. Причина, по которой свойство рекуррентности в настоящее время играет немалую роль в теории факторных языков, заключается в том, что в применении к бесконечным словам оно позволяет получать новые и улучшать имеющиеся результаты Рамсеевского типа (теоремы типа вал дер Вардена, Семереди, Хидмана). Этой теме посвящена монография [26]. Возможно, детальное изучение свойства рекуррентности приведет к получению еще более сильных результатов в этой области.

Перейдем к описанию содержания диссертационной работы по главам.

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

Основные результаты работы, а именно результаты исследований класса бесконечных слов, образующих равномерно рекуррентные пары со всеми равномерно рекуррентными словами, приведены в главе 2. Эти результаты частично изложены в работе [40] и докладывались на международных конференциях А1ЙоМа1;1:1А2009, Ма1Ып£о2010. Приведем формулировки некоторых из них с достаточным минимумом определений.

Конечное слово и называется подсловом (фактором) слова ., если и — . У1+п для некоторых п, г. В этом случае говорят, что и имеет вхождение (входит) в слово V на позиции г. Слово и входит в бесконечное слово х равномерно, если и имеет бесконечное число вхождений в х, и расстояния между соседними его вхождениями ограничены (другими словами, множество позиций вхождениям в х соединительно).

Бесконечное слово х над £ назовем равномерно рекуррентным, если всякое его подслово входит в него равномерно. Это эквивалентно тому, что слово х является равномерно рекуррентной точкой динамической системы (ЕПЧ°,Т), где оператор Т отображает слово у§у\уч. £ в слово уху^ —

Прямым произведением слов х = х$х\. и у = у$у\ . назовем слово х®у — (хо,уо)(х1,у1). над алфавитом пар символов. По определению, слово х <8) у равномерно рекуррентно тогда и только тогда, когда пара слов (х, у) является равномерно рекуррентной точкой произведения соответствующих систем. Бесконечное слово называется сильно рекуррентным, если его произведение со всяким равномерно рекуррентным словом равномерно рекуррентно. Обозначим класс сильно рекуррентных слов через ¿>72.

В главе 2 доказывается, что класс 57?,, в частности, содержит такие хорошо известные классические конструкции, как слово Туэ-Морса, слова Штурма (почти все), слова Теплица, и приводятся некоторые свойства этого класса.

Обозначим через £* множество конечных слов над алфавитом Е. Морфизмом называется отображение (р : X* —£*, удовлетворяющее соотношению (р(иу) = <р(м)</?(г>) для всех конечных слов и и V. Аи-типодальным назовем морфизм у?, определенный на словах над алфавитом {0,1} так, что длина слова (/?(0) больше единицы и слово <¿>(1) получается из слова <¿>(0) заменой 0 -Н- 1. Неподвижной точкой мор-физма (/? называется бесконечное слово х = . удовлетворяющее соотношению х = ф{хо)1р{х\). Таково, например, слово Туэ-Морса хтм = 0110100110. для морфизма </з(0) = 01, ср( 1) = 10, впервые упомянутое в работе А. Туэ [41].

Неподвижные точки морфизмов (так называемые ИОЬ последовательности) образуют обширный хорошо изученный класс слов. Введенные первоначально в 1968 г. для моделирования развития живых организмов [2], впоследствии они нашли применение во многих областях математики и теоретической кибернетики. В работе доказывается следующий результат о 1)01/ последовательностях.

Теорема 1. Неподвижные точки антиподалъных морфизмов сильно рекуррентны.

Верхним механическим словом называется бесконечное слово х = хо^!., задаваемое соотношением XI — |"(г + 1)а: + р] — \{а> + р], где а, р суть действительные числа, а [•] обозначает верхнюю целую часть числа. Нижнее механическое слово определяется аналогично с использованием нижней целой части числа. Частным случаем механических слов являются классические слова Штурма [34] слова минимальной факторной сложности среди непериодических. В главе 3 доказывается теорема, упрощенная формулировка которой приведена далее.

Теорема 2. Если для чисел а, р, определяющих механическое слово х, для всех г Е 1Чо выполняется га + р ^ то х сильно рекуррентно.

Для множества / = {го < г\ < . } С 1Чо и бесконечного слова х обозначим через х^ слово х^х^ .

Рассмотрим над алфавитом {0,1, ?} бесконечное слово х = 0?1?0?1? Теперь в слово х вместо символов ? последовательно вставим символы слова х, а результат обозначим через х <з х = 001?011?001?011? . Повторяя эту процедуру бесконечно, получим слово у = х < х < х . над алфавитом {0,1} - классический пример слова Теплица. Слова, получаемые таким образом из произвольного периодичного слова х, содержащего символ ?, называют словами Теплица. Из следующей теоремы, доказанной в главе 2, следует, что слова Теплица сильно рекуррентны.

Теорема 3. Пусть множество натуральных чисел с нулем разбито на непересекающиеся арифметические прогрессии А^, где j £ J, и слово х таково, что для всякого ] слово ха^ сильно рекуррентно. Тогда и слово х сильно рекуррентно.

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

В главе 3 приведены результат о специфических графовых структурах, используемых при изучении бесконечных слов. Эти результаты полностью изложены в работе [5] и докладывались па Международном симпозиуме по информатике в России 2007.

Язык, т. е. множество конечных слов, называют факторным, если он содержит все под слова своих слов.

Определим граф Рози порядка п факторного языка Ь, как орграф, чьими вершинами являются слова длины п > 1 из Ь, и в котором дуга ведет из слова щщ. ип~\ в ?;оУ\. г>п1 тогда и только тогда, когда щщ ■ ■ ■ = • • ■ 2; и щщ . ип-1Уп-1 является словом из Ь.

Графы Рози были введены в 1982 году [38]. Они активно используются для изучения бесконечных слов с низким разнообразием подслов [4, 1, 6, 17].

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

Назовем к-растяо/сением орграфа С и обозначим через результат замещения дуг этого графа цепями длины к (состоящими из к дуг). Обозначим через 7Грезультат перехода т раз к реберному графу, начиная с графа С. Число дуг, исходящих из вершины V, обозначим через (соответственно, число входящих - через 5£+(г>)). Для орграфов общего вида в этой главе доказывается приведенная ниже теорема.

Теорема 4. Если для всякой вершины V орграфа имеют место неравенства 5£(г>) ^ 5; 31+(у) ^ в, а в сильно связном орграфе Н найдутся такие вершины г>ь^2, что ^"(^г) = ¿'¿+(?;2) ^ то существуют числа к, т такие, что т^О ~ С С тттН. и следующая из него

Теорема 5. Для всякой последовательности (Сг)г'ем сильно связных орграфов, для вершин которых ^ в, существуют последовательность натуральных чисе.л и равномерно рекуррентное бесконечное слово х над в-буквенным алфавитом такие, что последовательность графов Рози слова х содержит подпоследовательность, 1-ый элемент которой изоморфен к{-растяжению орграфа Сг-.

Глава 4 посвящена изучению комбинаторных сложностных характеристик бесконечных слов. Классической такой характеристикой является факторная сложность - функция /ж(п), считающая количество различных нодслов длины п слова х. Обзор свойств этой и некоторых других сложиостных функций приведен, например, в [20]. В главе 4 сформулированы результаты о двух других сложностных функциях. Эти результаты полностью изложены в работах [39, 32] и частично докладывались на международной конференции 1^а2009.

Арифметической слиэюностъю бесконечного слова ж называется функция ах(ть) считающая количество различных его арифметических под-слов длины п, то есть слов вида х^хк+л ■ ■ ■ х^+п-и Для всевозможных к и с? > 1. Эта сложпостная функция была введена в 2000-м в работе [11]. Множество всех возможных функций арифметической сложности бесконечных слов не описано, хотя имеется ряд результатов в этом направлении. В частности, доказано [21], что арифметическая сложность слов типа Туэ-Морса равна 2п. Описано [24] множество равномерно рекуррентных слов линейной арифметической сложности. В работе [10] строятся слова низкой арифметической сложности. В работе [18] вычисляется арифметическая сложность слов Штурма.

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

Обозначим через х{п) количество различных подслов длины п всех слов Штурма. Известно [34], что для некоторой костанты сх выполнено х(п) ^ с\п3- Равноблочным бинарным морфизмом называется морфизм (р, заданный на словах над алфавитом {0,1}, такой, что длины слов <£>(0) и ^(1) совпадают. Морфизмом типа Серпинского назовем равноблочный бинарный морфизм <£>, такой, что ц>{1) = 1т, а слово </?(0) содержит хотя бы одно вхождение символа 1 и более одного символа 0. Например, давшее название классу слово Серпинского хзр = 01011101011. является неподвижной точкой морфизма 0 н-»- 010, 1 н-)- 111.

Автором доказано следующая

Теорема 6. Арифметическая сложность неподвижной точки морфиз-ма гпитш Серпинского удовлетворяет неравенству ах{п) < 4т2пХ(тп)2'2п1°Кт\ где для заданного морфизма т есть длина образов символов, а £ - количество символов 0 в образе нуля.

Помимо этого автором получен результат, аналогичный результату [16] о факторной сложности, а именно, предложен способ построения слов промежуточной арифметической сложности:

Теорема 7. Для произвольных чисел € 14, таких, что 1 < Ь < т, существует бесконечное слово х над алфавитом Ег, для арифметической сложности которого справедливы оценки ах(п) < 4т2пХ(тп)212п1оВт' .

Еще одной активно изучаемой в настоящий момент в мире сложност-ной функцией является функция максимальной шаблонной сложности.

Назовем к-окном множество чисел Т = {¿о < ¿1 < • • • < ¿&-1} С ЛЧГо, содержащее 0. Шаблонной сложностью бесконечного слова х по шаблону Т называется число рх(Т) различных слов вида х^х^^ ■ ■ где i 6 1Мо- Максимальная шаблонная сложность бесконечного слова х, введенная в 2002 [33], есть функция рх(п) = 8ир|Г|=п/^(Т).

Известным [33] является следующий факт: максимальная шаблонная сложность периодичных слов ограничена, но если никакой сдвиг слова х не является периодичным, то рх(п) > 2п. Множество непериодичных слов наименьшей максимальной шаблонной сложности, равной 2п, не описано, но известно [27],[33|, что оно включает слова Штурма и некоторые слова Теплица. Помимо этого в работе [27] доказывается теорема, позволяющая явно вычислять асимптотику максимальной шаблонной сложности слов Теплица. В работе [31] доказано, что для всякого слова х над алфавитом £¡2 функция р*х{п) либо тождественно равна 2П, либо ограничена сверху некоторым полиномом.

Гипотеза, высказанная Т. Камае и положившая начало изучению автором этой функции, состоит в том, что если слово х над алфавитом Т>2 рекуррентно, но не равномерно рекуррентно, тор*х(п) = 2" . Подтвердить или опровергнуть эту гипотезу пока не удалось, но автором совместно с Т. Камае получен следующий результат.

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

Случай 1) 0),¥>(1)) > 1 тогда р*х(п) = 2П ; (Случай 2) дн{(р{0),</?(1)) = 1 тогда рх(п) совпадает срх>(п) для некоторого слова Теплица х' и, в частности, линейна.

Здесь через ¿¿# (г/.,обозначается расстояние Хэмминга между словами и и V - количество позиций, в которых они различаются.

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

Апробация работы

Результаты диссертации докладывались на Международном симпозиуме по информатике в России (Екатеринбург, Россия, 2007), Международной конференции по языкам и автоматам ЬАТА2009 (Таррагона, Испания, 2009), Международной конференции по автоматам и комбинаторике на словах Аи1юМа<;11А2009 (Льеж, Бельгия, 2009), Международной конференции по дискретной математике и информатике МаШ1п£о2010 (Марсель, Франция, 2010), на заседаниях семинаров "Факторные языки" (НГУ), "Дискретный анализ" (НГУ), "Теория кодирования" (НГУ),

Синтез и сложность схем" (НГУ), на заседании семинара "Динамические системы" (Центр Математики Морнингсайд Китайской Академии Наук, Пекин, 2009).

Публикации

Результаты диссертации изложены в работах [5, 32, 39, 40].