Аннотация:
Теоретико-числовой предикат называется регулярным в системе счисления с основанием p, если он выразим в теории первого порядка со следующими элементарными предикатами: p-ичная запись числа x оканчивается на данную p-ичную цифру (для всех p-ичных цифр), длины p-ичных записей чисел x и y совпадают, p-ичная запись числа x является началом p-ичной записи числа y. Теоретико-числовой предикат называется пресбургеровым, если он выразим в теории первого порядка сложения натуральных чисел.
В работе доказывается пресбургеровостъ всякого предиката, регулярного в двух системах счисления с мультипликативно независимыми основаниями.
Образец цитирования:
А. Л. Семенов, “Пресбургеровость предикатов, регулярных в двух системах счисления”, Сиб. матем. журн., 18:2 (1977), 403–418; Siberian Math. J., 18:2 (1977), 289–300
А. А. Запрягаев, “Об интерпретациях арифметики Пресбургера в арифметиках Бюхи”, Докл. РАН. Матем., информ., проц. упр., 510 (2023), 3–7; A. A. Zapryagaev, “On interpretations of Presburger arithmetic in Büchi arithmetics”, Dokl. Math., 107:2 (2023), 89–92
А. Л. Семенов, С. Ф. Сопрунов, И. А. Иванов-Погодаев, “Создание новой математики школьниками”, Докл. РАН. Матем., информ., проц. упр., 511 (2023), 138–143; A. L. Semenov, S. F. Soprunov, I. A. Ivanov-Pogodaev, “Creating new mathematics by schoolchildren”, Dokl. Math., 107:Suppl 1 (2023), S132–S136
Sanjay Jain, Xiaodong Jia, Ammar Fathin Sabili, Frank Stephan, “Addition machines, automatic functions and open problems of Floyd and Knuth”, Journal of Computer and System Sciences, 136 (2023), 135
G. P. Amirdjanov, I. B. Gurevich, F. V. Kostyuk, N. S. Kulberg, T. A. Rudchenko, A. L. Semenov, A. N. Sotnikov, Yu. O. Trusova, A. Yu. Uvarov, V. A. Vardanyan, T. V. Yakovleva, V. V. Yashina, A. S. Zakharova, “The Role of the Scientific Council “Cybernetics” of the USSR Academy of Sciences/the Russian Academy of Sciences in the Development of National Cybernetics and Computer Technology”, Pattern Recognit. Image Anal., 33:4 (2023), 988
Seda Albayrak, Jason P. Bell, “Quantitative estimates for the size of an intersection of sparse automatic sets”, Theoretical Computer Science, 977 (2023), 114144
А. Л. Семёнов, С. Ф. Сопрунов, “Решетка определимости (редуктов) для целых чисел с операцией следования”, Изв. РАН. Сер. матем., 85:6 (2021), 245–258; A. L. Semenov, S. F. Soprunov, “Lattice of definability (of reducts) for integers with successor”, Izv. Math., 85:6 (2021), 1257–1269
Thijmen J. P. Krebs, “A More Reasonable Proof of Cobham's Theorem”, Int. J. Found. Comput. Sci., 32:02 (2021), 203
А. Л. Семенов, С. Ф. Сопрунов, “Решетка определимости. Источники и направления исследований”, Чебышевский сб., 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
Ан. А. Мучник, А. Л. Семёнов, “Решетка определимости в порядке рациональных чисел”, Матем. заметки, 108:1 (2020), 102–118; An. A. Muchnik, A. L. Semenov, “Lattice of Definability in the Order of Rational Numbers”, Math. Notes, 108:1 (2020), 94–107
Alexis Bès, Christian Choffrut, Lecture Notes in Computer Science, 12038, Language and Automata Theory and Applications, 2020, 128
Émilie Charlier, Svetlana Puzynina, Élise Vandomme, “Recurrence along directions in multidimensional words”, Discrete Mathematics, 343:10 (2020), 112006
Florent Guepin, Christoph Haase, James Worrell, 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2019, 1
Émilie Charlier, Trends in Mathematics, Sequences, Groups, and Number Theory, 2018, 89
Sanjay Jain, Bakhadyr Khoussainov, Frank Stephan, Dan Teng, Siyuan Zou, “Semiautomatic Structures”, Theory Comput Syst, 61:4 (2017), 1254
Arthur Milchior, Lecture Notes in Computer Science, 10185, Theory and Applications of Models of Computation, 2017, 440
Peter Habermehl, Dietrich Kuske, Lecture Notes in Computer Science, 9034, Foundations of Software Science and Computation Structures, 2015, 375
Alexei Semenov, Sergey Soprunov, Vladimir Uspensky, Lecture Notes in Computer Science, 8476, Computer Science - Theory and Applications, 2014, 23
Bernard Boigelot, “Domain-specific regular acceleration”, Int J Softw Tools Technol Transfer, 14:2 (2012), 193
Bernard Boigelot, Julien Brusten, Jérôme Leroux, Lecture Notes in Computer Science, 5663, Automated Deduction – CADE-22, 2009, 469
Bernard Boigelot, Julien Brusten, “A generalization of Cobham's theorem to automata over real numbers”, Theoretical Computer Science, 410:18 (2009), 1694
Цитирование в формате AMSBIB
Обратная связь: