|
This article is cited in 34 scientific papers (total in 34 papers)
Structures computable in polynomial time. I
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:
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:
locally finite structure, computable structure, structure computable in polynomial time, polynomially categorical structure, weakly polynomially categorical structure.
Received: 09.11.2015 Revised: 07.12.2015
Citation:
P. E. Alaev, “Structures computable in polynomial time. I”, Algebra Logika, 55:6 (2016), 647–669; Algebra and Logic, 55:6 (2017), 421–435
Linking options:
https://www.mathnet.ru/eng/al769 https://www.mathnet.ru/eng/al/v55/i6/p647
|
Statistics & downloads: |
Abstract page: | 364 | Full-text PDF : | 160 | References: | 54 | First page: | 19 |
|