{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:39:51Z","timestamp":1777516791668,"version":"3.51.4"},"reference-count":33,"publisher":"SAGE Publications","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["COM"],"published-print":{"date-parts":[[2019,9,20]]},"DOI":"10.3233\/com-180100","type":"journal-article","created":{"date-parts":[[2018,10,2]],"date-time":"2018-10-02T14:26:30Z","timestamp":1538490390000},"page":"265-280","source":"Crossref","is-referenced-by-count":4,"title":["Measuring the complexity of reductions between equivalence relations"],"prefix":"10.1177","volume":"8","author":[{"given":"Ekaterina","family":"Fokina","sequence":"first","affiliation":[{"name":"Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. ekaterina.fokina@tuwien.ac.at"}]},{"given":"Dino","family":"Rossegger","sequence":"additional","affiliation":[{"name":"Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. dino.rossegger@tuwien.ac.at"}]},{"given":"Luca","family":"San Mauro","sequence":"additional","affiliation":[{"name":"Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Austria. luca.san.mauro@tuwien.ac.at"}]}],"member":"179","reference":[{"key":"10.3233\/COM-180100_ref1","doi-asserted-by":"crossref","unstructured":"U.\u00a0Andrews, S.\u00a0Badaev and A.\u00a0Sorbi, A survey on universal computably enumerable equivalence relations, in: Computability and Complexity. Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Springer, 2017, pp.\u00a0418\u2013451.","DOI":"10.1007\/978-3-319-50062-1_25"},{"issue":"3","key":"10.3233\/COM-180100_ref2","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1017\/jsl.2015.59","article-title":"The complements of lower cones of degrees and the degree spectra of structures","volume":"81","author":"Andrews","year":"2016","journal-title":"The Journal of Symbolic Logic"},{"issue":"01","key":"10.3233\/COM-180100_ref3","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1017\/jsl.2013.8","article-title":"Universal computably enumerable equivalence relations","volume":"79","author":"Andrews","year":"2014","journal-title":"The Journal of Symbolic Logic"},{"issue":"3","key":"10.3233\/COM-180100_ref4","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1090\/S0002-9939-2014-12283-0","article-title":"Spectra of theories and structures","volume":"143","author":"Andrews","year":"2015","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"1","key":"10.3233\/COM-180100_ref6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01837553","article-title":"On the relation provable equivalence and on partitions in effectively inseparable sets","volume":"40","author":"Bernardi","year":"1981","journal-title":"Studia Logica"},{"issue":"03","key":"10.3233\/COM-180100_ref7","doi-asserted-by":"publisher","first-page":"529","DOI":"10.2307\/2273443","article-title":"Classifying positive equivalence relations","volume":"48","author":"Bernardi","year":"1983","journal-title":"The Journal of Symbolic Logic"},{"issue":"6","key":"10.3233\/COM-180100_ref8","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1023\/B:ALLO.0000048827.30718.2c","article-title":"Comparing classes of finite structures","volume":"43","author":"Calvert","year":"2004","journal-title":"Algebra and Logic"},{"issue":"11\u201314","key":"10.3233\/COM-180100_ref9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/malq.19610071108","article-title":"Creative functions","volume":"7","author":"Cleave","year":"1961","journal-title":"Mathematical Logic Quarterly"},{"issue":"1","key":"10.3233\/COM-180100_ref10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.3233\/COM-2012-004","article-title":"The hierarchy of equivalence relations on the natural numbers under computable reducibility","volume":"1","author":"Coskey","year":"2012","journal-title":"Computability"},{"key":"10.3233\/COM-180100_ref11","unstructured":"Y.L.\u00a0Ershov, Teoriya Numeratsii, Nauka, 1977."},{"key":"10.3233\/COM-180100_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(99)80030-5"},{"key":"10.3233\/COM-180100_ref13","unstructured":"E.\u00a0Fokina, D.\u00a0Rossegger and L.\u00a0San Mauro, Degree spectra of structures with respect to the bi-embeddability relation, in: Proceedings of the 11th Panhellenic Logic Symposium, 2017, pp.\u00a032\u201338."},{"issue":"01","key":"10.3233\/COM-180100_ref15","doi-asserted-by":"publisher","first-page":"122","DOI":"10.2178\/jsl\/1327068695","article-title":"Isomorphism relations on computable structures","volume":"77","author":"Fokina","year":"2012","journal-title":"The Journal of Symbolic Logic"},{"issue":"7","key":"10.3233\/COM-180100_ref16","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1016\/j.apal.2009.10.002","article-title":"The effective theory of Borel equivalence relations","volume":"161","author":"Fokina","year":"2010","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"10.3233\/COM-180100_ref17","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00153-009-0160-4","article-title":"Degrees of categoricity of computable structures","volume":"49","author":"Fokina","year":"2010","journal-title":"Archive for Mathematical Logic"},{"issue":"03","key":"10.3233\/COM-180100_ref18","doi-asserted-by":"publisher","first-page":"894","DOI":"10.2307\/2274750","article-title":"A Borel reducibility theory for classes of countable structures","volume":"54","author":"Friedman","year":"1989","journal-title":"The Journal of Symbolic Logic"},{"key":"10.3233\/COM-180100_ref19","doi-asserted-by":"crossref","unstructured":"S.\u00a0Gao, Invariant Descriptive Set Theory, CRC Press, 2008.","DOI":"10.1201\/9781584887942"},{"issue":"1","key":"10.3233\/COM-180100_ref20","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1023\/A:1010521410739","article-title":"Computably enumerable equivalence relations","volume":"67","author":"Gao","year":"2001","journal-title":"Studia Logica"},{"issue":"1","key":"10.3233\/COM-180100_ref21","doi-asserted-by":"publisher","first-page":"324","DOI":"10.2178\/jsl\/1174668398","article-title":"Spectra of structures and relations","volume":"72","author":"Harizanov","year":"2007","journal-title":"The Journal of Symbolic Logic"},{"issue":"4","key":"10.3233\/COM-180100_ref22","doi-asserted-by":"crossref","first-page":"521","DOI":"10.2307\/2271359","article-title":"Uniformly introreducible sets","volume":"33","author":"Jockusch","year":"1968","journal-title":"The Journal of Symbolic Logic"},{"key":"10.3233\/COM-180100_ref23","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1090\/S0002-9947-1972-0316227-0","article-title":"\u03a0 1 0 classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"issue":"10","key":"10.3233\/COM-180100_ref24","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1070\/SM2008v199n10ABEH003967","article-title":"Almost computably enumerable families of sets","volume":"199","author":"Kalimullin","year":"2008","journal-title":"Sbornik: Mathematics"},{"key":"10.3233\/COM-180100_ref25","unstructured":"V.G.\u00a0Kanoveui, Borel Equivalence Relations: Structure and Classification, Vol.\u00a044, American Mathematical Soc., 2008."},{"key":"10.3233\/COM-180100_ref26","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.2307\/2273915","article-title":"Degrees coded in jumps of orderings","volume":"51","author":"Knight","year":"1986","journal-title":"The Journal of Symbolic Logic"},{"key":"10.3233\/COM-180100_ref27","doi-asserted-by":"crossref","unstructured":"C.F.\u00a0Miller III, On Group-Theoretic Decision Problems and Their Classification. (AM-68), Vol.\u00a068, Princeton University Press, 1971.","DOI":"10.1515\/9781400881789"},{"issue":"4","key":"10.3233\/COM-180100_ref28","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1017\/jsl.2016.23","article-title":"Finitary reducibility on equivalence relations","volume":"81","author":"Miller","year":"2016","journal-title":"The Journal of Symbolic Logic"},{"issue":"4","key":"10.3233\/COM-180100_ref29","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF00284977","article-title":"Relatively precomplete numerations and arithmetic","volume":"11","author":"Montagna","year":"1982","journal-title":"Journal of Philosophical Logic"},{"key":"10.3233\/COM-180100_ref31","doi-asserted-by":"publisher","first-page":"723","DOI":"10.2307\/2273222","article-title":"Degrees of structures","volume":"46","author":"Richter","year":"1981","journal-title":"The Journal of Symbolic Logic"},{"key":"10.3233\/COM-180100_ref32","doi-asserted-by":"crossref","unstructured":"D.\u00a0Rossegger, Elementary bi-embeddability spectra of structures, in: Sailing Routes in the World of Computation, Lecture Notes in Computer Science, Springer, 2018. Forthcoming.","DOI":"10.1007\/978-3-319-94418-0_35"},{"key":"10.3233\/COM-180100_ref33","doi-asserted-by":"crossref","unstructured":"R.M.\u00a0Smullyan, Theory of Formal Systems, Princeton University Press, 1961.","DOI":"10.1515\/9781400882007"},{"key":"10.3233\/COM-180100_ref34","doi-asserted-by":"crossref","unstructured":"R.I.\u00a0Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Heidelberg, 1987.","DOI":"10.1007\/978-3-662-02460-7"},{"key":"10.3233\/COM-180100_ref35","first-page":"45","article-title":"Degree spectra and co-spectra of structures","volume":"96","author":"Soskov","year":"2004","journal-title":"Annuaire Univ. Sofia Fac. Math. Inform."},{"key":"10.3233\/COM-180100_ref36","unstructured":"A.\u00a0Visser, Numerations, \u03bb-calculus and arithmetic, in: To HB Curry: Essays on Combinatory Logic, Lambda-Calculus and Formalism, Academic Press, New York, 1980, pp.\u00a0259\u2013284."}],"container-title":["Computability"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/COM-180100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:00:02Z","timestamp":1777392002000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180100"}},"subtitle":[],"editor":[{"given":"Vasco","family":"Brattka","sequence":"additional","affiliation":[]},{"given":"Rod","family":"Downey","sequence":"additional","affiliation":[]},{"given":"Julia F.","family":"Knight","sequence":"additional","affiliation":[]},{"given":"Steffen","family":"Lempp","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,9,20]]},"references-count":33,"journal-issue":{"issue":"3-4"},"URL":"https:\/\/doi.org\/10.3233\/com-180100","relation":{},"ISSN":["2211-3576","2211-3568"],"issn-type":[{"value":"2211-3576","type":"electronic"},{"value":"2211-3568","type":"print"}],"subject":[],"published":{"date-parts":[[2019,9,20]]}}}