Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Computable Topology for Reliable Computations. / Korovina, Margarita; Kudinov, Oleg.
Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers. ред. / Nikolaj Bjørner; Irina Virbitskaite; Andrei Voronkov. Springer International Publishing AG, 2019. стр. 185-198 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11964 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Computable Topology for Reliable Computations
AU - Korovina, Margarita
AU - Kudinov, Oleg
N1 - Publisher Copyright: © Springer Nature Switzerland AG 2019. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2019/1/1
Y1 - 2019/1/1
N2 - Using the framework of computable topology we investigate computable minimality of lifted domain presentations of computable Polish spaces, in particular the real numbers, the Cantor and Baire spaces, the continuous functions on a compact interval, which are widely used in theoretical computer science, e.g., automata theory, computable analysis and reliable computations. We prove that all lifted domain presentations for computable Polish spaces are computably and topologically minimal. Then we show that a naive adaptation of the notion of stability from computable model theory does not work in this framework. Instead of stability we propose another approach based on principal translators and prove that in the case of the real numbers we can effectively construct a principal computable translator from the lifted domain presentation to any other effective domain presentation.
AB - Using the framework of computable topology we investigate computable minimality of lifted domain presentations of computable Polish spaces, in particular the real numbers, the Cantor and Baire spaces, the continuous functions on a compact interval, which are widely used in theoretical computer science, e.g., automata theory, computable analysis and reliable computations. We prove that all lifted domain presentations for computable Polish spaces are computably and topologically minimal. Then we show that a naive adaptation of the notion of stability from computable model theory does not work in this framework. Instead of stability we propose another approach based on principal translators and prove that in the case of the real numbers we can effectively construct a principal computable translator from the lifted domain presentation to any other effective domain presentation.
KW - Computable analysis
KW - Computable topology
KW - Lifted domain presentation
KW - Reliable computation
UR - http://www.scopus.com/inward/record.url?scp=85077496870&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-37487-7_15
DO - 10.1007/978-3-030-37487-7_15
M3 - Conference contribution
AN - SCOPUS:85077496870
SN - 9783030374860
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 185
EP - 198
BT - Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers
A2 - Bjørner, Nikolaj
A2 - Virbitskaite, Irina
A2 - Voronkov, Andrei
PB - Springer International Publishing AG
T2 - 12th International Andrei P. Ershov Informatics Conference, PSI 2019
Y2 - 2 July 2019 through 5 July 2019
ER -
ID: 23144482