Structures Computable in Polynomial Time. II Научная публикация
| Журнал |
Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302 |
||||
|---|---|---|---|---|---|
| Вых. Данные | Год: 2018, Том: 56, Номер: 6, Страницы: 429-442 Страниц : 14 DOI: 10.1007/s10469-018-9465-x | ||||
| Ключевые слова | categoricity; computable categoricity; computable stable relations; polynomially computable stable relations | ||||
| Авторы |
|
||||
| Организации |
|
Реферат:
We consider a new approach to investigating categoricity of structures computable in polynomial time. The approach is based on studying polynomially computable stable relations. It is shown that this categoricity is equivalent to the usual computable categoricity for computable Boolean algebras with computable set of atoms, and for computable linear orderings with computable set of adjacent pairs. Examples are constructed which show that this does not always hold. We establish a connection between dimensions based on computable and polynomially computable stable relations. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
Библиографическая ссылка:
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
Оригинальная:
АЛАЕВ П.Е.
Структуры, вычислимые за полиномиальное время. 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
Идентификаторы БД:
| Web of science: | WOS:000426390500001 |
| Scopus: | 2-s2.0-85042406953 |
| OpenAlex: | W4245421229 |