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.
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
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 .
Upper bounds on the context-free language recognition problem are
given in Brent and Goldschlager .
Go to next publication
Return to Richard Brent's index page