Geodesic
On certain extensions of the arithmetic of addition of natural numbers
Izvestiya. Mathematics, Tome 15 (1980) no. 2, pp. 401-418 
A. L. Semenov. On certain extensions of the arithmetic of addition of natural numbers. Izvestiya. Mathematics, Tome 15 (1980) no. 2, pp. 401-418. http://geodesic.mathdoc.fr/item/IM2_1980_15_2_a8/
@article{IM2_1980_15_2_a8,
     author = {A. L. Semenov},
     title = {On certain extensions of the arithmetic of addition of natural numbers},
     journal = {Izvestiya. Mathematics},
     pages = {401--418},
     year = {1980},
     volume = {15},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_1980_15_2_a8/}
}
TY  - JOUR
AU  - A. L. Semenov
TI  - On certain extensions of the arithmetic of addition of natural numbers
JO  - Izvestiya. Mathematics
PY  - 1980
SP  - 401
EP  - 418
VL  - 15
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/IM2_1980_15_2_a8/
LA  - en
ID  - IM2_1980_15_2_a8
ER  - 
%0 Journal Article
%A A. L. Semenov
%T On certain extensions of the arithmetic of addition of natural numbers
%J Izvestiya. Mathematics
%D 1980
%P 401-418
%V 15
%N 2
%U http://geodesic.mathdoc.fr/item/IM2_1980_15_2_a8/
%G en
%F IM2_1980_15_2_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper the problems of expressibility and decidability are studied for elementary theories obtained by extending the arithmetic of order and the arithmetic of addition of natural numbers. Results are obtained on the decidability and undecidability of elementary theories of concrete structures of the form $\langle\mathbf N;+,P\rangle$, where $P$ is a fixed monadic predicate, as well as results on the class of sets definable in the theory $\mathbf T\langle\mathbf N;+,\lambda x,\exists\,y\,(x=d^y)\rangle$. Bibliography: 6 titles.

[1] Jacobs K., “Turing-Maschinen und zufällige $0-1$-Folgen”, Selecta Mathematica, II, Springer, Berlin, 1970, 141–167 ; K. Yakobs, “Mashinno-porozhdennye $0,-1$-posledovatelnosti”, Mashiny Tyuringa i rekursivnye funktsii, Mir, M., 1972, 216–247 | MR | MR

[2] Büchi J. R., “Weak second-order arithmetic and finite automata”, Z. Math. Logik und Grundl. Math., 6:1 (1960), 66–92 ; D. R. Byukhi, “Slabaya arifmetika vtorogo poryadka i konechnye avtomaty”, Kibern. sb., 8, Mir, M., 1964, 42–77 | DOI | MR

[3] McNaughton R., “Referat [2]”, J. Symbolic Logic, 28:1 (1963), 100–103 | DOI | MR

[4] Tijdeman R., “On integers with many small prime factors”, Compositio Math., 26:3 (1973), 319–330 | MR | Zbl

[5] Elgot C. C., Rabin M. O., “Decidability and undecidability of extentions of second (first) order theory of (generalized) successor”, J. Symbolic Logic, 31:2 (1966), 169–181 | DOI | Zbl

[6] Oppen D., “Elementary bounds for Presburger arithmetic”, 5th ACM Symposium on Theory of Computing, 1973, 34–37 | MR | Zbl