Geodesic
Branching programs provide lower bounds on the area of VLSI circuits
Kybernetika, Tome 27 (1991) no. 6, pp. 542-550 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 68Q05, 68Q25, 68Q35 
@article{KYB_1991_27_6_a5,
     author = {Hromkovi\v{c}, Juraj},
     title = {Branching programs provide lower bounds on the area of {VLSI} circuits},
     journal = {Kybernetika},
     pages = {542--550},
     year = {1991},
     volume = {27},
     number = {6},
     mrnumber = {1150942},
     zbl = {0746.68039},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_1991_27_6_a5/}
}
TY  - JOUR
AU  - Hromkovič, Juraj
TI  - Branching programs provide lower bounds on the area of VLSI circuits
JO  - Kybernetika
PY  - 1991
SP  - 542
EP  - 550
VL  - 27
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/KYB_1991_27_6_a5/
LA  - en
ID  - KYB_1991_27_6_a5
ER  - 
%0 Journal Article
%A Hromkovič, Juraj
%T Branching programs provide lower bounds on the area of VLSI circuits
%J Kybernetika
%D 1991
%P 542-550
%V 27
%N 6
%U http://geodesic.mathdoc.fr/item/KYB_1991_27_6_a5/
%G en
%F KYB_1991_27_6_a5
Hromkovič, Juraj. Branching programs provide lower bounds on the area of VLSI circuits. Kybernetika, Tome 27 (1991) no. 6, pp. 542-550. http://geodesic.mathdoc.fr/item/KYB_1991_27_6_a5/

[1] L. Babai P. Hajnal E. Szemeredi, G. Turán: A lower bound for read-once only branching programs. J. Computer System Sci. 35 (1987), 153-162. | MR

[2] D. A. Barrington: Bounded width polynomial-size branching programs recognize exactly those languages in $NC^{1}$. In: Proc. 18th ACM STOC, ACM 1986, pp. 1-5.

[3] A. Borodin D. Dolev F. E. Fich, W. Paul: Bounds for width two branching programs. In: Proc. 15th ACM STOC, ACM 1983, pp. 87-93.

[4] A. K. Chandra M. L. Furst, R. J. Lipton: Multiparty protocols. In: Proc. 15th ACM STOC, ACM 1983, pp. 94-99.

[5] M. Ftáčnik, J. Hromkovič: Nonlinear lower bounds for real-time branching programs. Comput. Artificial Intelligence 4 (1985), 3, 353-359.

[6] J. Hromkovič: Some complexity aspects of VLSI computations. Part 1. A framework for the study of information transfer in VLSI circuits. Comput. Artificial Intelligence 7 (1988), 3, 229-252. | MR

[7] J. Hromkovič: Some complexity aspects of VLSI computations. Part 2. Topology of circuits and information transfer. Comput. Artificial Intelligence 7 (1988), 4, 289-302, | MR

[8] J. Hromkovič: Some complexity aspects of VLSI computations. Part 5. Nondeterministic and probabilistic VLSI circuits. Comput. Artificial Intelligence 8 (1989), 2, 169-188. | MR

[9] S. P. Jukna: Lower bounds on the complexity of local circuits. In: Mathematical Foundation of Computer Science - Proc. 12th Symposium, Bratislava, Czechoslovakia, August 25-29, 1986 (J. Gruska, B. Rovan, J. Wiedermann, eds.). (Lecture Notes in Computer Science 233.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1986, pp. 440-448. | Zbl

[10] W. Masek: A Fast Algorithm for String Editing Problem and Decision Graph Complexity. M. Sc. Thesis, MIT, May 1976.

[11] E. I. Nečiporuk: On a Boolean function. Dokl. Akad. Nauk SSSR 169 (1966), 4, 765-766. English translation: Soviet Math. Dokl. 7 (1966), 999-1000. | MR

[12] P. Pudlák, S. Žák: Space complexity of computations. Unpublished manuscript, 1982.

[13] P. Pudlák: A lower bound on complexity of branching programs. In: Mathematical Foudations of Computer Science - Proc. 11th Symposium, Prague, Czechoslovakia, September 3-7, 1984 (M. P. Chytil, V. Koubek, eds.). (Lecture Notes in Computer Science 176.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984, pp. 480-489. | MR

[14] P. Pudlák: The hierarchy of Boolean circuits. Comput. Artificial Intelligence 6 (1987), 5, 449-468. | MR

[15] C D. Thompson: A Complexity Theory for VLSI. Doctoral Dissertation, CMU-CS-88-140, Computer Science Dept., Carnegie-Mellon University, Pittsburg, August 1980, 131 p.

[16] J. D. Ullman: Computational Aspects of VLSI. Computer Science Press, New York 1984. | Zbl

[17] I. Wegener: On the Complexity of Branching Programs and Decision Trees for Qlique Functions. Universitat Frankfurt, Fachbereich Informatik, Int. Rept. 5/84, 1984. | MR

[18] I. Wegener: Time-space trade-offs for branching programs. J. Comput. System. Sci. 32 (1986), 1,91-96. | MR | Zbl

[19] I. Wegener: Optimal decision trees and one-time only branching programs for symmetric Boolean functions. Inform. Control 62 (1984), 129-143. | MR | Zbl

[20] I. Wegener: The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, B. G. Teubner, Stuttgart, John Wiley and Sons, New York 1987. | MR | Zbl

[21] S. Žák: An exponential lower bound for one-time-only branching programs. In: Mathematical Foundations of Computer Science - Proc. 11th Symposium, Prague, Czechoslovakia, September 3 - 7, 1984 (M. P. Chytil, V. Koubek, eds.). (Lecture Notes in Computer Science 176.) Springer-Verlag, Berlin-Heidelberg-New York-Tokyo 1984, pp. 562-566. | MR