Structures Computable in Polynomial Time. I | Sciact - Система учета научной деятельности ИМ СО РАН

Structures Computable in Polynomial Time. I Научная публикация

Журнал

Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302

Вых. Данные

Год: 2017, Том: 55, Номер: 6, Страницы: 421-435 Страниц : 15 DOI: 10.1007/s10469-017-9416-y

Ключевые слова

computable structure; locally finite structure; polynomially categorical structure; structure computable in polynomial time; weakly polynomially categorical structure

Авторы

Alaev P.E. ^1,2

Организации

1	Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russian Federation

It is proved that every computable locally finite structure with finitely many functions has a presentation computable in polynomial time. Furthermore, a structure computable in polynomial time is polynomially categorical iff it is finite. If a structure is computable in polynomial time and locally finite then it is weakly polynomially categorical (i.e., categorical with respect to primitive recursive isomorphisms) iff it is finite. © 2017, Springer Science+Business Media New York.

Alaev P.E.
Structures Computable in Polynomial Time. I
Algebra and Logic. 2017. V.55. N6. P.421-435. DOI: 10.1007/s10469-017-9416-y WOS Scopus OpenAlex

Web of science:	WOS:000396462200001
Scopus:	2-s2.0-85015091737
OpenAlex:	W2597066232

БД	Цитирований
Scopus	33
OpenAlex	31
Web of science	28