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

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

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


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




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

Сибирский математический журнал, 2009, том 50, номер 2, страницы 243–249 (Mi smj1953)  
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

О полиномиальных ограничениях сложностей выводов в системах Фреге

С. Р. Алексанянa, А. А. Чубарянb

a Факультет прикладной математики ГИУА, г. Ереван, Армения
b Факультет информатики и прикладной математики ЕГУ, г. Ереван, Армения
PDF полного текста (299 kB) Список цитирования (3)
Список литературы:
PDF
HTML
Аннотация: Ранее одним из авторов было введено понятие определяющего множества переменных пропозициональной формулы, позволившее выделить множество трудноопределяемых тавтологий, сложности выводов которых в ряде систем доказательств классического исчисления высказываний (секвенциальной системе без правила сечения, системе резолюций, системе, основанной на методе расщепления, системе неравенств “Cutting planes”, ограниченных системах Фреге) оцениваются снизу экспонентой от длины выводимой формулы. В настоящей работе доказывается, что для получения суперполиномиальной нижней оценки шагов (длины) выводов в системах Фреге наличия свойства трудноопределяемости недостаточно: приводится пример последовательности трудноопределяемых формул, имеющих полиномиально ограниченные сложности выводов в любой системе Фреге.
Ключевые слова: сложность вывода, система Фреге, определяющий конъюнкт, определяющее множество переменных пропозициональной формулы, трудноопределяемая формула.
Статья поступила: 02.02.2008
Окончательный вариант: 08.10.2008
Англоязычная версия:
Siberian Mathematical Journal, 2009, Volume 50, Issue 2, Pages 193–198
DOI: https://doi.org/10.1007/s11202-009-0022-7
Реферативные базы данных:
УДК: 510.64
Образец цитирования: С. Р. Алексанян, А. А. Чубарян, “О полиномиальных ограничениях сложностей выводов в системах Фреге”, Сиб. матем. журн., 50:2 (2009), 243–249; Siberian Math. J., 50:2 (2009), 193–198
Цитирование в формате AMSBIB
\RBibitem{AleChu09}
\by С.~Р.~Алексанян, А.~А.~Чубарян
\paper О полиномиальных ограничениях сложностей выводов в~системах Фреге
\jour Сиб. матем. журн.
\yr 2009
\vol 50
\issue 2
\pages 243--249
\mathnet{http://mi.mathnet.ru/smj1953}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2531750}
\transl
\jour Siberian Math. J.
\yr 2009
\vol 50
\issue 2
\pages 193--198
\crossref{https://doi.org/10.1007/s11202-009-0022-7}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000265386500001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-65349118156}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/smj1953
  • https://www.mathnet.ru/rus/smj/v50/i2/p243
    • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Сибирский математический журнал Siberian Mathematical Journal
    Статистика просмотров:
    Страница аннотации:349
    PDF полного текста:90
    Список литературы:62
    Первая страница:1
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024