Geodesic
Normal algorithms connected with the computation of boolean functions
Izvestiya. Mathematics, Tome 1 (1967) no. 1, pp. 151-194 
A. A. Markov. Normal algorithms connected with the computation of boolean functions. Izvestiya. Mathematics, Tome 1 (1967) no. 1, pp. 151-194. http://geodesic.mathdoc.fr/item/IM2_1967_1_1_a9/
@article{IM2_1967_1_1_a9,
     author = {A. A. Markov},
     title = {Normal algorithms connected with the computation of boolean functions},
     journal = {Izvestiya. Mathematics},
     pages = {151--194},
     year = {1967},
     volume = {1},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_1967_1_1_a9/}
}
TY  - JOUR
AU  - A. A. Markov
TI  - Normal algorithms connected with the computation of boolean functions
JO  - Izvestiya. Mathematics
PY  - 1967
SP  - 151
EP  - 194
VL  - 1
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/IM2_1967_1_1_a9/
LA  - en
ID  - IM2_1967_1_1_a9
ER  - 
%0 Journal Article
%A A. A. Markov
%T Normal algorithms connected with the computation of boolean functions
%J Izvestiya. Mathematics
%D 1967
%P 151-194
%V 1
%N 1
%U http://geodesic.mathdoc.fr/item/IM2_1967_1_1_a9/
%G en
%F IM2_1967_1_1_a9

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

The article deals with lower and upper bounds for the complexity of normal algorithms related to the computation of Boolean functions.

[1] Klini S. K., Vvedenie v metamatematiku, M., 1957

[2] Kuzmin V. A., “Realizatsiya formul algebry logiki avtomatami, normalnymi algorifmami i mashinami Tyuringa”, Problemy kibernetiki, 13 (1965), 75–96 | MR

[3] Markov A. A., Teoriya algorifmov, Tr. Matem. in-ta im. V. A. Steklova AN SSSR, 42, 1954 | MR | Zbl

[4] Markov A. A., “O nekotorykh algorifmakh, svyazannykh s sistemami slov”, Izv. AN SSSR. Ser. matem., 27 (1963), 101–160 | MR | Zbl

[5] Markov A. A., “O normalnykh algorifmakh, vychislyayuschikh bulevy funktsii”, Dokl. AN SSSR, 157:2 (1964), 262–264 | MR | Zbl

[6] Syrkin G. I., “Kriterii spravedlivosti teoremy perevoda v teorii normalnykh algorifmov”, Dokl. AN SSSR, 173:2 (1967) | MR | Zbl

[7] Shanin N. A., “O konstruktivnom ponimanii matematicheskikh suzhdenii”, Tr. Matem. in-ta im. V. A. Steklova AN SSSR, 52, 1958, 226–311

[8] Markov A., “On algorithms connected with the computation of Boolean functions”, Proc. of IFIP Congress, 1965, v. 2, 1966, 499