• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Interpretations of presburger arithmetic in itself(
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.
September 9, 2026
Scientists Train Neural Network to Generate Process Plans from 3D Models
Researchers at the HSE FCS AI and Digital Science Institute have developed CAD2TechSpec, a framework that converts 3D models of mechanical parts into machining process plans—step-by-step instructions for machine tools. The solution aims to reduce the time required for the design and preparation of technical process documentation in mechanical engineering, aircraft manufacturing, and other high-tech industries. The study findings have been published in PeerJ Computer Science.
September 7, 2026
Biologists Discover 'Molecular Fingerprint' of Preeclampsia
Researchers at HSE University employed a new method to model hypoxia in placental cells during pregnancies complicated by preeclampsia and identified molecular markers of tissue hypoxia. Since hypoxia is one of the key mechanisms underlying preeclampsia, these findings are important for a more accurate and timely diagnosis of the disease and for the development of effective treatment methods. The paper has been published in Placenta.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Interpretations of presburger arithmetic in itself(

P. 354–367.
Zapryagaev A., Pahomov F.

Presburger arithmetic PrA is the true theory of natural numbers with addition. We study interpretations of PrA in itself. We prove that all one-dimensional self-interpretations are definably isomorphic to the identity self-interpretation. In order to prove the results we show that all linear orders that are interpretable in (N,+) are scattered orders with the finite Hausdorff rank and that the ranks are bounded in terms of the dimension of the respective interpretations. From our result about self-interpretations of PrA it follows that PrA isn’t one-dimensionally interpretable in any of its finite subtheories. We note that the latter was conjectured by A. Visser.

Language: English
DOI
Text on another site
Keywords: Presburger ArithmeticInterpretations

In book

International Symposium on Logical Foundations of Computer Science, LFCS 2018
Vol. 10703. , Springer, 2018.
Similar publications
Linear orders in Presburger arithmetic
Pahomov F., Zapryagaev A., Logic Journal of the IGPL 2026 Vol. 34 No. 4 Article jzag045
We prove the linear orders first-order definable in the standard model (Z;<,+) of Presburger arithmetic are exactly those that are (Z;<,+)-definably embeddable into the lexicographic ordering on Z^n for some ⁠n. ...
Added: July 16, 2026
Some properties of Büchi Arithmetics
Zapryagaev A., / Series arXiv "math". 2023.
Büchi arithmetics BA_n, n≥2, are extensions of Presburger arithmetic with an unary functional symbol V_n(x) denoting the largest power of n that divides x. A rank of a linear order is the minimal number of condensations required to reach a finite order. We show that linear orders of arbitrarily large finite rank can be interpreted in BA_n. We also prove that the extension ...
Added: October 25, 2023
Об интерпретациях арифметики Пресбургера в арифметиках Бюхи
Zapryagaev A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2023 Т. 510 С. 3–7
Büchi arithmetics BAn, , are extensions of Presburger arithmetic with an unary functional symbol 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 ...
Added: July 27, 2023
К вопросу о применении гуманитарно-научных методов в процессе анализа историко-правовых источников
Zorile Dorina D., Тенденции развития науки и образования 2021 Т. 75 № 3 С. 37–42
The article deals with the involving into the history of law the methodology of a new branch - jurislinguistics and of a traditional one - comparativistics, wich supply methdological approaches to the historical investigations. The features of its implementation in order to acheave a correct translation of foreign legal texsts and interpretation of their terminology are ...
Added: December 4, 2022
Presburger arithmetic and Visser's conjecture
Zapryagaev A., , in: Logical Perspectives 2021 Workshop.: M.: [б.и.], 2021. Ch. 18.
Presburger Arithmetic the true theory of natural numbers with addition. We show that the interpretations of Presburger Arithmetic in itself are definably isomorphic to the trivial one, confirming the conjecture of A. Visser. To prove that, we develop a characterization of linear orderings interpretable in (N, +). We show that all interpretable linear orderings can ...
Added: December 14, 2021
Классификация линейных порядков, интерпретируемых многомерно в арифметике Пресбургера
Zapryagaev A., В кн.: Двенадцатые Смирновские чтения: материалы Международной научной конференции, Москва, 24–26 июня 2021 г.: М.: Русское общество истории и философии науки, 2021. С. 16–18.
Мы рассматриваем многомерные интерпретации линейных порядков в стандартной модели (N, +) арифметики Пресбургера. Устанавливается, что всякий такой порядок переводится определимым изоморфизмом в сужение лексикографического порядка Z 𝑛 на некоторое определимое множество для достаточно большого 𝑛. Это даёт более простое доказательство гипотезы Виссера об определимом изоморфизме тождественной всякой интерпретации самой арифметики Пресбургера в (N, +). ...
Added: June 28, 2021
Multi-dimensional Interpretations of Presburger Arithmetic in Itself
Pahomov F., Zapryagaev A., Journal of Logic and Computation 2020 Vol. 30 No. 8 P. 1681–1693
Presburger arithmetic is the true theory of natural numbers with addition. We study interpretations of Presburger arithmetic in itself. The main result of this paper is that all self-interpretations are definably isomorphic to the trivial one. Here we consider interpretations that might be multi-dimensional. We note that this resolves a conjecture by Visser (1998, An ...
Added: November 12, 2020
Interpretations of Linear Orderings in Presburger Arithmetic
Zapryagaev A., / Series arXiv "math". 2019. No. 1911.07182.
Presburger Arithmetic PrA is the true theory of natural numbers with addition. We consider linear orderings interpretable in Presburger Arithmetic and establish various necessary and sucient conditions for interpretability depending on dimension n of interpretation. We note this problem is relevant to the interpretations of Presburger Arithmetic in itself, as well as the characterization of ...
Added: November 28, 2019
Interpretations of Presburger Arithmetic in Itself
Zapryagaev A., Pahomov F., , in: International Symposium on Logical Foundations of Computer Science, LFCS 2018Vol. 10703.: Springer, 2018. P. 354–367.
Presburger arithmetic PrA is the true theory of natural numbers with addition. We study interpretations of PrA in itself. We prove that all one-dimensional self-interpretations are definably isomorphic to the identity self-interpretation. In order to prove the results we show that all linear orders that are interpretable in (N,+) are scattered orders with the finite Hausdorff rank and that the ranks ...
Added: October 25, 2019
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit