Автоматные и вычислимые упорядочиваемые множества тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

004бИЗйЪ На правах рукописи

Гаврюшкина Александра Анатольевна

АВТОМАТНЫЕ И ВЫЧИСЛИМЫЕ УПОРЯДОЧИВАЕМЫЕ МНОЖЕСТВА

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

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

- З'ИЮН 2010

Новосибирск-2010

004603275

Работа выполнена в Новосибирском государственном университете

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

Официальные оппоненты: доктор физико-математических наук Алаев Павел Евгеньевич

доктор физико-математических наук, профессор Добрица Вячеслав Порфирьевич

Ведущая организация: Иркутский государственный университет

Защита диссертации состоится 18 июня 2010 г. в 15 часов на заседании диссертационного совета Д 003.015.02 при Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан «17» мая 2010 г.

Учёный секретарь диссертационного совета

кандидат физико-математических наук А. Н. Ряскин

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

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

В 50-е годы прошлого столетия в работах А. Фрелиха, Д. Шефердсона, А. И. Мальцева, М. О. Рабина, Р. Воота и других появилось понятие вычислимой или конструктивной модели, то есть модели, основное множество, все отношения и функции которой могут быть заданы алгоритмически. В связи с богатством и сложностью класса вычислимых моделей возникло стремление выделить подкласс моделей, являющихся простейшими с алгоритмической точки зрения. Одним из таких классов был, предложенный А. Нероудом и Дж. Б. Реммелем, класс р-структур, то есть моделей которые могут быть заданы алгоритмами с полиномиальной сложностью [21]. Но вскоре выяснилось, что любая вычислимая модель в предикатной сигнатуре вычислимо изоморфна р-структуре [7] и, следовательно, желаемого упрощения такое ограничение не дает. Следующим претендентом на роль простейшего стал класс автоматных структур, то есть структур, задаваемых с помощью элементарных устройств — конечных автоматов. Одной из причин выбора именно этого класса является разрешимость элементарной теории автоматных структур [10, 13].

Упоминания такого рода моделей впервые появились в работах Дж. Р. Бюхи и М. О. Рабина [5, 6, 23, 24]. С выходом статьи А. Нероуда и Б. Хусаинова [13], в которой было вновь введено понятие автоматной структуры и были предложены направления исследований в этой области, автоматные структуры подверглись активному изучению.

Дадим более точное определение автоматной структуры. Автоматная структура — это структура в конечной предикатной сигнатуре, основное множество и все отношения ко-

торой распознаются конечными автоматами. Остается не ясным, что подразумевается под словами «отношение распознаётся конечным автоматом», так как отношения в таком случае состоят из п-ок слов. Рассмотрим п-ку слов некоторого алфавита Е, запишем слова этой п-ки одно под другим и выравним слева. Далее выравним длины слов в этой п-ке добавлением к правым концам слов минимального количества символов где Е. Проделав такую процедуру с каждым словом из отношения, мы получим некоторый язык (конво-люцию отношения), состоящий из п-мерных слов, записанных в алфавите (Е и {-!})". Будем говорить, что отношение распознаётся автоматом, если полученный язык распознаётся некоторым конечным автоматом, переходы в котором осуществляются по п-мерным буквам.

