Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Izv. RAN. Ser. Mat.: Year: Volume: Issue: Page: Find

 Izv. Akad. Nauk SSSR Ser. Mat., 1979, Volume 43, Issue 5, Pages 1175–1195 (Mi izv1752)

On certain extensions of the arithmetic of addition of natural numbers

A. L. Semenov

Abstract: 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.

Full text: PDF file (2342 kB)
References: PDF file   HTML file

English version:
Mathematics of the USSR-Izvestiya, 1980, 15:2, 401–418

Bibliographic databases:

UDC: 519.9
MSC: Primary 03F30; Secondary 03B25, 03C10

Citation: A. L. Semenov, “On certain extensions of the arithmetic of addition of natural numbers”, Izv. Akad. Nauk SSSR Ser. Mat., 43:5 (1979), 1175–1195; Math. USSR-Izv., 15:2 (1980), 401–418

Citation in format AMSBIB
\Bibitem{Sem79} \by A.~L.~Semenov \paper On certain extensions of the arithmetic of addition of natural numbers \jour Izv. Akad. Nauk SSSR Ser. Mat. \yr 1979 \vol 43 \issue 5 \pages 1175--1195 \mathnet{http://mi.mathnet.ru/izv1752} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=552556} \zmath{https://zbmath.org/?q=an:0443.03008|0417.03005} \transl \jour Math. USSR-Izv. \yr 1980 \vol 15 \issue 2 \pages 401--418 \crossref{https://doi.org/10.1070/IM1980v015n02ABEH001252} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1980LD11600009} 

• http://mi.mathnet.ru/eng/izv1752
• http://mi.mathnet.ru/eng/izv/v43/i5/p1175

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. L. Semenov, “Logical theories of one-place functions on the set of natural numbers”, Math. USSR-Izv., 22:3 (1984), 587–618
2. Roger Villemaire, “The theory of is undecidable”, Theoretical Computer Science, 106:2 (1992), 337
3. Jean-Eric Pin, “Logic, semigroups and automata on words”, Ann Maths Artificial Intell, 16:1 (1996), 343
4. 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
5. Arnaud Maes, “Morphisms and almost-periodicity”, Discrete Applied Mathematics, 86:2-3 (1998), 233
6. Ivan Korec, “A list of arithmetical structures complete with respect to the first-order definability”, Theoretical Computer Science, 257:1-2 (2001), 115
7. William Gasarch, G.R.. Hird, “Automata techniques for query inference machines”, Annals of Pure and Applied Logic, 117:1-3 (2002), 169
8. 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
9. An. A. Muchnik, Yu. L. Pritykin, A. L. Semenov, “Sequences close to periodic”, Russian Math. Surveys, 64:5 (2009), 805–871
10. Yu. L. Pritykin, “Almost periodicity, finite automata mappings, and related effectiveness issues”, Russian Math. (Iz. VUZ), 54:1 (2010), 59–69
11. A. S. Snyatkov, “Razreshimost teorii $\mathrm{Th}(\omega,0,1,<,+,f_0,…,f_n)$”, Model. i analiz inform. sistem, 17:3 (2010), 72–90
•  Number of views: This page: 512 Full text: 226 References: 38 First page: 1