{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T10:23:22Z","timestamp":1776680602920,"version":"3.51.2"},"reference-count":11,"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)00109-2","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T10:59:17Z","timestamp":1027594757000},"page":"51-77","source":"Crossref","is-referenced-by-count":20,"title":["Decidability of the theory of the natural integers with the cantor pairing function and the successor"],"prefix":"10.1016","volume":"257","author":[{"given":"Patrick","family":"Cegielski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Richard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(00)00109-2_BIB1","unstructured":"G. Cantor, R. Dedekind, Briefwelrel, Hermann, Paris, 1937; traduction fran\u00e7aise in: J. Cavaill\u00e8s, Philosophie math\u00e9matique, Hermann, Paris, 1962, pp. 177\u2013249."},{"key":"10.1016\/S0304-3975(00)00109-2_BIB2","unstructured":"G. Cantor, Uber eine Eigenschaft des Inbegroffes aller reellen algebraischen Zahlen, J. Reine Angew. Math. 77 (1874) 258\u2013262; = Gesamm. abh., pp. 15\u2013118, Springer, Berlin, 1930; traduction fran\u00e7aise in Acta Math. 2 (1883) 305\u2013310."},{"key":"10.1016\/S0304-3975(00)00109-2_BIB3","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. Artif. Intell."},{"key":"10.1016\/S0304-3975(00)00109-2_BIB4","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(97)00281-8","article-title":"On arithmetical first-order theories allowing encoding and decoding of lists","volume":"222","author":"Cegielski","year":"1999","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00109-2_BIB5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(90)90080-L","article-title":"A uniform method for proving lower bounds on the computational complexity of logical theories","volume":"48","author":"Compton","year":"1990","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0304-3975(00)00109-2_BIB6","unstructured":"H.B. Enderton, A Mathematical Introduction to Logic, Academic Press, New York, 1972, XIII + 295 p."},{"key":"10.1016\/S0304-3975(00)00109-2_BIB7","doi-asserted-by":"crossref","unstructured":"J. Ferrante, C. Rackoff, The Computational Complexity of Logical Theories, Lecture Notes in Mathematics, vol. 718, Springer, Berlin, 1979, X + 243 p.","DOI":"10.1007\/BFb0062837"},{"key":"10.1016\/S0304-3975(00)00109-2_BIB8","doi-asserted-by":"crossref","unstructured":"I. Korec, A list of arithmetical structures complete with respect to the first-order definability, Theoret. Comput. Sci. 257 (this Vol.) (2001) 115\u2013151.","DOI":"10.1016\/S0304-3975(00)00113-4"},{"key":"10.1016\/S0304-3975(00)00109-2_BIB9","doi-asserted-by":"crossref","unstructured":"J. Robinson, Definability and decision problems in arithmetic, J. Symbolic Logic 14 (1949) 98\u2013114; rep. in: S. Feferman (Ed.), The Collected Works of Julia Robinson, American Mathematical Society, Provindence, RI, 1996, 338. p.","DOI":"10.2307\/2266510"},{"key":"10.1016\/S0304-3975(00)00109-2_BIB10","unstructured":"R. Tenney, Decidable pairing functions, manuscript, 1974, Department of Computer Science, Cornell University."},{"key":"10.1016\/S0304-3975(00)00109-2_BIB11","unstructured":"P. Cegielski, S. Grigorieff, D. Richard, La th\u00e9orie \u00e9l\u00e9mentaire de la fonction de couplage de Cantor des entiers naturels est d\u00e9cidable, Comptes rendus de l'Acad\u00e9mie des Sciences, Paris, to appear."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001092?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500001092?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T04:48:25Z","timestamp":1578458905000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500001092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,4]]},"references-count":11,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,4]]}},"alternative-id":["S0304397500001092"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00109-2","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2001,4]]}}}