|
This article is cited in 11 scientific papers (total in 11 papers)
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
Received: 10.01.1979
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}
Linking options:
http://mi.mathnet.ru/eng/izv1752 http://mi.mathnet.ru/eng/izv/v43/i5/p1175
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:
-
A. L. Semenov, “Logical theories of one-place functions on the set of natural numbers”, Math. USSR-Izv., 22:3 (1984), 587–618
 -
Roger Villemaire, “The theory of is undecidable”, Theoretical Computer Science, 106:2 (1992), 337
-
Jean-Eric Pin, “Logic, semigroups and automata on words”, Ann Maths Artificial Intell, 16:1 (1996), 343
-
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
-
Arnaud Maes, “Morphisms and almost-periodicity”, Discrete Applied Mathematics, 86:2-3 (1998), 233
-
Ivan Korec, “A list of arithmetical structures complete with respect to the first-order definability”, Theoretical Computer Science, 257:1-2 (2001), 115
-
William Gasarch, G.R.. Hird, “Automata techniques for query inference machines”, Annals of Pure and Applied Logic, 117:1-3 (2002), 169
-
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
 -
An. A. Muchnik, Yu. L. Pritykin, A. L. Semenov, “Sequences close to periodic”, Russian Math. Surveys, 64:5 (2009), 805–871
 -
Yu. L. Pritykin, “Almost periodicity, finite automata mappings, and related effectiveness issues”, Russian Math. (Iz. VUZ), 54:1 (2010), 59–69
-
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 |
|
Terms of Use