Сибирские электронные математические известия
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сиб. электрон. матем. изв., 2019, том 16, страницы 1289–1294 (Mi semr1130)  

Математическая логика, алгебра и теория чисел

Генерическая неразрешимость универсальных теорий

А. Н. Рыбаловab

a Omsk State Technical University, 11, Mira ave., Omsk, 644050, Russia
b Sobolev Institute of Mathematics, 13, Pevtsova str., Omsk, 644043, Russia

Аннотация: Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper we study generic complexity of undecidable universal theories. We prove that any undecidable universal theory remains generically undecidable (i.e. for almost all inputs).

Ключевые слова: universal theory, generic complexity.

Финансовая поддержка Номер гранта
Российский научный фонд 19-11-00209
Работа поддержана грантом РНФ № 19-11-00209.


DOI: https://doi.org/10.33048/semi.2019.16.089

Полный текст: PDF файл (136 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.652
MSC: 11U99
Поступила 30 января 2019 г., опубликована 23 сентября 2019 г.

Образец цитирования: А. Н. Рыбалов, “Генерическая неразрешимость универсальных теорий”, Сиб. электрон. матем. изв., 16 (2019), 1289–1294

Цитирование в формате AMSBIB
\RBibitem{Ryb19}
\by А.~Н.~Рыбалов
\paper Генерическая неразрешимость универсальных теорий
\jour Сиб. электрон. матем. изв.
\yr 2019
\vol 16
\pages 1289--1294
\mathnet{http://mi.mathnet.ru/semr1130}
\crossref{https://doi.org/10.33048/semi.2019.16.089}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr1130
  • http://mi.mathnet.ru/rus/semr/v16/p1289

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:108
    Полный текст:68
    Литература:6
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2022