Computable Topology for Reliable Computations | Sciact - Система учета научной деятельности ИМ СО РАН

Computable Topology for Reliable Computations Научная публикация

Журнал

Lecture Notes in Computer Science
ISSN: 0302-9743 , E-ISSN: 1611-3349

Вых. Данные

Год: 2019, Том: 11964 LNCS, Страницы: 185-198 Страниц : 14 DOI: 10.1007/978-3-030-37487-7_15

Ключевые слова

Computable analysis; Computable topology; Lifted domain presentation; Reliable computation

Авторы

Korovina M. ¹ , Kudinov O. ^2,3

Организации

1	A.P. Ershov Institute of Informatics Systems, SbRAS, Novosibirsk, Russian Federation
2	Sobolev Institute of Mathematics
3	Novosibirsk State University, Novosibirsk, Russian Federation

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. © Springer Nature Switzerland AG 2019.

Korovina M. , Kudinov O.
Computable Topology for Reliable Computations
Lecture Notes in Computer Science. 2019. V.11964 LNCS. P.185-198. DOI: 10.1007/978-3-030-37487-7_15 Scopus OpenAlex

Scopus:	2-s2.0-85077496870
OpenAlex:	W2996082684

Пока нет цитирований