Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/45473
Title: SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE
Authors: Eberly, Wayne
Cleve, Richard
Bshouty, Nader H.
Keywords: Computer Science
Issue Date: 1-May-1992
Abstract: We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an equivalent formula of depth $\s+1O\s-1 (log \s+1S\s-1)$ and size $O(S sup {1+ epsilon})$. This result is an improvement over previously-known results where, to obtain the same depth bound, the formula-size is $ OMEGA (S sup alpha )$, with $ alpha~>=~2$.
URI: http://hdl.handle.net/1880/45473
Appears in Collections:Eberly, Wayne
Cleve, Richard
Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1992-478-16.pdf218.06 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.