Автоматные и вычислимые упорядочиваемые множества

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

Упоминания такого рода моделей впервые появились в работах Дж. Р. Вюхи и М. О. Рабина [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:641 674, 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.