WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

На правах рукописи

Корнеева Наталья Николаевна

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

01.01.06 – математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Казань – 2012

Работа выполнена на кафедре алгебры и математической логики Федерального государственного автономного образовательного учреждения высшего профессионального образования “Казанский (Приволжский) федеральный университет”.

Научный консультант: доктор физико-математических наук, профессор Арсланов Марат Мирзаевич,

Официальные оппоненты: доктор физико-математических наук, профессор Добрица Вячеслав Порфирьевич, доктор физико-математических наук, профессор Ишмухаметов Шамиль Талгатович.

Ведущая организация : Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования “Вятский государственный гуманитарный университет”.

Защита состоится «28» марта 2012 г. в __.__ на заседании диссертационного совета Д 212.081.24 при ФГАОУВПО “Казанский (Приволжский) федеральный университет” по адресу: 420008, г. Казань, ул. Кремлевская, д. 35., конференц-зал библиотеки им. Н. И. Лобачевского.

С диссертацией можно ознакомиться в библиотеке Казанского (Приволжского) федерального университета.

Автореферат разослан « » 2012 г.

Ученый секретарь диссертационного совета Д 212.081.к.ф.-м.н., доцент Еникеев А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Работа посвящена изучению свойств структуры степеней асинхронно автоматных преобразований бесконечных последовательностей (или, другими словами, бесконечных слов или сверхслов), а также некоторых свойств бесконечных слов, сохраняющихся относительно автоматных преобразований.

В теории алгоритмов значительное место отводится сравнению сложности множеств или бесконечных последовательностей при помощи некоторой алгоритмической сводимости и изучению степеней неразрешимости относительно этой сводимости. Наиболее известны и употребительны e, T, t t, m сводимости (см., например, [12]). Менее известны и изучены сводимости, определяемые при помощи конечных автоматов. В 1974 году Г. Рейна [21] ввел понятия конечно–автоматной сводимости при помощи конечных автоматов Мили, классов эквивалентности (или степеней неразрешимости) относительно этой сводимости и частичный порядок на этих классах эквивалентности. Он назвал две бесконечные последовательности (два сверхслова) конечно–автоматно эквивалентными, если каждую из них можно преобразовать в другую при помощи некоторого конечного автомата Мили, возможно с некоторой фиксированной конечной задержкой. Г. Рейна [21] также получил первые результаты для частично упорядоченного множества степеней конечно–автоматных преобразований. Он показал, что это множество (обозначенное им через V ) является верхней полурешеткой с наименьшим элементом, без максимальных элементов, в которой существуют атом и плотный участок.

Результаты, полученные Г. Рейна [21], в значительной степени были обобщены В.Р. Байрашевой [1] – [4]. Она показала вложимость в V любого конечного линейно упорядоченного множества как начального сегмента [2], изоморфность любого счетного частично упорядоченного множества некоторому подмножеству V [2]. С.С. Марченковым [5] было показано, что любое конечное частично упорядоченное множество с наименьшим и наибольшим элементом вложимо как начальный сегмент в V. Этот результат был усилен В.Д. Соловьевым [14], который показал, что любое конечное частично упорядоченное множество с наименьшим и наибольшим элементом изоморфно начальному сегменту структуры степеней конечно–автоматных преобразований сверхслов в алфавите f0; 1g.

Обобщив процедуру Г. Рейна построения атома [21], В.Р. Байрашева [4] показала существование континуума атомов. Кроме того, ею [3] были построены атомы со следующими заранее заданными свойствами: атом, состоящий из эффективно обобщенно почти периодических сверхслов (в терминологии [8]); атом, состоящий из обобщенно почти периодических сверхслов с неразрешимой монадической теорией; атом, состоящий из сверхслов с разрешимой монадической теорией, которые не являются обобщенно почти периодическими; атом, состоящий из сверхслов с неразрешимой монадической теорией, которые не являются обобщенно почти периодическими. Независимо от того, что существуют атомы со столь различными свойствами, любой атом структуры V состоит только из плотно упакованных сверхслов (В.Д. Соловьев [14]).

