|
Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)
Структуры, вычислимые за полиномиальное время. II
П. Е. Алаевab a Ин-т матем. им. С. Л. Соболева СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ
b Новосибирский гос. ун-т, ул. Пирогова, 2, г. Новосибирск, 630090, РОССИЯ
Аннотация:
Рассматривается новый подход к изучению категоричности структур, вычислимых за полиномиальное время, который основан на изучении полиномиально вычислимых устойчивых отношений. Показывается, что для вычислимых булевых алгебр с вычислимым множеством атомов и для вычислимых линейных порядков с вычислимым множеством соседних пар эта категоричность равносильна обычной вычислимой категоричности. Строятся примеры, показывающие, что это верно не всегда. Устанавливается связь между размерностями, основанными на вычислимых и полиномиально вычислимых устойчивых отношениях.
Ключевые слова:
вычислимые устойчивые отношения, полиномиально вычислимые устойчивые отношения, категоричность, вычислимая категоричность.
Поступило: 24.02.2016 Окончательный вариант: 29.11.2017
Образец цитирования:
П. Е. Алаев, “Структуры, вычислимые за полиномиальное время. II”, Алгебра и логика, 56:6 (2017), 651–670; Algebra and Logic, 56:6 (2018), 429–442
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al822 https://www.mathnet.ru/rus/al/v56/i6/p651
|
Статистика просмотров: |
Страница аннотации: | 241 | PDF полного текста: | 45 | Список литературы: | 43 | Первая страница: | 19 |
|