{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T12:36:14Z","timestamp":1749213374249,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T00:00:00Z","timestamp":1723075200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Rutherford Discovery","award":["RDF-VUW1902","RDF-VUW1902"],"award-info":[{"award-number":["RDF-VUW1902","RDF-VUW1902"]}]},{"DOI":"10.13039\/501100009193","name":"Marsden Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009193","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001538","name":"Victoria University of Wellington","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001538","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We investigate the problem of punctual (fully primitive recursive) presentability of algebraic structures up to primitive recursive and computable isomorphism. We show that for mono-unary structures and undirected graphs, if a structure is not punctually categorical then it has infinitely many punctually non-isomorphic punctual presentations. We also show that the punctual degrees of any computably almost rigid structure as well as the order (<jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathbb {Z},&lt;$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>Z<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mo>&lt;<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>) are dense. Finally we characterise the Boolean algebras which have a punctually 1-decidable presentation that is computably isomorphic to a 1-decidable presentation.<\/jats:p>","DOI":"10.1007\/s00153-024-00940-7","type":"journal-article","created":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T04:02:05Z","timestamp":1723089725000},"page":"159-184","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Punctually presented structures II: comparing presentations"],"prefix":"10.1007","volume":"64","author":[{"given":"Marina","family":"Dorzhieva","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodney","family":"Downey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ellen","family":"Hammatt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander G.","family":"Melnikov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keng Meng","family":"Ng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,8]]},"reference":[{"key":"940_CR1","first-page":"jzac065","volume":"08","author":"M Askes","year":"2022","unstructured":"Askes, M., Downey, R.: Online, computable and punctual structure theory. Log. J. IGPL 08, jzac065 (2022)","journal-title":"Log. J. IGPL"},{"key":"940_CR2","unstructured":"Ash, C., Knight, J.: Computable structures and the hyperarithmetical hierarchy. Studies in Logic and the Foundations of Mathematics, vol. 144. North-Holland Publishing Co., Amsterdam (2000)"},{"issue":"1","key":"940_CR3","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/s10469-016-9377-6","volume":"55","author":"PE Alaev","year":"2016","unstructured":"Alaev, P.E.: Existence and uniqueness of structures computable in polynomial time. Algebra Log. 55(1), 72\u201376 (2016)","journal-title":"Algebra Log."},{"issue":"4","key":"940_CR4","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10469-018-9498-1","volume":"57","author":"PE Alaev","year":"2018","unstructured":"Alaev, P.E.: Categoricity for primitively recursive and polynomial Boolean algebras. Algebra Log. 57(4), 389\u2013426 (2018)","journal-title":"Algebra Log."},{"issue":"5","key":"940_CR5","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1134\/S0037446622050019","volume":"63","author":"PE Alaev","year":"2022","unstructured":"Alaev, P.E.: Finitely generated structures computable in polynomial time. Sib. Math. J. 63(5), 801\u2013818 (2022)","journal-title":"Sib. Math. J."},{"key":"940_CR6","doi-asserted-by":"crossref","unstructured":"Alaev, P.E., Selivanov, V.L.: Searching for applicable versions of computable structures. In: Connecting with computability, volume 12813 of Lecture Notes in Comput. Sci., pp. 1\u201311. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-80049-9_1"},{"issue":"4","key":"940_CR7","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/s10958-014-2148-9","volume":"203","author":"NA Bazhenov","year":"2014","unstructured":"Bazhenov, N.A.: $$\\Delta ^0_2$$-categoricity of Boolean algebras. J. Math. Sci. (N. Y.) 203(4), 444\u2013454 (2014)","journal-title":"J. Math. Sci. (N. Y.)"},{"issue":"2","key":"940_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1017\/bsl.2019.20","volume":"25","author":"N Bazhenov","year":"2019","unstructured":"Bazhenov, N., Downey, R., Kalimullin, I., Melnikov, A.: Foundations of online structure theory. Bull. Symb. Log. 25(2), 141\u2013181 (2019)","journal-title":"Bull. Symb. Log."},{"issue":"4","key":"940_CR9","doi-asserted-by":"publisher","first-page":"1630","DOI":"10.1017\/jsl.2019.26","volume":"84","author":"N Bazhenov","year":"2019","unstructured":"Bazhenov, N., Harrison-Trainor, M., Kalimullin, I., Melnikov, A., Ng, K.M.: Automatic and polynomial-time algebraic structures. J. Symb. Log. 84(4), 1630\u20131669 (2019)","journal-title":"J. Symb. Log."},{"key":"940_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.tcs.2020.08.021","volume":"844","author":"N Bazhenov","year":"2020","unstructured":"Bazhenov, N., Kalimullin, I., Melnikov, A., Ng, K.M.: Online presentations of finitely generated structures. Theoret. Comput. Sci. 844, 195\u2013216 (2020)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"940_CR11","doi-asserted-by":"publisher","first-page":"28","DOI":"10.33048\/smzh.2019.60.103","volume":"60","author":"KV Blinov","year":"2019","unstructured":"Blinov, K.V.: Primitively recursively categorical linear orderings. Sibirsk. Mat. Zh. 60(1), 28\u201336 (2019)","journal-title":"Sibirsk. Mat. Zh."},{"issue":"6","key":"940_CR12","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1134\/S0037446621060033","volume":"62","author":"KV Blinov","year":"2021","unstructured":"Blinov, K.V.: Primitively recursive categoricity for unars and equivalence structures. Sib. Math. J. 62(6), 994\u20131009 (2021)","journal-title":"Sib. Math. J."},{"issue":"1","key":"940_CR13","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0168-0072(91)90008-A","volume":"54","author":"DA Cenzer","year":"1991","unstructured":"Cenzer, D.A., Remmel, J.B.: Polynomial-time versus recursive models. Ann. Pure Appl. Logic 54(1), 17\u201358 (1991)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"1\u20133","key":"940_CR14","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0168-0072(92)90076-C","volume":"56","author":"DA Cenzer","year":"1992","unstructured":"Cenzer, D.A., Remmel, J.B.: Polynomial-time abelian groups. Ann. Pure Appl. Logic 56(1\u20133), 313\u2013363 (1992)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"4","key":"940_CR15","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1017\/jsl.2020.51","volume":"85","author":"R Downey","year":"2020","unstructured":"Downey, R., Greenberg, N., Melnikov, A., Ng, K.M., Turetsky, D.: Punctual categoricity and universality. J. Symb. Log. 85(4), 1427\u20131466 (2020)","journal-title":"J. Symb. Log."},{"key":"940_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2020.02.004","volume":"112","author":"R Downey","year":"2020","unstructured":"Downey, R., Harrison-Trainor, M., Kalimullin, I., Melnikov, A., Turetsky, D.: Graphs are not universal for online computability. J. Comput. Syst. Sci. 112, 1\u201312 (2020)","journal-title":"J. Comput. Syst. Sci."},{"issue":"9","key":"940_CR17","doi-asserted-by":"publisher","first-page":"3999","DOI":"10.1090\/proc\/15471","volume":"149","author":"R Downey","year":"2021","unstructured":"Downey, R., Harrison-Trainor, M., Melnikov, A.: Relativizing computable categoricity. Proc. Am. Math. Soc. 149(9), 3999\u20134013 (2021)","journal-title":"Proc. Am. Math. Soc."},{"issue":"4","key":"940_CR18","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1134\/S1995080221040089","volume":"42","author":"MV Dorzhieva","year":"2021","unstructured":"Dorzhieva, M.V., Issakhov, A.A., Kalmurzayev, B.S., Kornev, R.A., Kotov, M.V.: Punctual dimension of algebraic structures in certain classes. Lobachevskii J. Math. 42(4), 716\u2013725 (2021)","journal-title":"Lobachevskii J. Math."},{"key":"940_CR19","unstructured":"Dorzhieva, M., Melnikov, A.: Punctually presented structures I: existential closures. Preprint"},{"issue":"3","key":"940_CR20","first-page":"35","volume":"17","author":"R Downey","year":"2021","unstructured":"Downey, R., Melnikov, K.M., Ng, K.M.: Foundations of online structure theory II: the operator approach. Log. Methods Comput. Sci. 17(3), 35 (2021)","journal-title":"Log. Methods Comput. Sci."},{"key":"940_CR21","doi-asserted-by":"crossref","unstructured":"Ershov, Y., Goncharov, S.: Constructive models. Siberian School of Algebra andLogic. Consultants Bureau, New York (2000)","DOI":"10.1007\/978-1-4615-4305-3"},{"issue":"9","key":"940_CR22","doi-asserted-by":"publisher","first-page":"102985","DOI":"10.1016\/j.apal.2021.102985","volume":"172","author":"N Greenberg","year":"2021","unstructured":"Greenberg, N., Harrison-Trainor, M., Melnikov, A., Turetsky, D.: Non-density in punctual computability. Ann. Pure Appl. Log. 172(9), 102985 (2021)","journal-title":"Ann. Pure Appl. Log."},{"issue":"6","key":"940_CR23","first-page":"621","volume":"19","author":"S Goncharov","year":"1980","unstructured":"Goncharov, S.: The problem of the number of nonautoequivalent constructivizations. Algebra i Logika 19(6), 621\u2013639 (1980)","journal-title":"Algebra i Logika"},{"issue":"2","key":"940_CR24","first-page":"269","volume":"256","author":"S Goncharov","year":"1981","unstructured":"Goncharov, S.: Groups with a finite number of constructivizations. Dokl. Akad. Nauk SSSR 256(2), 269\u2013272 (1981)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"1\u20133","key":"940_CR25","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0168-0072(01)00087-2","volume":"115","author":"D Hirschfeldt","year":"2002","unstructured":"Hirschfeldt, D., Khoussainov, B., Shore, R., Slinko, A.: Degree spectra and computable dimensions in algebraic structures. Ann. Pure Appl. Log. 115(1\u20133), 71\u2013113 (2002)","journal-title":"Ann. Pure Appl. Log."},{"key":"940_CR26","doi-asserted-by":"crossref","unstructured":"Khisamiev, N.: Constructive abelian groups. In: Handbook of recursive mathematics, Vol. 2, volume 139 of Stud. Logic Found. Math., pp. 1177\u20131231. North-Holland, Amsterdam (1998)","DOI":"10.1016\/S0049-237X(98)80050-5"},{"issue":"8","key":"940_CR27","doi-asserted-by":"publisher","first-page":"102987","DOI":"10.1016\/j.apal.2021.102987","volume":"172","author":"I Kalimullin","year":"2021","unstructured":"Kalimullin, I., Melnikov, A., Montalban, A.: Punctual definability on structures. Ann. Pure Appl. Log. 172(8), 102987 (2021)","journal-title":"Ann. Pure Appl. Log."},{"issue":"2","key":"940_CR28","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/s10469-017-9437-6","volume":"56","author":"I Kalimullin","year":"2017","unstructured":"Kalimullin, I., Melnikov, A., Ng, K.M.: Different versions of categoricity without delays. Algebra Log. 56(2), 256\u2013266 (2017)","journal-title":"Algebra Log."},{"key":"940_CR29","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2017.01.029","volume":"674","author":"I Kalimullin","year":"2017","unstructured":"Kalimullin, I., Melnikov, A., Ng, K.M.: Algebraic structures computable without delay. Theoret. Comput. Sci. 674, 73\u201398 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"940_CR30","unstructured":"Kalimullin, I., Melnikov, A., Zubkov, M.: Punctual degrees and lattice embeddings. To appear in proceedings of Aspects of Computation, World-Scientific."},{"key":"940_CR31","doi-asserted-by":"crossref","unstructured":"Khoussainov, B., Shore, R.A.: Effective model theory: the number of models and their complexity. In: Models and computability (Leeds, 1997), volume 259 of London Math. Soc. Lecture Note Ser., pp. 193\u2013239. Cambridge Univ. Press, Cambridge (1999)","DOI":"10.1017\/CBO9780511565670.009"},{"issue":"5","key":"940_CR32","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/BF02259824","volume":"31","author":"OV Kudinov","year":"1992","unstructured":"Kudinov, O.V.: A criterion for the autostability of $$1$$-decidable models. Algebra Log. 31(5), 479\u2013492 (1992)","journal-title":"Algebra Log."},{"issue":"4","key":"940_CR33","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/BF02367027","volume":"35","author":"OV Kudinov","year":"1996","unstructured":"Kudinov, O.V.: An autostable $$1$$-decidable model without a computable Scott family of $$\\exists $$-formulas. Algebra Log. 35(4), 458\u2013467 (1996)","journal-title":"Algebra Log."},{"key":"940_CR34","doi-asserted-by":"crossref","unstructured":"Mal, A.: cev. Constructive algebras. I. Uspehi Mat. Nauk 16(3 (99)):3\u201360 (1961)","DOI":"10.1070\/RM1961v016n03ABEH001120"},{"issue":"1\u20133","key":"940_CR35","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0168-0072(02)00035-0","volume":"119","author":"C McCoy","year":"2003","unstructured":"McCoy, C.: $$\\Delta ^0_2$$-categoricity in Boolean algebras and linear orderings. Ann. Pure Appl. Logic 119(1\u20133), 85\u2013120 (2003)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"940_CR36","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1007\/s11856-019-1948-5","volume":"234","author":"A Melnikov","year":"2019","unstructured":"Melnikov, A., Ng, K.M.: The back-and-forth method and computability without delay. Israel J. Math. 234(2), 959\u20131000 (2019)","journal-title":"Israel J. Math."},{"issue":"7","key":"940_CR37","doi-asserted-by":"publisher","first-page":"3113","DOI":"10.1090\/proc\/15020","volume":"148","author":"A Melnikov","year":"2020","unstructured":"Melnikov, A., Ng, K.M.: A structure of punctual dimension two. Proc. Am. Math. Soc. 148(7), 3113\u20133128 (2020)","journal-title":"Proc. Am. Math. Soc."},{"key":"940_CR38","doi-asserted-by":"crossref","unstructured":"Montalb\u00e1n, A.: Computable Structure Theory\u2014Within the Arithmetic. Perspectives in Logic. Cambridge University Press, Cambridge; Association for Symbolic Logic, Ithaca (2021)","DOI":"10.1017\/9781108525749"},{"key":"940_CR39","first-page":"341","volume":"95","author":"M Rabin","year":"1960","unstructured":"Rabin, M.: Computable algebra, general theory and theory of computable fields. Trans. Am. Math. Soc. 95, 341\u2013360 (1960)","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"940_CR40","doi-asserted-by":"publisher","first-page":"595","DOI":"10.2307\/2273758","volume":"46","author":"JB Remmel","year":"1981","unstructured":"Remmel, J.B.: Recursive Boolean algebras with recursive atoms. J. Symb. Log. 46(3), 595\u2013616 (1981)","journal-title":"J. Symb. Log."},{"key":"940_CR41","unstructured":"Remmel, J.B.: Recursive Boolean lgebras. In: Handbook of Boolean Algebras, Vol. 3, pp. 1097\u20131165. North-Holland, Amsterdam (1989)"},{"issue":"3","key":"940_CR42","doi-asserted-by":"publisher","first-page":"2050016","DOI":"10.1142\/S0219061320500166","volume":"20","author":"D Turetsky","year":"2020","unstructured":"Turetsky, D.: Coding in the automorphism group of a computably categorical structure. J. Math. Log. 20(3), 2050016 (2020)","journal-title":"J. Math. Log."},{"issue":"6","key":"940_CR43","doi-asserted-by":"publisher","first-page":"1271","DOI":"10.33048\/smzh.2019.60.607","volume":"60","author":"MV Zubkov","year":"2019","unstructured":"Zubkov, M.V., Kalimullin, I., Melnikov, A., Frolov, A.N.: Punctual copies of algebraic structures. Sibirsk. Mat. Zh. 60(6), 1271\u20131285 (2019)","journal-title":"Sibirsk. Mat. Zh."}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00940-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-024-00940-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-024-00940-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T05:40:37Z","timestamp":1739338837000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-024-00940-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,8]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["940"],"URL":"https:\/\/doi.org\/10.1007\/s00153-024-00940-7","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"type":"print","value":"0933-5846"},{"type":"electronic","value":"1432-0665"}],"subject":[],"published":{"date-parts":[[2024,8,8]]},"assertion":[{"value":"1 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}