Computable Topology for Reliable Computations

Margarita Korovina, Oleg Kudinov

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

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.

Язык оригиналаанглийский
Название основной публикации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
Страницы185-198
Число страниц14
ISBN (печатное издание)9783030374860
DOI
СостояниеОпубликовано - 1 янв 2019
Событие12th International Andrei P. Ershov Informatics Conference, PSI 2019 - Novosibirsk, Российская Федерация
Продолжительность: 2 июл 20195 июл 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11964 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция12th International Andrei P. Ershov Informatics Conference, PSI 2019
СтранаРоссийская Федерация
ГородNovosibirsk
Период02.07.201905.07.2019

Fingerprint Подробные сведения о темах исследования «Computable Topology for Reliable Computations». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Korovina, M., & Kudinov, O. (2019). Computable Topology for Reliable Computations. В N. Bjørner, I. Virbitskaite, & A. Voronkov (Ред.), Perspectives of System Informatics - 12th International Andrei P. Ershov Informatics Conference, PSI 2019, Revised Selected Papers (стр. 185-198). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11964 LNCS). Springer International Publishing AG. https://doi.org/10.1007/978-3-030-37487-7_15