Characterization of a next generation step-and-scan system
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
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.
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.