Автоморфизмы автоматных структур

На сегодняшний момент получила широкое распространение теория конструктивных моделей (см. книги С. С. Гончарова, Ю. Л. Ершова [1], Ю. Л. Ершова [4]), появившаяся на стыке теории моделей (см. книгу Г. Кейслера, Ч. Ч. Чэна [6], Дж.Е. Сакса [9]) и теории вычислимости (см. монографию X. Роджерса [8]), изучающая свойства объектов, вычисляемых произвольными алгоритмами (машинами Тьюринга). В связи с резким развитием вычислительной техники появилась потребность в изучении не каких-то абстрактных вычислимых объектов, а вполне конкретных, вычисляемых за определённое время, т. е. надо было каким то образом сделать ограничение на вычисляющий алгоритм (вы-числяющеую машину), чтобы вычисляемый объект обладал достачно хорошими свойствами.

Появился ряд различных определений: структуры, вычислимые за полиномиальное время, вычислимые на машинах Тьюринга с ограниченной лентой и т. д. В частности в 1995 году в работе Б. Хусаинова и А. Нероуда [14] появилось понятие автоматной структуры, т. е. структуры, вычислимой с помощью конечного автомата. Напомним это определение.

Пусть, А обозначает пустое слово. Пусть? — некоторый конечный алфавит. Тогда ?* будет обзначать множество всех слов над этим алфавитом, а ?+ будет обозначать Е* {Л}.

Определение 1 Пусть Е — некоторый конечный алфавит. Обозначим через ?<> алфавит £и{0}, где 0 ^ Е. Тогда конволюцией кортео/са (wi, ., шп) € (?*)" назовём кортеж (uii, 6 (??>)", полученный добавлением наименьшего числа символов ф к правым концам 1 < г < п, так, чтобы все получившиеся слова имели одинаковую длину. Конволюцией отношения R С (Е*)п назовём отношение R^ С (Е^)п, сформированного как множество конволюций всех кортежей в R.

Определение 2 Будем говорить, что отношение R С (?*)" распознаваемо конечным автоматом, если его конволюция R? распознаваема конечным автоматом над алфавитом (Е^)71.

Определение 3 Будем говорить, что структура автоматна над Е, если её носитель, А С ?*, и все отношения Rf С (?*)" ' распознаваемы конечными автоматами. Будем говорить, что структура автоматна, если она автоматна над некоторым алфавитом. Если существует изоморфизм между некоторой структурой В и автоматной структурой А, тогда В называется автоматно представимой (над Е), и структура, А называется автоматной копией структуры В, а изоморфизм называется автоматным представлением структуры В.

Эти объекты сразу же привлекли внимание исследователей, т.к. с ними было довольно просто работать, кроме того автоматные модели, как было показано в работе Е. Грёделя и А. Блумензаца[12], обладали разрешимой теорией, а именно была доказана следующая теорема:

