|
This article is cited in 12 scientific papers (total in 12 papers)
Structures computable in polynomial time. II
P. E. Alaevab a Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia
b Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090 Russia
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:
computable stable relations, polynomially computable stable relations, categoricity, computable categoricity.
Received: 24.02.2016 Revised: 29.11.2017
Citation:
P. E. Alaev, “Structures computable in polynomial time. II”, Algebra Logika, 56:6 (2017), 651–670; Algebra and Logic, 56:6 (2018), 429–442
Linking options:
https://www.mathnet.ru/eng/al822 https://www.mathnet.ru/eng/al/v56/i6/p651
|
Statistics & downloads: |
Abstract page: | 241 | Full-text PDF : | 45 | References: | 43 | First page: | 19 |
|