Structures Computable in Polynomial Time. I

Structures Computable in Polynomial Time. I Full article

Journal

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

Output data

Year: 2017, Volume: 55, Number: 6, Pages: 421-435 Pages count : 15 DOI: 10.1007/s10469-017-9416-y

Tags

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

Authors

Alaev P.E. ^1,2

Affiliations

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

DB	Citing
Scopus	33
OpenAlex	31
Web of science	28