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

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

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



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






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


Сиб. электрон. матем. изв., 2020, том 17, страницы 380–394 (Mi semr1218)  

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

The expressiveness of looping terms in the semantic programming

S. Goncharovab, S. Ospichevab, D. Ponomaryovacb, D. Sviridenkoab

a Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
b Novosibirsk State University, 2, Pirogova str., Novosibirsk, 630090, Russia
c Ershov Institute of Informatics Systems, 6, Lavrentyeva ave., Novosibirsk, 630090, Russia

Аннотация: We consider the language of $\Delta_0$-formulas with list terms interpreted over hereditarily finite list superstructures. We study the complexity of reasoning in extensions of the language of $\Delta_0$-formulas with non-standard list terms, which represent bounded list search, bounded iteration, and bounded recursion. We prove a number of results on the complexity of model checking and satisfiability for these formulas. In particular, we show that the set of $\Delta_0$-formulas with bounded recursive terms true in a given list superstructure $HW(\mathcal{M})$ is non-elementary (it contains the class $\mathrm{kExpTime}$, for all $k\geqslant 1$). For $\Delta_0$-formulas with restrictions on the usage of iterative and recursive terms, we show lower complexity.

Ключевые слова: semantic programming, list structures, bounded quantification, reasoning complexity.

Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01176
The authors were supported by the Russian Science Foundation (Grant No. 17-11-01176).


DOI: https://doi.org/10.33048/semi.2020.17.024

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

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

Тип публикации: Статья
УДК: 510.5
MSC: 03D15, 68Q15
Поступила 19 ноября 2019 г., опубликована 10 марта 2020 г.
Язык публикации: английский

Образец цитирования: S. Goncharov, S. Ospichev, D. Ponomaryov, D. Sviridenko, “The expressiveness of looping terms in the semantic programming”, Сиб. электрон. матем. изв., 17 (2020), 380–394

Цитирование в формате AMSBIB
\RBibitem{GonOspPon20}
\by S.~Goncharov, S.~Ospichev, D.~Ponomaryov, D.~Sviridenko
\paper The expressiveness of looping terms in the semantic programming
\jour Сиб. электрон. матем. изв.
\yr 2020
\vol 17
\pages 380--394
\mathnet{http://mi.mathnet.ru/semr1218}
\crossref{https://doi.org/10.33048/semi.2020.17.024}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000518787600001}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr1218
  • http://mi.mathnet.ru/rus/semr/v17/p380

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:164
    Полный текст:97
    Литература:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021