W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Consider an arithmetic expression of lengthninvolving only the operations {+,×} and non-negative constants. We prove lower bounds on the depth of any binary computation tree over the same sets of operations and constants that computes such an expression. We exhibit a family of arithmetic expressions that requires computation trees of depth at least 1.5log2n-O(1), thus proving a conjecture of S. R. Kosaraju (1986,in"Proc. of the 18th ACM Symp. on Theory Computing," pp. 231-239). In contrast, Kosaraju showed how to compute such expressions with computation trees of depth 2log2n+O(1). © 1999 Academic Press.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
S.F. Fan, W.B. Yun, et al.
Proceedings of SPIE 1989
David L. Shealy, John A. Hoffnagle
SPIE Optical Engineering + Applications 2007
Harpreet S. Sawhney
IS&T/SPIE Electronic Imaging 1994