Geodesic
О~функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида
Diskretnyj analiz i issledovanie operacij, Tome 14 (2007) no. 3, pp. 31-39.

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

@article{DA_2007_14_3_a2,
     author = {A. V. Vasiliev},
     title = {{\CYRO}~{\cyrf}{\cyru}{\cyrn}{\cyrk}{\cyrc}{\cyri}{\cyrya}{\cyrh}, {\cyrv}{\cyrery}{\cyrch}{\cyri}{\cyrs}{\cyrl}{\cyri}{\cyrm}{\cyrery}{\cyrh} {\cyrb}{\cyru}{\cyrl}{\cyre}{\cyrv}{\cyrery}{\cyrm}{\cyri} {\cyrs}{\cyrh}{\cyre}{\cyrm}{\cyra}{\cyrm}{\cyri} {\cyrl}{\cyro}{\cyrg}{\cyra}{\cyrr}{\cyri}{\cyrf}{\cyrm}{\cyri}{\cyrch}{\cyre}{\cyrs}{\cyrk}{\cyro}{\cyrishrt} {\cyrg}{\cyrl}{\cyru}{\cyrb}{\cyri}{\cyrn}{\cyrery} {\cyri} {\cyrv}{\cyre}{\cyrt}{\cyrv}{\cyrya}{\cyrshch}{\cyri}{\cyrm}{\cyri}{\cyrs}{\cyrya} {\cyrp}{\cyrr}{\cyro}{\cyrg}{\cyrr}{\cyra}{\cyrm}{\cyrm}{\cyra}{\cyrm}{\cyri} {\cyrs}{\cyrp}{\cyre}{\cyrc}{\cyri}{\cyra}{\cyrl}{\cyrsftsn}{\cyrn}{\cyro}{\cyrg}{\cyro} {\cyrv}{\cyri}{\cyrd}{\cyra}},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {31--39},
     publisher = {mathdoc},
     volume = {14},
     number = {3},
     year = {2007},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2007_14_3_a2/}
}
TY  - JOUR
AU  - A. V. Vasiliev
TI  - О~функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2007
SP  - 31
EP  - 39
VL  - 14
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2007_14_3_a2/
LA  - ru
ID  - DA_2007_14_3_a2
ER  - 
%0 Journal Article
%A A. V. Vasiliev
%T О~функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида
%J Diskretnyj analiz i issledovanie operacij
%D 2007
%P 31-39
%V 14
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2007_14_3_a2/
%G ru
%F DA_2007_14_3_a2
A. V. Vasiliev. О~функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида. Diskretnyj analiz i issledovanie operacij, Tome 14 (2007) no. 3, pp. 31-39. http://geodesic.mathdoc.fr/item/DA_2007_14_3_a2/

[1] Barrington D. M., “Bounded-with polynomial-size branching programs recognize exactly those languages in NC”, J. Comput. and System Sci., 38:4 (1989), 150–164 ; Barrington D., “Vetvyaschiesya programmy ogranichennoi shiriny, imeyuschie polinomalnuyu slozhnost, raspoznayut v tochnosti yazyki iz $NC^1$”, Kiberneticheskii sbornik. Novaya seriya, 28, Mir, M., 1991, 94–113 | DOI | MR

[2] Vollmer H., Introduction to circuit complexity. A uniform approach, Springer-Verlag, Berlin, 1999 | MR

[3] Wegener I., The complexity of Boolean functions, John Wiley Sons Ltd., and B. G. Teubner, Stuttgart, 1987 | MR

[4] Wegener I., Branching programs and binary decision diagrams, SIAM, Philadelphia, CA, 2000 | MR