Lower bounds on the complexity of real-time branching programs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) no. 4, pp. 447-459. 
@article{ITA_1988__22_4_447_0,
     author = {Kriegel, Klaus and Waack, Stephan},
     title = {Lower bounds on the complexity of real-time branching programs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {447--459},
     publisher = {EDP-Sciences},
     volume = {22},
     number = {4},
     year = {1988},
     mrnumber = {984586},
     zbl = {0664.68046},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1988__22_4_447_0/}
}
TY  - JOUR
AU  - Kriegel, Klaus
AU  - Waack, Stephan
TI  - Lower bounds on the complexity of real-time branching programs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1988
SP  - 447
EP  - 459
VL  - 22
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1988__22_4_447_0/
LA  - en
ID  - ITA_1988__22_4_447_0
ER  - 
%0 Journal Article
%A Kriegel, Klaus
%A Waack, Stephan
%T Lower bounds on the complexity of real-time branching programs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1988
%P 447-459
%V 22
%N 4
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1988__22_4_447_0/
%G en
%F ITA_1988__22_4_447_0
Kriegel, Klaus; Waack, Stephan. Lower bounds on the complexity of real-time branching programs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) no. 4, pp. 447-459. http://www.numdam.org/item/ITA_1988__22_4_447_0/

1. M. Ajtai, L. Babai, P. Hajnal, J. Komlos, P. Pudlak, V. Rödel, E. Szemeredi and G. Turan, Two lower bounds for branching programs, 18th ACM STOC, 1986, pp. 30-39.

2. A. Borodin, D. Dolev, F. E. Fich and W. Paul, Bounds for width two branching programs, 15th ACM STOC, 1983, pp. 87-93.

3. L. Budach, Lower bounds for the number of nodes in a decision tree, EIK 21, 1985, No 4/5, pp.221-228. | MR

4. A. K. Chandra, M. L. Furst and R. J. Lipton, Multiparty protocols, 15th ACM STOC, 1983, pp.94-99.

5. P. E. Dunne, Lower bounds on the complexity of 1-time-only branching programs, FCT Proc., Lect. Notes in Comp. Sci.,Vol. 199, 1985, pp. 90-99. | MR | Zbl

6. R. J. Lipton and Y. Zalcstein, Word problems solvable in logspace, Journal of the ACM, Vol. 24, No.3, 1977, pp. 522-526. | MR | Zbl

7. E. I. Nechiporuk, On a Boolean function, Dokl. Akad. Nauk USSR, Vol. 169, No. 4, 1966, pp.765-766. | MR | Zbl

8. P. Pudlak, A lower bound on the complexity of branching programs, Preprint, Univ. Prague, 1983. | MR

9. U. Vishkin and A. Wigderson, Trode-offs between depth and width in parallel computation, SIAM J. Comput, Vol. 14, No.2, 1985, pp. 303-314. | MR | Zbl

10. I. Wegener, On the complexity of branching programs and decision trees for clique fonctions, Univ. of Frankfurt, Fachbereich Informatik, Interner Bericht, 5/84, 1984.

11. A. C. Yao, Lower bounds by probabilistic arguments, 24th IEEE FOCS, 1983, pp. 420-428.

12. S. Zak, An exponential lower bound for one-time-only branching programs, MFCS Proc., Lect. Notes in Comp. Sci., Vol. 176, 1984, pp. 562-566. | MR | Zbl

13. S. Zak, An exponential lower bound for real-time branching programs, manuscript.