{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T07:48:42Z","timestamp":1773820122969,"version":"3.50.1"},"reference-count":117,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,4,1]],"date-time":"2001-04-01T00:00:00Z","timestamp":986083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4490,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2001,4]]},"DOI":"10.1016\/s0304-3975(00)00113-4","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T10:59:17Z","timestamp":1027594757000},"page":"115-151","source":"Crossref","is-referenced-by-count":12,"title":["A list of arithmetical structures complete with respect to the first-order definability"],"prefix":"10.1016","volume":"257","author":[{"given":"Ivan","family":"Korec","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(00)00113-4_BIB1","doi-asserted-by":"crossref","first-page":"239","DOI":"10.2307\/1970573","article-title":"The elementary theory of finite fields","volume":"88","author":"Ax","year":"1968","journal-title":"Ann. Math."},{"issue":"2","key":"10.1016\/S0304-3975(00)00113-4_BIB2","doi-asserted-by":"crossref","first-page":"672","DOI":"10.2307\/2275227","article-title":"Decidability and undecidability of theories with a predicate for the primes","volume":"58","author":"Bateman","year":"1993","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB3","doi-asserted-by":"crossref","first-page":"1280","DOI":"10.2307\/2275643","article-title":"Undecidable extensions of B\u00fcchi arithmetic and Cobham\u2013Semenov theorem","volume":"62","author":"\u00e8s","year":"1997","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB4","unstructured":"A. B\u00e8s, An extension of the Cobham\u2013Sem\u00ebnov theorem, a preprint, 1996, 10pp."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB5","unstructured":"A. B\u00e8s, Probl\u00e8mes de d\u00e9finissabilit\u00e9 arithm\u00e9tique: triagles de Pascal, arithm\u00e9tique de Presburger et arithm\u00e9tique de Skolem, Ph.D. Thesis, Universit\u00e9 Paris VII, 1996."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB6","doi-asserted-by":"crossref","unstructured":"A. B\u00e8s, On Pascal triangles modulo a prime power, Ann. Pure Appl. Logic 89 (1997) 17\u201335, Logic Colloquium\u201994, Clermont-Ferrand.","DOI":"10.1016\/S0168-0072(97)85376-6"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.4064\/fm-156-2-111-129","article-title":"Definability within structures related to Pascal triangles modulo an integer","volume":"156","author":"\u00e8s","year":"1998","journal-title":"Fundam. Math."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB8","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/2586837","article-title":"Undecidable extensions of Skolem arithmetic","volume":"63","author":"B\u00e8s","year":"1998","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB9","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1016\/S1385-7258(53)50042-3","article-title":"On PADOA's method in the theory of definition","volume":"15","author":"Beth","year":"1953","journal-title":"Indagationes Math."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB10","doi-asserted-by":"crossref","unstructured":"M. Boffa, More on an undecidability result of Bateman, Jokusch and Woods, J. Symbolic Logic, to appear.","DOI":"10.2307\/2586585"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB11","unstructured":"B.A. Bondarenko, Generalized Pascal Triangles and Pyramids, their Fractals, Graphs and applications, Fan, Tashkent, 1990 (in Russian)."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB12","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","article-title":"Weak second-order arithmetic and finite automata","volume":"6","author":"B\u00fcchi","year":"1960","journal-title":"Zeitschrift f\u00fcr Math. Logik Grundlagen Math."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB13","unstructured":"J.R. B\u00fcchi, On a decision method in restricted second order arithmetic, Logic, Methodology, and Philosophy of Science, Proc. 1960 Congr., Stanford University Press, California, 1960, pp. 1\u201311."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB14","doi-asserted-by":"crossref","first-page":"166","DOI":"10.2307\/2271090","article-title":"Definability in the monadic second-order theory of successor","volume":"34","author":"B\u00fcchi","year":"1969","journal-title":"J. for Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB15","first-page":"44","article-title":"Th\u00e9orie \u00e9l\u00e9mentaire de la multiplication des entiers naturels","volume":"Vol. 890","author":"Cegielski","year":"1981"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB16","first-page":"367","article-title":"La th\u00e9orie \u00e9l\u00e9mentaire de la divisibilit\u00e9 est finiment axiomatisable","volume":"299","author":"Cegielski","year":"1984","journal-title":"C. R. Acad. Sc. Paris, S\u00e9r. I"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB17","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1305\/ndjfl\/1093635001","article-title":"The elementary theory of the natural lattice is finitely axiomatizable","volume":"30","author":"Cegielski","year":"1989","journal-title":"Notre Dame J. Formal Logic"},{"issue":"5","key":"10.1016\/S0304-3975(00)00113-4_BIB18","first-page":"239","article-title":"La th\u00e9orie de corps r\u00e9el-clos inductifs est une extension conservative de l'Arithm\u00e9tique de Peano","volume":"310","author":"Cegielski","year":"1990","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences. S\u00e9r I. Math."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB19","unstructured":"P. Cegielski, Quelques contributions a l'etude des arithmetiques faibles, Th\u00e8se, LITP 90.77, October 1990."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB20","unstructured":"P. Cegielski, Julia Robinson definability forty years later, Seminaire du LLAIC, Vol. I, Universit\u00e9 d'Auvergne, Clermont 1, 1989\u20131990, pp. 32\u201345."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB21","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF02127802","article-title":"Definability, decidability and complexity","volume":"16","author":"Cegielski","year":"1996","journal-title":"Ann. Math. Artificial Intelligence"},{"issue":"2","key":"10.1016\/S0304-3975(00)00113-4_BIB22","doi-asserted-by":"crossref","first-page":"515","DOI":"10.2307\/2275673","article-title":"Definability and decidability issues in extensions of the integers with the divisibility predicate","volume":"61","author":"Cegielski","year":"1996","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB23","unstructured":"P. Cegielski, D. Richard, Ind\u00e9cidabilit\u00e9 de la th\u00e9orie des entiers naturels munis d'un e\u00e9num\u00e9ration des premiers et de la divisibilit\u00e9, C. R. Acad. Sc. Paris, S\u00e9r. I 315, 1992, 1431\u20131434, also Seminaire du LLAIC, Universit\u00e9 d'Auvergne, Clermont 1, Vol. IV, 1992\u20131993, 17\u201323."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB24","unstructured":"P. Cegielski, D. Richard, Une application de la complexit\u00e8 \u00e0 la non-d\u00e9finissabilit\u00e9, Seminaire du LLAIC, Vol. IV, Universit\u00e9 d'Auvergne, Clermont 1, 1992\u20131993, pp. 25\u201331."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB25","unstructured":"P. Cegielski, D. Richard, Sur les th\u00e9ories arithm\u00e9tiques du premier ordre permettant le codage ou le d\u00e9codage des sites finies d'entiers naturels, Actes du LLAIC, Vol. VI, Universit\u00e9 d'Auvergne, Clermont 1, 1995\u20131996, pp. 23\u201339."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB26","unstructured":"P. Cegielski, D. Richard, Decidability of the theory of the natural integers with the Cantor pairing function and the successor, A manuscript, LLaicl Universit\u00e9 d'Auvergne and L.A.C.L. Universit\u00e9 Paris, Vol. 12, 1998, 22pp."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB27","first-page":"253","article-title":"Modular trellises","volume":"9","author":"C\u0306ern\u00fd","year":"1986","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB28","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1007\/BF01746527","article-title":"On the base dependence of sets of numbers recognizable by finite automata","volume":"3","author":"Cobham","year":"1969","journal-title":"Math. System Theory"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB29","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/BF01706087","article-title":"Uniform tag sequences","volume":"6","author":"Cobham","year":"1972","journal-title":"Math. System Theory"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB30","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1090\/S0002-9947-1961-0139530-9","article-title":"Decision problems of finite automata design and related arithmetics","volume":"98","author":"Elgot","year":"1961","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB31","doi-asserted-by":"crossref","first-page":"169","DOI":"10.2307\/2269808","article-title":"Decidability and undecidability of second (first) order theory of (generalized) successor","volume":"31","author":"Elgot","year":"1966","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB32","doi-asserted-by":"crossref","first-page":"391","DOI":"10.2307\/2321216","article-title":"How many pairs of products of consecutive integers have the same prime factors?","volume":"87","author":"Erd\u00f6s","year":"1980","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB33","series-title":"Logique et Informatique: Une Introduction","first-page":"7","article-title":"D\u00e9cidabilit\u00e9 et complexit\u00e9 des th\u00e9ories logiques","author":"Grigorieff","year":"1991"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB34","first-page":"125","article-title":"Contibution \u00e0 l\u2019\u00e9tude d'une conjecture de th\u00e9orie des nombres par le codage ZBV","volume":"35","author":"Grigorieff","year":"1989","journal-title":"L'Enseignement Math. 2\u00b0, S\u00e9r."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB35","series-title":"Sieve Methods","author":"Halberstam","year":"1974"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB36","first-page":"83","article-title":"Multiples of an integer in the Pascal triangle","volume":"46\u201347","author":"Korec","year":"1985","journal-title":"Acta Math. Univ. Comen."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB37","series-title":"Proceedings of the V Universal Algebra Symposium, Turawa, Poland, 3\u20137 May 1988","first-page":"198","article-title":"Generalized Pascal triangles","author":"Korec","year":"1989"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB38","first-page":"105","article-title":"Pascal triangles modulo n and modular trellises","volume":"9","author":"Korec","year":"1990","journal-title":"Comput. Artificial Intelligence"},{"issue":"2\u20134","key":"10.1016\/S0304-3975(00)00113-4_BIB39","doi-asserted-by":"crossref","first-page":"287","DOI":"10.3233\/FI-1993-182-414","article-title":"Definability of arithmetic operations from the order and a random relation","volume":"18","author":"Korec","year":"1993","journal-title":"Fundamenta Inform."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB40","first-page":"53","article-title":"Definability of arithmetic operations in Pascal triangle modulo an integer divisible by two primes","volume":"318","author":"Korec","year":"1993","journal-title":"Grazer Mat. Berichte"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB41","series-title":"Proc. Seventh IMYCS, Smolenice 92, November 16\u201320, 1992","first-page":"59","article-title":"Generalized Pascal triangles, their relation to cellular automata and their elementary theories, Development in theoretical computer science","author":"Korec","year":"1994"},{"issue":"5","key":"10.1016\/S0304-3975(00)00113-4_BIB42","first-page":"531","article-title":"Structures related to Pascal's triangle modulo 2 and their elementary theories","volume":"44","author":"Korec","year":"1994","journal-title":"Math. Slovaca"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB43","series-title":"Summer School on General Algebra and Ordered Sets, Horn\u0131\u0301 Lipov\u00e1, September 1994","first-page":"63","article-title":"Substantially different theories of two structures associated to the same generalized Pascal triangle","author":"Korec","year":"1994"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB44","unstructured":"I. Korec, Elementary theories of structures containing generalized Pascal triangles modulo a prime,in: S. Shtrakov, Iv. Mirchev (Eds.), Discrete Mathematics and Applications, Blagoevgrad\/Predel, September 12\u201316, 1994, Blagoevgrad, 1995, pp. 91\u2013102."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB45","series-title":"General Algebra and Discrete Mathematics, Potsdam, September 27\u2013 October 1, 1993","first-page":"169","article-title":"Decidable and undecidable theories of generalized Pascal triangles","author":"Korec","year":"1995"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB46","first-page":"151","article-title":"Undecidable elementary theories of classes of generalized Pascal triangles","volume":"5","author":"Korec","year":"1995","journal-title":"Tatra Mountains Math. Publ."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB47","unstructured":"I. Korec, Undecidability and uniform definability in classes of structures related to Pascal triangles modulo n, Tatra Mountains Math. Publ. 11 (1997) 129\u2013146, also preprint 18\/1996 of Math. Institute SAV Bratislava."},{"issue":"2","key":"10.1016\/S0304-3975(00)00113-4_BIB48","first-page":"214","article-title":"Theories of generalized Pascal triangles (Abstract)","volume":"1","author":"Korec","year":"1995","journal-title":"Bull. Assoc. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB49","unstructured":"I. Korec, Definability of arithmetical operations from Pascal's triangle modulo n and arithmetical functions, preprint 19\/1996 of Math. Institute SAV Bratislava, 8pp."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB50","unstructured":"I. Korec, Definability of addition from multiplication and neighborhood relation and some related results, in: W.G. Nowak, J. Schoissengeier (Eds.), Proc. Conf. Analytic and Elementary Number Theory, Vienna, July 18\u201320, 1996, Universit\u00e4t f\u00fcr Bodenkultur and Universit\u00e4t Wien, 1996, pp. 137\u2013148, also preprint 23\/1996 of Math. Institute SAV Bratislava."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB51","unstructured":"I. Korec, Definability of Pascal's triangles modulo 4 and 6 and some other binary operations from their associated equivalence relations, Acta. Univ. Math. Belii 4 (1996) 53\u201366, also preprint 32\/1996 of Math. Inst. SAV Bratislava."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB52","series-title":"Number Theory, Diophantine, Computational and Algebraic Aspects","first-page":"295","article-title":"Elementary definability from Pascal's triangle modulo p and the set of e-th powers","author":"Korec","year":"1998"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB53","doi-asserted-by":"crossref","unstructured":"I. Korec, Theories of generalized Pascal triangles, Ann. Pure Appl. Logic 89 (1997) 45\u201352, Logic Colloquium\u201994, Clermont-Ferrand.","DOI":"10.1016\/S0168-0072(97)00006-7"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB54","unstructured":"I. Korec, Arithmetical operations strongest with respect to the first order definability (submitted August 1997), Theoretical Computer Science, 12pp, also preprint 12\/1997 of Math. Inst. Slovak Acad. Sci. Bratislava."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB55","unstructured":"I. Korec, Definability of arithmetical operations from binary quadratic forms, Proc. Number Theory Ostravice\u201997 (submitted February 1998) 8pp, also preprint 4\/1998 of Math. Inst. Slovak Acad. Sci. Bratislava."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB56","unstructured":"I. Korec, Definability of addition and multiplication from some quadratic forms ax2 + cy2, Proceedings MFCS\u201998, March 1998 10pp, submitted for publication."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB57","doi-asserted-by":"crossref","first-page":"173","DOI":"10.4064\/fm-81-2-173-181","article-title":"Definability in structures of finite valency","volume":"81","author":"Korec","year":"1974","journal-title":"Fundam. Math."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB58","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02276797","article-title":"Model-interpretability into trees and applications","volume":"17","author":"Korec","year":"1976","journal-title":"Archiv f\u00fcr Math. Logik Grundlagenforschung"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB59","unstructured":"A. Ko\u015bcielski, Borel determinacy, weak set theories and higher order arithmetics, Seminaire du LLAIC, vol. IV, Universit\u00e9 d'Auvergne, Clermont 1, 1992\u20131993, pp. 144\u2013196."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB60","doi-asserted-by":"crossref","unstructured":"M. Langevin, Partie sans facteur carr\u00e9 d'un produit d'entiers voisins, in Approximations diophantiennes et nombres transcendants, P. Philippon (ed.), de Gruyter, Berlin, 203\u2013214 (1992) (C.R. Colloq. Luminy\/Fr. 1990).","DOI":"10.1515\/9783110861440.203"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB61","series-title":"Contributions to Mathematical Logic","first-page":"189","article-title":"A decision procedure for the weak second order theory of linear order","author":"L\u00e4uchli","year":"1968"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB62","unstructured":"A.I. Mal'cev, Elementary theories of locally free universal algebras, Dokl. Akad. Nauk SSSR 138 (1961) 1009\u20131012 (Russian)."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB63","first-page":"267","article-title":"The divisibility of the binomial coefficients near a half-line and in convex sets","volume":"50\u201351","author":"Marko","year":"1987","journal-title":"Acta Math. Univ. Comen"},{"issue":"5","key":"10.1016\/S0304-3975(00)00113-4_BIB64","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1090\/S0002-9947-1978-0487048-9","article-title":"Completeness theorems, incompleteness theorems and models of arithmetic","volume":"239","author":"McAloon","year":"1978","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB65","doi-asserted-by":"crossref","unstructured":"E. Mendelson, Introduction to Mathematical Logic, 3rd ed., Van Nostrand, 1964, Wadsworth, California, 1987, X+342 p.","DOI":"10.1007\/978-1-4615-7288-6"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB66","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0168-0072(95)00022-4","article-title":"Presburger arithmetic and recognabilizity of sets of natural numbers by automata: new proof of Cobham's and Semenov's theorems","volume":"77","author":"Michaux","year":"1996","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB67","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0304-3975(92)90250-J","article-title":"Complexity of logical theories involving primality","volume":"106","author":"Michel","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB68","first-page":"242","article-title":"Borne sup\u00e9rieure de la complexit\u00e9 de la th\u00e9orie de N muni de la relation de divisibilit\u00e9","volume":"vol. 890","author":"Michel","year":"1981"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB69","series-title":"Mathematical Logic","author":"Monk","year":"1976"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB70","first-page":"343","article-title":"Images de spectres binaires par des polyn\u00f4mes","volume":"315","author":"More","year":"1992","journal-title":"C. R. Acad. Sci. Paris, S\u00e9r. I"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB71","series-title":"On direct products of theories, J. Symbolic Logic 17(1) (1952) 1\u201331, also in Foundational Studies Selected Works, vol. 2","author":"Mostowski","year":"1979"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB72","doi-asserted-by":"crossref","first-page":"130","DOI":"10.2307\/2266972","article-title":"A reduction in the number of primitive ideas in arithmetic","volume":"15","author":"Myhill","year":"1950","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB73","unstructured":"F. N\u00e9zondet, D. Richard, Brief survey and latest results up to 97 on successor and coprimeness, Actes du LLAIC, vol. VI, Universit\u00e9 d'Auvergne, Clermont 1, 1995\u20131996, pp. 163\u2013183."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB74","series-title":"Open Days in Model Theory and Set Theory, Jadwisin, Poland, September 1981","article-title":"Synonymy and re-interpretation for some sublanguages of Peano arithmetic","author":"Pabion","year":"1981"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB75","doi-asserted-by":"crossref","unstructured":"A. Padoa, Essai d'une th\u00e9orie alg\u00e9brique des nombres entiers, pr\u00e9c\u00e9d\u00e9 d'une introduction logique\u00e1 une th\u00e9orie d\u00e9ductive quelconque, Biblioth\u00e8que du Congr\u00e8s international de philosophie, vol. 3, Paris, 1900, Armand Colin, 1901, pp. 309\u2013365 (Engl. translation in van Heijenoort, From Frege to G\u00f6del, Harvard University Press, Cambridge, MA, 1967, 118\u2013123).","DOI":"10.5840\/wcp11901312"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB76","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(92)90328-D","article-title":"Logically defined subsets of Nk","volume":"93","author":"P\u00e9ladeau","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB77","doi-asserted-by":"crossref","unstructured":"Yu.G. Penzin, Razreshimost\u2019 teorii celych chisel so slozheniem, porjadkom i umnozheniem na proizvol'noe chislo, Matematicheskie Zametki 13(5) (1973) 667\u2013675 (Translated in: Mathematical Notes 13(5) (1973) 401\u2013405).","DOI":"10.1007\/BF01147467"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB78","unstructured":"Yu.G. Penzin, Undecidability of the theory of the integers with addition and the predicate of coprimality, Third All-Union Conf. Mathematics and Logic Novosibirsk, 1974, (information: [19]) (in Russian)."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB79","unstructured":"Yu.G. Penzin, Undecidability of a theory of the integers with addition and predicate mutually disjoint, Algeb. Systemy (Irkutsk 1976) 149\u2013153 (in Russian)."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB80","unstructured":"Yu.G. Penzin, Nerazreshimye teorii kol'ca nepreryvnykh funkcij, Algoritmicheskie voprosy algebraicheskikh sistem, Irkutsk, 1978, pp. 142\u2013147."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB81","unstructured":"Yu.G. Penzin, Problema bliznecov v formal'noj arifmetike, Matematicheskie Zametki 26(4) (1979) 505\u2013511 (Translated in: Mathematical Notes 26(3,4) (1980) 743\u2013746.)"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB82","series-title":"Cours de th\u00e9orie des mod\u00e8les","author":"Poizat","year":"1985"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB83","doi-asserted-by":"crossref","first-page":"39","DOI":"10.2307\/2964057","article-title":"Decidability and essential undecidability","volume":"22","author":"Putnam","year":"1957","journal-title":"J. Symbolic Logic"},{"issue":"4","key":"10.1016\/S0304-3975(00)00113-4_BIB84","doi-asserted-by":"crossref","first-page":"105","DOI":"10.2307\/2268308","article-title":"Concatenation as a basis for arithmetic","volume":"11","author":"Quine","year":"1946","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB85","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Trans. Amer. Math. Society"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB86","first-page":"270","article-title":"De la structure additive \u00e0 la saturation des mod\u00e8les de Peano et \u00e0 la classification des sous-languages de l'Arithm\u00e8tique","volume":"vol. 890","author":"Richard","year":"1981"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB87","first-page":"287","article-title":"The arithmetics as theories of two orders","volume":"23","author":"Richard","year":"1984","journal-title":"Ann. Disc. Math."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB88","doi-asserted-by":"crossref","first-page":"927","DOI":"10.2307\/2273981","article-title":"Answer to a problem raised by J. Robinson: the arithmetic of positive or negative integers is definable from successor and divisibility","volume":"50","author":"Richard","year":"1985","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB89","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90144-X","article-title":"All arithmetical sets of powers of primes are first order definable in terms of the successor and the coprimeness predicate","volume":"53","author":"Richard","year":"1985","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB90","unstructured":"D. Richard, D\u00e9finissabilit\u00e9 en arithm\u00e9tique et m\u00e9thode de codage Z.B.V. appliqu\u00e9e\u00e0 des langages avec successeurs et coprimarit\u00e9, Th\u00e8se de doctorat d\u2019\u00e9tat, Universit\u00e9 de Lyon-I, 1985."},{"issue":"13","key":"10.1016\/S0304-3975(00)00113-4_BIB91","first-page":"415","article-title":"D\u00e9finissabilit\u00e9 de l'arithm\u00e9tique et par successeurs, coprimarit\u00e9 et puissance","volume":"300","author":"Richard","year":"1985","journal-title":"C. R. Acad. Sc. Paris S\u00e9rie I"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB92","first-page":"665","article-title":"D\u00e9finissabilit\u00e9 de l\u00e1rithm\u00e9tique par coprimarit\u00e9 et restrictions de l'addition ou de la multiplication","volume":"305","author":"Richard","year":"1987","journal-title":"C. R. Acad. Sc. Paris S\u00e9rie I"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB93","unstructured":"D. Richard, Equivalence of some questions in mathematical logic with some conjectures in number theory, in: R. Mollin (Ed.), Number Theory and Applications, 1988, pp. 529\u2013545."},{"issue":"4","key":"10.1016\/S0304-3975(00)00113-4_BIB94","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.2307\/2274815","article-title":"Definability in terms of the successor function and the coprimeness predicate in the set of arbitrary integers","volume":"54","author":"Richard","year":"1989","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB95","doi-asserted-by":"crossref","first-page":"98","DOI":"10.2307\/2266510","article-title":"Definability and decision problems in arithmetic","volume":"14","author":"Robinson","year":"1949","journal-title":"J. Symbolic Logic"},{"issue":"3","key":"10.1016\/S0304-3975(00)00113-4_BIB96","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1090\/S0002-9947-1952-0048374-2","article-title":"Existential definability in arithmetic","volume":"72","author":"Robinson","year":"1952","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB97","article-title":"The indecidability of algebraic rings and fields","volume":"10","author":"Robinson","year":"1960","journal-title":"Proc. AMS"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB98","series-title":"The Theory of Models","first-page":"299","article-title":"The decision problem for fields","author":"Robinson","year":"1965"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB99","unstructured":"J. Robinson, Collected papers S. Feferman (Ed.), AMS Publications, 1996, probably contains the four items above."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB100","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1090\/S0002-9947-1960-0114855-0","article-title":"Elementary properties of ordered Abelian groups","volume":"96","author":"Robinson","year":"1960","journal-title":"Trans. AMS"},{"issue":"2","key":"10.1016\/S0304-3975(00)00113-4_BIB101","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF00967164","article-title":"The Presburger nature of predicates that are regular in two number systems","volume":"18","author":"Semenov","year":"1977","journal-title":"Siberian Math. J."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB102","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1070\/IM1980v015n02ABEH001252","article-title":"On certain extensions of the arithmetic of addition of natural numbers","volume":"15","author":"Semenov","year":"1980","journal-title":"Math. USSR Izvestiya"},{"issue":"1","key":"10.1016\/S0304-3975(00)00113-4_BIB103","first-page":"44","article-title":"On definability of arithmetic in their fragments","volume":"263","author":"Semenov","year":"1982","journal-title":"Doklady Akad. nauk SSSR"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB104","doi-asserted-by":"crossref","unstructured":"A.L. Semenov, Logical theories of one-place functions on the set of natural numbers, Izvestiya Akad. SSSR Serija Mat. 47 (1983) 623\u2013658 (English translation: Mathematics of the USSR \u2014 Izvestiya 22 (1984) 162\u2013175).","DOI":"10.1070\/IM1984v022n03ABEH001456"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB105","doi-asserted-by":"crossref","unstructured":"A.L. Semenov, Decidability of Monadic Theories, Lecture Notes in Computer Science, vol. 176, Springer, Berlin, 1984, 401\u2013419.","DOI":"10.1007\/BFb0030296"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB106","series-title":"B\u00fcchi's Monadic Second Order Successor Arithmetics","volume":"vol. 120","author":"Siefkes","year":"1970"},{"issue":"8","key":"10.1016\/S0304-3975(00)00113-4_BIB107","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1112\/jlms\/s2-8.3.555","article-title":"Notes on binomial coefficients III \u2014 Any integer divides almost all binomial coefficients","volume":"2","author":"Singmaster","year":"1974","journal-title":"J. London Math. Soc."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB108","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF02280812","article-title":"A note on undecidable extensions of monadic second-order successor arithmetic","volume":"17","author":"Thomas","year":"1975","journal-title":"Arch. Math. Logik"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB109","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01351676","article-title":"The theory of successor with an extra predicate","volume":"237","author":"Thomas","year":"1978","journal-title":"Math. Ann."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB110","doi-asserted-by":"crossref","first-page":"334","DOI":"10.2307\/2273193","article-title":"On the bounded monadic theory of well-ordered structures","volume":"45","author":"Thomas","year":"1980","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB111","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0019-9958(81)90663-X","article-title":"A combinatorial approach to the theory of \u03c9-automata","volume":"48","author":"Thomas","year":"1981","journal-title":"Inform. Control"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB112","unstructured":"R. Villemaire, Joining k- and l-recognizable sets of natural numbers, Lecture Notes in Computer Science, vol. 577, Springer, Berlin, 1986, pp. 458\u2013466."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB113","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(92)90256-F","article-title":"The theory of \u3008N,+, Vk, Vl\u3009 is undecidable","volume":"106","author":"Villemaire","year":"1993","journal-title":"Theoret. Comput. Sci"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB114","doi-asserted-by":"crossref","unstructured":"P.J. Voda, Basis for a feasible programming language, Computer Science Logic CSL\u201994, Lecture Notes in Computer Science, vol. 933, Springer, Berlin, 1995, pp. 324\u2013338.","DOI":"10.1007\/BFb0022266"},{"key":"10.1016\/S0304-3975(00)00113-4_BIB115","unstructured":"P.J. Voda, Programming by Logic & Logic by Programming, Vol. 1, Computability, in preparation."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB116","unstructured":"A.R. Woods, Some problems in logic and number theory, and their connection, Ph.D. Thesis, University of Manchester, 1981."},{"key":"10.1016\/S0304-3975(00)00113-4_BIB117","series-title":"Decidability Problems and Constructive Models","author":"Yershow","year":"1980"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001134?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001134?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,12,30]],"date-time":"2023-12-30T19:57:24Z","timestamp":1703966244000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500001134"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,4]]},"references-count":117,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,4]]}},"alternative-id":["S0304397500001134"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00113-4","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,4]]}}}