| Title:
|
Branching programs provide lower bounds on the area of VLSI circuits (English) |
| Author:
|
Hromkovič, Juraj |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
27 |
| Issue:
|
6 |
| Year:
|
1991 |
| Pages:
|
542-550 |
| . |
| Category:
|
math |
| . |
| MSC:
|
68Q05 |
| MSC:
|
68Q25 |
| MSC:
|
68Q35 |
| idZBL:
|
Zbl 0746.68039 |
| idMR:
|
MR1150942 |
| . |
| Date available:
|
2009-09-24T18:28:57Z |
| Last updated:
|
2012-06-05 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/124289 |
| . |
| Reference:
|
[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 0910210 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[4] A. K. Chandra M. L. Furst, R. J. Lipton: Multiparty protocols.In: Proc. 15th ACM STOC, ACM 1983, pp. 94-99. |
| Reference:
|
[5] M. Ftáčnik, J. Hromkovič: Nonlinear lower bounds for real-time branching programs.Comput. Artificial Intelligence 4 (1985), 3, 353-359. |
| Reference:
|
[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 0980773 |
| Reference:
|
[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 0961318 |
| Reference:
|
[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 0994291 |
| Reference:
|
[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 0609.94018 |
| Reference:
|
[10] W. Masek: A Fast Algorithm for String Editing Problem and Decision Graph Complexity.M. Sc. Thesis, MIT, May 1976. |
| Reference:
|
[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 0218148 |
| Reference:
|
[12] P. Pudlák, S. Žák: Space complexity of computations.Unpublished manuscript, 1982. |
| Reference:
|
[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 0783479 |
| Reference:
|
[14] P. Pudlák: The hierarchy of Boolean circuits.Comput. Artificial Intelligence 6 (1987), 5, 449-468. MR 0974649 |
| Reference:
|
[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. |
| Reference:
|
[16] J. D. Ullman: Computational Aspects of VLSI.Computer Science Press, New York 1984. Zbl 0539.68021 |
| Reference:
|
[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 0787469 |
| Reference:
|
[18] I. Wegener: Time-space trade-offs for branching programs.J. Comput. System. Sci. 32 (1986), 1,91-96. Zbl 0593.68038, MR 0844204 |
| Reference:
|
[19] I. Wegener: Optimal decision trees and one-time only branching programs for symmetric Boolean functions.Inform. Control 62 (1984), 129-143. Zbl 0592.94025, MR 0789891 |
| Reference:
|
[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. Zbl 0623.94018, MR 0905473 |
| Reference:
|
[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 0783488 |
| . |