Частичные упорядочения степеней конечно–автоматных преобразований обобщенно почти периодических сверхслов и сверхслов с разрешимой монадической теорией являются начальными сегментами V, но в отличие от V не являются верхними полурешетками (В.Р. Байрашева [3]). Также не является верхней полурешеткой частичное упорядочение степеней конечно–автоматных преобразований сверхслов, заданных в алфавите, мощность которого ограничена некоторым натуральным числом (В.Р. Байрашева [2]).

В дальнейшем вопрос о замкнутости свойств бесконечных слов относительно автоматных преобразований рассматривался не только для преобразований, определяемых при помощи автоматов Мили (в терминологии [8, 9, 10, 20], равномерных преобразователей), но и для преобразований, определяемых асинхронными автоматами (или, в терминологии [8, 9, 10, 20], конечными преобразователями). Относительно произвольных (не обязательно равномерных) автоматных преобразований сохраняются свойства сверхслов быть обобщенно почти периодическими ([13, 20, 8]), эффективно обобщенно почти периодическими ([13, 20, 8]), заключительно почти периодическими ([9, 10]), рекуррентными ([8, 11]), морфическими [17]. Множество k-автоматных сверхслов сохраняется относительно равномерных конечно–автоматных преобразований [16]. До сих пор остается открытым вопрос: сохраняется ли множество kавтоматных сверхслов относительно произвольных автоматных преобразований.

Для доказательства отсутствия максимального элемента в множестве степеней конечно–автоматных преобразований, Г. Рейна [21] ввел понятие полного сверхслова. Он назвал сверхслово, заданное над некоторым фиксированным алфавитом, полным, если в нем для любого натурального числа k встречается каждый блок длины k из символов этого алфавита. Если мощность алфавита, над которым рассматриваются сверхслова, фиксирована, то степень конечно– автоматных преобразований, содержащая полное сверхслово, состоит только из полных сверхслов. Такие степени Г. Гордон назвал полными степенями [18, 19]. В своих работах [18, 19] он получил некоторые результаты для частично упорядоченного множества полных степеней. В частности, Г. Гордон дал частичный ответ на вопрос: имеет ли полная степень покрытие. Оказалось, либо все полные степени имеют покрытие, либо ни одна не имеет [18].

Кроме того, для любых полной степени x и неполной степени y таких, что x > y, существуют полная степень x0 и неполная степень y0 такие, что x > x0 > y0 > y ([18]), то есть каждая полная степень определяет бесконечный начальный сегмент в V [18]. Г. Гордон [18] показал, что существует неполная степень, над которой нет полной степени. В [19] показано, что частичные порядки степеней конечно–автоматных преобразований, лежащие выше заданных произвольно выбранных полных степеней, изоморфны.

В.Р. Байрашевой [1] было показано, что частично упорядоченная система полных степеней не является верхней полурешеткой.

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

Рядом авторов исследовалась разрешимость монадических теорий бесконечных слов. Например, монадическая теория обобщенно почти периодического сверхслова разрешима тогда и только тогда, когда сверхслово является эффективно обобщенно почти периодичным [13, 8]. Как следствие, монадическая теория почти периодического сверхслова разрешима тогда и только тогда, когда сверхслово вычислимо и множество его подслов разрешимо [8].

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

Цель диссертационной работы. Исследование структуры степеней асинхронно автоматных преобразований сверхслов, а также некоторых свойств бесконечных слов, сохраняющихся относительно автоматных преобразований.

Научная новизна. Все основные результаты являются новыми, получены автором самостоятельно. Часть результатов обобщает известные свойства структуры степеней конечно–автоматных преобразований, часть результатов дополняет известные результаты о разрешимости монадических теорий некоторых классов сверхслов.

Теоретическая и практическая значимость. Диссертация носит теоретический характер, её результаты могут использоваться в дальнейших исследованиях при изучении сводимостей, определяемых конечными автоматами.

Материалы диссертации могут быть использованы при чтении спецкурсов для студентов и аспирантов в университетах.

Основные результаты диссертации.

