SOME AREA-TIME TRADEOFFS FOR VLSI

RICHARD P. BRENT AND LESLIE M. GOLDSCHLAGER

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α} = Ω(n^{1+α}) is proved, where A is the chip area, T the execution time, and 0 ≤ α ≤ 1. Similar results were known for computations with Ω(n)-bit outputs, but the computations considered here have only 1-bit outputs. Upper bounds are also discussed.

Comments

Only the Abstract is given here. The full paper appeared as [2]. For related work on problems with Ω(n)-bit outputs, see [1]. Upper bounds on the context-free language recognition problem are given in [3].

References

1. R. P. Brent and H. T. Kung, “The area-time complexity of binary multiplication”, Journal of the ACM 28 (1981), 521–534. CR 22#38242, MR 82i:68027. Corrigendum: ibid 29 (1982), 904. MR 83j:68046. rpb055.

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

3. R. P. Brent and L. M. Goldschlager, “A parallel algorithm for context-free parsing”, Proc. Seventh Australian Computer Science Conference, special issue of Australian Computer Science Communications 6 (1984), 7.1–7.10. rpb085.

(Brent) Department of Computer Science, Australian National University, Canberra

(Goldschlager) Department of Computer Science, University of Queensland, St Lucia, Queensland, Australia

Current address, Goldschlager: Basser Department of Computer Science, Sydney University, Sydney, Australia

1991 Mathematics Subject Classification. Primary 68Q35; Secondary 65Y05, 68M07, 68Q25.

Key words and phrases. Area-time tradeoffs, VLSI, formula evaluation, circuit-value problem, contextfree language recognition, set equality, set disjointness, computational complexity, crossing sequences, models of computation.

Received January 5, 1981 and in revised form January 15, 1982.

We are grateful to Al Borodin for suggesting the set equality and disjointness problems, and for fruitful discussions. We also thank the referees and W. L. Ruzzo for their comments, which helped us to sharpen Theorem 3.9 and to correct the proof of Theorem 4.1.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1982, SIAM.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent. rpb064a typeset using AMS-L^{A}TEX