Geodesic
On images of partial computable functions over computable Polish~spaces
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 418-432.

Voir la notice de l'article provenant de la source Math-Net.Ru

This paper is a part of the ongoing program on analysing the complexity of various problems in computable analysis in terms of the effective Borel and Lusin hierarchies. We give an answer to the question by A. Morozov and K. Weihrauch that concerns a characterisation of image complexity of partial computable functions over computable Polish spaces.
Keywords: computable Polish space, partial computable function, computable analysis. 
@article{SEMR_2017_14_a12,
     author = {M. V. Korovina and O. V. Kudinov},
     title = {On images of partial computable functions over computable {Polish~spaces}},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {418--432},
     publisher = {mathdoc},
     volume = {14},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2017_14_a12/}
}
TY  - JOUR
AU  - M. V. Korovina
AU  - O. V. Kudinov
TI  - On images of partial computable functions over computable Polish~spaces
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2017
SP  - 418
EP  - 432
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2017_14_a12/
LA  - en
ID  - SEMR_2017_14_a12
ER  - 
%0 Journal Article
%A M. V. Korovina
%A O. V. Kudinov
%T On images of partial computable functions over computable Polish~spaces
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2017
%P 418-432
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2017_14_a12/
%G en
%F SEMR_2017_14_a12
M. V. Korovina; O. V. Kudinov. On images of partial computable functions over computable Polish~spaces. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 418-432. http://geodesic.mathdoc.fr/item/SEMR_2017_14_a12/

[1] Becher V., Heiber P., Slaman T. A., “Normal numbers and the Borel hierarchy”, Fundamenta Mathematicae, 226:1 (2014), 63–78 | DOI | MR

[2] Brattka V., Gherardi G., “Borel Complexity of Topological Operations on Computable Metric Spaces”, J. Log. Comput., 19:1 (2009), 45–76 | DOI | MR | Zbl

[3] Grubba T., Weihrauch K., “On Computable Metrization”, Electr. Notes Theor. Comput. Sci., 167 (2007), 345–364 | DOI | MR | Zbl

[4] Kechris A. S., Classical Descriptive set theory, Springer-Verlag, New York, 1995 | MR | Zbl

[5] Kolmogorov A. N., Fomin S. V., Elements of the Theory of Functions and Functional Analysis, Dover Publications, 1999 | MR

[6] Korovina M. V., Kudinov O. V., “Complexity for partial computable functions over computable Polish spaces”, Mathematical structure in Computer Science, 2016 (Published online: 19 December 2016) | DOI

[7] Korovina M. V., Kudinov O. V., “Computable Elements and Functions in Effectively Enumerable Topological spaces”, Mathematical structure in Computer Science, 2016 (Published online: 23 June 2016) | DOI

[8] Korovina M. V., Kudinov O. V., “Index sets as a measure of continuous constraints complexity”, Lecture Notes in Computer Science, 8974, 2015, 201–215 | DOI | MR | Zbl

[9] Korovina M. V., Kudinov O. V., “Towards Computability over Effectively Enumerable Topological Spaces”, Electr. Notes Theor. Comput. Sci., 221 (2008), 115–125 | DOI | MR | Zbl

[10] Korovina M. V., Kudinov O. V., “Towards computability of higher type continuous data”, Proc. CiE'05, Lecture Notes in Computer Science, 3526, 2005, 235–241 | DOI | Zbl

[11] Montalban A., Nies A., “Borel structures: a brief survey”, Lecture Notes in Logic, 41, 2013, 124–134 | MR | Zbl

[12] Moschovakis Y. N., Descriptive set theory, North-Holland, Amsterdam, 2009 | MR

[13] Moschovakis Y. N., “Recursive metric spaces”, Fund. Math., 55 (1964), 215–238 | MR | Zbl

[14] Rogers H., Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York, 1967 | MR | Zbl

[15] Soare R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer Science and Business Media, 1987 | MR

[16] Spreen D., “On Effective Topological Spaces”, J. Symb. Log., 63:1 (1998), 185–221 | DOI | MR | Zbl

[17] Selivanov V., “Towards the Effective Descriptive Set Theory”, Lecture Notes in Computer Science, 9136, 2015, 324–333 | DOI | MR | Zbl

[18] Selivanov V., Schr{ö}der M., “Hyperprojective Hierarchy of $qcb_0$-Space”, J. Computability, 4:1 (2014), 1–17 | MR

[19] Weihrauch K., Computable Analysis, Springer Verlag, 2000 | MR | Zbl

[20] Weihrauch K., “Computability on Computable Metric Spaces”, Theor. Comput. Sci., 113:1 (1993), 191–210 | DOI | MR | Zbl