1. Исследовано частично упорядоченное множество степеней асинхронно автоматных преобразований: доказано существование континуума атомов, установлена вложимость в качестве начального сегмента конечного линейно упорядоченного множества. Получен положительный ответ на вопрос дополняемости вниз в множестве степеней асинхронно автоматных преобразований и в множестве степеней конечно–автоматных преобразований.

2. Исследована структура степеней конечно–автоматных преобразований k–полных сверхслов и полных сверхслов с заданным регулятором полноты.

3. Доказано, что свойство разрешимости монадических теорий сверхслов сохраняется относительно асинхронно автоматных преобразований.

4. Получен критерий разрешимости монадической теории полного сверхслова.

Апробация работы.

По результатам диссертации были сделаны доклады:

на международных конференциях “Мальцевские чтения 2010” и “Мальцевские чтения 2011” (Новосибирск, 2010 г., 2011 г.);

на международной конференции “Алгебра и математическая логика” (Казань, 2011 г.);

на международной конференции “Воображаемая логика Н.А. Васильева и современные неклассические логики” (Казань, 2010 г.);

на молодежных научных школах–конференциях “Лобачевские чтения 2009” и “Лобачевские чтения 2010” (Казань, 2009 г., 2010 г.);

на научных семинарах и итоговых конференциях кафедры алгебры и математической логики Казанского (Приволжского) федерального университета 2009–2011 гг.

Публикации. Основные результаты опубликованы в трех статьях [22] – [24] в журналах, входящих в перечень ВАК Министерства образования и науки РФ, и пяти тезисах [25] – [29], список которых приведен в конце автореферата.

Личный вклад автора. Все основные результаты диссертации получены автором.

Структура и объем диссертации. Диссертационная работа изложена на 78 страницах и состоит из введения, трех глав, разделенных на параграфы, и списка литературы, содержащего 37 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, приведен обзор результатов исследований по ее тематике.

В первой главе устанавливается связь между степенями конечно–автоматных и асинхронно автоматных преобразований и доказываются свойства структуры степеней асинхронно автоматных преобразований.

В §1.1 приведены основные определения, используемые в работе: определения конечно–автоматной и асинхронно автоматной сводимости.

Будем рассматривать бесконечные последовательности над заданным конечным алфавитом , то есть отображения x W N ! . (Полагаем, что N D f0; 1; 2; :::g.) Такие последовательности также называют бесконечными словами или сверхсловами.

На бесконечных словах вводится понятие сводимости либо при помощи автоматов Мили (см. [21]), либо при помощи асинхронных автоматов.

Определение 1. Конечным автоматом Мили (конечным асинхронным автоматом) называется пятерка.S; ; 0; ; !/; где S, , 0 – конечные множества состояний, входных и выходных символов соответственно; W S ! S – функция переходов; ! W S ! 0 (соответственно, ! W S !.0/ ) – функция выходов. Если дополнительно выделено начальное состояние s0, то автомат называется инициальным.

Единственное отличие конечного асинхронного автомата от конечного автомата Мили в том, что областью значений функции выхода являются не только символы выходного алфавита, но и слова из символов выходного алфавита произвольной длины (в том числе и пустое слово).

Определение 2. Пусть x и y – сверхслова над конечными алфавитами (каждое над своим алфавитом). Сверхслово y конечно–автоматно сводится (асинхронно автоматно сводится) к сверхслову x, если существует конечный инициальный автомат Мили (соответственно, конечный инициальный асинхронный автомат).S; s0/ такой, что !S.s0; x/ D Ay; где блок A 2 S определяет некоторую конечную задержку (соответственно, !S.s0; x/ D y).

Отношения сводимости из данного определения индуцируют отношения эквивалентности на множестве бесконечных слов. Класс эквивалентности, который содержит сверхслово x, обозначается x (для асинхронно автоматной сводимости x ) и называется степенью конечно–автоматных преобразований сверхслова x (соответственно, степенью асинхронно автоматных преобразований).

Отношение сводимости на бесконечных словах индуцирует частичный порядок на множестве степеней автоматных преобразований.

