Structures Computable in Polynomial Time. I

Standard

Structures Computable in Polynomial Time. I. / Alaev, P. E.

In: Algebra and Logic, Vol. 55, No. 6, 01.01.2017, p. 421-435.

Research output: Contribution to journal › Article › peer-review

Harvard

Alaev, PE 2017, 'Structures Computable in Polynomial Time. I', Algebra and Logic, vol. 55, no. 6, pp. 421-435. https://doi.org/10.1007/s10469-017-9416-y

APA

Alaev, P. E. (2017). Structures Computable in Polynomial Time. I. Algebra and Logic, 55(6), 421-435. https://doi.org/10.1007/s10469-017-9416-y

Vancouver

Alaev PE. Structures Computable in Polynomial Time. I. Algebra and Logic. 2017 Jan 1;55(6):421-435. doi: 10.1007/s10469-017-9416-y

Author

Alaev, P. E. / Structures Computable in Polynomial Time. I. In: Algebra and Logic. 2017 ; Vol. 55, No. 6. pp. 421-435.

BibTeX

@article{83ed1fc4a28a48bd9070a217c72f49a3,

title = "Structures Computable in Polynomial Time. I",

abstract = "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.",

keywords = "computable structure, locally finite structure, polynomially categorical structure, structure computable in polynomial time, weakly polynomially categorical structure",

author = "Alaev, {P. E.}",

note = "Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media New York.",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/s10469-017-9416-y",

language = "English",

volume = "55",

pages = "421--435",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "6",

}

RIS

TY - JOUR

T1 - Structures Computable in Polynomial Time. I

AU - Alaev, P. E.

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