scientific article; zbMATH DE number 4051518

From MaRDI portal
Publication:3787930





This paper is the first part of the work having the following three aims: 1. To introduce new frameworks useful for the study of computational properties of VLSI circuits. 2. To present some new and basic results concerning the ideas from 1. 3. To formulate a large number of open problems and research directions for further research in this area. This Part I is devoted to the mathematical formalization of the notion of a VLSI circuit [\textit{C. D. Thompson}: A complexity theory for VLSI, Doctoral Diss., CMU-CS-80-140, Comput. Sci. Dep., Carnagie-Mellon Univ., Pittsburg (1980)], and the technique for proving lower bounds on the area-time squared complexity measure is presented [\textit{A. V. Aho}, \textit{J. D. Ullman} and \textit{M. Yanakakis}: On notions of information transfer in VLSI circuits, In: Proc. 15th ACM Symp. Theory of Computing, 133-139 (1983); \textit{J. D. Ullman}: Computational aspects of VLSI (1984; Zbl 0539.68021)]. New results are obtained in the comparison of the computational power of different types of circuits.




Cited in
(21)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787930)