Определение 3. x y ( x y ), если существует конечный инициальный автомат Мили (соответственно, конечный инициальный асинхронный автомат).S; s0/ такой, что !S.s0; x/ D Ay, где блок A 2 S определяет некоторую конечную задержку (соответственно, !S.s0; x/ D y).

Частично упорядоченные множества степеней конечно–автоматных и асинхронно автоматных преобразований обозначаются V и V соответственно.

В §1.2 строится начальный сегмент в множестве степеней конечно–автоматных преобразований, который является булевой алгеброй.

Пусть f W N ! N – произвольная функция. По определению полагаем, что сверхслово x построено с помощью функции f, если x начинается с единицы и за i-й единицей следует f.i/ нулей.

Теорема 1. Пусть f W N ! N – возрастающая функция, обладающая свойством:.f.i/ f.j /.mod k// ).f.i C 1/ f.j C 1/.mod k//: Пусть x – сверхслово, построенное с помощью функции f. Множество L D fy j y x g является булевой алгеброй.

В §1.3 получены соотношения между степенями конечно–автоматных и асинхронно автоматных преобразований.

Предложение 1. Между степенями конечно–автоматных и асинхронно автоматных преобразований имеют место следующие соотношения:

1) если x y, то x y, 2) существуют сверхслова x и y такие, что x jy и x D y, 3) для любого сверхслова x его степень асинхронно автоматных преобразований есть объединение степеней конечно–автоматных преобразований:

S x D yj.

j 2J Предложение 2. Существует степень асинхронно автоматных преобразований, которая состоит из счетного числа степеней конечно–автоматных преобразований.

Далее в первой главе (в параграфах 1.4, 1.5) получены свойства структуры степеней асинхронно автоматных преобразований.

Предложение 3. Класс 0 (содержащий нулевое бесконечное слово) состоит из заключительно периодических сверхслов (то есть, периодических сверхслов с предпериодом). Для любого сверхслова x, x 0.

Теорема 2. Существует континуум атомов V.

Теорема 3. Любое конечное линейно упорядоченное множество вложимо как начальный сегмент V.

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

Теорема 4. В V и в V справедливо следующее утверждение: для любых двух сверхслов x и y таких, что 0 < x < y (соответственно, 0 < x < y ) существует сверхслово z такое, что z jx, z jy и .x; z/ jy (соответственно, z j x, z j y и .x; z/ j y ).

Следствие 1. В V и в V справедливо следующее утверждение: для любого сверхслова x такого, что x > 0 (соответственно, x > 0 ) существует сверхслово y такое, что x jy (соответственно, x j y ).

Следствие 2. В V и в V справедливо следующее утверждение: для любых двух сверхслов x и y таких, что x < y (соответственно, x < y ) существует сверхслово z такое, что z > x и z jy (соответственно, z > x и z j y ).

Из результатов первой главы следует, что вопрос дополняемости вверх решается отрицательно (то есть существуют степени x и y, где x > y, такие, что x не является верхней гранью y и z ни для какого z < x и z j y ), а вопрос дополняемости вниз, согласно следствию 2, положительно (то есть для любых степеней x и y, где x < y, существует степень z такая, что z > x и z j y ) в множестве степеней асинхронно автоматных преобразований. Для множества степеней конечно–автоматных преобразований справедлив аналогичный результат.

Во второй главе изучаются свойства полных и k–полных сверхслов и соответствующие им степени конечно–автоматных преобразований.

В §2.1 приведены основные определения и необходимые для дальнейшего изложения результаты.

Определение 4. Сверхслово x D fanjn 2 Ng над алфавитом называется полным, если для любого блока B D b1b2:::bk 2 существует m 2 N такое, что amCi D bi для всех i D 1; k.

Вводится понятие регулятора полноты для полных сверхслов.

Пусть f W N ! N – одноместная функция. Регулятором полноты для полного сверхслова x 2 N назовем функцию f, которая каждому натуральному числу k сопоставляет наименьшее натуральное число l такое, что любое слово длины k из символов алфавита встречается на начальном отрезке сверхслова x длины l.

