The relative complexities of two types of two-dimensional circuits made of functional elements

J. Hromkovič ; B. Shuster

Diskretnaya Matematika, Tome 2 (1990) no. 2, pp. 121-126.

Résumé

We consider two methods for placing circuits made of functional elements on a two-dimensional rectangular lattice. The first method allows one to position input processors in any cell of the lattice. The second method requires that the input processors be placed along the boundary of the lattice. We consider a specific sequence of Boolean functions $g_n(x_1,\dots,x_n)$ which in the case of the first placement method occupy $gn$ cells of the lattice, while in the second case it is necessary to use at least $c_2n^{3/2}$ cells of the lattice for their placement. We give a constructive method for placing input processors on the boundary of the lattice that allows one to show that $c_1n^{3/2}$ cells are sufficient for placement of the function $g_n$ by the second method.