A note on read- times branching programs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1995)
- Volume: 29, Issue: 1, page 75-83
- ISSN: 0988-3754
Access Full Article
topHow to cite
topJukna, Stasys. "A note on read-$k$ times branching programs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 29.1 (1995): 75-83. <http://eudml.org/doc/92497>.
@article{Jukna1995,
author = {Jukna, Stasys},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {branching program},
language = {eng},
number = {1},
pages = {75-83},
publisher = {EDP-Sciences},
title = {A note on read-$k$ times branching programs},
url = {http://eudml.org/doc/92497},
volume = {29},
year = {1995},
}
TY - JOUR
AU - Jukna, Stasys
TI - A note on read-$k$ times branching programs
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1995
PB - EDP-Sciences
VL - 29
IS - 1
SP - 75
EP - 83
LA - eng
KW - branching program
UR - http://eudml.org/doc/92497
ER -
References
top- 1. A. BORODIN, A. RAZBOROV, R. SMOLENSKY, On lower bounds for read-k times branching programs, Computational Complexity, 1993, 3, pp. 1-18. Zbl0777.68043MR1220075
- 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. Zbl0104.36402MR112768
- 3. N. IMMERMAN, Nondeterministic space is closed under complementation, SIAM J. Comput, 1988, 77, pp. 935-938. Zbl0668.68056MR961049
- 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. Zbl0728.94012MR1033553
- 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. Zbl0749.68036MR1122791
- 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. Zbl0819.94031MR1177381
- 8. A. A. RAZBOROV, Lower bounds for deterministic and nondeterministic branching programs, Springer Lecture Notes in Computer Science, 1991, 529, pp. 47-60. MR1136069
- 9. R. SZELEPCÉNYI, The method of forcing for nondeterministic automata, Bull. European Assoc. Theoret. Comput. Sci., 1987, 33, pp. 96-100. Zbl0664.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]. Zbl0652.68063MR935261
- 11. S. ŽAK, An exponential lower bound for one-time-only branching programs, Springer Lecture Notes in Computer Science, 1984, 176, pp. 562-566. Zbl0558.68044MR783488
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.