Для дальнейшего нам достаточно будет знать не сами значения регулятора полноты, а значения некоторой функции, мажорирующей регулятор полноты.

Полное сверхслово x с регулятором полноты, ограниченным функцией f, будем называть, для краткости, f –полным.

Определение 5. Сверхслово x 2 N называется f –полным, если для любого k 2 N каждый блок длины k из символов алфавита встречается на начальном отрезке сверхслова x длины f.k/.

Определение 6. Вычислимое сверхслово x называется эффективно полным, если x является f –полным для некоторой вычислимой функции f.

Пусть теперь ' W ! 0 – k–равномерный морфизм (то есть, '.AB/ D '.A/'.B/ для любых A; B 2 и j'.a/j D k для любого a 2 ), x – полное сверхслово над алфавитом . Бесконечное слово вида '.x/ будем называть k–полным.

Определение 7. Сверхслово называется k–полным, если оно является образом полного сверхслова при действии k–равномерного морфизма.

Если фиксировать мощность алфавита, над которым рассматриваются сверхслова, то степень конечно–автоматных преобразований, содержащая полное сверхслово, состоит только из полных сверхслов и называется полной степенью [18]. Соответственно, степень конечно–автоматных преобразований, содержащая k–полное сверхслово, состоит из k–полных сверхслов и заключительно k–полных сверхслов и называется k–полной степенью.

В §2.2. изучаются свойства полных сверхслов с заданным регулятором полноты.

Теорема 5. Пусть S D.S; ; 0; ; !/ – (сильно связный) полный автомат Мили с n состояниями, x – f –полное сверхслово. Тогда !.s0; x/ будет g– полным сверхсловом, где g.k/ D f..k C n 1/n/.

Под полным автоматом понимается конечный сильно связный автомат Мили S D.S; ; ; !/ такой, что для любого натурального k и любого k–блока B 2 существуют состояние s 2 S и k–блок A 2 такие, что !.s; A/ D B.

Следствие 3. Пусть S D.S; ; 0; ; !/ – (сильно связный) полный автомат Мили, x – эффективно полное сверхслово. Тогда !.s0; x/ также эффективно полное сверхслово.

Следующая теорема обобщает известный результат Г. Гордона [18].

Теорема 6. Пусть f W N ! N – возрастающая функция. Пусть y – сверхслово, построенное с помощью функции f. Тогда не существует полного сверхслова x и конечного автомата Мили S таких, что !S.s0; x/ D Ay, где блок A определяет некоторую конечную задержку.

Следствие 4. Существует неполная степень y, над которой нет полных степеней, то есть не существует полной степени x такой, что x y.

Предложение 4. Каждое полное сверхслово является жестким.

Здесь сверхслово x называется жестким ([14]), если для любой периодической f0; 1g–последовательности , содержащей бесконечное число нулей, сверхслово y, элементы которого удовлетворяют свойству y.i/ D x.i/, если .i/ D 1; y.i/ D 0, если .i/ D 0, имеет степень строго меньшую, чем степень x. Само сверхслово y называется –прореженным из сверхслова x.

В §2.3. изучаются свойства k–полных сверхслов и k–полных степеней.

Теорема 7. Для любого натурального k, для любого k–полного сверхслова x существует полное сверхслово y такое, что !S.s0; y/ D x для некоторого конечного автомата Мили S.

Следующее утверждение является следствием теорем 6 и 7.

Следствие 5. Существует сверхслово y такое, что для любого натурального k не существует k–полного сверхслова x и конечного автомата Мили S, для которых выполнено !S.s0; x/ D Ay, где A – блок, определяющий некоторую конечную задержку.

Теорема 8. Для любого полного сверхслова x, для любого натурального k существует k–полное сверхслово y такое, что y не является n–полным при n ¤ 0.mod k/ и !S.s0; x/ D y для некоторого конечного автомата Мили S.

Теорема 9. Если x является k–полным и n–полным сверхсловом и d – наибольший общий делитель k и n, то x является d –полным сверхсловом.

