Степени асинхронно автоматных преобразований сверхслов над конечными алфавитами тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Корнеева, Наталья Николаевна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Казань
МЕСТО ЗАЩИТЫ
|
||||
|
2012
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Л7
Корнеева Наталья Николаевна
Степени асинхронно автоматных преобразований сверхслов над конечными алфавитами
01.01.06 - математическая логика, алгебра и теория чисел
Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
1 5 [лДР Ш
Казань - 2012
005011785
Работа выполнена на кафедре алгебры и математической логики Федерального государственного автономного образовательного учреждения высшего профессионального образования "Казанский (Приволжский) федеральный
университет ". Научный руководитель:
Официальные оппоненты:
Ведущая организация:
Защита состоится «28» марта 2012 г. в/¿.50 на заседании диссертационного совета Д 212.081.24 при ФГАОУВПО "Казанский (Приволжский) федеральный университет" по адресу: 420008, г. Казань, ул. Кремлевская, д. 35., конференц-зал библиотеки им. Н. И. Лобачевского.
С диссертацией можно ознакомиться в библиотеке Казанского (Приволжского) федерального университета.
Автореферат разослан «^»^^^2012 г. Ученый секретарь
диссертационного совета Д 212.081.24 к.ф.-м.н., доцент
доктор физико-математических наук, профессор Арсланов Марат Мирзаевич,
доктор физико-математических наук, профессор Добрица Вячеслав Порфирьевич, доктор физико-математических наук, профессор Ишмухаметов Шамиль Талгатович.
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Вятский государственный гуманитарный университет".
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Работа посвящена изучению свойств структуры степеней асинхронно автоматных преобразований бесконечных последовательностей (или, другими словами, бесконечных слов или сверхслов), а также некоторых свойств бесконечных слов, сохраняющихся относительно автоматных преобразований. .
В теории алгоритмов значительное место отводится сравнению сложности множеств или бесконечных последовательностей при помощи некоторой алгоритмической сводимости и изучению степеней неразрешимости относительно этой сводимости. Наиболее известны и употребительны е-, Т-, П-, т— сводимости (см., например, [12]). Менее известны и изучены сводимости, определяемые при помощи конечных автоматов. В 1974 году Г. Рейна [21] ввел понятия конечно-автоматной сводимости при помощи конечных автоматов Мили, классов эквивалентности (или степеней неразрешимости) относительно этой сводимости и частичный порядок на этих классах эквивалентности. Он назвал две бесконечные последовательности (два сверхслова) конечно-автоматно эквивалентными, если каждую из них можно преобразовать в другую при помощи некоторого конечного автомата Мили, возможно с некоторой фиксированной конечной задержкой. Г. Рейна [21] также получил первые результаты для частично упорядоченного множества степеней конечно-автоматных преобразований. Он показал, что это множество (обозначенное им через V) является верхней полурешеткой с наименьшим элементом, без максимальных элементов, в которой существуют атом и плотный участок.
Результаты, полученные Г. Рейна [21], в значительной степени были обобщены В.Р. Байрашевой [1] - [4]. Она показала вложимость в V любого конечного линейно упорядоченного множества как начального сегмента [2], изо-морфность любого счетного частично упорядоченного множества некоторо-
му подмножеству V [2]. С.С. Марченковым [5] было показано, что любое конечное частично упорядоченное множество с наименьшим и наибольшим элементом вложимо как начальный сегмент в V. Этот результат был усилен В.Д. Соловьевым [14], который показал, что любое конечное частично упорядоченное множество с наименьшим и наибольшим элементом изоморфно начальному сегменту структуры степеней конечно-автоматных преобразований сверхслов в алфавите {0,1}.
Обобщив процедуру Г. Рейна построения атома [21], В.Р. Байрашева [4] показала существование континуума атомов. Кроме того, ею [3] были построены атомы со следующими заранее заданными свойствами: атом, состоящий из эффективно обобщенно почти периодических сверхслов (в терминологии [8]); атом, состоящий из обобщенно почти периодических сверхслов с неразрешимой монадической теорией; атом, состоящий из сверхслов с разрешимой монадической теорией, которые не являются обобщенно почти периодическими; атом, состоящий из сверхслов с неразрешимой монадической теорией, которые не являются обобщенно почта периодическими. Независимо от того, что существуют атомы со столь различными свойствами, любой атом структуры V состоит только из плотно упакованных сверхслов (В.Д. Соловьев [14]).
Частичные упорядочения степеней конечно-автоматных преобразований обобщенно почти периодических сверхслов и сверхслов с разрешимой монадической теорией являются начальными сегментами V, но в отличие от V не являются верхними полурешетками (В.Р. Байрашева [3]). Также не является верхней полурешеткой частичное упорядочение степеней конечно-автоматных преобразований сверхслов, заданных в алфавите, мощность которого ограничена некоторым натуральным числом (В.Р. Байрашева [2]).
В дальнейшем вопрос о замкнутости свойств бесконечных слов относительно автоматных преобразований рассматривался не только для преобразований, определяемых при помощи автомагов Мили (в терминологии [8, 9, 10,
4
20], равномерных преобразователей), но и для преобразований, определяемых асинхронными автоматами (или, в терминологии [8,9,10,20], конечными преобразователями). Относительно произвольных (не обязательно равномерных) автоматных, преобразований сохраняются свойства сверхслов быть обобщенно почти периодическими ([13, 20,8]), эффективно обобщенно почти периодическими ([13, 20, 8]), заключительно почти периодическими ([9, 10]), рекуррентными ([8, И]), морфическими [17]. Множество ¿-автоматных сверхслов сохраняется относительно равномерных конечно-автоматных преобразований [16]. До сих пор остается открытым вопрос: сохраняется ли множество к-авгомашых сверхслов относительно произвольных автоматных преобразований.
Для доказательства отсутствия максимального элемента в множестве степеней конечно-автоматных преобразований, Г. Рейна [21] ввел понятие полного сверхслова. Он назвал сверхслово, заданное над некоторым фиксированным алфавитом, полным, если в нем для любого натурального числа к встречается каждый блок длины к из символов этого алфавита. Если мощность алфавита, над которым рассматриваются сверхслова, фиксирована, то степень конечно-автоматных преобразований, содержащая полное сверхслово, состоит только из полных сверхслов. Такие степени Г. Гордон назвал полными степенями [18, 19]. В своих работах [18, 19] он получил некоторые результаты для частично упорядоченного множества полных степеней. В частности, Г. Гордон дал частичный ответ на вопрос: имеет ли полная степень покрытие. Оказалось, либо все полные степени имеют покрытие, либо ни одна не имеет [18]. Кроме того, для любых полной степени [*] и неполной степени [у] таких, что [х] > [у], существуют полная степень [х] и неполная степень [/] такие, что [х] > [х'\ > [>''] > [>"] ([18]), то есть каждая полная степень определяет бесконечный начальный сегмент в V [18]. Г. Гордон [18] показал, что существует неполная степень, над которой нет полной степени. В [19] показано,
5
что частичные порядки степеней конечно-автоматных преобразований, лежащие выше заданных произвольно выбранных полных степеней, изоморфны. В .Р. Байрашевой [1] было показано, что частично упорядоченная система полных степеней не является верхней полурешеткой.
Частным случаем конечно-автоматной сводимости (когда рассматриваются автомата с несколькими входами и одним состоянием, работающие на бесконечных двоичных последовательностях) является булева сводимость. Булеву сводимость определил и изучал С.С. Марченков [6, 7]. Он [6] исследовал структурные свойства частично упорядоченного множества <2-степеней для множества булевых функций Q, содержащего селекторную функцию и замкнутого относительно суперпозиции специального вида. Множество ()-степеней континуально, не имеет наибольшего элемента, не является верхней полурешеткой. Кроме того, С.С. Марченков исследовал наличие минимальных и наименьшего элементов, существование бесконечных антицепей в общем случае, а также наличие минимального и наименьшего, максимального и наибольшего элементов и существование бесконечных цепей и антицепей в некоторых частных случаях. Он показал [7], что частично упорядоченное множество 2-степеней имеет в зависимости от наличия или отсутствия наименьшего элемента либо счетное число атомов, либо счетное число минимальных элементов, которые являются периодическими 2-степенями. Также в [7] исследуется положение периодических и узких £-степеней (доказывается, что они не являются максимальными), доказывается континуальность множества минимальных элементов и атомов, находятся начальные сегменты, изоморфные заданным конечным решеткам, в частично упорядоченном множестве 2-степеней для некоторых классов булевых функций О,.
Радом авторов исследовалась разрешимость монадических теорий бесконечных слов. Например, монадическая теория обобщенно почти периодического сверхслова разрешима тогда и только тоща, когда сверхслово является
6
эффективно обобщенно почти периодичным [13, 8]. Как следствие, монади-ческая теория почти периодического сверхслова разрешима тоща и только тогда, когда сверхслово вычислимо и множество его подслов разрешимо [8]. В частности, получается разрешимость монадических теорий последовательностей Ту>-Морса, Фибоначчи, механической последовательности с наклоном а и сдвигом р, если аир- вычислимые действительные числа [8]. В работе О. Картона и В. Томаса [15] доказана разрешимость монадической теории
морфического сверхслова.
Цель диссертационной работы. Исследование структуры степеней асинхронно автоматных преобразований сверхслов, а также некоторых свойств бесконечных слов, сохраняющихся относительно автоматных преобразований.
Научная новизна. Все основные результаты являются новыми, получены автором самостоятельно. Часть результатов обобщает известные свойства структуры степеней конечно-автоматных преобразований, часть результатов дополняет известные результаты о разрешимости монадических теорий некоторых классов сверхслов.
Теоретическая и практическая значимость. Диссертация носит теоретический характер, её результаты могут использоваться в дальнейших исследованиях при изучении сводимостей, определяемых конечными автоматами. Материалы диссертации могут быть использованы при чтении спецкурсов для студентов и аспирантов в университетах.
Основные результаты диссертации.
1. Исследовано частично упорядоченное множество степеней асинхронно автоматных преобразований: доказано существование континуума атомов, установлена вложимость в качестве начального сегмента конечного линейно упорядоченного множества. Получен положительный ответ на вопрос дополняемости вниз в множестве степеней асинхронно ав-
томатных преобразований и в множестве степеней конечно-автоматных преобразований.
2. Исследована структура степеней конечно-автоматных преобразований fc-полных сверхслов и полных сверхслов с заданным регулятором полноты.
3. Доказано, чю свойство разрешимости монадических теорий сверхслов сохраняется относительно асинхронно автоматных преобразований.
4. Получен критерий разрешимости монадической теории полного сверхслова.
Апробация работы.
По результатам диссертации были сделаны доклады:
. на международных конференциях "Мальцевские чтения 2010" и "Маль-цевские чтения 2011" (Новосибирск, 2010 г., 2011 г.);
. на международной конференции "Алгебра и математическая логика" (Казань, 2011 г.);
. на международной конференции "Воображаемая логика H.A. Васильева и современные неклассические логики" (Казань, 2010 г.);
• на молодежных научных школах-конференциях "Лобачевские -пения 2009" и "Лобачевские чтения 2010" (Казань, 2009 г., 2010 г.);
. на научных семинарах и итоговых конференциях кафедры алгебры и математической логики Казанского (Приволжского) федерального университета 2009-2011 гг.
Публикации. Основные результаты опубликованы в трех статьях [22] -[24] в журналах, входящих в перечень ВАК Министерства образования и науки РФ, и пяти тезисах [25] - [29], список которых приведен в конце автореферата.
Личный вклад автора. Все основные результаты диссертации получены автором.
Структура и объем диссертации. Диссертационная работа изложена на 78 страницах и состоит из введения, трех глав, разделенных на параграфы, и списка литературы, содержащего 37 наименований.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, приведен обзор результатов исследований по ее тематике.
В первой главе устанавливается связь между степенями конечно-автоматных и асинхронно автоматных преобразований и доказываются свойства структуры степеней асинхронно автоматных преобразований.
В §1.1 приведены основные определения, используемые в работе: определения конечно-автоматной и асинхронно автоматной сводимости.
Будем рассматривать бесконечные последовательности над заданным конечным алфавитом Г, то есть отображения * : N 27. (Полагаем, что N — {0,1,2,...}.) Такие последовательности также называют бесконечными
словами или сверхсловами.
На бесконечных словах вводится понятие сводимости либо при помощи автоматов Мили (см. [21]), либо при помощи асинхронных автоматов.
Определение 1. Конечным автоматом Мили (конечным асинхронным автоматом) называется пятерка (5, 27, 27', 8, со), где Б, 27, 27' - конечные множества состояний, входных и выходных символов соответственно; 8 : Б х 27 ► 5 - функция переходов; со : 5 х 27 —► 27' (соответственно, со : 5 х 27 —►
9
(Е'У) _ функция выходов. Если дополнительно выделено начальное состояние 5о, то автомат называется инициальным.
Единственное отличие конечного асинхронного автомата от конечного автомага Мили в том, что областью значений функции выхода являются не только символы выходного алфавита, но и слова из символов выходного алфавита произвольной длины (в том числе и пустое слово).
Определение 2. Пусть хиу- сверхслова над конечными алфавитами (каждое над своим алфавитом). Сверхслово у конечно-автоматно сводится (асинхронно автоштно сводится) к сверхслову х, если существует конечный инициальный автомат Мили (соответственно, конечный инициальный асинхронный автомат) (5,¿о) такой, чтощ{зо,*) = Ау, где блок А е Е? определяет некоторую конечную задержку (соответственно, щ Оо,*) = у).
Отношения сводимости из данного определения индуцируют отношения эквивалентности на множестве бесконечных слов. Класс эквивалентности, который содержит сверхслово х, обозначается [х] (для асинхронно автоматной сводимости [хП и называется степенью конечно-автоматных преобразований сверхслова X (соответственно, степенью асинхронно автоматных преобразований).
Отношение сводимости на бесконечных словах индуцирует частичный порядок на множестве степеней автоматных преобразований.
Определение 3. [х] > [у] ( И* >* Ы*), если существует конечный инициальный автомат Мили (соответственно, конечный инициальный асинхронный автомат) (5, ¿о) такой, что й)5(л0, х) = Ау, где блок А е определяет некоторую конечную задержку (соответственно, = у).
Частично упорядоченные множества степеней конечно-автоматных и асинхронно автоматных преобразований обозначаются V и V* соответственно.
10
В §1.2 строится начальный сегмент в множестве степеней конечно-автоматных преобразований, который является булевой алгеброй.
Пусть / : N N - произвольная функция. По определению полагаем, что сверхслово х построено с помощью функции /, если х начинается с единицы и за 1-й единицей следует /(() нулей.
Теорема 1. Пусть / : N -* N - возрастающая функция, обладающая свойством: (/(/) ^ /О') {гпой к)) =► (/(/ + 1) = /и + 1) {той к)). Пусть х -сверхслово, построенное с помощью функции /. Множество Ь = {[у] | \у] < [*]} является булевой алгеброй.
В §1.3 получены соотношения между степенями конечно-автоматных и асинхронно автоматных преобразований.
Предложение 1. Между степенями конечно-автоматных и асинхронно автоматных преобразований имеют место следующие соотношения:
1) если [х] < [у], то [х]* <* [у]*,
2) существуют сверхслова хиу такие, что М1М и М* =* Ы*>
3) для любого сверхслова х его степень асинхронно автоматных преобразований есть объединение степеней конечно-автоматных преобразований:
[*Г= и Ы
Предложение 2. Существует степень асинхронно автоматных преобразований, которая состоит из счетного числа степеней конечно-автоматных преобразований.
Далее в первой главе (в параграфах 1.4, 1.5) получены свойства структуры степеней асинхронно автоматных преобразований.
Предложение 3. Класс [0]* (содержащий нулевое бесконечное слово) состоит из заключительно периодических сверхслов (то есть, периодических сверхслов с предпериодом). Для любого сверхслова х,
М* >* [0]*.
и
Теорема 2. Существует континуум атомов V*.
Теорема 3. Любое конечное линейно упорядоченное множество вложимо как начальный сегмент V*.
Результаты §1.6 получены как для множества степеней асинхронно автоматных преобразований, так и для множества степеней конечно-автоматных преобразований.
Теорема 4. 3 V и в V* справедливо следующее утверждение: для любых двух сверхслов х и у таких, что [0] < [х] < [>>] (соответственно, [0]* <* [х]* <* \у]*) существует сверхслово г такое, что [г]|[х], [г]|[у] и [(х,2)]|[>] (соответственно, итм*. ИТМ* « К*.*)]ТЫ*)-
Следствие 1. В V и в V* справедливо следующее утверждение: для любого сверхслова х такого, что [х] > [0] (соответственно, [х]* >* [0]*,) существует сверхслово у такое, что [х]|[у] (соответственно, [хГГМ*Л
Следствие 2. В V и в V* справедливо следующее утверждение: для любых двух сверхслов х и у таких, что [х] < [у] (соответственно, [х]* <* [у]*) существует сверхслово г такое, что [г] > [х] и (соответственно,
[А* >•[*]> МТМ*Л
Из результатов первой главы следует, что вопрос дополняемости вверх решается отрицательно (то есть существуют степени [х]* и [у]*, где [х]* >* [у]*, такие, что [х]* не является верхней гранью [у]* и [г]* ни для какого [г]* <* [х]* и И*!*[>']*)> а вопрос дополняемости вниз, согласно следствию 2, положительно (то есть для любых степеней [х]* и \у]*, где [х]* <* [у]*, существует степень [г]* такая, что [г]* >* [х]* и [г]*|*в множестве степеней асинхронно автоматных преобразований. Для множества степеней конечно-автоматных преобразований справедлив аналогичный результат.
Во второй главе изучаются свойства полных и ¿'-полных сверхслов и соответствующие им степени конечно-автоматных преобразований.
В §2.1 приведены основные определения и необходимые для дальнейшего изложения результаты.
Определение 4. Сверхслово х = {ап\п е ГС} над алфавитом Е называется полным, если для любого блока В = Ьф2...Ьк 6 Е* существует т е N такое, что ат+1 = Ь{ для всех / = 1, к.
Вводится понятие регулятора полноты для полных сверхслов. Пусть / : N -»■ N - одноместная функция. Регулятором полноты для полного сверхслова х е Е® назовем функцию /, которая каждому натуральному числу к сопоставляет наименьшее натуральное число / такое, что любое слово длины к из символов алфавита Е встречается на начальном отрезке сверхслова х длины 1.
Для дальнейшего нам достаточно будет знать не сами значения регулятора полноты, а значения некоторой функции, мажорирующей регулятор полноты. Полное сверхслово х с регулятором полноты, ограниченным функцией /, будем называть, для краткости, /-полным.
Определение 5. Сверхслово х е называется /-полным, если для любого к £ N каждый блок длины к из символов алфавита Е встречается на начальном отрезке сверхслова х длины /(к).
Определение 6. Вычислимое сверхслово х называется эффективно полным, если х является /-полным для некоторой вычислимой функции /.
Пусть теперь <р : Е* -*■ Е'* - А:-равномерный морфизм (то есть, <р(АВ) = <р(А)<р(В) для любых А, В е Е* и \<р(а)\ = к для любого а <= Е), х - полное сверхслово над алфавитом Е. Бесконечное слово вида <р(х) будем называть А'-полным.
Определение 7. Сверхслово называется к-полным, если оно является образом полного сверхслова при действии к-равномерного морфизма.
Если фиксировал, мощность алфавита, над которым рассматриваются сверхслова, то степень конечно-автоматных преобразований, содержащая полное сверхслово, состоит только из полных сверхслов и называется полной степенью [18]. Соответственно, степень конечно-автоматных преобразований, содержащая £-полное сверхслово, состоит из ¿-полных сверхслов и заключительно ¿-полных сверхслов и называется к-полной степенью.
В §2.2. изучаются свойства полных сверхслов с заданным регулятором
полноты.
Теорема 5. Пусть Б = (в.Г.Е'Лй») - (сильно связный) полный автомат Мши с п состояниями, х - /-полное сверхслово. Тогда фо,х) будет g-полным сверхсловом, где g(k) = /((к + п - 1)").
Под полным автоматом понимается конечный сильно связный автомат Мили 5 = такой, что для любого натурального к и любого ¿-блока
В е Е* существуют состояние 5 6 5 и ¿-блок А € £* такие, что ф, А) = В.
Следствие 3. Пусть Б = (5, Е, Е', 8, со) - (сильно связный) полный автомат Мили, х - эффективно полное сверхслово. Тогда со^х) также эффективно полное сверхслово.
Следующая теорема обобщает известный результат Г. Гордона [18].
Теорема 6. Пусть / : N -»• N - возрастающая функция. Пусть у - сверхслово, построенное с помощью функции /. Тогда не существует полного сверхслова х и конечного автомата Мили 5 таких, что (¿о,*) = Ау, где блок А определяет некоторую конечную задержку.
Следствие 4. Существует неполная степень [у], над которой нет полных степеней, то есть не существует полной степени [х] такой, что [х] > [у].
Предложение 4. Каждое полное сверхслово является жестким.
Здесь сверхслово х называется жестким ([14]), если для любой периодической (0, ^-последовательности а, содержащей бесконечное число нулей, сверхслово у, элементы которого удовлетворяют свойству 0 = *(/), если «(/) = 1, у(0 = 0, если а(0 = 0, имеет степень строго меньшую, чем степень х. Само сверхслово у называется а-прореженным из сверхслова х.
В §2.3. изучаются свойства ¿-полных сверхслов и ¿-полных степеней.
Теорема 7. Для любого натурального к, для любого к-полного сверхслова х существует полное сверхслово у такое, что са$(?о,у) = х для некоторого конечного автомата Мили 5.
Следующее утверждение является следствием теорем 6 и 7.
Следствие 5. Существует сверхслово у такое, что для любого натурального к не существует к-полного сверхслова х и конечного автомата Мили 5, для которых выполнено (0з(?0,х) = Ау, где А - блок, определяющий некоторую конечную задержку.
Теорема 8. Для любого полного сверхслова х, для любого натурального к существует к-полное сверхслово у такое, что у не является п-полным при пфО {той к) и = у для некоторого конечного автомата Мили Б.
Теорема 9. Если х является к-полным и п-полным сверхсловом ий- наибольший общий делитель кип, то х является й-полным сверхсловом.
Все полученные результаты для ¿-полных сверхслов переносятся на случай ¿-полных степеней.
Следствие 6. Для любого натурального к, для любой к-полной степени [*] существует полная степень [у] татя, что [у] > М-
Следствие 7. Существует неполная степень [у], над которой нет к-полных степеней для любого натурального к, то есть не существует к-полной степени [*] такой, что [х] > [у].
Следствие 8. Для любой полной степени [х], для любого натурального к существует к-полная степень [у], которая не является п-полной при пфЪ (imod k) и [х] > [у].
Следствие 9. Если [х] является k-полной и п-полной степенью и d - наибольший общий делитель кип, то [х] является d-полной степенью.
В теореме 10 установлено, что, в отличие от полных сверхслов, которые являются жесткими, it-полные сверхслова не всегда являются жесткими.
Теорема 10. Пусть х - к-полное сверхслово над алфавитом Е, полученное из полного сверхслова у над алфавитом 2" при помощи к-равномерного мор-физма (р: Е' -*■ Ек. Сверхслово х является жестким тогда и только тогда, когда число различных а-прореженных слов из слов (p(i), i <= Е', меньше числа различных слов <p{i), i 6 Е', для любого {0,1 }-слова а длины к.
Глава 3 посвящена исследованию проблемы разрешимости монадических теорий сверхслов.
В §3.1 приведены основные определения и некоторые известные результаты, необходимые для дальнейшего изложения.
Рассмотрим структуру {N, <• X), где N - множество натуральных чисел, которое пробегают индивидуальные переменные, < - двухместный предикат
порядка, X - функциональный символ, который интерпретируется как последовательность х : N -* 27. Под логической теорией первого порядка сверхслова х понимают обычную теорию первого порядка этой структуры. В монади-ческой теории (второго порядка) кроме предметных переменных (по натуральным числам) разрешены также монадические переменные по подмножествам натуральных чисел (или одноместным предикатам) Р(у), Q(z),... Разрешаются кванторы как по предметным переменным (натуральным числам), так и по монадическим переменным. Вводятся также атомарные формулы вида Р(р) ('р принадлежит Р"). Такую теорию обозначают МТ(Ы, <,х) [8].
Существует критерий разрешимости монадической теории сверхслова на языке теории автоматов, а именно: монадическая теория сверхслова * разрешима тогда и только тогда, когда существует алгоритм, который по любому автомату Бюхи (или любому детерминированному автомату Мюллера) может определить, принимает ли этот автомат сверхслово х или нет [8]. Этот критерий используется при доказательстве разрешимости монадических теорий сверхслов.
В §3.2 доказывается, что свойство разрешимости монадических теорий сверхслов сохраняется относительно асинхронно автоматных преобразований или, другими словами, замкнуто вниз относительно асинхронно автоматной сводимости.
Теорема И. Пусть [>>]* <* [х]* и MT(N, <,*)разрешима. Тогда MT(N, <,у) также разрешима.
В §3.3 получен критерий разрешимости монадической теории полного сверхслова.
Теорема 12. Монадическая теория MT{N, <,х) полного сверхслова х разрешима тогда и только тогда, когда х - эффективно полное сверхслово.
Очевидным следствием теоремы 12 является аналогичный результат для ¿-полных сверхслов.
Следствие 10. Монадическая теория МТ{Ш, <,х) к-полного сверхслова х разрешима тогда и только тогда, когда х является образом эффективно полного сверхслова при действии к-равномерного морфизма.
В заключение, автор выражает глубокую благодарность своему научному руководителю Марату Мирзаевичу Арсланову за постановку задач, поддержку и внимание к работе, а также всем сотрудникам кафедры алгебры и математической логики Казанского (Приволжского) федерального университета и отдела алгебры и математической логики НИЦ "НИНММ им. Н.Г. Чеботарева" Казанского (Приволжского) федерального университета за доброжелательную атмосферу.
Литература
[1] Байрашева В.Р. Степени автоматных преобразований. // Вероятностные методы и кибернетика. - 1982. -№ 18. - С. 17-25.
[2] Байрашева В.Р. Структурные свойства автоматных преобразований. II Известия вузов. Математика. - 1988. - № 7. - С. 34-39.
[3] Байрашева В.Р. Степени автоматных преобразований почти периодических сверхслов и сверхслов с разрешимой монадической теорией. /I Казань, 1989, 29 с. - Деп. в ВИНИТИ 11.05.1989 - № 3103. - В89.
[4] Байрашева В.Р. Степени автоматных преобразований случайных последовательностей. II Диссертация на соискание ученой степени кандидата физико-математических наук. Саратовский государственный университет им. Н.Г. Чернышевского. Саратов. - 1990. - 104 с.
[5] МарченковС.С. Конечные начальные сегменты верхней полурешетки конечно-автоматных степеней. II Дискретная математика. - 1989. -Т. 1. - № 3. - С. 96-103.
[6] Марченков С.С. Булева сводимость. II Дискретная математика. - 2003. -№ 3. - Т. 15.-С. 40-53.
[7] Марченков С.С. О строении частично упорядоченных множеств булевых степеней. // Дискретная математика. - 2006. - № 1. - Т. 18. - С. 61-75.
[8] Мучник Ан.А., Притыкин Ю.Л., Семенов А.Л. Последовательности, близкие к периодическим. II Успехи математических наук. - 2009. - Т. 64. -№ 5 (389). - С. 21-96.
[9] Пригыкин Ю.Л. Конечно-автоматные преобразования строго почти периодических последовательностей. // Математические заметки. - 2006. -Т. 80. - № 5. - С. 751-756.
[10] Пригыкин Ю.Л. Почти периодичность, конечно-автоматные преобразования и вопросы эффективности. И Известия вузов. Математика. -2010.-№ 1.-С. 74-87.
[И] Пригыкин Ю.Л. Алгоритмические свойства последовательностей, близких к периодическим. // Диссертация на соискание ученой степени кандидата физико-математических наук. Московский государственный университет им. М.В. Ломоносова. Москва. - 2009. - 96 с.
[12] Роджерс X. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972. - 624 с.
[13] Семенов АЛ. Логические теории одноместных функций на натуральном ряде. П Известия Академии наук СССР. Серия математическая. - 1983. -№ 3. - Т. 47. - С. 623-658.
[14] Соловьев В.Д. Структура распределения информации в бесконечной последовательности. I/ Дискретная математика. - 1996. - № 2. - Т. 8. -С. 97-107.
[15] Carton О., Thomas W. The monadic theory of morphic infinite words and generalizations. // Information and Computation. - 2002. - V. 176. - P. 5165.
[16] Cobham A. Uniform tag sequences. II Math. Systems Theory. - 1972. - V. 6. -P. 164-192.
[17] Dekking F.M. Iteration of maps by an automaton. U Discrete Matli. - 1994. -V. 126. - P. 81-86.
[18] Gordon H.G. Complete Degrees of Finite-State Transformability. II Information and Control. - 1976. - V. 32. - P. 169-187.
[19] Gordon H.G. An Isomorphism of Complete Degrees of Finite-State Transformability. // Information and Control. - 1979. - V. 40. - P. 192-204.
[20] Muchnik An., Semenov A., Ushakov M. Almost periodic sequences. II Theoretical Computer Science. - 2003. - V. 304. - P. 1-33.
[21] Rayna G. Degrees of finite-state transformability.il Information and Control. -1974. _ v. 24. - P. 144-154. [русский перевод: Рейна Г. Степени автоматных преобразований.!I Кибернетический сборник. - 1977. - № 14. -С. 95-106.]
Работы автора по теме диссертации
Работы, опубликованные в журналах, входящих в перечень ВАК Министерства образования и науки РФ:
[22] Корнеева Н.Н. Степени асинхронно автоматных преобразований. // Известия вузов. Математика. - 2011. -№ 3. - С. 30-40.
[23] Корнеева Н.Н. Об автоматных преобразованиях и монадичеасих теориях бесконечных последовательностей. II Известия вузов. Математика. -2011.-№8.-С. 90-93.
[24] Корнеева Н.Н. Монадические теории последовательностей при асинхронно автоматных преобразованиях. И Ученые записки Казанского университета. Серия Физико-математические науки. - Принято к печати.
Другие публикации:
[25] Корнеева H.H. Структура степеней асинхронно автоматных преобразований. // Труды Математического центра им. Н.И. Лобачевского: Материалы Восьмой молодежной научной школы-конференции "Лобачевские чтения - 2009"; Казань, 1-6 ноября 2009 г. - Казань, Казанское математическое общество, 2009. - Т. 39. - С. 270-272.
[26] Корнеева H.H. Степени автоматных преобразований бесконечных последовательностей. II Международная конференция "Мальцевские чтения", посвященная 70-летию Академика Юрия Леонидовича Ершова, 2-6 мая 2010 г: тезисы докладов. - 2010. - С. 50.
[27] Корнеева H.H. Автоматные преобразования и монадические теории f-полных последовательностей. I/ Труды Математического центра им. Н.И. Лобачевского: Материалы Девятой молодежной научной школы-конференции "Лобачевские чтения - 2010"; Казань, 1-6 октября 2010 г. -Казань, Казанское математическое общество, 2010. - Т. 40. - С. 188-191.
[28] Корнеева H.H. О разрешимости монадических теории бесконечных последовательностей. II Алгебра и математическая логика: материалы международной конференции, посвященной 100-летию со дня рождения профессора В.В. Морозова, и молодежной школы-конференции "Современные проблемы алгебры и математической логики"; Казань, 25-30 сентября 2011 г. - Казань, КФУ, 2011. - С. 111-112.
[29] Корнеева H.H. О степенях автоматных преобразований k-полных последовательностей. II Международная конференция "Мальцевские чтения", посвященная 60-леггию со дня рождения Сергея Савостьяновича Гончарова, 11-14 октября 2011 г: тезисы докладов. - 2011. - С. 103.
Подписано в печать 16.02.12 Бумага офсетная. Печать ризографическая. Формат 60x84 1/16. Гаршпура «Times New Roman». Усл. печ. л. 1,3 Уч.-изд. л. 1,4. Тираж 110 экз. Заказ 72/2
Отпечатано с готового оригинала-макета в типографии Издательства Казанского университета
420008, г. Казань, ул. Профессора Нужина, 1/37 тел. 233-73-59,292-65-60
61 12-1/685
Федеральное государственное автономное образовательное учреждение высшего профессионального образования "КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ''
На правах рукописи УДК 519.71
Корнеева Наталья Николаевна
Степени асинхронно автоматных преобразований сверхслов над конечными алфавитами
01.01.06 — математическая логика, алгебра и теория чисел
ДИССЕРТАЦИЯ
на соискание ученой степени кандидата физико-математических наук
Научный руководитель д. ф.-м. н., профессор Арсланов Марат Мирзаевич
Казань - 2012
Содержание
Введение 3
Глава 1. Структура степеней асинхронно автоматных преобразований 11
§1.1. Автоматные преобразования сверхслов ........................11
§1.2. Существование плотных участков в множестве степеней конечно-
автоматных преобразований ....................................17
§1.3. Связь между степенями конечно-автоматных и асинхронно
автоматных преобразований ....................................23
§1.4. Существование наименьшего элемента и атомов ............25
§1.5. Вложимость конечных линейно упорядоченных множеств . 32 §1.6. Дополняемость вверх, вниз в множестве степеней автоматных преобразований..............................................39
Глава 2. Полные и /¿-полные сверхслова и степени 47
§2.1. Полные и £;-полные сверхслова ................................47
§2.2. Свойства полных сверхслов и полных степеней................52
§2.3. Свойства А;-полных сверхслов и к-полных степеней..........55
Глава 3. Разрешимость монадических теорий сверхслов 63
§3.1. Логические теории сверхслов....................................63
§3.2. Асинхронно автоматные преобразования сверхслов с разрешимой монадической теорией ..................................66
§3.3. Разрешимость монадической теории полного сверхслова . . 71
Литература 74
Введение
В теории алгоритмов значительное место отводится сравнению сложности множеств или бесконечных последовательностей при помощи некоторой алгоритмической сводимости и изучению степеней неразрешимости относительно этой сводимости. Наиболее известны и употребительны е—, Т—, и—, га— сводимости (см., например, [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
Структура степеней асинхронно автоматных преобразований
В этой главе устанавливается связь между степенями конечно-автоматных преобразований и степенями асинхронно автоматных преобразований и доказываются некоторые свойства структуры степеней асинхронно автоматных преобразований.
§1.1. Автоматные преобразования сверхслов
Алфавитом будем называть произвольное конечное множество. Будем обозначать алфавит символами Е, Е',.--- Элементы алфавита называем буквами или символами, конечную последовательность букв алфавита - словом или блоком. При этом отождествляем однобуквенные слова и буквы алфавита. Конечные слова будем обозначать большими или малыми буквами из начала латинского алфавита. Через Е* обозначаем множество всех слов над алфавитом Е, включая пустое слово (слово нулевой длины) Л, через Е+ - множество всех непустых слов над алфавитом Е. Через \А\ будем обозначать длину слова А, через \А\а - количество букв а в слове А.
Множество натуральных чисел {0,1,2,...} обозначаем N.
Будем рассматривать бесконечные последовательности над заданным конечным алфавитом Е, то есть отображения х : N —> Е. Такие бесконечные последовательности также называют бесконечными словами или сверхсловами. Бесконечные слова будем обозначать малыми буквами с конца латинского алфавита х, у,.... Если �
