Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Structures Computable in Polynomial Time. I. / Alaev, P. E.
в: Algebra and Logic, Том 55, № 6, 01.01.2017, стр. 421-435.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Structures Computable in Polynomial Time. I
AU - Alaev, P. E.
N1 - Publisher Copyright: © 2017, Springer Science+Business Media New York.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - 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.
AB - 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.
KW - computable structure
KW - locally finite structure
KW - polynomially categorical structure
KW - structure computable in polynomial time
KW - weakly polynomially categorical structure
UR - http://www.scopus.com/inward/record.url?scp=85015091737&partnerID=8YFLogxK
U2 - 10.1007/s10469-017-9416-y
DO - 10.1007/s10469-017-9416-y
M3 - Article
AN - SCOPUS:85015091737
VL - 55
SP - 421
EP - 435
JO - Algebra and Logic
JF - Algebra and Logic
SN - 0002-5232
IS - 6
ER -
ID: 8967988