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

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

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


Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти




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

Записки научных семинаров ПОМИ, 2004, том 316, страницы 147–162 (Mi znsl730)  
Новый разрешимый хорновский фрагмент исчисления предикатов

В. П. Оревков

Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН
PDF полного текста (202 kB)
Список литературы:
PDF
HTML
Аннотация: В работе описано расширение хорновского варианта класса формул $\forall\exists$. Для секвенций из этого класса доказана разрешимость проблемы выводимости в исчислении предикатов. Найдены сложностные характеристики, фиксация которых разбивает это расширение на полиномиально разрешимые подклассы. Фиксация максимальной размерности предикатов разбивает рассматриваемое расширение на подклассы, принадлежащие NP. Библ. – 11 назв.
Поступило: 02.12.2004
Англоязычная версия:
Journal of Mathematical Sciences (New York), 2006, Volume 134, Issue 5, Pages 2403–2410
DOI: https://doi.org/10.1007/s10958-006-0117-7
Реферативные базы данных:
УДК: 510.635+510.57
Образец цитирования: В. П. Оревков, “Новый разрешимый хорновский фрагмент исчисления предикатов”, Теория сложности вычислений. IX, Зап. научн. сем. ПОМИ, 316, ПОМИ, СПб., 2004, 147–162; J. Math. Sci. (N. Y.), 134:5 (2006), 2403–2410
Цитирование в формате AMSBIB
\RBibitem{Ore04}
\by В.~П.~Оревков
\paper Новый разрешимый хорновский фрагмент исчисления предикатов
\inbook Теория сложности вычислений.~IX
\serial Зап. научн. сем. ПОМИ
\yr 2004
\vol 316
\pages 147--162
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl730}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2113062}
\zmath{https://zbmath.org/?q=an:1088.03011}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2006
\vol 134
\issue 5
\pages 2403--2410
\crossref{https://doi.org/10.1007/s10958-006-0117-7}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl730
  • https://www.mathnet.ru/rus/znsl/v316/p147
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Записки научных семинаров ПОМИ
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024