Структуры, вычислимые за полиномиальное время. II Full article
| Journal |
Алгебра и логика
ISSN: 0373-9252 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2017, Volume: 56, Number: 6, Pages: 651-670 Pages count : 20 DOI: 10.17377/alglog.2017.56.601 | ||||
| Authors |
|
||||
| Affiliations |
|
Abstract:
В статье рассматривается новый подход к изучению категоричности структур,
вычислимых за полиномиальное время, который основан на изучении
полиномиально вычислимых устойчивых отношений. Показано, что
для вычислимых булевых алгебр с вычислимым множеством атомов и
для вычислимых линейных порядков с вычислимым множеством соседних
пар эта категоричность равносильна обычной вычислимой категоричности.
Строятся примеры, показывающие, что это верно не всегда.
Установлена связь между размерностями, основанными на
вычислимых и полиномиально вычислимых устойчивых отношениях.
Cite:
АЛАЕВ П.Е.
Структуры, вычислимые за полиномиальное время. II
Алгебра и логика. 2017. Т.56. №6. С.651-670. DOI: 10.17377/alglog.2017.56.601
Структуры, вычислимые за полиномиальное время. II
Алгебра и логика. 2017. Т.56. №6. С.651-670. DOI: 10.17377/alglog.2017.56.601
Translated:
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
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
Identifiers:
No identifiers
Citing:
Пока нет цитирований