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

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

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


Докл. РАН. Матем., информ., проц. упр.:
Год:
Том:
Выпуск:
Страница:
Найти




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

Доклады Российской академии наук. Математика, информатика, процессы управления, 2022, том 507, страницы 61–65
DOI: https://doi.org/10.31857/S2686954322600501 (Mi danma320) 		 
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

МАТЕМАТИКА

Алгоритмическая сложность теорий бинарного предиката в языках с малым числом переменных

М. Рыбаков

Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Москва, Россия
Список цитирования (2)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.31857/S2686954322600501
Аннотация: Доказана Σ01-трудность различных теорий бинарного предиката в языке с тремя предметными переменными и бинарной предикатной буквой (без констант и равенства). Показано, что при добавлении равенства, композиции и транзитивного замыкания получаются Π11-трудные теории бинарного предиката при двух предметных переменных в языке.
Ключевые слова: классическая логика предикатов, диадическая логика, неразрешимость, теорема Чёрча, теорема Трахтенброта.
Финансовая поддержка Номер гранта
Российский научный фонд 21-18-00195
Исследования выполнены в ИППИ РАН при финансовой поддержке Российского научного фонда, грант 21-18-00195.
Статья представлена к публикации: А. Л. Семёнов
Поступило: 07.08.2022
После доработки: 19.09.2022
Принято к публикации: 23.09.2022
Англоязычная версия:
Doklady Mathematics, 2022, Volume 106, Issue 3
DOI: https://doi.org/10.1134/S1064562422700053
Реферативные базы данных:
Тип публикации: Статья
УДК: 510.635, 510.665
Образец цитирования: М. Рыбаков, “Алгоритмическая сложность теорий бинарного предиката в языках с малым числом переменных”, Докл. РАН. Матем., информ., проц. упр., 507 (2022), 61–65
Цитирование в формате AMSBIB
\RBibitem{Ryb22}
\by М.~Рыбаков
\paper Алгоритмическая сложность теорий бинарного предиката в языках с малым числом переменных
\jour Докл. РАН. Матем., информ., проц. упр.
\yr 2022
\vol 507
\pages 61--65
\mathnet{http://mi.mathnet.ru/danma320}
\crossref{https://doi.org/10.31857/S2686954322600501}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4563848}
\elib{https://elibrary.ru/item.asp?id=49991286}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/danma320
  • https://www.mathnet.ru/rus/danma/v507/p61
    Исправления
    Эта публикация цитируется в следующих 2 статьяx:
    1. Mikhail Rybakov, Dmitry Shkatov, “Variations on the Kripke Trick”, Stud Logica, 2024  crossref
    2. М. Н. Рыбаков, “Деревья как средство моделирования неразрешимых проблем”, Вестник ТвГУ. Серия: Прикладная математика, 2023, № 1, 5–23  mathnet  crossref  elib
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Доклады Российской академии наук. Математика, информатика, процессы управления Доклады Российской академии наук. Математика, информатика, процессы управления
    Статистика просмотров:
    Страница аннотации:95
    Список литературы:30
     
      Обратная связь:
    math-net2025_04@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025