A note on read-k times branching programs
Jukna, Stasys
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 75-83 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1995-01-01
@article{ITA_1995__29_1_75_0,
     author = {Jukna, Stasys},
     title = {A note on read-$k$ times branching programs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {29},
     year = {1995},
     pages = {75-83},
     mrnumber = {1315701},
     zbl = {0889.68021},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1995__29_1_75_0}
}

Jukna, Stasys. A note on read-$k$ times branching programs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) pp. 75-83. http://gdmltest.u-ga.fr/item/ITA_1995__29_1_75_0/

1. A. Borodin, A. Razborov, R. Smolensky, On lower bounds for read-k times branching programs, Computational Complexity, 1993, 3, pp. 1-18. | MR 1220075 | Zbl 0777.68043

2. R. C. Bose, D. K. Ray-Chaudhuri, On a class of error-correcting binary group codes, Information and Control, 1960, 3, 1, pp. 68-79. | MR 112768 | Zbl 0104.36402

3. N. Immerman, Nondeterministic space is closed under complementation, SIAM J. Comput, 1988, 77, pp. 935-938. | MR 961049 | Zbl 0668.68056

4. S. Jukna, The effect of null-chains on the complexity of contact circuits, Springer Lecture Notes in Computer Science, 1989, 380, pp. 246-256. | MR 1033553 | Zbl 0728.94012

5. M. Krause, Ch. Meinel, S. Waack, Separating the eraser Turing machine classes Le, NLe, co - NLe and Pe, Theor. Comp. Sci., 1991, 86, pp. 267-275. | MR 1122791 | Zbl 0749.68036

6. S. E. Kuznetsov, The influence of null-chains on the complexity of contact circuits, Probabilistic Methods in Cybernetics, 1984, 20, in Russian.

7. E. A. Okolnishnikova, Lower bounds on the complexity of realization of characteristic functions of binary codes by branching programs, Diskretnii Analiz, 1991, Novosibirsk, 57, pp. 61-83, in Russian. | MR 1177381 | Zbl 0819.94031

8. A. A. Razborov, Lower bounds for deterministic and nondeterministic branching programs, Springer Lecture Notes in Computer Science, 1991, 529, pp. 47-60. | MR 1136069

9. R. Szelepcényi, The method of forcing for nondeterministic automata, Bull. European Assoc. Theoret. Comput. Sci., 1987, 33, pp. 96-100. | Zbl 0664.68082

10. I. Wegener, On the complexity of branching programs and décision trees for clique functions, Internal Rept. 5/84, FB Inforrnatik, Univ. of Frankfurt, 1984 [see also: Journal of the ACM, 1988, 35, pp. 461-471]. | MR 935261 | Zbl 0652.68063

11. S. Žak, An exponential lower bound for one-time-only branching programs, Springer Lecture Notes in Computer Science, 1984, 176, pp. 562-566. | MR 783488 | Zbl 0558.68044