Geodesic
The relative complexities of two types of two-dimensional circuits made of functional elements
Diskretnaya Matematika, Tome 2 (1990) no. 2, pp. 121-126

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_1990_2_2_a10,
     author = {J. Hromkovi\v{c} and B. Shuster},
     title = {The relative complexities of two types of two-dimensional circuits made of functional elements},
     journal = {Diskretnaya Matematika},
     pages = {121--126},
     publisher = {mathdoc},
     volume = {2},
     number = {2},
     year = {1990},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1990_2_2_a10/}
}
TY  - JOUR
AU  - J. Hromkovič
AU  - B. Shuster
TI  - The relative complexities of two types of two-dimensional circuits made of functional elements
JO  - Diskretnaya Matematika
PY  - 1990
SP  - 121
EP  - 126
VL  - 2
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1990_2_2_a10/
LA  - ru
ID  - DM_1990_2_2_a10
ER  - 
%0 Journal Article
%A J. Hromkovič
%A B. Shuster
%T The relative complexities of two types of two-dimensional circuits made of functional elements
%J Diskretnaya Matematika
%D 1990
%P 121-126
%V 2
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1990_2_2_a10/
%G ru
%F DM_1990_2_2_a10
J. Hromkovič; B. Shuster. The relative complexities of two types of two-dimensional circuits made of functional elements. Diskretnaya Matematika, Tome 2 (1990) no. 2, pp. 121-126. http://geodesic.mathdoc.fr/item/DM_1990_2_2_a10/