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

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

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


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




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

Сибирские электронные математические известия, 2018, том 15, страницы 987–995
DOI: https://doi.org/10.17377/semi.2018.15.083 (Mi semr973) 		 
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)

Математическая логика, алгебра и теория чисел

On the complexity of formulas in semantic programming

S. Ospichevab, D. Ponomarevabc

a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Novosibirsk State University, Pirogova, 2, 630090, Novosibirsk, Russia
c A.P. Ershov Institute of Informatics Systems, pr. Lavrentyeva, 6, 630090, Novosibirsk, Russia
PDF полного текста (150 kB) Список цитирования (8)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.17377/semi.2018.15.083
Аннотация: We consider the complexity of $\Delta_0$ formulas augmented with conditional terms. We show that for formulas having $n$ bounded quantifiers, for a fixed $n$, deciding the truth in a list superstructure with polynomial computable basic operations is of polynomial complexity. When the quantifier prefix has $n$ alternations of quantifiers, the truth problem is complete for the $n$-th level of the polynomial-time hierarchy. Under no restrictions on the quantifier prefix the truth problem is PSPACE-complete. Thus, the complexity results indicate the analogy between the truth problem for $\Delta_0$ formulas with conditional terms and the truth problem for quantified boolean formulas.
Ключевые слова: semantic programming, list structures, polynomial time/space complexity, $\Delta_0$-formulas.
Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01176
The authors were supported by the Russian Science Foundation (Grant No. 17-11-01176).
Поступила 28 июня 2018 г., опубликована 10 сентября 2018 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 510.5
MSC: 03D15, 68Q15
Язык публикации: английский
Образец цитирования: S. Ospichev, D. Ponomarev, “On the complexity of formulas in semantic programming”, Сиб. электрон. матем. изв., 15 (2018), 987–995
Цитирование в формате AMSBIB
\RBibitem{OspPon18}
\by S.~Ospichev, D.~Ponomarev
\paper On the complexity of formulas in semantic programming
\jour Сиб. электрон. матем. изв.
\yr 2018
\vol 15
\pages 987--995
\mathnet{http://mi.mathnet.ru/semr973}
\crossref{https://doi.org/10.17377/semi.2018.15.083}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000454860200025}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr973
  • https://www.mathnet.ru/rus/semr/v15/p987
    • Эта публикация цитируется в следующих 8 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:279
    PDF полного текста:71
    Список литературы:33
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024