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

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

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



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






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


Алгебра и логика, 2022, том 61, номер 1, страницы 42–76
DOI: https://doi.org/10.33048/alglog.2022.61.103
(Mi al2696)
 

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Об индексных множествах для классов позитивных предпорядков

Б. С. Калмурзаевab, Н. А. Баженовc, М. А. Торебековаb

a Казахский нац. ун-т им. аль-Фараби, г. Алма-Ата, КАЗАХСТАН
b Казахстанско-Британский техн. ун-т, г. Алма-Ата, КАЗАХСТАН
c Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ
Список литературы:
Аннотация: Изучается сложность индексных множеств относительно универсальной вычислимой нумерации семейства всех позитивных предпорядков. Пусть $\leq_c$ — вычислимая сводимость на позитивных предпорядках. Для произвольного позитивного предпорядка $R$, такого что $R$-индуцированная эквивалентность $\sim_R$ имеет бесконечно много классов, устанавливаются следующие результаты. Индексное множество предпорядков $P$, таких что $R\leq_c P$, является $\Sigma^0_3$-полным. Предпорядок $R$ называют самополным, если область значений любой вычислимой функции, осуществляющей сводимость $R \leq_c R$, пересекает все $\sim_R$-классы. Если $L$ — позитивный линейный предпорядок, не являющийся самополным, то индексное множество предпорядков $P$, таких что $P\equiv_c L$, является $\Sigma^0_3$-полным. Доказывается, что индексное множество самополных линейных предпорядков является $\Pi^0_3$-полным.
Ключевые слова: позитивный предпорядок, позитивная эквивалентность, позитивный линейный предпорядок, вычислимая сводимость, индексное множество.
Финансовая поддержка Номер гранта
Министерство образования и науки Республики Казахстан AP08856493
Министерство науки и высшего образования Российской Федерации FWNF-2022-0011
Работа выполнена при финансовой поддержке Комитета науки Минобрнауки РК, грант № AP08856493, работа второго из авторов выполнена в рамках гос. задания ИМ СО РАН, проект № FWNF-2022-0011.
Поступило: 28.07.2021
Окончательный вариант: 07.06.2022
Тип публикации: Статья
УДК: 510.5
Образец цитирования: Б. С. Калмурзаев, Н. А. Баженов, М. А. Торебекова, “Об индексных множествах для классов позитивных предпорядков”, Алгебра и логика, 61:1 (2022), 42–76
Цитирование в формате AMSBIB
\RBibitem{KalBazTor22}
\by Б.~С.~Калмурзаев, Н.~А.~Баженов, М.~А.~Торебекова
\paper Об индексных множествах для классов позитивных предпорядков
\jour Алгебра и логика
\yr 2022
\vol 61
\issue 1
\pages 42--76
\mathnet{http://mi.mathnet.ru/al2696}
\crossref{https://doi.org/10.33048/alglog.2022.61.103}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/al2696
  • https://www.mathnet.ru/rus/al/v61/i1/p42
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и логика Algebra and Logic
    Статистика просмотров:
    Страница аннотации:126
    PDF полного текста:42
    Список литературы:23
    Первая страница:6
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024