Очевидно, что любая конечная модель является автоматной, примерами бесконечных структур, обладающих автоматным представлением, могут служить: (М, <,+), ((¡3, <), полное бинарное дерево. В то время как такие модели как (М, х) [4], ((¡2,4-) [28], безатомная булева алгебра [15, 26], автоматными не являются.

Как уже говорилось выше, теория первого порядка автоматных структур разрешима, более того, она разрешима в некоторых кванторных расширениях. Рассмотрим квантор 3°°, трактуемый как «существует бесконечно много», и кванторы обозначающие «существует к по модулю т

много», тогда теория первого порядка в языке, расширенном квантором 3°° и кванторами , автоматных структур является разрешимой [4, 17, 26]. Следствием этого является замкнутость класса автоматных структур относительно естественных операций, таких как объединение, декартово произведение, взятие фактора и других, и разрешимость многих свойств автоматных структурах, так, например, проблема существования бесконечной клики в автоматном графе является разрешимой [27].

Центральными проблемами в теории автоматных структур являются: характеризация подклассов автоматных структур, таких как отношения эквивалентности, линейные, частичные порядки, графы, булевы алгебры, группы и другие; исследование теоретико-модельных свойств автоматных структур; проблемы, связанные с алгоритмической сложностью автоматных структур, такие как сложность проблемы изоморфизма для автоматных структур и подклассов автоматных структур, проблема автоустойчивости автоматных структур, оценка индексных множеств различных подклассов автоматных структур.

Типы изоморфизма некоторых подклассов автоматных структур полностью описаны, так, например, было показано, что автоматными ординалами являются в точности те ординалы, которые строго меньше [8]. Бесконечная булева алгебра является автоматной тогда и только тогда, когда она является конечным декартовым произведением алгебр конечных и коконечных подмножеств натуральных чисел [15, 26]. Конечно порождённая группа является автоматной в том и только в том случае, когда она является виртуально абелевой [22]. Для линейных порядков, как и для отношений эквивалентности, полной характеризации не было получено, но для автоматных линейных порядков доказано, что они обладают конечным FC-paнгoм [16].

Мерой сложности типа изоморфизма модели является её ранг Скотта, Б. Хусаинов и М. Миннес доказали, что для любого а < шс(к + 1 существует автоматная структура, ранг Скотта которой равен а [11, 12, 20]. Таким образом, исходя из того факта, что вычислимые структуру обладают рангом Скотта, не превосходящим +1, получается, что автоматные структуры устроены настолько сложно, насколько это могло быть возможно.

Теоретико-модельные свойства автоматных структур довольно слабо изучены, хотя существует ряд работ, посвящён-

ных этим вопросам [4, 18].

В [15, 26] доказана Е]-полнота проблемы изоморфизма для класса всех автоматных структр. Проблема изоморфизма автоматных ординалов и булевых алгебр является разрешимой [15, 16, 26]. Недавний ещё неопубликованный результат Д. Куске М. Лори и Дж. Лю говорит о том, что проблема изоморфизма для отношений эквивалентности является П^-полной, а для линейных порядков не является арифметической [19].

В работе [1] приведены оценки индексных множеств для некоторых подклассов автоматных структур.

Понятие автоустойчивости появилось в работах А.И.Мальцева [3]. Если любые два вычислимых представления модели вычислимо изоморфны, то такая модель называется автоустойчивой. Для автоустойчивой модели все разрешимые свойства в одном её вычислимом представлении остаются разрешимыми и во всех других её вычислимых представлениях. То есть, можно сказать, что автоустойчивые модели обладают единственным вычислимым представлением. Исследование автоустойчивости моделей и более общего понятия алгоритмической размерности моделей было продолжено С. С. Гончаровым, А. Т. Нуртазиным, Дж. Б. Реммелем, Б. Хусаиновым, Р. Шором и другими известными математиками. В диссертации изучается вопрос автоустойчивости моделей относительно автоматных представлений, то есть вопрос существования вычислимого изоморфизма между любыми двумя автоматными представлениями модели.

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

Сводка результатов, открытые вопросы и направления для дальнейших исследований в теории автоматных структур сформулированы в обзорных статьях Б.Хусаинова и А. Нероуда [14] и С. Рубина [27].

Научная новизна. Все основные результаты диссертации являются новыми.

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

1. Опровергнута гипотеза о том, что линейные порядки разрешимые в расширенном квантором 3°° языке являются автоматными. Доказано, что любой автоматный линейный порядок формульно определим в подходящем автоматном линейном порядки FC-ранга 1.

2. Доказана автоустойчивость отношений эквивалентности, ординалов и некоторого подкласса линеных порядков относительно автоматных представлений. Изучена связь между автоустойчивостью линейных порядков в классе автоматных представлений и в классе разрешимых представлений.

3. Показано, что автоматные частичные порядки могут обладать сколь угодно высоким рангом Скотта.

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

Апробация работы. По результатам диссертации были сделаны: доклад на конференции «Мальцевские чтения 2005» (Новосибирск, Россия), доклад на «Международной студенческой конференции 2006» (Новосибирск, Россия), доклады на конференциях «Logic Colloquium 2007» (Вроцлав, Польша), «Logic Colloquium 2009» (София, Болгария). Кроме того, результаты докладывались на семинаре НГУ

«Конструктивные модели», на совместном семинаре ИМ СО РАН - The University of Notre Dame «Constructive models» (Новосибирск, Россия), на школе-семинаре ИМ СО РАН «Workshop on Computable Models and Numberings» (Новосибирск, Россия), а также на логических семинарах университетов The University of Notre Dame (Нотр-Дам, США), Cornell University (Итака, США), The City University of New York (Нью-Йорк, США).

Публикации. Основные результаты изложены в работах [29]—[31], опубликованных в журналах, входящих в перечень ВАК ведущих рецензируемых научных журналов и изданий, и в работах {32}—[34].

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав и списка литературы (50 наименования). Объём диссертации 73 стр.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ

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

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

Вторая глава посвящена линейным порядкам. В ней представлены классические сведения о линейных порядках, такие как определения рангов, характеризация линейных порядков.

Рассмотрим линейный порядок С и введём на нем отно-

А

шение эквивалентности, при котором элементы эквивалентны, если между ними лишь конечное число элементов. Про-факторизовав этот линейный порядок по введённому отношению эквивалентности, сохраняя исходное упорядочение, мы вновь получаем линейный порядок. Мы можем продолжить эту процедуру конденсирования по всем счётным ординалам.

РС-ранг линейного порядка — это наименьший ординал а, такой, что после конденсирования а раз мы получаем плотный линейный порядок или линейный порядок, состоящий из одного элемента. Как мы уже говорили, в [15] доказано, что FC-paнг любого автоматного линейного порядка конечен. В разделе 2.3 формулируется и доказывается, что в некотором смысле можно рассматривать лишь автоматные линейные порядки ранга 1.

Теорема 1. Любой автоматный линейный порядок определим в подходящем автоматном линейном порядке РС-ранга 1.

Эта теорема является следствием замкнутости класса автоматных структур относительно декартова произведения и определимости.

В связи с разрешимостью теории автоматных структур в расширенном квантором Э°° языке возникает предположение, что обратное утверждение тоже верно. В разделе 2.4 это предположение опровергнуто.

Теорема 2. Существует линейный порядок, являющийся разрешимым в расширенном квантором 3°° языке, но не являющийся автоматным.

Доказательство этой теоремы основано на лемме о накачке, за счёт которой локально конечные отношения (функции в более общем смысле, то есть отношения, в которых каждый элемент связан этим отношением лишь с конечным числом элементов) в автоматных структурах имеют ограниченный рост (см. [26]).

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

Третья глава посвящена автоустойчивости в классе автоматных структур и в классе разрешимых структур. Пусть С — класс моделей, обладающих определёнными алгоритмическими свойствами, назовём С-представлением модели Л модель принадлежащую классу С, такую, что Л = В. Таким образом, если взять в качестве класса С класс автоматных моделей, то С-представление есть в точности автоматное представление модели. Будем говорить, что модель автоустойчива в классе С-представлений, если любые два её С-представления вычислимо изоморфны. В разделе 3.1 доказана теорема:

Теорема 3. Отношения эквивалентности автоустойчивы в классе автоматных представлений.

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

Теорема 4. Ординалы автоустойчивы в классе автоматных представлений.

Будем называть линейный порядок разреженным, если он не содержит плотных подпорядков. Любой счётный линейный порядок может быть представлен как плотная сумма разреженных линейных порядков [25]. Таким образом, первым шагом в изучении автоустойчивости линейных порядков является изучение разреженных линейных порядков.

Теорема 5. Разреженные линейные порядки FC-ранга, не превосходящего 2, автоустойчивы в классе автоматных представлений.

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

Теорема 6. Существует линейный порядок автоустойчивый в классе автоматных представлений, но не автоустойчивый в классе разрешимых представлений.

Теорема 7. Существует линейный порядок являющийся автоустойчивым в классе разрешимых представлений, но не являющийся автоматным.

В 4 главе доказывается, что автоматные частичные порядки могут обладать сколь угодно высоким рангом Скотта.

Пусть х,у кортежи из А. Будем говорить, что х 0-эквивалентен у в (обозначим через х у), если х и

у удовлетворяют одним и тем же бескванторным формулам в Л. И для а > 0 будем говорить, что х а-эквивалентен у в А (х у), если для любого (3 < а, для любого кортежа й существует кортеж Т> и для любого V существует й такие, что х,Ъ=^ у, 17.

Рангом Скотта кортежа х в А называется наименьший ординал /?, такой, что для любого у из того, что х у, следует, что (А,х) = {А, у)- И ранг Скотта модели А — это наименьший ординал а, превосходящий ранги всех кортежей из А.

Ранг Скотта автоматных структур может принимать любое значение меньшее либо равное + 1 [11, 12]. Используя конструкцию С. С. Гончарова сведения произвольной предикатной сигнатуры к частичному порядку [2, 9], может быть доказана следующая теорема:

Теорема 8. Для любого ординала а < и>^к + 1 существует автоматный частичный порядок, обладающий рангом Скотта равным а или а + 1.

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

Список литературы

[1] Н. С. Винокуров. Индексные множества классов автоматных структур. Сибирский математический журнал, том 47(5), стр. 1019-1030, 2006.

[2] С. С. Гончаров. Проблема числа неавтоэквивалентных конструктивизаций. Алгебра и логика, том 19(6), стр. 2344, 1980.

[3] А. И. Мальцев. О рекурсивных абелевых группах. Доклады АН СССР, 146(5), стр. 1009-1012, 1962.

[4] A. Blumensath. Automatic Structures. Diploma thesis. RWTH Aachen, 1999.

[5] J. R. Biichi. On a decision method in restricted second order arithmetic. Logic, Methodology and Philosophy of Science (Proc. 1960 International Congress), pp. 1-11, 1962.

[6] J. R. Biichi, L. H. Landweber. Definability in the monadic second-order theory of successor. Journal of Symbolic Logic, 34(2):166-170, 1969.

[7] D.Cenzer and J.B. Remmel. Polynomial-time versus recursive models. Annals of Pure and Applied Logic, 54:17-58, 1991.

[8] C. Delhomme. Non-automaticity of шш. 2001, unpublished.

[9] S.S. Goncharov. Isomorphism and Definable Relations on Computable Models. Lecture Notes in Logic (Logic Colloquium '05), 28, pp. 26-45, 2006.

[10] B. R. Hodgson, Théories décidables par automate fini. PhD thesis, University of Montréal, 1976.

[11] B. Khoussainov, M. Minnes. Model Theoretic Complexity of Automatic Structures. Lecture Notes in Computer Science, vol. 4978, pp. 514-525, 2008.

[12] B. Khoussainov, M. Minnes. Model Theoretic Complexity of Automatic Structures. Annals of Pure and Applied Logic, vol. 161, pp. 416-426, 2009.

[13] B. Khoussainov, A. Nerode. Automatic presentations of structures. Lecture Notes in Computer Science, 960:367392, 1995.

[14] B. Khoussainov, A. Nerode. Open Questions in the Theory of Automatic Structures. Bulleten of EATCS, 94, pp. 181— 204, 2008.

[15] B.Khoussainov, A.Nies, S.Rubin, and F.Stephan. Automatic structures: Richness and limitations. Proceedings of 19th IEEE Symposium on Logic in Computer Science, pp. 44-53, 2004.

[16] B. Khoussainov, S. Rubin, F. Stephan. Automatic Linear Orders and Trees. ACM Transactions on Computational Logic, 6(4), pp. 675-700, 2005.

[17] B.Khoussainov, S.Rubin, F.Stephan. Definability and Regularity in automatic structures. In STACS 2004, LNSC vol. 2996, pp. 440-451, 2004.

[18] D.Kuske. Is Cantor's Theorem Automatic? Proceedings of the 10th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), 2850, pp. 332-345, 2003.

[19] D. Kuske, J. Liu, M. Lohrey. The Isomorphism Problem On Classes of Automatic Structures, manuscript.

[20] M. Minnes PhD Thesis, Cornell University, 2008.

[21] A. Nerode and J. B. Remmel. Polynomial time equivalence types. In Logic and Computation, Proceedings of a Workshop held at Carnegie Mellon University 1987, vol. 106, pp. 221-249, 1990.

[22] G.Oliver and RThomas. Automatic presentations of finitely generated groups. Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, LNCS, vol. 3404, pp. 693-704, 2005.

[23] M. O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1-35, 1969.

[24] M. O. Rabin, D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3:114-125, 1959.

[25] J. G. Rosenstein. Linear Orderings. Academic Press, 1982.

[26] S. Rubin. Automatic Structures. PhD thesis, The University of Auckland, 2004.

[27] S.Rubin. Automata presenting structures: A survey of the finite string case. The Bulletin of Symbolic Logic, vol. 14, issue 2, pp. 169-200, 2008.

[28] T.Tsankov. The additive group of rationals does not have an automatic presentation, http://arxiv.org/abs/0905.1505

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

[29] А. А. Ревенко. Автоустойчивость автоматных представлений ординалов и линейных порядков низкого ранга. Вестник НГУ, серия: Математика, механика, информатика, том 8, вып. 4, стр. 76-88 , 2008.

[30] А. А. Гаврюшкина. Ранг Скотта автоматных частичных порядков. Вестник НГУ, серия: Математика, механика, информатика, том 10, вып. 2, стр. 37-44, 2010.

[31] А. А. Гаврюшкина. Об автоматных и разрешимых линейных порядках. Сибирские электронные математические известия, http://semr.math.nsc.ru, том 7, стр. 100— 110, 2010.

[32] А. А. Ревенко. Изоморфизм автоматных представлений полных порядков. Материалы XLIV МНСК, серия Математика, стр. 79, 2006.

[33] A. Revenko. Automatic linear orders, Logic Colloquium 2007, Book of Abstracts, p. 68, 2007.

[34] A. Revenko. The Complexity of Automatic Partial Orders, Logic Colloquium 2009, Abstracts, p. 79, 2009.

Гаврюшкина Александра Анатольевна

АВТОМАТНЫЕ И ВЫЧИСЛИМЫЕ УПОРЯДОЧИВАЕМЫЕ МНОЖЕСТВА

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

Формат 60 х 84 1/16 Усл. печ. л. 1.0 Тираж 100 экз.

Подписано в печать 30.04.10 Печать офсетная Заказ №108

Редакционно-издательский центр НГУ. 630090, Новосибирск-90, ул.Пирогова 2

Введение

1. Основные понятия

1.1. Разрешимые структуры.

1.2. Некоторые сведения из теории конечных автоматов

1.3. Автоматные структуры.

2. Линейные порядки

2.1. Предварительные сведения о линейных порядках.

2.2. Автоматные линейные порядки.

2.3. Разрешимые и автоматные линейные порядки.

2.4. Некоторые примеры автоматных линейных порядков

3. Автоустойчивость

3.1. Для автоматных отношений эквивалентности.

3.2. Для линейных порядков

4. Сложность автоматных частичных порядков

4.1. Сведение модели в конечной предикатной сигнатуре к частичному порядку.

4.2. Сохранение автоматности.

Объектами изучения математики являются модели (структуры) — множества с заданными на них отношениями и операциями. В середине прошлого столетия в работах А. Фрелиха, Д. Шефердсона, А. И. Мальцева, М. О. Рабина, Р. Воота и других появилось понятие вычислимой или конструктивной модели, то есть модели, которая может быть описана алгоритмически. С этого момента в математической логике образовалась новая подобласть — конструктивные модели, активное развитие которой продолжается до сих пор. Класс вычислимых моделей является наиболее общим и довольно сложным, в связи с этим возникло стремление выделить простейший с алгоритмической точки зрения подкласс вычислимых моделей. Одним из предложенных на эту роль классов является класс автоматных структур. Достоинства этого класса заключаются в том, что наиболее естественные проблемы и свойства автоматных моделей являются разрешимыми.

Упоминания такого рода моделей впервые появились в работах Дж. Р. Вюхи и М. О. Рабина [15], [16], [37], [38], которые изучали теорию конечных автоматов и рассматривали представления некоторых структур с помощью автоматов. С появлением в 1995 году статьи А. Нероуда и

Б.Хусаинова [25], в которой было предложено систематическое исследование автоматных структур, последние подверглись интенсивному изучению. К настоящему времени теория автоматных структур представляет одно из основных направлений исследований в области конструктивных моделей.

Под автоматной структурой подразумевается модель в конечной предикатной сигнатуре, основное множество и все отношения которой распознаются конечными автоматами (автоматы, распознающие п-местные отношения, работают синхронно на n-ках слов). Различные типы конечных автоматов, таких как автоматы на конечных словах, автоматы Бюхи, автоматы на деревьях, порождают различные типы автоматных структур. Автоматные структуры всех перечисленных типов обладают рядом разрешимых свойств. Элементарная теория автоматных структур, например, является разрешимой [22, 25, 12].

Класс словесно-автоматных структур, то есть структур в конечной предикатной сигнатуре, распознаваемых автоматами на конечных словах, наиболее простой среди упомянутых, в него попадают лишь счётные модели. Словесно-автоматными структурами, например, являются: (N,+), (Q, <), булева алгебра Вш конечных и коконечных подмножеств натуральных чисел, в то время как такие структуры, как (N, х) [12], (Q,+) [44], безатомная булева алгебра [28], не являются словесно-автоматными.

Класс Бюхи-автоматных структур, где автоматы работают на бесконечных словах, охватывает как счётные так и несчётные структуры, хотя на счётных структурах эти два класса совпадают [10, 11]. В класс древесно-автоматных структур также попадают только счётные модели, однако, он обширнее класса автоматных структур, (N, х) и безатомная булева алгебра, например, являются древесно-автоматными. Интересен также класс Рабин-автоматных структур, распознаваемых конечными автоматами, работающими на бесконечных полных бинарных деревьях. В этой работе мы будем касаться только словесно-автоматных структур, так как они всё ещё остаются слабо изученными, поэтому мы будем использовать везде термин автоматная структура, подразумевая под ним словесно-автоматную структуру.

Основные результаты этой работы касаются наиболее естественных классов структур, таких как линейные порядки, частичные порядки и отношения эквивалентности. В области характеризации типов изоморфизма автоматных моделей из перечисленных классов получены следующие результаты: автоматными ординалами являются в точности те ординалы, которые строго меньше чем [17]; С. Рубин, Ф.Стефан и Б.Хусаинов доказали, что -РС-ранг автоматных линейных порядков и деревьев конечен [29]; в [23, 24, 33] исследованы автоматные вполне упорядочиваемые частичные порядки и показано, что они являются автоматными тогда и только тогда, когда их ранг строго меньше и>ш. В [31] исследованы некоторые теоретико-модельные свойства автоматных представлений плотного линейного порядка, а именно, доказано существование автоматно-однородного представления для (Q, <), то есть любые два одинаково упорядоченных кортежа в этом представлении могут быть переведены один в другой с помощью автоматного изоморфизма, и также было показано, что любой автоматный линейный порядок автоматно вкладывается в подходящее автоматное представление плотного порядка. Мы показали, что любой автоматный линейный порядок формульно определим в подходящем автоматном линейном порядке ранга 1.

Известно, что вычислимые модели определимы формулами в языке логики первого порядка в (N, +, х). Аналогичное утверждение верно для автоматных структур, то есть любая автоматная структура определима в A/fc = (N, +, где |к — двухместное отношение и х\кУ, если у является степенью к и х делится на у (см. [12, 41]). Пусть к > 1 и Е^. = {0,1,., к— 1}, рассмотрим структуру Wk = (S^, (cra)^6Sfc, eZ2), где сга(го) = wa, х < у, если х есть префикс у, и el(u,v), если = |г;|. Для всех к > 1, Wk является автоматной и полной, в том смысле, что любая автоматная структура определима в ней (см. [12, 41]).

Как уже было сказано выше, естественные теоретико-модельные свойства для автоматных структур являются разрешимыми. А именно, модели, обладающие автоматным представлением, являются разрешимыми и, более того, разрешимыми в некоторых кванторных расширениях. Рассмотрим квантор Э°°, трактуемый как «существует бесконечно много», и для к,т Е N, 0 < к < т, т > 1, кванторы обозначающие «существует к по модулю т много», тогда теория первого порядка в языке, расширенном квантором 3°° и кванторами автоматных структур является разрешимой [12, 30, 41]. Мы показали, что класс автоматных линейных порядков не совпадает с классом разрешимых в расширенном квантором 3°° языке линейных порядков.

Так как модель может обладать различными вычислимыми представлениями, то естественным образом возникает вопрос об эквивалентности этих представлений с алгоритмической точки зрения. Исследование этого вопроса было начато А. И. Мальцевым, который заметил, что конечно порождённые алгебраические системы обладают единственным с точностью до вычислимого изоморфизма представлением, то есть все разрешимые свойства в одном представлении остаются разрешимыми в другом. Но уже в [5] было показано, что для бесконечномерного векторного пространства над полем рациональных чисел можно построить два различных вычислимых представления, таких, что в одном проблема линейной зависимости векторов разрешима, а в другом нет. Таким образом, различные вычислимые представления одной модели могут обладать различными алгоритмическими свойствами. Модели, любые два вычислимых представления которых вычислимо изоморфны, были названы автоустойчивыми (вычислимо категоричными), а вычислимые представления, между которыми существует вычислимый изоморфизм, автоэквивалентными. Исследование автоустойчивости моделей и более общего понятия алгоритмической размерности моделей продолжили такие математики, как С. С. Гончаров, А. Т. Нуртазин, Дж. Б. Реммел, Б. Хусаинов, Р. Шор и другие.

В диссертации поднимается вопрос об автоустойчивости моделей в классе автоматных представлений. Естественней было бы называть автоэквивалентными автоматные представления, между которыми существует автоматный изоморфизм, но в таком случае каждая бесконечная модель имеет счётное число не автоматно изоморфных автоматных представлений [25]. Таким образом, здесь мы будем называть модель автоустойчивой в классе автоматных представлений, если любые два её автоматных представления вычислимо изоморфны. Нас интересует в каких моделях разрешимые свойства сохраняются при переходе от одного автоматного представления к другому.

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

Так как автоматные модели являются разрешимыми, то представляется интересным исследовать связь автоустойчивости в классе разрешимых представлений с автоустойчивостью в классе автоматных представлений. Пусть А — класс автоматных линейных порядков, АА — класс автоустойчивых в классе автоматных представлений линейных порядков, АЪ — класс автоустойчивых в классе разрешимых представлений линейных порядков. Очевидно, что АТ>Г\А С АЪ. Ввиду разрешимости автоматных структур АЪ П А С АА, несложно показать, что АТ> П А не пусто, как минимум там содержатся все конечные линейные порядки. Мы показали, что существует линейный порядок L\ 6 АА, такой, что С\ ^ АЪ, и линейный порядок £2 £ АХ), такой, что Hi А. Тем самым показано, что включения AT) П А С АЪ и АЪ П А с АА строгие.

Другое определение эквивалентных автоматных представлений было рассмотрено в диссертации В.Барани [10], представления являются эквивалентными, если при переходе от одного представления к другому сохраняются автоматные (регулярные) свойства. Там же показано, что если модель обладает единственным с точностью до описанной эквивалентности представлением, то она является полной. Примером, автоматной структуры обладающей «единственным» автоматным представлением служит полная модель Wk- Кроме того, в [10, 41] исследуется, связанное с понятием автоустойчивости, понятие внутренней регулярности отношения, то есть осуществляется поиск условия, гарантирующего регулярность отношения во всех автоматных представлениях.

Исследование автоустойчивости в классе автоматных представлений тесно связано с описанием типов изоморфизма для автоматных структур. Для некоторых классов структур описание было найдено. Как уже говорилось выше, ординалы, обладающие автоматными представлениями, описаны полностью. Бесконечные автоматные булевы алгебры, как показано в [28], — это в точности конечные декартовы произведения булевой алгебры Вш. Конечно порождённые группы описаны в [36] и являются автоматными тогда и только тогда, когда содержат абелеву подгруппу конечного индекса .

Однако в общем случае возможность хорошего описания типов изоморфизма автоматных структур не представляется. Мерой сложности типа изоморфизма модели является ее ранг Скотта. М. Минее и Б.Хусаиновым [23, 24, 33] было показано, что для любого ординала а < u>fK 4- 1 существует автоматная структура с рангом Скотта равным а, что в месте с тем фактом, что ранг Скотта вычислимой модели не превосходит + 1 (см. [9]) говорит о том, что типы изоморфизма автоматных структур максимально сложны. Таким образом, задача сводится к описанию типов изоморфизма для различных подклассов автоматных структур. Здесь мы покажем, что автоматные частичные порядки также могут обладать сколь угодно большим рангом Скотта.

Проблема изоморфизма для класса всех автоматаных структру является Ej-полной [28, 41]. Однако для некоторых подклассов автоматных структур, например, ординалов и булевых алгебр является разрешимой (см. [41]). Недавним, еще не опубликованным, результатом Д. Куске, М. Лори и Дж. Лю является П?-полнота проблемы изоморфизма для автоматных отношений эквивалентности и оценка сложности проблемы изоморфизма для автоматных линейных порядков как неарифметической. В этой работе приведены некоторые примеры автоматных линейный порядков, наталкивающие на мысль о том, что автоустойчивость для линейных порядков высоких рангов не может быть получена.

В работе А. Нероуда и Б.Хусаинова [27] приведены открытые вопросы и направления для дальнейших исследований в теории автоматных структур. Для случая словесно-автоматных структур сделан обзор в статье С. Рубина [42].

1. С. С. Гончаров. Сильная конструктивизируемость однородных моделей. Алгебра и логика, том 17(4), стр. 363-388, 1978.

2. С. С. Гончаров. Проблема числа неавтоэквивалентных конструкти-визаций. Алгебра и логика, том 19(6), стр. 23-44, 1980.

3. С.С.Гончаров, Ю.Л.Ершов. Конструктивные модели. Новосибирск, Научная книга, 1999.

4. Г. Кейслер, Ч. Ч. Чен. Теория моделей. Москва, Мир, 1977.

5. А. И. Мальцев. О рекурсивных абелевых группах. Доклады АН СССР, 146(5), стр. 1009-1012, 1962.

6. А. Т. Нуртазин. Сильные и слабые конструктивизации и вычислимые семейства. Алгебра и логика, том 13(3), стр. 311-323, 1974.

7. М. Г. Перетятькин. Критерий сильной конструктивизируемости однородной модели. Алгебра и логика, том 17(4), стр. 436-454, 1978.

8. Б. А. Трахтенброт, Я. М. Барздинь. Конечные автоматы (поведение и синтез). Москва, Наука, 1970.

9. С. J. Ash, J. F. Knight. Computable Structures and the Hyperarithmetical Hierarchy. Studies in Logic and the Foundations of Mathematics, vol. 144, 2000.

10. V. Bar&ny. Automatic Presentations of Infinite Structures. PhD Thesis, RWTH Aachen, 2007.

11. V. Вагйпу, L. Kaiser, S.Rubin. Cardinality and counting quantifiers on ы-automatic structures. Manuscript, 2007.

12. A. Blumensath. Automatic Structures. Diploma thesis. RWTH Aachen, 1999.

13. A. Blumensath, E. Gradel. Automatic structures. In 15th Symposium on Logic in Computer Science (LICS), pp. 51-62, 2000.

14. A. Blumensath, E. Gradel. Finite presentations of infinite structures: Automata and interpretations. Theory of Computing Systems, 37:641674, 2004

15. J. R. Biichi. On a decision method in restricted second order arithmetic. Logic, Methodology and Philosophy of Science (Proc. 1960 International Congress), pp. 1-11, 1962.

16. J. R. Biichi, L. H. Landweber. Definability in the monadic second-order theory of successor. Journal of Symbolic Logic, 34(2):166-170, 1969.

17. C. Delhomme. Non-automaticity of 2001, unpublished.

18. R. G. Downey. Computability Theory and Linear Orderings. Handbook of Recursive Mathematics, vol. 2, chapter 14, pp. 823—976, Studies in Logic and the Foundations of Mathematics, vol. 139, 1998.

19. С. C. Elgot and J. E. Mezei. On relations defined by generalized finite automata, IBM J. Res. Develop., 9, pp. 47-68, 1965.

20. S. S. Goncharov. Autostable Models and Algorithmic Dimensions. Handbook of Recursive Mathematics, vol. 1, chapter 6, pp. 261-287, Studies in Logic and the Foundations of Mathematics, vol. 138, 1998.

21. S. S. Goncharov. Isomorphism and Definable Relations on Computable Models. Lecture Notes in Logic (Logic Colloquium '05), 28, pp. 26-45, 2006.

22. B. R. Hodgson, Th£ories decidables par automate fini. PhD Thesis, University of Montreal, 1976.

23. B. Khoussainov, M. Minnes. Model Theoretic Complexity of Automatic Structures. Lecture Notes in Computer Science, vol. 4978, pp. 514-525, 2008.

24. B. Khoussainov, M. Minnes. Model Theoretic Complexity of Automatic Structures. Annals of Pure and Applied Logic, vol. 161, pp. 416-426, 2009.

25. B. Khoussainov, A. Nerode. Automatic presentations of structures. Lecture Notes in Computer Science, 960:367-392, 1995.

26. В. Khoussainov, A. Nerode. Automata Theory and Its Applications. Progress in Computer Science and Applied Logic. Burkhauser, 2001.

27. B. Khoussainov, A. Nerode. Open Questions in the Theory of Automatic Structures. Bulletin of EATCS, 94, pp. 181-204, 2008.

28. B. Khoussainov, A. Nies, S. Rubin, and F. Stephan. Automatic structures: Richness and limitations. Proceedings of 19th IEEE Symposium on Logic in Computer Science, pp. 44-53, 2004.

29. B. Khoussainov, S. Rubin, F. Stephan. Automatic Linear Orders and Trees. ACM Transactions on Computational Logic, 6(4), pp. 675-700, 2005.

30. B. Khoussainov, S. Rubin, F. Stephan. Definability and Regularity in automatic structures. In ST ACS 2004, LNSC vol. 2996, pp. 440-451, 2004.

31. D.Kuske. Is Cantor's Theorem Automatic? Proceedings of the 10th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), 2850, pp. 332-345, 2003.

32. С. H. Langford. Theorems on deducibility. Annals of Mathematics, ser. 2, vol. 28, pp. 459-471, 1927.

33. M. Minnes PhD Thesis, Cornell University, 2008.

34. M. Moses. Recursive Properties of Isomorphism Types. PhD Thesis, Monash University, Clayton, Victoria, Australia, 1983.

35. M. Moses. Recursive Linear Orderings with Recursive Successivities. Annals of Pure and Appleing Logic, 27, pp. 253-264, 1984.

36. G. Oliver and R. Thomas. Automatic presentations of finitely generated groups. Proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, LNCS, vol. 3404, pp. 693-704, 2005.

37. M. O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1-35, 1969.

38. M. O. Rabin, D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3:114-125, 1959.

39. J. B. Remmel. Recursively Categorical Linear Orderings. Proceedings of American Mathematical Society, 83, pp. 387-391, 1981

40. J. G. Rosenstein. Linear Orderings. Academic Press, 1982.

41. S.Rubin. Automatic Structures. PhD Thesis, The University of Auckland, 2004.

42. S. Rubin. Automata presenting structures: A survey of the finite string case. The Bulletin of Symbolic Logic, vol. 14, issue 2, pp. 169-200, 2008.

43. A. Szilard, S. Yu, K. Zhang and J. Shallit. Characterizing regular languages with polynomial densities. Lecture Notes in Computer Science (Mathematical Foundations of Computer Science 1992, 17th International Symposium), vol. 629, pp. 494—503, 1992.

44. Т. Tsankov. The additive group of rationals does not have an automatic presentation. http://arxiv.org/abs/0905.1505Работы автора по теме диссертации

45. А. А. Ревенко. Изоморфизм автоматных представлений полных порядков. Материалы XLIV МНСК, серия Математика, стр. 79, 2006.

46. A. Revenko. Automatic linear orders, Logic Colloquium 2007, Book of Abstracts, p. 68, 2007.

47. А. А. Ревенко. Автоустойчивость автоматных представлений ординалов и линейных порядков низкого ранга. Вестник НГУ, серия: Математика, механика, информатика, том 8, вып. 4, стр. 76-88, 2008.

48. A. Revenko. The Complexity of Automatic Partial Orders, Logic Colloquium 2009, Abstracts, p. 79, 2009.

49. А. А. Гаврюшкина. Ранг Скотта автоматных частичных порядков. Вестник НГУ, серия: Математика, механика, информатика, том 10, вып. 2, стр. 37-44, 2010.

50. А. А. Гаврюшкина. Об автоматных и разрешимых линейных порядках. Сибирские электронные математические известия, http://semr.math.nsc.ru, том 7, стр. 100-110, 2010.