Some Area-Time Tradeoffs for VLSI
Richard P. Brent, Leslie M. Goldschlager · SIAM Journal on Computing · 1982
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 } = \Omega (n^{1 + \alpha } )$ is proved, where A is the chip area, T the execution time, and $0 \leqq \alpha \leqq 1$. Similar results were known for computations with $\Omega (n)$-bit outputs, but the computations considered here have only 1-bit outputs. Upper bounds are also discussed.