{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T19:47:18Z","timestamp":1648669638648},"reference-count":46,"publisher":"Cambridge University Press (CUP)","issue":"8","license":[{"start":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T00:00:00Z","timestamp":1466640000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>This paper is a part of the ongoing program of analysing the complexity of various problems in computable analysis in terms of the complexity of the associated index sets. In the framework of effectively enumerable topological spaces, we investigate the following question: given an effectively enumerable topological space whether there exists a computable numbering of all its computable elements. We present a natural sufficient condition on the family of basic neighbourhoods of computable elements that guarantees the existence of a principal computable numbering. We show that weakly-effective \u03c9\u2013continuous domains and the natural numbers with the discrete topology satisfy this condition. We prove weak and strong analogues of Rice's theorem for computable elements. Then, we construct principal computable numberings of partial majorant-computable real-valued functions and co-effectively closed sets and calculate the complexity of index sets for important problems such as root verification and function equality. For example, we show that, for partial majorant-computable real functions, the equality problem is \u03a0<jats:sup>1<\/jats:sup><jats:sub>1<\/jats:sub>-complete.<\/jats:p>","DOI":"10.1017\/s0960129516000141","type":"journal-article","created":{"date-parts":[[2016,6,23]],"date-time":"2016-06-23T09:55:53Z","timestamp":1466675753000},"page":"1466-1494","source":"Crossref","is-referenced-by-count":2,"title":["Computable elements and functions in effectively enumerable topological spaces"],"prefix":"10.1017","volume":"27","author":[{"given":"MARGARITA","family":"KOROVINA","sequence":"first","affiliation":[]},{"given":"OLEG","family":"KUDINOV","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,6,23]]},"reference":[{"key":"S0960129516000141_ref39","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1143"},{"key":"S0960129516000141_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2006.08.020"},{"key":"S0960129516000141_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129513000315"},{"key":"S0960129516000141_ref14","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/008\/653176"},{"key":"S0960129516000141_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19730191901"},{"key":"S0960129516000141_ref45","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-65-03247-3"},{"key":"S0960129516000141_ref36","volume-title":"Degrees of Unsolvability","author":"Shoenfield","year":"1971"},{"key":"S0960129516000141_ref40","doi-asserted-by":"publisher","DOI":"10.2307\/2586596"},{"key":"S0960129516000141_ref34","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1967"},{"key":"S0960129516000141_ref30","volume-title":"Notes on Constructive Mathematics","author":"Martin-L\u00f6f","year":"1970"},{"key":"S0960129516000141_ref32","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200710064"},{"key":"S0960129516000141_ref43","volume-title":"Schriften zur Angew. Math. u. Informatik","author":"Weihrauch","year":"1980"},{"key":"S0960129516000141_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(99)80030-5"},{"key":"S0960129516000141_ref33","doi-asserted-by":"publisher","DOI":"10.4064\/fm-55-3-215-238"},{"key":"S0960129516000141_ref46","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0241295-4"},{"key":"S0960129516000141_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00284-9"},{"key":"S0960129516000141_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44683-4_20"},{"key":"S0960129516000141_ref9","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350796"},{"key":"S0960129516000141_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00286-2"},{"key":"S0960129516000141_ref11","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1090\/trans2\/098\/02","article-title":"Mean value theorems in constructive analysis","volume":"98","author":"Ceitin","year":"1971","journal-title":"American Mathematical Society Translations: Series"},{"key":"S0960129516000141_ref44","doi-asserted-by":"publisher","DOI":"10.2307\/2274268"},{"key":"S0960129516000141_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90038-F"},{"key":"S0960129516000141_ref38","first-page":"103","article-title":"On r.e. inseparability of cpo index sets","volume":"171","author":"Spreen","year":"1984","journal-title":"Logic and Machines: Decision Problems and Complexity, Lecture Notes in Computer Science"},{"key":"S0960129516000141_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0960129516000141_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511542725"},{"key":"S0960129516000141_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-008-0065-7"},{"key":"S0960129516000141_ref6","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1294170993"},{"key":"S0960129516000141_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90001-A"},{"key":"S0960129516000141_ref35","first-page":"1","article-title":"Hyperprojective hierarchy of qcb 0-Space","volume":"4","author":"Selivanov","year":"2014","journal-title":"Journal Computability"},{"key":"S0960129516000141_ref15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025971406116"},{"key":"S0960129516000141_ref1","volume-title":"Computable Structures and the Hyperarithmetical Hierarchy","author":"Ash","year":"2000"},{"key":"S0960129516000141_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.12.011"},{"key":"S0960129516000141_ref29","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exn033"},{"key":"S0960129516000141_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2008.06.007"},{"key":"S0960129516000141_ref18","first-page":"455","volume-title":"Logic Colloquium","author":"Ershov","year":"1977"},{"key":"S0960129516000141_ref23","first-page":"1381","article-title":"Elementary computable topology","volume":"15","author":"Grubba","year":"2009","journal-title":"Journal of UCS"},{"key":"S0960129516000141_ref31","first-page":"124","article-title":"Borel structures: A brief survey","volume":"41","author":"Montalban","year":"2013","journal-title":"Lecture Notes in Logic"},{"key":"S0960129516000141_ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56999-9"},{"key":"S0960129516000141_ref2","doi-asserted-by":"publisher","DOI":"10.4064\/fm226-1-4"},{"key":"S0960129516000141_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39813-4_21"},{"key":"S0960129516000141_ref5","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exn027"},{"key":"S0960129516000141_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45220-1_27"},{"key":"S0960129516000141_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00052-3"},{"key":"S0960129516000141_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/11494645_30"},{"key":"S0960129516000141_ref20","first-page":"755","article-title":"Spectra of high n and nonlow n degrees","volume":"22","author":"Frolov","year":"2012","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"S0960129516000141_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10469-006-0029-0"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129516000141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T19:39:45Z","timestamp":1600803585000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129516000141\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,23]]},"references-count":46,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["S0960129516000141"],"URL":"https:\/\/doi.org\/10.1017\/s0960129516000141","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,23]]}}}