Степени асинхронно автоматных преобразований сверхслов над конечными алфавитами

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

Содержание
Введение
Глава 1. Структура степеней асинхронно автоматных преобразований
§1.1. Автоматные преобразования сверхслов
§1.2. Существование плотных участков в множестве степеней конечноавтоматных преобразований
§1.3. Связь между степенями конечно-автоматных и асинхронно
автоматных преобразований
§1.4. Существование наименьшего элемента и атомов
§1.5. Вложимость конечных линейно упорядоченных множеств §1.6. Дополняемость вверх, вниз в множестве степеней автоматных преобразований
Глава 2. Полные и -полные сверхслова и степени
§2.1. Полные и к полные сверхслова
§2.2. Свойства полных сверхслов и полных степеней
§2.3. Свойства к полных сверхслов и к полных степеней
Глава 3. Разрешимость монадических теорий сверхслов
§3.1. Логические теории сверхслов
§3.2. Асинхронно автоматные преобразования сверхслов с разрешимой монадической теорией
§3.3. Разрешимость монадической теории полного сверхслова
Литература

Введение
В теории алгоритмов значительное место отводится сравнению сложности множеств или бесконечных последовательностей при помощи некоторой алгоритмической сводимости и изучению степеней неразрешимости относительно этой сводимости. Наиболее известны и употребительны е—, Т—, tt—, тп— сводимости (см., например, [1, 12, 16]). Менее известны и изучены сводимости, определяемые при помощи конечных автоматов. В 1974 году Г. Рейна [29] ввел понятие конечно автоматной сводимости, классов эквивалентности (или степеней неразрешимости) относительно этой сводимости и частичный порядок на этих классах эквивалентности. Он назвал две бесконечные последовательности (их также называют бесконечными словами или сверхсловами) конечно-автоматно эквивалентными, если каждую из них можно преобразовать в другую при помощи некоторого конечного автомата Мили, возможно с некоторой фиксированной конечной задержкой. Г. Рейна [29] также получил первые результаты для частично упорядоченного множества степеней конечно-автоматных преобразований. Он показал, что это множество (обозначенное им через V) является верхней полурешеткой с наименьшим элементом, без максимальных элементов, в котором существуют атом и плотный участок.
Результаты, полученные Г. Рейна [29], в значительной степени были обобщены в работах В.Р. Байрашевой [2-5]. Она показала вложимость в V любого конечного линейно упорядоченного множества как начального сегмента [3], изоморфность любого счетного частично упорядоченного множества некоторому подмножеству V [3]. С.С. Марченковым [8] было показано, что любое конечное частично упорядоченное множество с наименьшим и наибольшим элементом вложимо как начальный сегмент в V. Этот результат С.С. Марченкова был усилен В.Д. Соловьевым [19], который показал,

что любое конечное частично упорядоченное множество с наименьшим и наибольшим элементом изоморфно начальному сегменту структуры степеней конечно-автоматных преобразований сверхслов в алфавите {0,1}. При доказательстве были использованы результаты, полученные В.Д. Соловьевым для жестких и плотно упакованных бесконечных последовательностей: любая степень, которая определяет конечный начальный сегмент в множестве степеней конечно-автоматных преобразований, является плотно упакованной. Понятия жесткой и плотно упакованной последовательностей были введены В.Д. Соловьевым [19] для характеризации степени дублирования информации в бесконечной последовательности.
Обобщив процедуру Г. Рейна построения атома [29], В.Р. Байрашева [5] показала существование континуума атомов. Кроме того, ею [4] были построены атомы со следующими заранее заданными свойствами: атом, состоящий из эффективно обобщенно почти периодических сверхслов (в терминологии [11]); атом, состоящий из обобщенно почти периодических сверхслов с неразрешимой монадической теорией; атом, состоящий из сверхслов с разрешимой монадической теорией, которые не являются обобщенно почти периодическими; атом, состоящий из сверхслов с неразрешимой монадической теорией, которые не являются обобщенно почти периодическими. Независимо от того, что существуют атомы со столь различными свойствами, любой атом структуры V состоит только из плотно упакованных сверхслов (В.Д. Соловьев [19]).
Частичные упорядочения степеней конечно-автоматных преобразований обобщенно почти периодических сверхслов и сверхслов с разрешимой монадической теорией являются начальными сегментами V, но в отличие от V не являются верхними полурешетками (В.Р. Байрашева [4]). Также не является верхней полурешеткой частичное упорядочение степеней конечно-автоматных преобразований сверхслов, заданных в алфавите,
Пусть іді - финальное состояние автомата (Т, іп) для входного блока Ау Очевидно, что іщ е (іп} и, в силу минимальности (Д) , (іді)1 = Фп)1 Поэтому іп Є (іді)1. Обозначим через П]+11 блок, состоящий из блока П.] и следующего за ним такого блока из множества {[АА)*), что финальное состояние автомата (Т, іп) для П]+11 есть О
Аналогично для г — 2,п + 1 определяем блок как блок из мно-
жества {(Н*|...|А*)*), который начинается с А*. такой, что финальное состояние автомата (Т, іп) при подаче Л*+11 есть іп.
Далее следует п подшагов, удовлетворяющих условию (5).
Подшаг 0. Блок /|+1 уже построен.
Подшаг I. Пусть построено /]+1. Строим 1. Рассмотрим автомат (т і{). Проверим выполняется ли равенство
т(г0,о“) = Т'(/'+1).
Если |сит(і0,0°°)| < |шг(іг,/]+1)|, то очевидно, что Т(іо, О00) ф ті+х) и полагаем 11А = /]+1.
Если |ссгДо,0°°)| > І(Ь]+і)|) то возможны следующие случаи.
Если равенства нет, то полагаем І — Iі-+1.
Если равенство есть, то существует к (1 < к < п + 1) такое, что Т(іо,0°°) ф Т1(Ц+1А+1Л). Тогда полагаем І*+ = і]+1А)+11.
После шага п — 1 получим /”+1.
Следующие п — 1 подшагов удовлетворяют условию (6).
Подшаг п — 1. Блок /”+1 уже построен.
Подшаг I = т + гг — 2 (т = 2,гг—1). Пусть построено /]+1. Строим Подадим на вход автомата (Тп іш) слово -+1)+1д+1д д+ідо-На выходе имеем аВіН, где Ві = |/+1[, |//| = |А+1дП+1д |,
причем Н имеет ВИД (Пд)г.
Подадим получившееся слово на вход автомата (Т, ф).