Standard

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

In: Algebra and Logic, Vol. 56, No. 6, 01.01.2018, p. 429-442.

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

Harvard

Alaev, PE 2018, 'Structures Computable in Polynomial Time. II', Algebra and Logic, vol. 56, no. 6, pp. 429-442. https://doi.org/10.1007/s10469-018-9465-x

APA

Alaev, P. E. (2018). Structures Computable in Polynomial Time. II. Algebra and Logic, 56(6), 429-442. https://doi.org/10.1007/s10469-018-9465-x

Vancouver

Alaev PE. Structures Computable in Polynomial Time. II. Algebra and Logic. 2018 Jan 1;56(6):429-442. doi: 10.1007/s10469-018-9465-x

Author

Alaev, P. E. / Structures Computable in Polynomial Time. II. In: Algebra and Logic. 2018 ; Vol. 56, No. 6. pp. 429-442.

BibTeX

@article{fb2f4e41be2f433799ec5d491478e8ad,
title = "Structures Computable in Polynomial Time. II",
abstract = "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.",
keywords = "categoricity, computable categoricity, computable stable relations, polynomially computable stable relations",
author = "Alaev, {P. E.}",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/s10469-018-9465-x",
language = "English",
volume = "56",
pages = "429--442",
journal = "Algebra and Logic",
issn = "0002-5232",
publisher = "Springer US",
number = "6",

}

RIS

TY - JOUR

T1 - Structures Computable in Polynomial Time. II

AU - Alaev, P. E.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - categoricity

KW - computable categoricity

KW - computable stable relations

KW - polynomially computable stable relations

UR - http://www.scopus.com/inward/record.url?scp=85042406953&partnerID=8YFLogxK

U2 - 10.1007/s10469-018-9465-x

DO - 10.1007/s10469-018-9465-x

M3 - Article

AN - SCOPUS:85042406953

VL - 56

SP - 429

EP - 442

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 6

ER -

ID: 10453108