Аннотация:
В работе изучаются вопросы выразимости и разрешимости для элементарных теорий, получаемых расширением арифметики порядка и арфиметики сложения натуральных чисел. Получены результаты о разрешимости и неразрешимости элементарных теорий конкретных структур вида ⟨N;+,P⟩, где P – фиксированный одноместный предикат, и о классе множеств, определимых в теории T⟨N;+,λx,∃y(x=dy)⟩.
Библиография: 6 названий.
Образец цитирования:
А. Л. Семёнов, “О некоторых расширениях арифметики сложения натуральных чисел”, Изв. АН СССР. Сер. матем., 43:5 (1979), 1175–1195; Math. USSR-Izv., 15:2 (1980), 401–418
Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, James Worrell, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024, 1
Mikhail R. Starchak, Lecture Notes in Computer Science, 14773, Twenty Years of Theoretical and Practical Synergies, 2024, 218
V. V. Verbovskiy, A. D. Yershigeshova, “On o-Stable Expansions of \boldsymbol{(\mathbb{Z},<,+)}”, Lobachevskii J Math, 44:12 (2023), 5485
Alexei Semenov, Sergei Soprunov, “Automorphisms and Definability (of Reducts) for Upward Complete Structures”, Mathematics, 10:20 (2022), 3748
А. Л. Семенов, С. Ф. Сопрунов, “Решетка определимости. Источники и направления исследований”, Чебышевский сб., 22:1 (2021), 304–327; A. L. Semenov, S. F. Soprunov, “The lattice of definability. Origins and directions of research”, Doklady Mathematics (Supplementary issues), 106:2 (2022), 288–298
Gabriel Conant, “Multiplicative structure in stable expansions of the group of integers”, Illinois J. Math., 62:1-4 (2018)
Alexei Semenov, Sergey Soprunov, Vladimir Uspensky, Lecture Notes in Computer Science, 8476, Computer Science - Theory and Applications, 2014, 23
Ю. Л. Притыкин, “Почти периодичность, конечно-автоматные преобразования и вопросы эффективности”, Изв. вузов. Матем., 2010, № 1, 74–87; Yu. L. Pritykin, “Almost periodicity, finite automata mappings, and related effectiveness issues”, Russian Math. (Iz. VUZ), 54:1 (2010), 59–69
А. С. Снятков, “Разрешимость теории \mathrm{Th}(\omega,0,1,<,+,f_0,\dots,f_n)”, Модел. и анализ информ. систем, 17:3 (2010), 72–90
Ан. А. Мучник, Ю. Л. Притыкин, А. Л. Семенов, “Последовательности, близкие к периодическим”, УМН, 64:5(389) (2009), 21–96; An. A. Muchnik, Yu. L. Pritykin, A. L. Semenov, “Sequences close to periodic”, Russian Math. Surveys, 64:5 (2009), 805–871
Yuri Pritykin, Lecture Notes in Computer Science, 4588, Developments in Language Theory, 2007, 361
С. М. Дудаков, “Трансляционный результат для расширений арифметики Пресбургера одноместной функцией, согласованной со сложением”, Матем. заметки, 76:3 (2004), 362–371; S. M. Dudakov, “Collapse Result for Extensions of the Presburger Arithmetic by a Unary Function Compatible with Addition”, Math. Notes, 76:3 (2004), 339–347
Pure and Applied Mathematics, 141, Infinite Words - Automata, Semigroups, Logic and Games, 2004, 499
William Gasarch, G.R.. Hird, “Automata techniques for query inference machines”, Annals of Pure and Applied Logic, 117:1-3 (2002), 169
Ivan Korec, “A list of arithmetical structures complete with respect to the first-order definability”, Theoretical Computer Science, 257:1-2 (2001), 115
Jean-Eric Pin, “Logic, semigroups and automata on words”, Ann Maths Artificial Intell, 16:1 (1996), 343
Christian Michaux, Roger Villemaire, “Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems”, Annals of Pure and Applied Logic, 77:3 (1996), 251
Christian Michaux, Roger Villemaire, Lecture Notes in Computer Science, 700, Automata, Languages and Programming, 1993, 325
Roger Villemaire, “The theory of is undecidable”, Theoretical Computer Science, 106:2 (1992), 337
Цитирование в формате AMSBIB
Обратная связь: