Geodesic
On a relation between the depth and complexity of~monotone Boolean formulas
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 108-120.

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

We present a sequence of monotone Boolean functions whose depth over the basis $\{\vee,\wedge\}$ is $c>1.06$ times greater than the logarithm of the formula complexity. Tab. 1, bibliogr. 24.
Keywords: Boolean formula, depth, complexity, monotone function. 
@article{DA_2019_26_4_a5,
     author = {I. S. Sergeev},
     title = {On a relation between the depth and complexity of~monotone {Boolean} formulas},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {108--120},
     publisher = {mathdoc},
     volume = {26},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_4_a5/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - On a relation between the depth and complexity of~monotone Boolean formulas
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 108
EP  - 120
VL  - 26
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_4_a5/
LA  - ru
ID  - DA_2019_26_4_a5
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T On a relation between the depth and complexity of~monotone Boolean formulas
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 108-120
%V 26
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_4_a5/
%G ru
%F DA_2019_26_4_a5
I. S. Sergeev. On a relation between the depth and complexity of~monotone Boolean formulas. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 108-120. http://geodesic.mathdoc.fr/item/DA_2019_26_4_a5/

[1] M. I. Grinchuk, “Sharpening an upper bound on the adder and comparator depths”, J. Appl. Ind. Math., 3:1 (2009), 61–67 | DOI | MR | MR | Zbl

[2] R. F. Safin, “On a relation between depth and complexity in precomplete classes of k-valued logic”, Mathematical Problems of Cybernetics, 13, Fizmatlit, M., 2004, 223–278 (Russian) | MR

[3] P. B. Tarasov, Conditions for the uniformity of systems of multivalued logic functions, Cand. Sci. Dissertation, Moscow State Univ., M., 2016 (Russian)

[4] A. B. Ugol'nikov, “Depth and polynomial equivalence of formulas for closed classes of two-valued logic”, Math. Notes, 42:4 (1987), 832–837 | DOI | MR | Zbl

[5] V. M. Khrapchenko, “Asymptotic estimate of addition time of a parallel adder”, Syst. Theory Res., 19 (1970), 105–122

[6] V. M. Khrapchenko, “On a relation between complexity and depth of formulas”, Methods of Discrete Analysis in Synthesis of Control Systems, 32, Izd. Inst. Mat., Novosibirsk, 1978, 76–94 (Russian) | MR

[7] V. M. Khrapchenko, “On a relation between complexity and depth of formulas in the basis containing median”, Methods of Discrete Analysis in Studying Boolean Functions and Graphs, 37, Izd. Inst. Mat., Novosibirsk, 1981, 77–84 (Russian) | MR

[8] S. V. Yablonskii, V. P. Kozyrev, “Mathematical problems of cybernetics”, Information Materials of Scientific Council of Academy of Sciences USSR on Complex Problem “Cybernetics”, 19a, Akad. Nauk USSR, M., 1968, 3–15 (Russian)

[9] S. V. Yablonskii, Introduction to Discrete Mathematics, Nauka, M., 1986 (Russian) | MR

[10] A. Barak, E. Shamir, “On the parallel evaluation of Boolean expressions”, SIAM J. Comput., 5:4 (1976), 678–681 | DOI | MR | Zbl

[11] R. P. Brent, D. J. Kuck, K. Maruyama, “The parallel evaluation of arithmetic expressions without division”, IEEE Trans. Comp., C-22 (1973), 532–534 | DOI | MR

[12] R. P. Brent, “The parallel evaluation of general arithmetic expressions in logarithmic time”, J. ACM, 21:2 (1974), 201–206 | DOI | MR | Zbl

[13] B. Commentz-Walter, “Size-depth tradeoff in monotone Boolean formulae”, Acta Inf., 12 (1979), 227–243 | DOI | MR | Zbl

[14] B. Commentz-Walter, J. Sattler, “Size-depth tradeoff in non-monotone Boolean formulae”, Acta Inf., 14 (1980), 257–269 | DOI | MR | Zbl

[15] D. Coppersmith, B. Schieber, “Lower bounds on the depth of monotone arithmetic computations”, Proc. 33rd Symp. Found. Comput. Sci., IEEE CS, Washington, 1992, 288–295 | DOI | Zbl

[16] S. R. Kosaraju, “Parallel evaluation of division-free arithmetic expressions”, Proc. 18th Annual ACM Symp. Theory Comput., ACM, New York, 1986, 231–239

[17] W. F. McColl, Some results on circuit depth. Theory of computation, Rep. No 18, Univ. Warwick, Coventry, 1977

[18] D. E. Muller, F. P. Preparata, “Restructuring of arithmetic expressions for parallel evaluation”, J. ACM, 23:3 (1976), 534–543 | DOI | MR | Zbl

[19] F. P. Preparata, D. E. Muller, “The time required to evaluate division-free arithmetic expressions”, Proc. Inf. Lett., 3:5 (1975), 144–146 | DOI | MR | Zbl

[20] F. P. Preparata, D. E. Muller, “Efficient parallel evaluation of Boolean expressions”, IEEE Trans. Comp., C-25:5 (1976), 548–549 | DOI | MR

[21] F. P. Preparata, D. E. Muller, A. B. Barak, “Reduction of depth of Boolean networks with a fan-in constraint”, IEEE Trans. Comp., C-26:5 (1977), 474–479 | DOI | MR

[22] M. Ragaz, “Parallelizable algebras”, Arch. Math. Logic, 26 (1986/87), 77–99 | DOI | MR

[23] E. Shamir, M. Snir, “On the depth complexity of formulas”, Math. Syst. Theory, 13:4 (1979/80), 301–322 | DOI | MR

[24] P. M. Spira, “On time-hardware complexity tradeoffs for Boolean functions”, Proc. 4th Hawaii Symp. System Sci., Western Periodical Co., N. Hollywood, 1971, 525–527