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

• Корнеева, Наталья Николаевна
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Корнеева, Наталья Николаевна

Содержание

Введение

Глава 1. Структура степеней асинхронно автоматных преобразований

§1.1. Автоматные преобразования сверхслов

§1.2. Существование плотных участков в множестве степеней конечно-

автоматных преобразований

§1.3. Связь между степенями конечно-автоматных и асинхронно

автоматных преобразований

§1.4. Существование наименьшего элемента и атомов

§1.5. Вложимость конечных линейно упорядоченных множеств . 32 §1.6. Дополняемость вверх, вниз в множестве степеней автоматных преобразований

Глава 2. Полные и /¿-полные сверхслова и степени

§2.1. Полные и £;-полные сверхслова

§2.2. Свойства полных сверхслов и полных степеней

§2.3. Свойства А;-полных сверхслов и к-полных степеней

Глава 3. Разрешимость монадических теорий сверхслов

§3.1. Логические теории сверхслов

§3.2. Асинхронно автоматные преобразования сверхслов с разрешимой монадической теорией

§3.3. Разрешимость монадической теории полного сверхслова

Литература

Введение диссертации (часть автореферата) на тему «Степени асинхронно автоматных преобразований сверхслов над конечными алфавитами»

Введение

В теории алгоритмов значительное место отводится сравнению сложности множеств или бесконечных последовательностей при помощи некоторой алгоритмической сводимости и изучению степеней неразрешимости относительно этой сводимости. Наиболее известны и употребительны е—, Т—, и—, га— сводимости (см., например, [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]). Также не является верхней полурешеткой частичное упорядочение степеней конечно-автоматных преобразований сверхслов, заданных в алфавите,

мощность которого ограничена некоторым натуральным числом (В.Р. Бай-рашева [3]).

Понятия почти периодического, обобщенно почти периодического сверхслова (или, другими словами, последовательности) являются естественным обобщением понятия периодического сверхслова (последовательности). Все приводимые ниже определения можно найти, например, в [11]. Бесконечное слово х называется периодическим, если для некоторого Т Е N (называемого периодом) х{г) = х(г-\-Т) для любого г € N. Сверхслово х называется заключительно периодическим, если ж(г) = х[г -\-Т) для любого натурального г > К, где К ~ некоторое натуральное число. Сверхслово х называется почти периодическим, если для любого его подслова найдется число А такое, что это подслово встречается на любом отрезке х длины А. Соответственно, сверхслово называется заключительно почти периодическим, если некоторый его суффикс почти периодичен. Бесконечное слово х называется обобщенно почти периодическим, если для любого его подслова, входящего в х бесконечное число раз, найдется такое натуральное число А, что это подслово встречается на любом отрезке х длины А. Сверхслово называется рекуррентным, если каждое входящее в него подслово входит бесконечное число раз, и заключительно рекуррентным, если некоторый его суффикс рекуррентеп. Для обобщенно почти периодических сверхслов вводится функция, которая каждому натуральному числу п ставит в соответствие такое минимальное натуральное число А, что любое слово длины п, входящее в обобщенно почти периодическое сверхслово х, входит либо в начальный отрезок х длины А, либо в любой отрезок х длины А. Эта функция называется регулятором почти периодичности сверхслова х. Бесконечное слово называется эффективно (обобщенно) почти периодическим, если оно вычислимо, (обобщенно) почти периодично и регулятор почти периодичности этого сверхслова является вычислимой функцией.

Вопрос о замкнутости относительно автоматных преобразований, определяемых при помощи автоматов Мили (в терминологии [11, 13. 14, 28], равномерных преобразователей) и асинхронных автоматов (или, другими словами, конечных преобразователей), рассматривался для различных классов сверхслов. Выше уже приведены результаты о замкнутости относительно равномерных конечно-автоматных преобразований для обобщенно почти периодических сверхслов и сверхслов с разрешимой монадической теорией [4]. Оказывается, свойство обобщенной почти периодичности сохраняется также и под действием произвольных (не обязательно равномерных) конечных преобразователей [18] (а также [11, 28]). Относительно произвольных автоматных преобразований (то есть преобразований, определяемых произвольным конечным преобразователем) сохраняется также свойство сверхслова быть эффективно обобщенно почти периодическим ([11, 18, 28]), заключительно почти периодическим ([13, 14]), рекуррентным ([11, 15]), морфическим [23]. Множество ¿¡-автоматных сверхслов сохраняется относительно равномерных конечно-автоматных преобразований [22]. До сих пор остается открытым вопрос: сохраняется ли множество /с-автоматных сверхслов относительно произвольных автоматных преобразований.

