## 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).

## Abstract

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
*AT*^{2×alpha} >
*c.n*^{1+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.
## Comments

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