General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Izv. RAN. Ser. Mat.:

Personal entry:
Save password
Forgotten password?

Izv. Akad. Nauk SSSR Ser. Mat., 1983, Volume 47, Issue 3, Pages 623–658 (Mi izv1415)  

This article is cited in 20 scientific papers (total in 20 papers)

Logical theories of one-place functions on the set of natural numbers

A. L. Semenov

Abstract: In this paper the author studies the decision problem for logical languages intended to describe the properties of one-place functions $f$ on the set $\mathbf N$ of natural numbers. For functions $f$ taking a finite number of values a criterion for decidability of the monadic theory of the structure $\langle\mathbf N;\leqslant,f\rangle$ is obtained. For a large class of monotone functions $f$, conditions are found under which the elementary theory of the structure $\langle\mathbf N;\leqslant,f\rangle$ is decidable; corresponding conditions are also found for structures of the form $\langle\mathbf N;+,f\rangle$.
Bibliography: 20 titles.

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

English version:
Mathematics of the USSR-Izvestiya, 1984, 22:3, 587–618

Bibliographic databases:

UDC: 519.9
MSC: Primary 03D05; Secondary 03B25
Received: 29.04.1982

Citation: A. L. Semenov, “Logical theories of one-place functions on the set of natural numbers”, Izv. Akad. Nauk SSSR Ser. Mat., 47:3 (1983), 623–658; Math. USSR-Izv., 22:3 (1984), 587–618

Citation in format AMSBIB
\by A.~L.~Semenov
\paper Logical theories of one-place functions on the set of natural numbers
\jour Izv. Akad. Nauk SSSR Ser. Mat.
\yr 1983
\vol 47
\issue 3
\pages 623--658
\jour Math. USSR-Izv.
\yr 1984
\vol 22
\issue 3
\pages 587--618

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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. A. Tverskoi, “Nonconstructivizable formal arithmetic structures”, Math. USSR-Izv., 30:1 (1988), 103–122  mathnet  crossref  mathscinet  zmath
    2. Kevin J. Compton, C. Ward Henson, “A uniform method for proving lower bounds on the computational complexity of logical theories”, Annals of Pure and Applied Logic, 48:1 (1990), 1  crossref
    3. Pascal Michel, “Complexity of logical theories involving coprimality”, Theoretical Computer Science, 106:2 (1992), 221  crossref
    4. Thanases Pheidas, “Extensions of Hilbert's tenth problem”, J. symb. log, 59:02 (1994), 372  crossref
    5. Patrick Cegielski, Denis Richard, “On arithmetical first-order theories allowing encoding and decoding of lists”, Theoretical Computer Science, 222:1-2 (1999), 55  crossref
    6. Ivan Korec, “A list of arithmetical structures complete with respect to the first-order definability”, Theoretical Computer Science, 257:1-2 (2001), 115  crossref
    7. A. L. Semenov, “Finiteness Conditions for Algebras of Relations”, Proc. Steklov Inst. Math., 242 (2003), 92–96  mathnet  mathscinet  zmath
    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  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    9. An. A. Muchnik, Yu. L. Pritykin, A. L. Semenov, “Sequences close to periodic”, Russian Math. Surveys, 64:5 (2009), 805–871  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    10. FRANCOIS NICOLAS, YURI PRITYKIN, “ON UNIFORMLY RECURRENT MORPHIC SEQUENCES”, Int. J. Found. Comput. Sci, 20:05 (2009), 919  crossref
    11. Yu. L. Pritykin, “Almost periodicity, finite automata mappings, and related effectiveness issues”, Russian Math. (Iz. VUZ), 54:1 (2010), 59–69  mathnet  crossref  mathscinet  zmath
    12. A. S. Snyatkov, “Razreshimost teorii $\mathrm{Th}(\omega,0,1,<,+,f_0,…,f_n)$”, Model. i analiz inform. sistem, 17:3 (2010), 72–90  mathnet  elib
    13. Alla Sirokofskich, “Decidability questions for a ring of Laurent polynomials”, Annals of Pure and Applied Logic, 2011  crossref
    14. Alexis Bès, Alexander Rabinovich, Bruno Courcelle, “Decidable Expansions of Labelled Linear Orderings”, Log.Meth.Comput.Sci, 7:2 (2011)  crossref
    15. M. N. Vyalyi, A. A. Rubtsov, “Algoritmicheskaya razreshimost zadach o povedenii avtomatov na sverkhslovakh”, Diskretn. analiz i issled. oper., 19:2 (2012), 3–18  mathnet  mathscinet
    16. Alexander Rabinovich, “The Church problem for expansions of by unary predicates”, Information and Computation, 2012  crossref
    17. Francesco Alberti, Silvio Ghilardi, Natasha Sharygina, “Decision Procedures for Flat Array Properties”, J Autom Reasoning, 2015  crossref
    18. Alberti F., Ghilardi S., Sharygina N., “A New Acceleration-Based Combination Framework for Array Properties”, Frontiers of Combining Systems, Lecture Notes in Computer Science, 9322, eds. Lutz C., Ranise S., Springer-Verlag Berlin, 2015, 169–185  crossref  mathscinet  zmath  isi  scopus
    19. N. N. Korneeva, “Automata transformations of prefix decidable and decidable by Buchi superwords”, Russian Math. (Iz. VUZ), 60:7 (2016), 47–55  mathnet  crossref  isi
    20. F. A. Dudkin, A. V. Treier, “Zadacha o ryukzake dlya grupp Baumslaga–Solitera”, Sib. zhurn. chist. i prikl. matem., 18:4 (2018), 43–55  mathnet  crossref
  • Известия Академии наук СССР. Серия математическая Izvestiya: Mathematics
    Number of views:
    This page:460
    Full text:157
    First page:1

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020