ON INTERPRETATIONS OF PRESBURGER ARITHMETIC IN BÜCHI ARITHMETICS

封面

如何引用文章

全文:

详细

Büchi arithmetics BAn, \(n \geqslant 2\), are extensions of Presburger arithmetic with an unary functional symbol \({{V}_{n}}(x)\) denoting the largest power of n that divides x. Definability of a set in BAn is equivalent to its recognizability by a finite automaton receiving numbers in their n-ary expansion. We consider the interpretations of Presburger Arithmetic in the standard model of BAn and show that each such interpretation has an internal model isomorphic to the standard one. This answers a question by A. Visser on the interpretations of certain weak arithmetical theories in themselves.

作者简介

A. Zapryagaev

National Research University “Higher School of Economics”

编辑信件的主要联系方式.
Email: azapryagaev@hse.ru
Russian Federation, Moscow

参考

  1. Büchi J.R. Weak second-order arithmetic and finite automata // Mathematical Logic Quarterly. 1960. V. 6. № 1–6. P. 66–92. https://doi.org/10.1002/malq.19600060105
  2. Bruyère V. Entiers et automates finis // Mémoire de fin d’études, Université de Mons (1985).
  3. Bruyère V. et al. Logic and p-recognizable sets of integers // Bulletin of the Belgian Mathematical Society Simon Stevin. 1994. V. 1. № 2. P. 191–238. https://doi.org/10.36045/bbms/1103408547
  4. Cobham A. On the base-dependence of sets of numbers recognizable by finite automata // Mathematical systems theory. 1969. V. 3. № 2. P. 186–192. https://doi.org/10.1007/BF01746527
  5. Семёнов А.Л. Пресбургеровость предикатов, регулярных в двух системах счисления // Сибирский математический журнал. 1977. Т. 18. № 2. С. 403–418. https://doi.org/10.1007/BF00967164
  6. Presburger M. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt // Comptes Rendus du I congrès de Mathématiciens des Pays Slaves 92–101, 1929.
  7. Pakhomov F., Zapryagaev A. Multi-dimensional interpretations of Presburger arithmetic in itself // Journal of Logic and Computation. 2020. V. 30. № 8. P. 1681–1693. https://doi.org/10.1093/logcom/exaa050
  8. Tarski A., Mostowski A., Robinson R.M. Undecidable theories. North-Holland, 1953. 98 p.
  9. Braun G., Strüngmann L. Breaking up finite automata presentable torsion-free abelian groups // International Journal of Algebra and Computation. 2011. V. 21. № 08. P. 1463–1472. https://doi.org/10.1142/S0218196711006625

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © А.А. Запрягаев, 2023

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».