{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:54:21Z","timestamp":1774590861954,"version":"3.50.1"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":741,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of <jats:italic>FF<\/jats:italic>-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200000955_inline01\"\/> equivalence relations on hyperarithmetical subsets of <jats:italic>\u03c9<\/jats:italic>.<\/jats:p>","DOI":"10.2178\/jsl\/1327068695","type":"journal-article","created":{"date-parts":[[2012,1,20]],"date-time":"2012-01-20T09:16:13Z","timestamp":1327050973000},"page":"122-132","source":"Crossref","is-referenced-by-count":39,"title":["Isomorphism relations on computable structures"],"prefix":"10.1017","volume":"77","author":[{"given":"Ekaterina B.","family":"Fokina","sequence":"first","affiliation":[]},{"given":"Sy-David","family":"Friedman","sequence":"additional","affiliation":[]},{"given":"Valentina","family":"Harizanov","sequence":"additional","affiliation":[]},{"given":"Julia F.","family":"Knight","sequence":"additional","affiliation":[]},{"given":"Charles","family":"Mccoy","sequence":"additional","affiliation":[]},{"given":"Antonio","family":"Montalb\u00e1n","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200000955_ref019","volume-title":"Borel equivalence relations. Structure and classification","author":"Kanovei","year":"2008"},{"key":"S0022481200000955_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.06.010"},{"key":"S0022481200000955_ref028","first-page":"333","article-title":"Ulm's theorem for partially ordered structures related to simply presented Abelian p-groups","volume":"227","author":"Rogers","year":"1977","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200000955_ref016","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021758312697"},{"key":"S0022481200000955_ref013","first-page":"894","volume":"54","author":"Friedman","year":"1989","journal-title":"A Borel reducibility theory for classes of countable structures"},{"key":"S0022481200000955_ref005","first-page":"283","volume":"71","author":"Calvert","year":"2006","journal-title":"Computable trees of Scott rank \u03c9CK and computable approximations"},{"key":"S0022481200000955_ref001","volume-title":"Computable structures and the hyperarithmetical hierarchy","author":"Ash","year":"2000"},{"key":"S0022481200000955_ref002","unstructured":"[] Calvert W. , Algebraic structure and computable structure, PhD Dissertation, University of Notre Dame, 2005."},{"key":"S0022481200000955_ref004","doi-asserted-by":"publisher","DOI":"10.1023\/B:ALLO.0000048827.30718.2c"},{"key":"S0022481200000955_ref009","first-page":"198","article-title":"Equivalence relations on classes of computable structures","volume":"5635","author":"Fokina","year":"2009","journal-title":"Computability in Europe, 2009"},{"key":"S0022481200000955_ref014","first-page":"243","volume":"76","author":"Friedman","year":"2011","journal-title":"Analytic equivalence relations and bi-embeddability"},{"key":"S0022481200000955_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2008.06.007"},{"key":"S0022481200000955_ref020","volume-title":"Infinite Abelian groups","author":"Kaplansky","year":"1954"},{"key":"S0022481200000955_ref025","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-05-04005-5"},{"key":"S0022481200000955_ref027","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200000955_ref024","first-page":"901","volume":"73","author":"Knight","year":"2007","journal-title":"Turing computable embeddings"},{"key":"S0022481200000955_ref006","unstructured":"[] Carson J. , Fokina E. , Harizanov V. S. , Knight J. F. , Quinn S. , Safranski C. , and Wallbaum J. , Computable embedding problem, submitted."},{"key":"S0022481200000955_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.10.002"},{"key":"S0022481200000955_ref007","first-page":"99","article-title":"and  equivalence structures","volume":"5635","author":"Cenzer","year":"2009","journal-title":"Computability in Europe, 2009"},{"key":"S0022481200000955_ref021","doi-asserted-by":"publisher","DOI":"10.2307\/421088"},{"key":"S0022481200000955_ref012","first-page":"846","volume":"76","author":"Fokina","year":"2011","journal-title":"Ulm type, and coding rankhomogeneous trees in other structures"},{"key":"S0022481200000955_ref015","volume-title":"Invariant descriptive set theory","author":"Gao","year":"2009"},{"key":"S0022481200000955_ref017","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0244049-7"},{"key":"S0022481200000955_ref022","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-97-00221-X"},{"key":"S0022481200000955_ref026","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1174668219"},{"key":"S0022481200000955_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.10.002"},{"key":"S0022481200000955_ref018","doi-asserted-by":"publisher","DOI":"10.4064\/fm175-3-2"},{"key":"S0022481200000955_ref010","unstructured":"[] Fokina E. , equivalence relations on \u03c9, submitted."}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200000955","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T20:57:55Z","timestamp":1556225875000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200000955\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["S0022481200000955"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1327068695","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}