Сверхслова, меры на них и их полупрямые произведения (1104768)
Текст из файла
ФГБОУ ВПО «Московский государственный университет имени М.В.Ломоносова»Механико-математический факультетНа правах рукописиРаскин Михаил АлександровичСверхслова, меры на них и их полупрямыепроизведения01.01.06 – математическая логика, алгебра и теория чиселдиссертация на соискание ученой степеникандидата физико-математических наукНаучный руководительд. ф.-м. н., профессорНиколай Константинович ВерещагинМосква – 20142СодержаниеВведение . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Глава 1.4Действие конечного автомата на почти периодическомсверхслове . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.1. Поведение регулятора почти периодичности . . . . . . . . . . . 231.2. Почти периодические сверхслова и конечные автоматы . . . . . 231.3. Основной результат о почти периодических сверхсловах .
. . . 241.4. Конструкция требуемого сверхслова . . . . . . . . . . . . . . . . 251.5. Базовые свойства конструкции . . . . . . . . . . . . . . . . . . . 271.6. Позиции вхождений слов в сверхслово и их остатки от деленияна . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 291.7. Нижняя оценка на регулятор почти периодичности прямогопроизведения построенного сверхслова и периодического сверхслова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311.8. Верхняя оценка регулятора построенного сверхслова . . . . . .
321.9. Завершение доказательства . . . . . . . . . . . . . . . . . . . . . 331.10. Улучшение нижней оценки теоремы 0.2 . . . . . . . . . . . . . . 34Глава 2.Полупрямые произведения вычислимых мер на сверхсловах . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 392.1. Основные свойства полупрямых произведений, согласованныхс отношением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.2. Основной результат. . . . . . . . . . . . . . . . . . . . . . . . . . 42Глава 3.Меры на сверхсловах и клеточные автоматы . . . .
. 503.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . 503.2. Используемые базовые понятия и обозначения . . . . . . . . . . 5233.3. Инвариантные меры и операторы на них . . . . . . . . . . . . . 543.4. Определение оператора Ann . . . . . . . . . . . . . . . . . . . . 563.5. Частичный порядок > на инвариантных мерах . . . . .
. . . . 593.6. Частичный порядок D на инвариантных мерах . . . . . . . . . 683.7. Основной результат . . . . . . . . . . . . . . . . . . . . . . . . . 733.8. Возможные применения отношения D . . . . . . . . . . . . . . . 92Список литературы. . . . . . . . . . . . . . . . . . . .
. . . . . . . . 97Список публикаций автора по теме диссертации . . . . . . . . . . . . 984Введение0.1. Регуляторы почти периодических последовательностейВ первой главе диссертации изучается вопрос о нижних оценках длярегулятора почти периодичности автоматного образа почти периодическойпоследовательности, в частности, прямого произведения периодической и почти периодической последовательности.Нестрого говоря, последовательность называется почти периодической,если для всякого слова, которое в ней встречается, расстояние между соседними вхождениями ограничено сверху некоторой функцией (регулятором)от длины слова. Понятие почти периодичности было введено А. Туэ в началеXX века.В работах к.ф.-м.н.
Ан. А. Мучника, акад. РАН проф. А.Л. Семёнова ик.ф.-м.н. М.А. Ушакова, а позже к.ф.-м.н. Притыкина, изучалось действие конечно-автоматных преобразователей на почти периодических последовательностях. Было известно, что образ почти периодической последовательностипод действием конечно-автоматного преобразования является почти периодическим, но верхняя оценка на регулятор образа казалась избыточной.В первой главе доказывается нижняя оценка аналогичная ранее известной верхней.Основные определенияОпределение 0.1. Пусть дан некоторый алфавит Σ. Словом над этим алфавитом называется конечная последовательность букв (элементов алфавита).Сверхсловом называется бесконечная последовательность букв.
Мы считаем,что буквы в сверхслове занумерованы элементами N; в последующих главахмы будем называть двусторонними сверхсловами бесконечные двусторонние5последовательности букв, то есть отображения из Z в Σ.Сверхслово 1 , 2 , . . . , , . . . называется периодическим, если для некоторого целого положительного числа при всех выполняется равенство = + .
Как обычно, наименьшее такое число называется периодом.Определение 0.2. Слово входит в сверхслово с ограниченными интервалами, если существует такое число , что каждый отрезок сверхслова длины содержит вхождение слова .Сверхслово называется почти периодическим, если любое входящее внего слово входит в с ограниченными интервалами. Регулятором почтипериодичности называется функция, сопоставляющая каждому натуральному числу минимальное натуральное число , такое что любое слово длиныне больше либо не входит в , либо входит на каждом отрезке длины .Конечный преобразователь с входным алфавитом Σ и выходным алфавитом Δ задаётся множеством внутренних состояний , начальным состоянием 0 ∈ и функцией перехода : × Σ → × Δ.
Конечный преобразователь получает на вход символы из алфавита Σ по одному; функцияперехода по состоянию на каждом шаге и входному символу возвращает состояние на следующем шаге и выходной символ. Таким образом, подавая навход некоторое сверхслово = 0 1 . .
. мы получаем последовательность состояний 0 1 . . . и выходных символов 0 1 . . . такие, что ( , ) = (+1 , );выходное слово при этом будет = 0 1 . . ..Замечание 0.1. Мы рассматриваем здесь то же определение, что используется в работах Ю.Л. Притыкина.История рассматриваемых понятийПонятие почти периодичности сверхслов было введено в рассмотрениеА. Туэ в начале XX века как ослабление понятия периодичности. В частно6сти, А.Туэ использовал это понятие при описании свойств последовательности Туэ-Морса 0110100110010110 .
. .. Это сверхслово получается, если начатьсо слова 0 и бесконечное число раз приписывать к уже имеющемуся слову результат замены в нём 1 на 0 и 0 на 1.Другим известным примером почти периодических сверхслов являютсяпоследовательности Штурма. По определению, каждая последовательностьШтурма описывает последовательность пересечений некоторого луча с иррациональным тангенсом угла наклона с вертикальными и горизонтальнымилиниями на бесконечной клетчатой бумаге: идя вдоль луча от его начала,мы записываем ноль, когда пересекается горизональный отрезок, и записываем единицу, когда пересекается вертикальный отрезок.
Если тангенс угланаклона рационален, то возникающая таким образом последовательность нулей и единиц периодична. Иначе она не периодична, но является почти периодической. Сверхслова Штурма имеют следующее интересное свойство: длякаждого натурального числа любая последовательность Штурма содержитровно + 1 различных подслов длины . Более того, любая последовательность с этим свойством обязательно есть последовательность Штурма (см.,например, учебник [1]).Легко проверить, что понятие почти периодичности является ослаблением понятия периодичности. В частности, регулятор почти периодичностипериодической последовательности с периодом ограничен сверху функцией ↦→ + − 1.Для последовательностей Штурма и для последовательности Туэ-Морсарегулятор пости периодичности ограничен сверху линейной функцией.
Впрочем, регулятор может расти намного быстрее. В первой главе приводитсяконструкция, позволяющая по функции построить сверхслово, регулятор которого бесконечно много раз превышает эту функцию.Понятие почти периодичности тоже можно обобщить.7Определение 0.3. Сверхслово называется заключительно (почти) периодическим, если при удалении из него некоторого начала остаётся (почти)периодическое сверхслово.Сверхслово называется обобщённо почти периодическим, если каждое слово либо встречается в конечное число раз, либо входит в сограниченными интервалами.
При этом для обобщённо почти периодическихслов регулятор надо определять немного не так, как для почти периодических. Регулятором в общем случае называется минимальная такая функция : N → N, такая что для каждого любое слово длины либо входит вкаждый отрезок сверхслова длины () либо не входит в сверхслово ,начиная с позиций с номерами, большими чем значение (). Легко видеть,что регулятор любой почти периодической последовательности совпадает срегулятором её почти периодичности, определённым ранее.Например, сверхслово 0111 .
. . является заключительно периодическим,но не почти периодическим. А сверхслово 00000110100110010110 . . . (полученное добавлением четырех нулей к последовательности Туэ–Морса) являетсязаключительно почти периодическим, но не является заключительно периодическим. В работе [2] показано существование обобщённо почти периодического слова, не являющегося почти периодическим и даже заключительнопочти периодическим.В работах Ан.А. Мучника, А.Л. Семёнова, М.А. Ушакова и Ю.Л. Притыкина изучался вопрос сохранения почти периодичности под действием различных преобразований.В [3] показано, что если подавать конечному автомату на вход обобщенно почти периодическое сверхслово, то на выход он будет выдавать обобщенно почти периодическое сверхслово.
В [2] доказан аналог этого результатадля более узкого класса: показано, что заключительно почти периодические8сверхслова под действием конечного автомата переходят в заключительнопочти периодические.Эти результаты сделали естественным вопрос о том, как при этом изменяется регулятор. Если рассмотреть проекцию, то есть конечно-автоматное преобразование с одним состоянием, то регулятор не может увеличиться.В [3, 4] фактически получена в общем случае верхняя оценка регулятораконечно-автоматного образа через регулятор исходного сверхслова.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
