Алгоритмические свойства последовательностей, близких к периодическим

• Автор: Притыкин, Юрий Львович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 96 с. : ил.

Оглавление
1. Введение
1.1. Актуальность темы и цель работы
1.2. Основные результаты
2. Обзор основных понятий
2.1. Основные определения
2.2. Морфизмы
2.3. Основные классы последовательностей
2.4. Последовательность Туэ — Морса и последовательности Штурма
2.5. Блочное произведение и его обобщения
2.6. Конечные автоматы и конечно-автоматные преобразователи
2.7. Произведение с периодической последовательностью
3. Конечно-автоматные преобразования
3.1. Конечно-автоматные преобразования последовательностей со свойствами типа почти периодичности
3.2. Конечно-автоматные преобразования рекуррентных последовательностей
3.3. Почти обратимые конечно-автоматные преобразования обобщённо почти периодических последовательностей
3.4. Стековые конечно-автоматные преобразования
4. Вычислимые операторы на бесконечных последовательностях
4.1. Неразрешимость некоторых свойств почти периодических
последовательностей

4.2. Нерегулярность некоторых множеств последовательностей
5. Свойства автоматных и морфических последовательностей
5.1. Разрешимость почти периодичности для морфических последовательностей: предварительные
результаты
5.2. Разрешимость почти периодичности для чисто морфических последовательностей
5.3. Разрешимость почти периодичности для автоматных последовательностей
5.4. Линейность подсловной сложности почти периодических морфических последовательностей
6. Мера апериодичности бесконечных последовательностей
6.1. Определения и простейшие оценки
6.2. Мера апериодичности конкретных последовательностей
Литература

Глава 1. Введение
1.1. Актуальность темы и цель работы
В работе мы рассматриваем разного типа обобщения понятия бесконечной периодической последовательности и исследуем их свойства.
Центральное понятие работы — почти периодические последовательности. Последовательность символов конечного алфавита почти периодическая, если для каждого конечного подслова и последовательности найдётся такое натуральное число те, что в каждом подслове длины те последовательности найдётся вхождение слова и.
Впервые почти периодические последовательности были рассмотрены в связи с символической динамикой. Продолжая и ссылаясь на работы Адамара и Пуанкаре, Морс в 1921 году опубликовал работу [24], в которой среди прочего определил почти периодические последовательности (он называл их рекуррентными). В 1938 — 1940 годах вышли работы Морса и Хедлунда “Символическая динамика” [22, 23], в которых многие свойства почти периодических последовательностей были подробно исследованы.
Идея символической динамики заключается в сопоставлении траектории в непрерывной динамической системе последовательности букв конечного алфавита. Понимая траекторию как движение точки в некотором пространстве, мы, во-первых, выделяем в пространстве конечное количество областей и, во-вторых, выбираем дискретное множество моментов времени (например, через каждую фиксированную единицу времени), после чего смотрим, в каких областях оказывается точка в эти моменты. Траектории точки сопоставляется бесконечная последовательность букв конечного алфавита, где буквы соответствуют областям про-

Определим блочное произведение и® V индукцией по длине V.
и ® Л = Л,
и® V 0 = (и® и)и, и® V1 = {и® и)й.
Легко проверить, что блочное произведение дистрибутивно справа (но не слева!) и ассоциативно, то есть и®(ии>) = (и®и)(и®и)) и и®(и®ю) = (и ® у) ® гг для любых слов и, V, гг. Пусть теперь ад, к = 0,1, 2,... — последовательность непустых слов из В*, таких что при к ^ 1 слово и к начинается с 0. Тогда в последовательности щ, щ <8> щ, щ ® щ ® и^, ■.. каждое из слов является префиксом любого из следующих, и значит, существует

Нт (5<)ик =
гг—Усо
А;=0 А:=
— бесконечная последовательность в Вм. Например, последовательность ТУэ — Морса — это блочное произведение слов ад = 01.
Блочное произведение подробно изучалось в [17]. В частности, там доказано, что иь всегда почти периодична.
Следующий метод построения последовательностей, по существу предложенный в [38] и обсуждавшийся также в [25], в некотором смысле обобщает блочное произведение. Он является универсальным, в том смысле, что с его помощью можно получить любые обобщённо почти периодические последовательности. Мы изложим немного модифицированную версию этого метода.
Последовательность (Вп,Сп,1п), где Вп и Сп — непустые множества непустых слов в фиксированном конечном алфавите А, 1п — натуральные числа, называется А-0 АТ-схемой, если для неё выполняются следующие четыре условия для любого
(1) все слова из Вп имеют длину 1п
(2) все слова из Сп представимы в виде щгг, где гадг^ £ Вп, и каждое слово из Вп используется в качестве в каком-то из слов множества Сп
(3) каждое слово из Вп+ имеет вид УУ1.. .ад, где для каждого г < к имеем У{Уг+1 £ Сп (в частности, все г)* & Вп), и для каждого гг £ Сп найдётся г < к, для которого гг =
(4) для каждого слова и — адад... адгщад ■ . ■ гад- из Сп+ (здесь ад ад Е Вп) имеем адгад 6 Сп.