Some area-time tradeoffs for VLSI

64. R. P. Brent and L. M. Goldschlager, Some area-time tradeoffs for VLSI, SIAM J. on Computing 11 (1982), 737-747. MR 83k:68024.

Abstract: dvi (3K), pdf (30K), ps (27K).

Paper: pdf (1750K).


Area-time bounds on VLSI circuits for context-free language recognition, for the evaluation of propositional calculus formulae and for set equality and disjointness questions, are considered. In all cases, a lower bound ATalpha >  c.n1+alpha is proved, where A is the chip area, T the execution time, and 0 < alpha <1. Similar results were known for computations with of order n output bits, but the computations considered here have only 1-bit outputs. Upper bounds are also discussed.


For earlier work on problems with of order n output bits, see Brent and Kung [55]. Upper bounds on the context-free language recognition problem are given in Brent and Goldschlager [85].

Go to next publication

Return to Richard Brent's index page