Geodesic
Strongly constructive Boolean algebras
Algebra i logika, Tome 44 (2005) no. 1, pp. 3-23.

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

A computable structure is said to be $n$-constructive if there exists an algorithm which, given a finite $\Sigma_n$-formula and a tuple of elements, determines whether that tuple satisfies this formula. A structure is strongly constructive if such an algorithm exists for all formulas of the predicate calculus, and is decidable if it has a strongly constructive isomorphic copy. We give a complete description of relations between $n$-constructibility and decidability for Boolean algebras of a fixed elementary characteristic.
Keywords: computable structure, Boolean algebra, strongly constructive structure, decidable structure.
Mots-clés : $n$-constructive structure 
@article{AL_2005_44_1_a0,
     author = {P. E. Alaev},
     title = {Strongly constructive {Boolean} algebras},
     journal = {Algebra i logika},
     pages = {3--23},
     publisher = {mathdoc},
     volume = {44},
     number = {1},
     year = {2005},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2005_44_1_a0/}
}
TY  - JOUR
AU  - P. E. Alaev
TI  - Strongly constructive Boolean algebras
JO  - Algebra i logika
PY  - 2005
SP  - 3
EP  - 23
VL  - 44
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2005_44_1_a0/
LA  - ru
ID  - AL_2005_44_1_a0
ER  - 
%0 Journal Article
%A P. E. Alaev
%T Strongly constructive Boolean algebras
%J Algebra i logika
%D 2005
%P 3-23
%V 44
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2005_44_1_a0/
%G ru
%F AL_2005_44_1_a0
P. E. Alaev. Strongly constructive Boolean algebras. Algebra i logika, Tome 44 (2005) no. 1, pp. 3-23. http://geodesic.mathdoc.fr/item/AL_2005_44_1_a0/

[1] S.S. Goncharov,, “Ogranichennye teorii konstruktivnykh bulevykh algebr”, Sib. matem. zh., 17:4 (1976), 797–812 | MR | Zbl

[2] Handbook of recursive mathematics, vol. 2, Stud. Logic Found. Math., 139, eds. Y. L.Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, Elsevier Science B.V., Amsterdam, 1998 | MR

[3] Logicheskaya tetrad. Nereshennye voprosy matematicheskoi logiki. Operativnyi informatsionnyi material, eds. Yu.L. Ershov, S.S. Goncharov, In-t matem. SO AN SSSR, Novosibirsk, 1986 | MR

[4] S.S. Goncharov, Schetnye bulevy algebry, Nauka, Novosibirsk, 1988

[5] S.S. Goncharov, Schetnye bulevy algebry i razreshimost (Sibirskaya shkola algebry i logiki), Nauchnaya kniga (NII MIOO NGU), Novosibirsk, 1996 | MR

[6] P.E. Alaev, “Razreshimye bulevy algebry kharakteristiki $(1,0,1)$”, Matem. trudy, 7:1 (2004), 3–12 | MR | Zbl

[7] S.S. Goncharov, “Nekotorye svoistva konstruktivizatsii bulevykh algebr”, Sib. matem. zh., 16:2 (1975), 264–278 | Zbl

[8] Yu.L. Ershov, “Razreshimost elementarnoi teorii distributivnykh struktur s otnositelnymi dopolneniyami i teorii filtrov”, Algebra i logika, 3:3 (1964), 17–38 | MR | Zbl

[9] S.P. Odintsov, Ogranichennye teorii konstruktivnykh bulevykh algebr nizhnego sloya, preprint No 21, In-t matem. SO AN SSSR, 1986 | MR | Zbl

[10] V.N. Vlasov, S.S. Goncharov, “O silnoi konstruktiviziruemosti bulevykh algebr elementarnoi kharakteristiki $(1,1,0)$”, Algebra i logika, 32:6 (1993), 618–630 | MR | Zbl

[11] V.N. Vlasov, “Konstruktiviziruemost bulevykh algebr elementarnoi kharakteristiki $(1,0,1)$”, Algebra i logika, 37:5 (1998), 499–521 | MR | Zbl

[12] J. F. Knight, M. Stob, “Computable Boolean algebras”, J. Symb. Log., 65:4 (2000), 1605–1623 | DOI | MR | Zbl

[13] R. Downey, C. G. Jockush, “Every low Boolean algebra is isomorphic to a recursive one”, Proc. Am. Math. Soc., 122:3 (1994), 871–880 | DOI | MR | Zbl