{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T10:05:42Z","timestamp":1772445942919,"version":"3.50.1"},"reference-count":35,"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":3298,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2005,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007246_inline1\"\/>-condition. We show that all trees which are not computably categorical have computable dimension \u03c9. Finally, we prove that for every <jats:italic>n<\/jats:italic> \u2265 1 in \u03c9, there exists a computable tree of finite height which is \u03a3<jats:sub arrange=\"stack\">3<\/jats:sub><jats:sup arrange=\"stack\">0<\/jats:sup>-categorical but not \u0394<jats:sub arrange=\"stack\"><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup arrange=\"stack\">3<\/jats:sup>-categorical<\/jats:p>","DOI":"10.2178\/jsl\/1107298515","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:56:28Z","timestamp":1109800588000},"page":"151-215","source":"Crossref","is-referenced-by-count":25,"title":["Computable categoricity of trees of finite height"],"prefix":"10.1017","volume":"70","author":[{"given":"Steffen","family":"Lempp","sequence":"first","affiliation":[]},{"given":"Charles","family":"McCoy","sequence":"additional","affiliation":[]},{"given":"Russell","family":"Miller","sequence":"additional","affiliation":[]},{"given":"Reed","family":"Solomon","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007246_ref024","first-page":"470","volume":"66","author":"Miller","year":"2001","journal-title":"The \u039420 spectrum of a linear order"},{"key":"S0022481200007246_ref022","first-page":"A","article-title":"Recursively presented Boolean algebras","volume":"24","author":"LaRoche","year":"1977","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200007246_ref034","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-98-04314-7"},{"key":"S0022481200007246_ref020","unstructured":"Kudinov O. V. , An integral domain with finite algorithmic dimension, unpublished manuscript."},{"key":"S0022481200007246_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/BF02367027"},{"key":"S0022481200007246_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669323"},{"key":"S0022481200007246_ref011","volume-title":"Nonequivalent constructivizations","author":"Goncharov","year":"1982"},{"key":"S0022481200007246_ref027","doi-asserted-by":"publisher","DOI":"10.1007\/BF01463352"},{"key":"S0022481200007246_ref026","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100003844"},{"key":"S0022481200007246_ref010","first-page":"58","article-title":"Groups with a finite number of constructivizations","volume":"19","author":"Goncharov","year":"1981","journal-title":"Soviet Mathematics Doklady"},{"key":"S0022481200007246_ref030","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1981-0624937-1"},{"key":"S0022481200007246_ref004","unstructured":"Chisholm J. , On intrisically 1-computable trees, unpublished manuscript."},{"key":"S0022481200007246_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(09)70156-9"},{"key":"S0022481200007246_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90070-9"},{"key":"S0022481200007246_ref012","volume-title":"Autostable models and algorithmic dimensions","volume":"1","author":"Goncharov","year":"1998"},{"key":"S0022481200007246_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1994-1203984-4"},{"key":"S0022481200007246_ref033","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200007246_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90015-8"},{"key":"S0022481200007246_ref013","first-page":"45","article-title":"Autostability of models","volume":"19","author":"Goncharov","year":"1980","journal-title":"Algebra and Logic"},{"key":"S0022481200007246_ref025","first-page":"111","volume":"70","author":"Miller","year":"2005","journal-title":"The computable dimension of trees of infinite height"},{"key":"S0022481200007246_ref006","first-page":"157","volume-title":"Complexity, logic, and recursion theory","author":"Downey","year":"1997"},{"key":"S0022481200007246_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF01054216"},{"key":"S0022481200007246_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90038-8"},{"key":"S0022481200007246_ref002","volume-title":"Computable structures and the hyperarithmetic hierarchy","author":"Ash","year":"2000"},{"key":"S0022481200007246_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/BF01668470"},{"key":"S0022481200007246_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0001-8708(02)00042-7"},{"key":"S0022481200007246_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00087-2"},{"key":"S0022481200007246_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00059-6"},{"key":"S0022481200007246_ref018","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565670.009"},{"key":"S0022481200007246_ref019","first-page":"210","article-title":"Well quasi-ordering, the tree theorem, and V\u00e1zsonyi's conjecture","volume":"95","author":"Kruskal","year":"1960","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200007246_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(79)90011-1"},{"key":"S0022481200007246_ref028","unstructured":"Nurtazin A. T. , Computable classes and algebraic criteria of autostability, thesis , Mathematical Institute of the Siberian Branch of SSSR Academy of Sciences, Novosibirsk, 1974 (Russian)."},{"key":"S0022481200007246_ref029","first-page":"572","volume":"46","author":"Remmel","year":"1981","journal-title":"Recursive isomorphism types of recursive Boolean algebras"},{"key":"S0022481200007246_ref032","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-98-04307-X"},{"key":"S0022481200007246_ref035","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310066"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T21:15:45Z","timestamp":1556918145000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007246\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["S0022481200007246"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1107298515","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]}}}