EN|RU
English version: Journal of Applied and Industrial Mathematics, 2019, 13:4, 746-752 |
![]() |
Volume 26, No 4, 2019, P. 108-120 UDC 519.7
Keywords: Boolean formula, depth, complexity, monotone function. DOI: 10.33048/daio.2019.26.643 Igor S. Sergeev 1 Received December 26, 2018 References[1] M. I. Grinchuk, Sharpening an upper bound on the adder and comparator depths, Diskretn. Anal. Issled. Oper., Ser. 1, 15 (2), 12–22 (2008) [Russian] [J. Appl. Ind. Math. 3 (1), 61–67 (2009)].[2] R. F. Safin, On a relation between depth and complexity in precomplete classes of $k$-valued logic, in Mathematical Problems of Cybernetics, Vol. 13 (Fizmatlit, Moscow, 2004), pp. 223–278 [Russian]. [3] P. B. Tarasov, Conditions for the uniformity of systems of multivalued logic functions, Cand. Sci. Dissertation (Moscow State Univ., Moscow, 2016) [Russian]. [4] A. B. Ugol’nikov, Depth and polynomial equivalence of formulas for closed classes of two-valued logic, Mat. Zametki 42 (4), 603–612 (1987) [Russian] [Math. Notes 42 (4), 832–837 (1987)]. [5] V. M. Khrapchenko, Asymptotic estimate of addition time of a parallel adder, in Problems of Cybernetics, Vol. 19 (Nauka, Moscow, 1967), pp. 107–120 [Russian] [Syst. Theory Res. 19, 105–122 (1970)]. [6] V. M. Khrapchenko, On a relation between complexity and depth of formulas, in Methods of Discrete Analysis in Synthesis of Control Systems, Vol. 32 (Izd. Inst. Mat., Novosibirsk, 1978), pp. 76–94 [Russian]. [7] V. M. Khrapchenko, On a relation between complexity and depth of formulas in the basis containing median, in Methods of Discrete Analysis in Studying Boolean Functions and Graphs, Vol. 37 (Izd. Inst. Mat., Novosibirsk, 1981), pp. 77–84 [Russian]. [8] S. V. Yablonskii and V. P. Kozyrev, Mathematical problems of cybernetics, in Information Materials of Scientific Council of Academy of Sciences USSR on Complex Problem “Cybernetics”, Vol. 19a (Akad. Nauk USSR, Moscow, 1968), pp. 3–15 [Russian]. [9] S. V. Yablonskii, Introduction to Discrete Mathematics (Nauka, Moscow, 1986) [Russian]. [10] A. Barak and E. Shamir, On the parallel evaluation of Boolean expressions, SIAM J. Comput. 5 (4), 678–681 (1976). [11] R. P. Brent, D. J. Kuck, and K. Maruyama, The parallel evaluation of arithmetic expressions without division, IEEE Trans. Comp. C-22, 532–534 (1973). [12] R. P. Brent, The parallel evaluation of general arithmetic expressions in logarithmic time, J. ACM 21 (2), 201–206 (1974). [13] B. Commentz-Walter, Size-depth tradeoff in monotone Boolean formulae, Acta Inform. 12, 227–243 (1979). [14] B. Commentz-Walter and J. Sattler, Size-depth tradeoff in nonmonotone Boolean formulae, Acta Inform. 14, 257–269 (1980). [15] D. Coppersmith and B. Schieber, Lower bounds on the depth of monotone arithmetic computations, in Proc. 33rd Symp. Found. Comput. Sci. (IEEE CS, Washington, 1992), pp. 288–295. [16] S. R. Kosaraju, Parallel evaluation of division-free arithmetic expressions, in Proc. 18th Annu. ACM Symp. Theory Comput. (ACM, New York, 1986), pp. 231–239. [17] W. F. McColl, Some results on circuit depth. Theory of computation, Report No. 18, (Univ. of Warwick, Coventry, 1977). [18] D. E. Muller and F. P. Preparata, Restructuring of arithmetic expressions for parallel evaluation, J. ACM 23 (3), 534–543 (1976). [19] F. P. Preparata and D. E. Muller, The time required to evaluate division-free arithmetic expressions, Inf. Proc. Lett. 3 (5), 144–146 (1975). [20] F. P. Preparata and D. E. Muller, Efficient parallel evaluation of Boolean expressions, IEEE Trans. Comp. C-25 (5), 548–549 (1976). [21] F. P. Preparata, D. E. Muller, and A. B. Barak, Reduction of depth of Boolean networks with a fan-in constraint, IEEE Trans. Comp. C-26 (5), 474–479 (1977). [22] M. Ragaz, Parallelizable algebras, Arch. Math. Logic 26, 77–99 (1986/87). [23] E. Shamir and M. Snir, On the depth complexity of formulas, Math. Syst. Theory 13 (4), 301–322 (1979/80). [24] P. M. Spira, On time-hardware complexity tradeoffs for Boolean functions, in Proc. Hawaii Symp. Syst. Sci. (Western Periodical Company, N. Hollywood, 1971), pp. 525–527. |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|