Все полученные результаты для k–полных сверхслов переносятся на случай k–полных степеней.

Следствие 6. Для любого натурального k, для любой k–полной степени x существует полная степень y такая, что y > x.

Следствие 7. Существует неполная степень y, над которой нет k–полных степеней для любого натурального k, то есть не существует k–полной степени x такой, что x y.

Следствие 8. Для любой полной степени x, для любого натурального k существует k–полная степень y, которая не является n– полной при n ¤ 0.mod k/ и x > y.

Следствие 9. Если x является k–полной и n–полной степенью и d – наибольший общий делитель k и n, то x является d–полной степенью.

В теореме 10 установлено, что, в отличие от полных сверхслов, которые являются жесткими, k–полные сверхслова не всегда являются жесткими.

Теорема 10. Пусть x – k–полное сверхслово над алфавитом , полученное из полного сверхслова y над алфавитом 0 при помощи k–равномерного морфизма ' W 0 ! k. Сверхслово x является жестким тогда и только тогда, когда число различных –прореженных слов из слов '.i/, i 2 0, меньше числа различных слов '.i/, i 2 0, для любого f0; 1g–слова длины k.

Глава 3 посвящена исследованию проблемы разрешимости монадических теорий сверхслов.

В §3.1 приведены основные определения и некоторые известные результаты, необходимые для дальнейшего изложения.

Рассмотрим структуру hN; <; Xi, где N – множество натуральных чисел, которое пробегают индивидуальные переменные, < – двухместный предикат порядка, X – функциональный символ, который интерпретируется как последовательность x W N ! . Под логической теорией первого порядка сверхслова x понимают обычную теорию первого порядка этой структуры. В монадической теории (второго порядка) кроме предметных переменных (по натуральным числам) разрешены также монадические переменные по подмножествам натуральных чисел (или одноместным предикатам) P.y/, Q.z/,... Разрешаются кванторы как по предметным переменным (натуральным числам), так и по монадическим переменным. Вводятся также атомарные формулы вида P.p/ ("p принадлежит P "). Такую теорию обозначают M T hN; <; xi [8].

Существует критерий разрешимости монадической теории сверхслова на языке теории автоматов, а именно: монадическая теория сверхслова x разрешима тогда и только тогда, когда существует алгоритм, который по любому автомату Бюхи (или любому детерминированному автомату Мюллера) может определить, принимает ли этот автомат сверхслово x или нет [8]. Этот критерий используется при доказательстве разрешимости монадических теорий сверхслов.

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

Теорема 11. Пусть y x и M T hN; <; xi разрешима. Тогда M T hN; <; yi также разрешима.

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

Теорема 12. Монадическая теория M T hN; <; xi полного сверхслова x разрешима тогда и только тогда, когда x – эффективно полное сверхслово.

Очевидным следствием теоремы 12 является аналогичный результат для k–полных сверхслов.

Следствие 10. Монадическая теория M T hN; <; xi k–полного сверхслова x разрешима тогда и только тогда, когда x является образом эффективно полного сверхслова при действии k–равномерного морфизма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[18] Gordon H.G. Complete Degrees of Finite-State Transformability. // 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. // Theoretical Computer Science. – 2003. – V. 304. – P. 1–33.

[21] Rayna G. Degrees of finite–state transformability.// Information and Control. – 1974. – V. 24. – P. 144–154. [русский перевод: Рейна Г. Степени автоматных преобразований.// Кибернетический сборник. – 1977. – № 14. – C. 95–106.] Работы автора по теме диссертации Работы, опубликованные в журналах, входящих в перечень ВАК Министерства образования и науки РФ:

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

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

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

Другие публикации:

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

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

[27] Корнеева Н.Н. Автоматные преобразования и монадические теории f –полных последовательностей. // Труды Математического центра им.

Н.И. Лобачевского: Материалы Девятой молодежной научной школы– конференции “Лобачевские чтения – 2010”; Казань, 1–6 октября 2010 г. – Казань, Казанское математическое общество, 2010. – Т. 40. – C. 188–191.

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

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






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.