Geodesic
Recognition complexity of theories and their computational expressivity
Algebra i logika, Tome 51 (2012) no. 2, pp. 216-238 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Computational complexity of a theory for a class $\mathfrak B$ of Boolean algebras is evaluated. We introduce a concept of computational expressivity for a theory, which is close in meaning to its computational complexity, but, as distinct from the latter, also fits well with undecidable theories.
Keywords: Boolean algebra, theory, computational expressivity of theories. 
@article{AL_2012_51_2_a4,
     author = {I. V. Latkin},
     title = {Recognition complexity of theories and their computational expressivity},
     journal = {Algebra i logika},
     pages = {216--238},
     year = {2012},
     volume = {51},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2012_51_2_a4/}
}
TY  - JOUR
AU  - I. V. Latkin
TI  - Recognition complexity of theories and their computational expressivity
JO  - Algebra i logika
PY  - 2012
SP  - 216
EP  - 238
VL  - 51
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/AL_2012_51_2_a4/
LA  - ru
ID  - AL_2012_51_2_a4
ER  - 
%0 Journal Article
%A I. V. Latkin
%T Recognition complexity of theories and their computational expressivity
%J Algebra i logika
%D 2012
%P 216-238
%V 51
%N 2
%U http://geodesic.mathdoc.fr/item/AL_2012_51_2_a4/
%G ru
%F AL_2012_51_2_a4
I. V. Latkin. Recognition complexity of theories and their computational expressivity. Algebra i logika, Tome 51 (2012) no. 2, pp. 216-238. http://geodesic.mathdoc.fr/item/AL_2012_51_2_a4/

[1] M. O. Rabin, “Razreshimye teorii”, Spravochnaya kniga po matematicheskoi logike, ch. III, Nauka, M., 1982, 77–111

[2] M. J. Fischer, M. O. Rabin, “Super-exponential complexity of Presburger arithmetic”, Complexity of Comput., Proc. Symp. Appl. Math., New York City, 1973, 1974, 27–41 | MR

[3] A. R. Meyer, “The inherent computational complexity of theories of ordered sets”, Proc. Int. Congr. Math., v. 2, Vancouver, 1974, 1975, 477–482 | MR

[4] A. Akho, Dzh. Khopkroft, Dzh. Ulman, Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979 | MR

[5] S. K. Klini, Vvedenie v metamatematiku, Inostr. lit-ra, M., 1957 | MR

[6] A. I. Maltsev, Algoritmy i rekursivnye funktsii, Nauka, M., 1965 | MR