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
AT2×alpha >
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.
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