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

• Салимов, Павел Вадимович
• кандидат физико-математических наук
• 2010

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

Введение

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