The performance of multilective VLSI algorithms (Q1069297)

Several models for VLSI algorithms have been postulated. The one treated in this paper differs from most others in that it explicitly permits inputs to be read multiple times, that is, algorithms used are multilective. The way in which lower bounds derived for VLSI depend on the number of times and places at which inputs are read are explored. The contribution of this paper is to present methods for treating such multilective algorithms and to apply these methods to a large variety of functions and predicates. Figuring prominently in this work is the planar circuit size of a problem. It is used to derive lower bounds to various area-time products. Also presented here is a method for deriving lower bounds on the area required by multilective algorithms.