{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:54:22Z","timestamp":1774590862444,"version":"3.50.1"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319500614","type":"print"},{"value":"9783319500621","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,12,1]],"date-time":"2016-12-01T00:00:00Z","timestamp":1480550400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-50062-1_25","type":"book-chapter","created":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T10:09:42Z","timestamp":1480500582000},"page":"418-451","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["A Survey on Universal Computably Enumerable Equivalence Relations"],"prefix":"10.1007","author":[{"given":"Uri","family":"Andrews","sequence":"first","affiliation":[]},{"given":"Serikzhan","family":"Badaev","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Sorbi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,12,1]]},"reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1017\/jsl.2013.8","volume":"79","author":"U Andrews","year":"2014","unstructured":"Andrews, U., Lempp, S., Miller, J.S., Ng, K.M., San Mauro, L., Sorbi, A.: Universal computably enumerable equivalence relations. J. Symbolic Logic 79(1), 60\u201388 (2014)","journal-title":"J. Symbolic Logic"},{"key":"25_CR2","unstructured":"Andrews, U., Sorbi, A.: The complexity of index sets of classes of computably enumerable equivalence relations. J. Symbolic Logic (to appear)"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Andrews, U., Sorbi, A.: Jumps of computably enumerable equivalence relations (2016, in preparation)","DOI":"10.1007\/978-3-319-50062-1_25"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF00972779","volume":"32","author":"S Badaev","year":"1991","unstructured":"Badaev, S.: On weakly precomplete positive equivalences. Siberian Math. J. 32, 321\u2013323 (1991)","journal-title":"Siberian Math. J."},{"issue":"1\u20132","key":"25_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1002\/malq.201500057","volume":"62","author":"S Badaev","year":"2016","unstructured":"Badaev, S., Sorbi, A.: Weakly precomplete computably enumerable equivalence relations. Mat. Log. Quart. 62(1\u20132), 111\u2013127 (2016)","journal-title":"Mat. Log. Quart."},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01837553","volume":"40","author":"C Bernardi","year":"1981","unstructured":"Bernardi, C.: On the relation provable equivalence and on partitions in effectively inseparable sets. Studia Logica 40, 29\u201337 (1981)","journal-title":"Studia Logica"},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"221","DOI":"10.4064\/fm-124-3-221-233","volume":"124","author":"C Bernardi","year":"1984","unstructured":"Bernardi, C., Montagna, F.: Equivalence relations induced by extensional formulae: classifications by means of a new fixed point property. Fund. Math. 124, 221\u2013232 (1984)","journal-title":"Fund. Math."},{"issue":"3","key":"25_CR8","doi-asserted-by":"publisher","first-page":"529","DOI":"10.2307\/2273443","volume":"48","author":"C Bernardi","year":"1983","unstructured":"Bernardi, C., Sorbi, A.: Classifying positive equivalence relations. J. Symbolic Logic 48(3), 529\u2013538 (1983)","journal-title":"J. Symbolic Logic"},{"key":"25_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/malq.19610071108","volume":"7","author":"JP Cleave","year":"1961","unstructured":"Cleave, J.P.: Creative functions. Z. Math. Logik Grundlag. Math. 7, 205\u2013212 (1961)","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"25_CR10","volume-title":"Computability Theory","author":"SB Cooper","year":"2003","unstructured":"Cooper, S.B.: Computability Theory. Chapman & Hall\/CRC Mathematics, Boca Raton, London, New York, Washington, DC (2003)"},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"15","DOI":"10.3233\/COM-2012-004","volume":"1","author":"S Coskey","year":"2012","unstructured":"Coskey, S., Hamkins, J.D., Miller, R.: The hierarchy of equivalence relations on the natural numbers. Computability 1, 15\u201338 (2012)","journal-title":"Computability"},{"issue":"6","key":"25_CR12","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/BF02218645","volume":"10","author":"YL Ershov","year":"1973","unstructured":"Ershov, Y.L.: Positive equivalences. Algebra Logic 10(6), 378\u2013394 (1973)","journal-title":"Algebra Logic"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/malq.19730191901","volume":"19","author":"YL Ershov","year":"1973","unstructured":"Ershov, Y.L.: Theorie der Numerierungen I. Z. Math. Logik Grundlag. Math. 19, 289\u2013388 (1973)","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/malq.19750210164","volume":"19","author":"YL Ershov","year":"1975","unstructured":"Ershov, Y.L.: Theorie der Numerierungen II. Z. Math. Logik Grundlag. Math. 19, 473\u2013584 (1975)","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"25_CR15","unstructured":"Fokina, E., Khoussainov, B., Semukhin, P., Turetsky, D.: Linear orders realized by c.e. equivalence relations. J. Symbolic Logic (to appear)"},{"key":"25_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-3-642-32621-9_2","volume-title":"Logic, Language, Information and Computation","author":"E Fokina","year":"2012","unstructured":"Fokina, E., Friedman, S., Nies, A.: Equivalence relations that are $$\\Sigma ^0_3$$ complete for computable reducibility. In: Ong, L., Queiroz, R. (eds.) WoLLIC 2012. LNCS, vol. 7456, pp. 26\u201333. Springer Berlin Heidelberg, Berlin, Heidelberg (2012). doi:10.1007\/978-3-642-32621-9_2"},{"issue":"1","key":"25_CR17","doi-asserted-by":"publisher","first-page":"122","DOI":"10.2178\/jsl\/1327068695","volume":"77","author":"EB Fokina","year":"2012","unstructured":"Fokina, E.B., Friedman, S.D., Harizanov, V., Knight, J.F., McCoy, C., Montalb\u00e1n, A.: Isomorphism relations on computable structures. J. Symbolic Logic 77(1), 122\u2013132 (2012)","journal-title":"J. Symbolic Logic"},{"key":"25_CR18","unstructured":"Friedman, H.: Proof-theoretic degrees (Unpublished)"},{"key":"25_CR19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1023\/A:1010521410739","volume":"67","author":"S Gao","year":"2001","unstructured":"Gao, S., Gerdes, P.: Computably enumerable equivalence realations. Studia Logica 67, 27\u201359 (2001)","journal-title":"Studia Logica"},{"issue":"7\u20138","key":"25_CR20","first-page":"1263","volume":"165","author":"A Gravuskin","year":"2014","unstructured":"Gravuskin, A., Jain, S., Khoussainov, A., Stephan, F.: Graphs realized by r.e. equivalence relations. Ann. Pure Appl. Logic 165(7\u20138), 1263\u20131290 (2014)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"25","key":"25_CR21","first-page":"137","volume":"612","author":"A Gravuskin","year":"2016","unstructured":"Gravuskin, A., Khoussainov, A., Stephan, F.: Reducibilities among equivalence relations induced by recursively enumerable structures. Theoret. Comput. Sci. 612(25), 137\u2013152 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"25_CR22","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1002\/malq.19870330106","volume":"33","author":"AH Lachlan","year":"1987","unstructured":"Lachlan, A.H.: A note on positive equivalence relations. Z. Math. Logik Grundlag. Math. 33, 43\u201346 (1987)","journal-title":"Z. Math. Logik Grundlag. Math."},{"issue":"2","key":"25_CR23","first-page":"4","volume":"2","author":"AI Mal\u2019tsev","year":"1963","unstructured":"Mal\u2019tsev, A.I.: Sets with complete numberings. Algebra i Logika 2(2), 4\u201329 (1963)","journal-title":"Algebra i Logika"},{"key":"25_CR24","series-title":"Annals of Mathematics Studies","volume-title":"On Group-Theoretic Decision Problems and Their Classification","author":"CF Miller III","year":"1971","unstructured":"Miller III, C.F.: On Group-Theoretic Decision Problems and Their Classification. Annals of Mathematics Studies. Princeton University Press, Princeton (1971)"},{"key":"25_CR25","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF00284977","volume":"11","author":"F Montagna","year":"1982","unstructured":"Montagna, F.: Relative precomplete numerations and arithmetic. J. Philos. Logic 11, 419\u2013430 (1982)","journal-title":"J. Philos. Logic"},{"key":"25_CR26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/malq.19550010205","volume":"1","author":"J Myhill","year":"1955","unstructured":"Myhill, J.: Creative sets. Z. Math. Logik Grundlag. Math. 1, 97\u2013108 (1955)","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Nies, A., Sorbi, A.: Calibrating word problems of groups via the complexity of equivalence relations. Math. Structures Comput. Sci. (2016, to apper)","DOI":"10.1017\/S0960129516000335"},{"key":"25_CR28","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H Rogers Jr","year":"1967","unstructured":"Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)"},{"key":"25_CR29","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1002\/malq.19960420107","volume":"42","author":"VY Shavrukov","year":"1996","unstructured":"Shavrukov, V.Y.: Remarks on uniformly finitely positive equivalences. Math. Log. Quart. 42, 67\u201382 (1996)","journal-title":"Math. Log. Quart."},{"key":"25_CR30","series-title":"Annals of Mathematical Studies","doi-asserted-by":"crossref","DOI":"10.1515\/9781400882007","volume-title":"Theory of Formal Systems","author":"R Smullyan","year":"1961","unstructured":"Smullyan, R.: Theory of Formal Systems. Annals of Mathematical Studies, vol. 47. Princeton University Press, Princeton (1961)"},{"key":"25_CR31","series-title":"Perspectives in Mathematical Logic, Omega Series","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"RI Soare","year":"1987","unstructured":"Soare, R.I.: Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series. Springer, Heidelberg (1987)"},{"key":"25_CR32","first-page":"259","volume-title":"To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism","author":"A Visser","year":"1980","unstructured":"Visser, A.: Numerations, $$\\lambda $$-calculus & arithmetic. In: Seldin, J.P., Hindley, J.R. (eds.) To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, pp. 259\u2013284. Academic Press, London (1980)"}],"container-title":["Lecture Notes in Computer Science","Computability and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-50062-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:57:44Z","timestamp":1709830664000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-50062-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,1]]},"ISBN":["9783319500614","9783319500621"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-50062-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,1]]},"assertion":[{"value":"1 December 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}