Сверхслова, меры на них и их полупрямые произведения

• Автор: Раскин, Михаил Александрович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 98 с.

Содержание
Введение

Глава 1. Действие конечного автомата на почти периодическом сверхслове

1.1. Поведение регулятора почти периодичности

1.2. Почти периодические сверхслова и конечные автоматы

1.3. Основной результат о почти периодических свсрхсловах

1.4. Конструкция требуемого сверхслова

1.5. Базовые свойства конструкции

1.6. Позиции вхождений слов в сверхслово и их остатки от деления

1.7. Нижняя оценка на регулятор почти периодичности прямого
произведения построенного сверхслова и периодического сверхслова
1.8. Верхняя оценка регулятора построенного сверхслова
1.9. Завершение доказательства
1.10. Улучшение нижней оценки теоремы 0.
Глава 2. Полупрямые произведения вычислимых мер на сверхсловах
2.1. Основные свойства полупрямых произведений, согласованных
с отношением
2.2. Основной результат
Глава 3. Меры на сверхсловах и клеточные автоматы
3.1. Постановка задачи
3.2. Используемые базовые понятия и обозначения

3.3. Инвариантные меры и операторы на них
3.4. Определение оператора Ашь
3.5. Частичный порядок ^ па инвариантных мерах
3.6. Частичный порядок > па инвариантных мерах
3.7. Основной результат
3.8. Возможные применения отношения >
Список литературы
Список публикаций автора по теме диссертации

Введение
0.1. Регуляторы почти периодических последовательностей
В первой главе диссертации изучается вопрос о нижних оценках для регулятора почти периодичности автоматного образа почти периодической последовательности, в частности, прямого произведения периодической и почти периодической последовательности.
Нестрого говоря, последовательность называется почти периодической, если для всякого слова, которое в ней встречается, расстояние между соседними вхождениями ограничено сверху некоторой функцией (регулятором) от длины слова. Понятие почти периодичности было введено А. Туэ в начале XX века.
В работах к.ф.-м.н. Ан. А. Мучника, акад. РАН проф. А.Л. Семёнова и к.ф.-м.п. М.А. Ушакова, а позже к.ф.-м.н. Притыкина, изучалось действие конечно-автоматных преобразователей на почти периодических последовательностях. Было известно, что образ почти периодической последовательности под действием конечно-автоматного преобразования является почти периодическим, но верхняя оценка на регулятор образа казалась избыточной.
В первой главе доказывается нижняя оценка аналогичная ранее известной верхней.
Основные определения
Определение 0.1. Пусть дан некоторый алфавит X. Словом над этим алфавитом называется конечная последовательность букв (элементов алфавита). Сверхсловом называется бесконечная последовательность букв. Мы считаем, что буквы в сверхслове занумерованы элементами М; в последующих главах мы будем называть двусторонними сверхсловами бесконечные двусторонние

по-другому:
Ат = Д;ЛДДДД(Б*'ДДДД)5ЛгДДД,
Вш = ДЛ-ДДДД^ДЫДДД^ДДДД,
Д+1 = ДЛ{ДДДД(В*Л,ДДД)5ДДДД.
Из определения видно, что для любого г длины слов Аі,Ві,Сі отличаются на 1: как и раньше, обозначим длину Ві через Ьтогда длина Л, есть Д — 1, а длина Д есть Д + 1. Последовательность к, Д,... подберём из того расчёта, чтобы для всех 77. при всех достаточно больших і число Д было кратно п и чтобы Д+і было больше 100.Р(Д). Кроме того, сделаем к, > 100. Слова Аі+,Ві+,Сі+ выбраны такими, чтобы:
(а) каждое из них содержало пары ДЛг-, Лг-Д, ДД, ДД и ДД в любой своей четверти и конкатенация любых слов из Л,__і, Дті, Д+і не содержала других пар из слов Л,, Д, Д;
(б) в каждом из них был фрагмент длины не менее одной шестой от всего слова, не содержащий Л,-.
(в) в любом начале любого из слов Лг+і,Д+і,Д+і разница между количеством Лі и количеством Д принимала оба значения 0 и 1 не менее одного раза и не принимала никаких других значений;
(г) в каждом из них ровно в одном месте входят кі + 2 копии Д подряд.
Из-за наличия уникального фрагмента В^‘+2 в одном и том же месте каждого из слов уровня і + 1 и того, что слова уровня г + 1 не продолжают друг друга, следует аналог леммы 1.1: для всех гп ф I все вхождения слов Ат, Вт, Ст в Лд Д, Д корректны. Из свойства (в) следует такой аналог леммы 1.3:
Лемма 1.7. В любом слове с индексом к + гп любое слово с индексом к входит начиная с позиций, дающих тюлько остатки от —т до 0 по модулю