Geodesic
On a class of cell circuits
Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 84-98.

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

We introduce a class of cell circuits, $T$-circuits, and describe a connection between the lower bound for the area and the depth of the circuits of this class: the less the depth the greater the area of a circuit. We give examples of $T$-circuits with logarithmic depth in the problem of calculation of $n$ prefix sums and also of sums and differences of two $n$-digit numbers. It is shown that the area of these circuits is $O(n\log n)$ and has the optimal order. 
@article{DM_2006_18_4_a7,
     author = {D. A. Zhukov},
     title = {On a class of cell circuits},
     journal = {Diskretnaya Matematika},
     pages = {84--98},
     publisher = {mathdoc},
     volume = {18},
     number = {4},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_4_a7/}
}
TY  - JOUR
AU  - D. A. Zhukov
TI  - On a class of cell circuits
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 84
EP  - 98
VL  - 18
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_4_a7/
LA  - ru
ID  - DM_2006_18_4_a7
ER  - 
%0 Journal Article
%A D. A. Zhukov
%T On a class of cell circuits
%J Diskretnaya Matematika
%D 2006
%P 84-98
%V 18
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2006_18_4_a7/
%G ru
%F DM_2006_18_4_a7
D. A. Zhukov. On a class of cell circuits. Diskretnaya Matematika, Tome 18 (2006) no. 4, pp. 84-98. http://geodesic.mathdoc.fr/item/DM_2006_18_4_a7/

[1] Albrekht A., “O skhemakh iz kletochnykh elementov”, Problemy kibernetiki, 33 (1977), 209–214

[2] Gromkovich Yu., Shuster B., “O sootnoshenii slozhnostei dvukh vidov ploskikh skhem iz funktsionalnykh elementov”, Diskretnaya matematika, 2:2 (1990), 121–126 | MR

[3] Zhukov D. A., “Bystrye kletochnye skhemy dlya umnozheniya”, Diskretnyi analiz i issledovanie operatsii, 9:3 (2002), 40–47 | MR | Zbl

[4] Kravtsov S. S., “O realizatsii funktsii algebry logiki v odnom klasse skhem iz funktsionalnykh i kommutatsionnykh elementov”, Problemy kibernetiki, 19 (1967), 285–293 | MR | Zbl

[5] Lozhkin S. A., Li Da Min, “O nekotorykh optimalnykh vlozheniyakh dvoichnykh i troichnykh derevev v ploskie pryamougolnye reshetki”, Vestnik Moskovskogo universiteta, ser. 15, 1995, no. 4, 49–55

[6] Lozhkin S. A., “Asimptoticheski optimalnye gomeomorfnye vlozheniya polnykh dvoichnykh i troichnykh derevev v ploskie pryamougolnye reshetki”, Problemy teoreticheskoi kibernetiki, Tez. dokl. 13 Mezhdunar. konf. v Kazani, chast II, Izd-vo Tsentra prikladnykh issledovanii pri mekh.-mat. f-te MGU, Moskva, 2002, 113

[7] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, Moskva, 1984

[8] Ulman Dzh. D., Vychislitelnye aspekty SBIS, Radio i svyaz, Moskva, 1990

[9] Khrapchenko V. M., “Ob asimptoticheskoi otsenke vremeni slozheniya parallelnogo summatora”, Problemy kibernetiki, 19 (1967), 107–122 | Zbl

[10] Chashkin A. V., “Bystroe slozhenie i umnozhenie tselykh chisel”, Diskretnaya matematika i ee prilozheniya, sbornik lektsii, II, Izd-vo Tsentra prikladnykh issledovanii pri mekh.-mat. f-te MGU, Moskva, 2001, 91–110

[11] Shkalikova N. A., “O realizatsii bulevykh funktsii skhemami iz kletochnykh elementov”, Matem. voprosy kibernetiki, 2 (1989), 177–197

[12] Akl S. G., Parallel computation: models and methods, Prentice–Hall, New Jersey, 1997

[13] Brent R. P., Kung H. T., “On the area of binary tree layouts”, Inform. Process. Lett., 11:1 (1980), 46–48 | DOI | MR

[14] Hromkovič J., Ložkin S. A., Rybko A. I., Sapoženko A. A., Škalikova N. A., “Lower bounds on the area complexity of Boolean circuits”, Theoret. Computer Sci., 97:2 (1992), 285–300 | DOI | MR | Zbl

[15] Ladner R. E., Fischer M. J., “Parallel prefix computation”, J. ACM, 27 (1980), 831–838 | DOI | MR | Zbl

[16] Wegener I., The complexity of Boolean functions, Teubner, Stuttgart, 1987 | MR | Zbl