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

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

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



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






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


Изв. АН СССР. Сер. матем., 1991, том 55, выпуск 2, страницы 227–253 (Mi izv1008)  

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

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

В. К. Булитко


Аннотация: Традиционный путь построения критериев полноты по сводимости – описание свойства ослабленной, вообще говоря, продуктивности дополнения полного по данной сводимости множества. Это свойство своим происхождением обязано сведению к полному множеству креативного множества. Такой путь апеллирует непосредственно к универсальности креативного множества в классе всех рекурсивно перечислимых.
Однако для ряда сводимостей полноту рекурсивно перечислимого множества можно констатировать на основе факта сведения к нему множества степени ниже степени креативного множества. Такое пробное множество, конечно, не рекурсивно перечислимо. При этом место свойства эффективной не рекурсивной перечислимости, как у продуктивно- го множества, могут занимать варианты свойства диагональной нерекурсивности, но не для всех сводимостей.
В статье рассматривается связь этих двух подходов, в частности, связь различных ослаблений свойства продуктивности с диагональной нерекурсивностью, и результаты, получаемые этими способами для тьюринговых и табличных сводимостей.

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

Англоязычная версия:
Mathematics of the USSR-Izvestiya, 1992, 38:2, 225–249

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

УДК: 517.11+518.5
MSC: 03D25
Поступило в редакцию: 27.12.1988

Образец цитирования: В. К. Булитко, “О способах характеризации полных множеств”, Изв. АН СССР. Сер. матем., 55:2 (1991), 227–253; Math. USSR-Izv., 38:2 (1992), 225–249

Цитирование в формате AMSBIB
\RBibitem{Bul91}
\by В.~К.~Булитко
\paper О способах характеризации полных множеств
\jour Изв. АН СССР. Сер. матем.
\yr 1991
\vol 55
\issue 2
\pages 227--253
\mathnet{http://mi.mathnet.ru/izv1008}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1133297}
\zmath{https://zbmath.org/?q=an:0743.03032}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?1992IzMat..38..225B}
\transl
\jour Math. USSR-Izv.
\yr 1992
\vol 38
\issue 2
\pages 225--249
\crossref{https://doi.org/10.1070/IM1992v038n02ABEH002197}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=A1992HR86300001}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/izv1008
  • http://mi.mathnet.ru/rus/izv/v55/i2/p227

    ОТПРАВИТЬ: 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
    Исправления

    Эта публикация цитируется в следующих статьяx:
    1. В. К. Булитко, “Письмо в редакцию”, Изв. РАН. Сер. матем., 56:4 (1992), 907–907  mathnet  mathscinet  zmath  adsnasa; V. K. Bulitko, “Letter to the editor”, Russian Acad. Sci. Izv. Math., 41:1 (1993), 185–185  crossref
    2. Р. Ш. Оманадзе, “Сложностные свойства рекурсивно перечислимых множеств и $sQ$-полнота”, Матем. заметки, 62:3 (1997), 425–429  mathnet  crossref  mathscinet  zmath; R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $sQ$-completeness”, Math. Notes, 62:3 (1997), 356–359  crossref  isi
    3. Р. Ш. Оманадзе, “Сложностные свойства рекурсивно перечислимых множеств и $bsQ$-полнота”, Матем. заметки, 68:4 (2000), 554–559  mathnet  crossref  mathscinet  zmath; R. Sh. Omanadze, “Complexity properties of recursively enumerable sets and $bsQ$-completeness”, Math. Notes, 68:4 (2000), 476–480  crossref  isi
  • Известия Академии наук СССР. Серия математическая Izvestiya: Mathematics
    Просмотров:
    Эта страница:144
    Полный текст:58
    Литература:23
    Первая стр.:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019