Структуры, вычислимые за полиномиальное время. II | Sciact - Система учета научной деятельности ИМ СО РАН

Структуры, вычислимые за полиномиальное время. II Научная публикация

Журнал

Алгебра и логика
ISSN: 0373-9252

Вых. Данные

Год: 2017, Том: 56, Номер: 6, Страницы: 651-670 Страниц : 20 DOI: 10.17377/alglog.2017.56.601

Авторы

АЛАЕВ ПАВЕЛ ЕВГЕНЬЕВИЧ ^1,2

Организации

1	Ин-т матем. им. С.Л.Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, Россия
2	Новосибирский национальный исследовательский государственный университет (Новосибирск)

В статье рассматривается новый подход к изучению категоричности структур, вычислимых за полиномиальное время, который основан на изучении полиномиально вычислимых устойчивых отношений. Показано, что для вычислимых булевых алгебр с вычислимым множеством атомов и для вычислимых линейных порядков с вычислимым множеством соседних пар эта категоричность равносильна обычной вычислимой категоричности. Строятся примеры, показывающие, что это верно не всегда. Установлена связь между размерностями, основанными на вычислимых и полиномиально вычислимых устойчивых отношениях.

АЛАЕВ П.Е.
Структуры, вычислимые за полиномиальное время. II
Алгебра и логика. 2017. Т.56. №6. С.651-670. DOI: 10.17377/alglog.2017.56.601

Alaev P.E.
Structures Computable in Polynomial Time. II
Algebra and Logic. 2018. V.56. N6. P.429-442. DOI: 10.1007/s10469-018-9465-x WOS Scopus OpenAlex

Нет идентификаторов

Пока нет цитирований