Сверхслово называется морфическим, если оно имеет вид /г(^°°(с)), где Н : Е —)■ Е' кодирование, а ср : Е* —Е* - морфизм, продолжаемый на с, где с £ Е, то есть ср(АВ) = (р(А)(р(В) для любых А,В е Е*, </?(с) = сА для некоторого А Е Е* и (рп(А) ф А для любого натурального п. Бесконечное слово вида (/?°°(с) называется чисто морфическим. Морфическое сверхслово, полученное при помощи ^-равномерного морфизма, называется А;-автоматным. Другое эквивалентное определение ^-автоматных последовательностей (или сверхслов) можно найти в работе Кобхэма [22], где они и были введены.

Для доказательства отсутствия максимального элемента в множестве степеней конечно-автоматных преобразований, Г. Рейна, [29] ввел понятие полной последовательности (полного сверхслова). Он назвал последовательность символов над некоторым фиксированным алфавитом полной, если в ней для любого натурального числа к встречается каждый блок длины к из символов этого алфавита. Если мощность алфавита, над которым рассматриваются бесконечные слова, фиксирована, то степень конечно-автоматных преобразований, содержащая полное сверхслово, состоит только из полных сверхслов. Такие степени Г. Гордон назвал полными степенями [24, 25]. В своих работах [24, 25] он получил некоторые результаты для частично упорядоченного множества полных степеней. В частности, Г. Гордон дал частичный ответ на вопрос: имеет ли полная степень покрытие. Оказалось, либо все полные степени имеют покрытие, либо ни одна не имеет ([24]). Кроме того, для любых полной степени [х] и неполной степени [у] таких, что [ж] > [у], существуют полная степень [х'\ и неполная степень [у'} такие, что [х] > [х1] > [у'} > [у] ([24]), то есть каждая полная степень определяет бесконечный начальный сегмент в У. Г. Гордон [24] показал, что существует неполная степень, над которой нет полной степени. В [25] показано, что частичные порядки степеней конечно-автоматных преобразований, лежащие выше заданных произвольно выбранных полных степеней, изоморфны. В.Р. Байрашевой [2] было показано, что частично упорядоченная система полных степеней не является верхней полурешеткой.

Частным случаем конечно-автоматной сводимости (когда рассматриваются автоматы с несколькими входами и одним состоянием, работающие на бесконечных двоичных последовательностях) является булева сводимость. Булеву сводимость определил и изучал С.С. Марченков [9, 10]. Он [9] исследовал свойства частично упорядоченного множества Q-степеней для множества булевых функций Q, содержащего селекторную функцию

и замкнутого относительно суперпозиции специального вида. Множество (^-степеней континуально, не имеет наибольшего элемента, не является верхней полурешеткой. Кроме того, С.С. Марченков исследовал наличие минимальных и наименьшего элементов, существование бесконечных антицепей в общем случае, а также наличие минимального и наименьшего, максимального и наибольшего элементов и существование бесконечных цепей и антицепей в некоторых частных случаях. Он показал [10], что частично упорядоченное множество (^-степеней имеет в зависимости от наличия или отсутствия наименьшего элемента либо счетное число атомов, либо счетное число минимальных элементов, которые являются периодическими (^-степенями. Также в [10] исследуется положение периодических и узких (^-степеней (доказывается, что они не являются максимальными), доказывается континуальность множества минимальных элементов и атомов, находятся начальные сегменты, изоморфные заданным конечным решеткам, в частично упорядоченном множестве (^-степеней для некоторых классов булевых функций О.

Еще один вопрос, рассматриваемый для бесконечных последовательностей, - это вопрос разрешимости их логических теорий. Определения логической теории первого порядка и монадической теории второго порядка бесконечной последовательности будут даны в третьей главе. Для теории первого порядка структуры (М, <,"Р) с почти периодической системой предикатов V критерий разрешимости получен А.Л. Семеновым [17]. Вопрос разрешимости теорий второго порядка более сложный, но благодаря применению теории автоматов можно получить результаты о разрешимости теорий некоторых классов сверхслов. Например, монадическа.я теория обобщенно почти периодического сверхслова разрешима тогда и только тогда, когда сверхслово эффективно обобщенно почти периодическое [11, 18]. Как следствие, монадическая теория почти периодического сверхслова раз-

решима тогда и только тогда, когда сверхслово вычислимо и множество его подслов разрешимо [11]. В частности, получается разрешимость монади-ческих теории последовательностей Туэ-Морса, Фибоначчи, механической последовательности с наклоном а и сдвигом р. если су и р - вычислимые действительные числа [11]. В работе О. Картона и В. Томаса [21] доказана разрешимость монадической теории морфического сверхслова.

Основные результаты данной работы изложены в трех главах. В начале каждой главы (в параграфах 1.1, 2.1, 3.1) приводятся основные определения и необходимые для дальнейшего изложения результаты. Определения параграфа 1.1 используются в дальнейшем также во второй и третьей главах. В первой главе рассматривается связь между степенями конечно-автоматных преобразований и степенями асинхронно автоматных преобразований, а также устанавливаются некоторые свойства частично упорядоченного множества степеней асинхронно автоматных преобразований: существование континуума атомов, вложимость в качестве начального сегмента конечного линейно упорядоченного множества. Положительный ответ на вопрос дополняемости вниз получен как в множестве степеней асинхронно автоматных преобразований, так и в множестве степеней конечно-автоматных преобразований. Вторая глава посвящена изучению свойств полных и Аг-полных сверхслов и соответствующих им степеней конечно-автоматных преобразований. В §2.2 изучаются некоторые свойства полных сверхслов с заданным регулятором полноты. В §2.3 изучаются свойства к-полных сверхслов, которые являются обобщением полных сверхслов. Глава 3 посвящена свойству разрешимости монадических теорий сверхслов. Во втором параграфе главы 3 доказывается, что свойство разрешимости монадических теорий сверхслов сохраняется относительно асинхронно автоматных преобразований. В третьем параграфе главы 3 получен критерий разрешимости монадической теории полного сверхслова.

Основные результаты первой главы опубликованы в работах [30, 33, 34], результаты второй главы - в работах [31, 32, 35, 37], третьей главы - в работах [31, 32, 35, 36].

Автор выражает глубокую благодарность своему научному руководителю Марату Мирзаевичу Арсланову за постановку задач, поддержку и внимание к работе, а также всем сотрудникам кафедры алгебры и математической логики Казанского (Приволжского) федерального университета и отдела алгебры и математической логики НИЦ "НИИММ им. Н.Г. Чеботарева" за доброжелательную атмосферу.

Список литературы диссертационного исследования кандидат физико-математических наук Корнеева, Наталья Николаевна, 2012 год

Литература

[lj Арсланов M.M. Рекурсивно перечислим,ые множества и степени неразрешимости. - Казань: Издательство Казанского университета, 1986. - 206 с.

[2] Байрашева В.Р. Степени автоматных преобразований. // Вероятностные методы и кибернетика. - 1982. - № 18. - С. 17-25.

[3] Байрашева В.Р. Структурные свойства автоматных преобразований. /7 Известия вузов. Математика. - 1988. - № 7. - С. 34-39.

[4] Байрашева В.Р. Степени автоматных преобразований почти периодических сверхслов и сверхслов с разрешимой монадической теорией. Ц Казань, 1989, 29 с. - Деп. в ВИНИТИ 11.05.1989 - № 3103 -В89.

[5] Байрашева В.Р. Степени автоматных преобразований случайных последовательностей. /[ Диссертация на соискание ученой степени кандидата физико-математических наук. Саратовский государственный университет им. И.Г. Чернышевского. Саратов. - 1990. - 104 с.

[6] Биркгоф Г. Теория решеток. - М.: Наука, 1984. - 566 с.

[7] Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. - М.: Наука, 1985. - 320 с.

[8] Марченков С. С. Конечные начальные сегменты верхней полурешетки конечно-автолштных степеней. // Дискретная математика. -1989.-Т. 1.-№3.-С. 96-103.

[9] Марченков С.С. Булева сводимость. // Дискретная математика. -2003. - № 3. - Т. 15. - С. 40-53.

[10] Марченков С.С. О строении частично упорядоченных множеств булевых степеней. // Дискретная математика. - 2006. - № 1. - Т. 18. -С. 61-75.

[11] Мучник Ан.А., Притыкин Ю.Л., Семенов А.Л. Последовательности, близкие к периодическим. /7 Успехи математических наук. - 2009. -Т. 64. - № 5 (389). - С. 21-96.

[12] Соар Р.И. Вычислимо перечислимые множества и степени. - Казань: Казанское математическое общество, 2000. - 576 с.

[13] Притыкин К).Л. Конечно-автоматные преобразования, строго почти периодических последовательностей. // Математические заметки. -2006. - Т. 80. - № 5. - С. 751-756.

[14] Притыкин Ю.Л. Почти периодичность, конечно-автоматные преобразования и вопросы эффективности. // Известия вузов. Математика. - 2010. - № 1. - С. 74-87.

[15] Притыкин Ю.Л. Алгоритмические свойства последовательностей, близких к периодическим. // Диссертация на соискание ученой степени кандидата физико-математических наук. Московский государственный университет им. М.В. Ломоносова. Москва. - 2009. - 96 с.

[16] Роджерс X. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972. - 624 с.

[17J Семенов А.Л. О некоторых расширениях арифметики сложения натуральных чисел. // Известия Академии наук СССР. Серия математическая. - 1979. - № 5. - Т. 43. - С. 1175-1195.

[18] Семенов A.JT. Логические теории одноместных функций па натуральном ряде. / / Известия Академии наук СССР. Серия математическая. - 1983. - № 3. - Т. 47. - С. 623-658.

[19] Соловьев В.Д. Структура распределения информации в бесконечной последовательности. // Дискретная математика. - 1996. - № 2. -Т. 8. - С. 97-107.

[20] Buchi J.R. On a decision method in restricted second-order arithmetic. /7 Proceedings of International Congress for Logic, Methodology and Philosophy of Science (1960). - Stanford University Press, Stanford, CA. -1962. - P. 1-11.

[21] Carton O., Thomas W. The monadic theory of morphic infinite words and generalizations. // Information and Computation. - 2002. - V. 176. -P. 51-65.

[22] Cobham A. Uniform tag sequences. // Math. Systems Theory. - 1972. -V. 6. - P. 164-192.

[23] Dekking F.M. Iteration of maps by an automaton. // Discrete Math. -1994. - V. 126. - P. 81-86.

[24] Gordon H.G. Complete Degrees of Finite-State Transformability. // Information and Control. - 1976. - V. 32. - P. 169-187.

[25j Gordon H.G. An Isomorphism of Complete Degrees of Finite-State Transformability. j I Information and Control. - 1979. - V. 40. - P. 192— 204.

[26] Lerman M. Degrees of Unsolvability. Local and Global Theory. Perspectives in Mathematical Logic. - Omega Series, Springer-Verlag, Berlin, Heiidelberg, New York, Tokio, 1983. - 307 pages.

[27] McNaughton R. Testing and generating infinite sequences by a finite automaton. /7 Information and Control. - 1966. - V. 9. - P. 521-530.

[28] Muchnik An., Semenov A., Ushakov M. Almost periodic sequences. // Theoretical Computer Science. - 2003. - V. 304. - P. 1-33.

[29] Rayna G. Degrees of finite-state transformability. // Information and Control. - 1974. - V. 24. - P. 144-154. [русский перевод: Рейна Г. Степени автоматных преобразований.!j Кибернетический сборник. -1977. - № 14. - С. 95-106.]

Работы автора по теме диссертации

[30] Корнеева H.H. Степени асинхронно автоматных преобразований. // Известия вузов. Математика. - 2011. - № 3. - С. 30-40.

[31] Корнеева H.H. Об автоматных преобразованиях и монадических теориях бесконечных последовательностей. // Известия вузов. Математика. - 2011. - № 8. - С. 90-93.

[32] Корнеева H.H. Монадические теории последовательностей при асинхронно автоматных преобразованиях. // Ученые записки Казанского университета. Серия Физико-математические науки. Принято к печати.

[33] Корнеева H.H. Структура степеней асинхронно автоматных преобразований. // Труды Математического центра им. Н.И. Лобачевского: Материалы Восьмой молодежной научной школы-конференции "Лобачевские чтения - 2009"; Казань, 1-6 ноября 2009 г. - Казань, Казанское математическое общество, 2009. - Т. 39. - С. 270-272.

[34] Корнеева H.H. Степени автоматных преобразований бесконечных последовательностей. / / Международная конференция "Мальцев-ские чтения", посвященная 70-летию Академика Юрия Леонидовича Ершова, 2-6 мая 2010 г: тезисы докладов. - 2010. - С. 50.

[35] Корнеева H.H. Автоматные преобразования и монадические теории f -полных последовательностей. // Труды Математического центра им. Н.И. Лобачевского: Материалы Девятой молодежной научной школы-конференции "Лобачевские чтения - 2010"; Казань, 1-6 октября 2010 г. - Казань, Казанское математическое общество, 2010. -Т. 40. - С. 188-191.

[36] Корнеева H.H. О разрешимости монадических теории бесконечных последовательностей. // Алгебра и математическая логика: материалы международной конференции, посвященной 100-летию со дня рождения профессора В.В. Морозова, и молодежной школы-конференции "Современные проблемы алгебры и математической логики"; Казань, 25-30 сентября 2011 г. - Казань, КФУ, 2011. - Т. 40. - С. 111-112.

[37] Корнеева H.H. О степенях автоматных; преобразований к-полных последовательностей. // Международная конференция "Мальцев-ские чтения", посвященная 60-летию со дня рождения Сергея Саво-стьяновича Гончарова, 11-14 октября 2011 г: тезисы докладов. - 2011. -С. 103.