Geodesic
Structures computable in polynomial time.~II
Algebra i logika, Tome 56 (2017) no. 6, pp. 651-670.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{AL_2017_56_6_a0,
     author = {P. E. Alaev},
     title = {Structures computable in polynomial {time.~II}},
     journal = {Algebra i logika},
     pages = {651--670},
     publisher = {mathdoc},
     volume = {56},
     number = {6},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2017_56_6_a0/}
}
TY  - JOUR
AU  - P. E. Alaev
TI  - Structures computable in polynomial time.~II
JO  - Algebra i logika
PY  - 2017
SP  - 651
EP  - 670
VL  - 56
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2017_56_6_a0/
LA  - ru
ID  - AL_2017_56_6_a0
ER  - 
%0 Journal Article
%A P. E. Alaev
%T Structures computable in polynomial time.~II
%J Algebra i logika
%D 2017
%P 651-670
%V 56
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2017_56_6_a0/
%G ru
%F AL_2017_56_6_a0
P. E. Alaev. Structures computable in polynomial time.~II. Algebra i logika, Tome 56 (2017) no. 6, pp. 651-670. http://geodesic.mathdoc.fr/item/AL_2017_56_6_a0/

[1] P. E. Alaev, “Struktury, vychislimye za polinomialnoe vremya. I”, Algebra i logika, 55:6 (2016), 647–669 | MR

[2] S. S. Goncharov, “Problema chisla neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 19:6 (1980), 621–639 | MR

[3] J. B. Remmel, “Recursive isomorphism types of recursive Boolean algebras”, J. Symb. Log., 46:3 (1981), 572–594 | DOI | MR

[4] J. B. Remmel, “Recursively categorical linear orderings”, Proc. Am. Math. Soc., 83:2 (1981), 387–391 | DOI | MR

[5] S. S. Goncharov, V. D. Dzgoev, “Avtoustoichivost modelei”, Algebra i logika, 19:1 (1980), 45–58 | MR

[6] P. E. Alaev, “Suschestvovanie i edinstvennost struktur, vychislimykh za polinomialnoe vremya”, Algebra i logika, 55:1 (2016), 106–112 | MR

[7] D. Cenzer, J. B. Remmel, “Complexity and categoricity”, Inf. Comput., 140:1 (1998), 2–25 | DOI | MR

[8] E. I. Latkin, “Polinomialnaya neavtoustoichivost. Algebraicheskii podkhod”, Logicheskie metody v programmirovanii, Vychisl. sist., 133, In-t matem. SO AN SSSR, Novosibirsk, 1990, 14–37 | MR

[9] S. S. Goncharov, “Algoritmicheskaya razmernost abelevykh grupp”, Tez. soobschenii XVII Vsesoyuz. algebr. konf. (Minsk, 14–17 sentyabrya 1983 g.), ch. 2

[10] B. M. Khusainov, “Ob algoritmicheskoi razmernosti unarov”, Algebra i logika, 27:4 (1988), 479–494 | MR

[11] O. V. Kudinov, “Algebraicheskie zavisimosti i svodimosti konstruktivizatsii v universalnykh oblastyakh”, Matematicheskaya logika i teoriya algoritmov, Tr. IM SO RAN, 25, Novosibirsk, Nauka, 74–81 http://math.nsc.ru/journals/ti/25/ti_25_004.pdf | MR

[12] S. T. Fedoryaev, “Schëtnost shiriny struktury algebraicheskoi svodimosti dlya modelei nekotorykh klassov”, Matematicheskaya logika i teoriya algoritmov, Tr. IM SO RAN, 25, Nauka, Novosibirsk, 1993, 133–154 http://math.nsc.ru/journals/ti/25/ti_25_007.pdf | MR

[13] S. T. Fedoryaev, “Rekursivno nesovmestnye algoritmicheskie problemy na 1-konstruktiviziruemykh distributivnykh reshetkakh s otnositelnymi dopolneniyami”, Algebra i logika, 34:6 (1995), 667–680 | MR

[14] V. A. Uspenskii, A. L. Semenov, “Teoriya algoritmov: osnovnye otkrytiya i prilozheniya”, Algoritmy v sovremennoi matematike i ee prilozheniyakh, Mater. mezhd. simp. (Urgench, UzSSR, 1979), ch. 1, VTs SO AN SSSR, Novosibirsk, 1982, 99–342

[15] V. A. Uspenskii, A. L. Semenov, Teoriya algoritmov: osnovnye otkrytiya i prilozheniya, B-chka programmista, Nauka, M., 1987 | MR

[16] S. T. Fedoryaev, “Konstruktiviziruemye modeli s lineinoi strukturoi algebraicheskoi svodimosti”, Matem. zametki, 48:6 (1990), 106–111 | MR | Zbl

[17] S. T. Fedoryaev, “Nekotorye svoistva algebraicheskoi svodimosti konstruktivizatsii”, Algebra i logika, 29:5 (1990), 597–612 | MR

[18] D. Cenzer, J. Remmel, “Polynomial-time versus recursive models”, Ann. Pure Appl. Logic, 54:1 (1991), 17–58 | DOI | MR

[19] M. Moses, “Relations intrinsically recursive in linear orders”, Z. Math. Logik Grundlagen Math., 32:5 (1986), 467–472 | DOI | MR

[20] A. G. Pinus, “Ob uslovnykh termakh i tozhdestvakh na universalnykh algebrakh”, Strukturnye algoritmicheskie svoistva vychislimosti, Vychisl. sist., 156, In-t matem. SO RAN, Novosibirsk, 1996, 59–78

[21] A. G. Pinus, “Vnutrennie gomomorfizmy i pozitivno-uslovnye termy”, Algebra i logika, 40:2 (2001), 158–173 | MR | Zbl