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

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

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

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

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

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

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

5. Биркгоф Г. Теория решеток. М.: Наука, 1984. — 566 с.

6. Кудрявцев В. Б., Алешин C.B., Подколзин A.C.

Введение

в теорию автоматов. М.: Наука, 1985. — 320 с.

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

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

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

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

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

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

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

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

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

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

17. 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.

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

19. Cobham A. Uniform tag sequences. // Math. Systems Theory. 1972. -V. 6. — P. 164−192.

20. Dekking F.M. Iteration of maps by an automaton. // Discrete Math. -1994. V. 126. — P. 81−86.

21. 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.

22. McNaughton R. Testing and generating infinite sequences by a finite automaton. /7 Information and Control. 1966. — V. 9. — P. 521−530.

23. Muchnik An., Semenov A., Ushakov M. Almost periodic sequences. // Theoretical Computer Science. 2003. — V. 304. — P. 1−33.

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

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

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

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