Теорема 1 ([12]) Для любой автоматной структуры А, множество всех FO (3-предложений, истинных в структуре А, разрешимо, где F0(3°°) язык первого порядка, обогащенный квантором 3°° (существует бесконечно много).

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

Замечание 1 Любые формульные отношения языка FO (3°°) на автоматной структуре являются автоматными.

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

Wk = (e*,(ffe)a6e,^p, eo, где? = {О,., А- — 1}, бинарное отношение аа выполняется на парах (w, wa), бинарное отношение -<�р есть отношение приставки и бинарное отношение el выполняется на словах равной длины. В работе А. Блумензаца [11] появилась характеризация автоматных структур в терминах этих полных структур. Автоматные модели это в точности те модели, которые относительно элементарно определимы в W* для к > 2.

Естественный вопрос, возникающий при задании бесконечного объекта конечным, это по двум данным конечным объектам, задающим разные бесконечные, понять изоморфны ли эти бесконечные объекты. Эта проблема называется проблемой изоморфизма. Для автоматных структур сложность проблемы изоморфизма была вычислена в совместной работе Б. Хусаинова, С. Рубина, А. Ниса и Ф. Штефана [19], и оказалась, несмотря на всю простоту автоматных моделей, максимально сложной, а именно £}-полной.

Также естественным вопросом является характеризация различных классов автоматных структур. В этом направлении было получено несколько интересных результатов. Г. Оливером и P.M. Томасом в [22] полностью описаны конеч-нопорождённые автоматные группы, это в точности почти абелевы группы. Б. Хусаиновым, А. Нисом, С. Рубиным, Ф. Штефаном в [19] описаны автоматные булевы алгебры, это все конечные и алгебры вида Ъихп, п € и. Там же описаны автоматные кольца целостности, это в точности все конечные. В [13] Ц. Делхом, В. Горанко, Т. Кнапик описали все автоматные ординалы, это все ординалы вида иin, n < ш, основываясь на этой работе Б. Хусаинов, С. Рубин, Ф.

Штефан в [17] получили важное свойство автоматных линейных порядков: любой автоматный линейный порядок имеет конечный ранг. Проблема описания автоматных линейных порядков пока открыта. В совместной работе Б. Хусаи-нова, С. Рубина и X. Ишихары [16] была доказана теорема, в некотором смысле сводящая изучение автоматных структур к изучению автоматных графов. По любой автоматной структуре Л эффективно строится автоматный граф С {Л), так что многие важные свойства со структур переносятся на графы например, если Л = Л2, то С (А) = С (Лг). В частности из этого следует, что для класса автоматных графов проблема изоморфизма £{-полна.

Следует также отметить работу Д. Куске [20], в которой он доказывает некоторый автоматный аналог известной теоремы Кантора, говорящей о том, что любой счётный линейный порядок вкладывается в (Q, <). Он показывает, что для любого автоматного порядка L существует автоматное представление ? рациональных чисел, такое что L автоматно вкладывается в Q^. Пока неизвестно, существует ли автоматное представление Q рациональных чисел, такое что любой автоматный порядок в него автоматно вкладывается. Кроме того он показывает автоматную однородность автоматной модели ({0,1}*, z

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

Определение сложности индексных множеств различных свойств автоматных структур важно с нескольких точек зрения :

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

2. Сложность определения по конечному заданию бесконечного объекта каких либо свойств этого объекта — задача сама по себе естественная и представляет особый интерес.

В работе получены следующие основные результаты:

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

2. Получены точные оценки ряда индексных множеств теоретико-модельных свойств автоматных моделей (однородности, универсальности и др.)

3. Доказана неразрешимость групп автоматных автоморфизмов некоторых автоматных моделей.

4. Построены примеры теорий, автоматный спектр которых может принимать все значения кроме 2. Для 2 вопрос построения такой теории, пока остаётся открытым.

В работе используются методы построения автоматных моделей, развитые в работах [20, 23, 19, 1С, 11, 17].

Результаты работы были представлены на XLI международной научной студенческой конференции, на XXVI Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова, на IX азиатской логической конференции, на XLIV международной научной студенческой конференции. А также на семинарах «Автоматы и сложность вычислений» и «Конструктивные модели» Новосибирского государственного университета.

Все основные результаты диссертации опубликованы в работах [25], [26], [27], [28], [29], [30], [31]

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

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

содержит 30 наименований. Объём диссертации составляет 63 страницы.

1. Blumensath A., Gradel^.Automatic structures // Proc. 15th IEEE Symp. on Logic in Computer Science. Santa Barbara (California), 2000. P. 51−62.

2. С. Delhomme, V. Goranko, Т. Knapik Automatic linear orderings. Not published, 2003.

3. B. Khoussainov, A. N erode Automatic presentations of structures // Lecture notes in computer science, 960:367−392, 1995.

4. Khoussainov В., Nerode A. Automata theory and its applications. 2001. Birkhauser, Boston etc.

5. Khoussainov В., Rubin S., Ishihara H. On isomorphism invariants of some automatic structures // Proc. 17th IEEE Symp. on Logic in Computer Science, 2002, Copenhagen (Denmark), pp. 43−53.

6. Khoussainov В., S. Rubin, F. Stephan Automatic linear orders and trees // 2003a. CDMTSC technical report 208, department of computer science, university of Auckland.

7. Khoussainov В., S. Rubin, F. Stephan Definability and regularity in automatic presentations of subsystems of arithmetic // 2003b. CDMTSC technical report 209, department of computer science, university of Auckland.

8. Khoussainov В., Nies A., Rubin S., Stephan F. Automatic structures: richness and limitations // Proc. 19th IEEE Symp. on Logic in Computer Science, 2004, Turku (Finland), pp 44−53.

9. D. Kuske. Is Cantor’s theorem automatic? // Proceedings of the 10th International Conferenca on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR). 2850:332−345, 2003.

10. A.S. Morozov, J.K. Truss. On computable automorphism of the rational numbers // The Journal of symbolic Logic, v.66, № 3, pp 1458 1469, 2001.

11. G. Oliver and R.M. Thomas. Automatic Presentations of Finitely Generated Groups, V. Diekert and B. Durand (Eds.): STACS '05, Logic Notes in computer science 3404, pp. 693−704, 2005 University of Stuttgart, Germany.

12. S. Rubin. Automata structures. PhD thesis. University of Auckland, 2004.

13. J.K. Truss. On recovering structures from quotients of their automorphism groups // Ordered groups and infinite permutations groups (W. Carles Holland, editor), Kluwer, 1996, pp 63−95.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

14. Н. С. Винокуров. Сложность некоторых естественных проблем в автоматных структурах // Сибирский математический журнал, т.46, № 1, стр. 71 -78, 2005.

15. Н. С. Винокуров. Индексные множества классов автоматных структур // Сибирский математический журнал, принята к печати.

16. Н. С. Винокуров. Группы автоматных автоморфизмов некоторых автоматных структур // Сибирские электронные математические известия, http://semr.math.nsc.ru, т. 3, стр. 145−152, 2006.

17. Н. С. Винокуров. Индексные множества классов автоматных структур // Сибирские электронные математические известия, http://semr.math.nsc.ru, т. З, стр. 153−154, 2006.

18. Н. С. Винокуров. Об автоматных структурах // Материалы XLI международной научной студенческой конференции «Студент и научно технический прогресс», Новосибирск, 2003, стр 3.