A note on read-$k$ times branching programs
RAIRO-Theor. Inf. Appl., 29 1 (1995) 75-83
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
On the Read-Once Property of Branching Programs and CNFs of Bounded Treewidth
Igor RazgonAlgorithmica 75 (2) 277 (2016)
https://doi.org/10.1007/s00453-015-0059-x
Limitations of Incremental Dynamic Programming
Stasys JuknaAlgorithmica 69 (2) 461 (2014)
https://doi.org/10.1007/s00453-013-9747-6
Yet harder knapsack problems
Stasys Jukna and Georg SchnitgerTheoretical Computer Science 412 (45) 6351 (2011)
https://doi.org/10.1016/j.tcs.2011.07.003
A nondeterministic space-time tradeoff for linear codes
S. JuknaInformation Processing Letters 109 (5) 286 (2009)
https://doi.org/10.1016/j.ipl.2008.11.001
Incremental Branching Programs
Anna Gál, Michal Koucký and Pierre McKenzieTheory of Computing Systems 43 (2) 159 (2008)
https://doi.org/10.1007/s00224-007-9049-y
Expanders and time-restricted branching programs
Stasys JuknaTheoretical Computer Science 409 (3) 471 (2008)
https://doi.org/10.1016/j.tcs.2008.09.012
Computer Science – Theory and Applications
Anna Gál, Michal Koucký and Pierre McKenzieLecture Notes in Computer Science, Computer Science – Theory and Applications 3967 178 (2006)
https://doi.org/10.1007/11753728_20
Comparing the sizes of nondeterministic branching read-k-times programs
E.A. Okol'nishnikovaDiscrete Applied Mathematics 135 (1-3) 205 (2004)
https://doi.org/10.1016/S0166-218X(02)00305-0
On uncertainty versus size in branching programs
S. Jukna and S. ŽákTheoretical Computer Science 290 (3) 1851 (2003)
https://doi.org/10.1016/S0304-3975(02)00323-7
Approximation of boolean functions by combinatorial rectangles
Martin SauerhoffTheoretical Computer Science 301 (1-3) 45 (2003)
https://doi.org/10.1016/S0304-3975(02)00568-6
Lower Bounds for Linearly Transformed OBDDs and FBDDs
Detlef SielingJournal of Computer and System Sciences 64 (2) 419 (2002)
https://doi.org/10.1006/jcss.2001.1818
STACS 2001
Pavol Ďuriš, Juraj Hromkovič, Stasys Jukna, Martin Sauerhoff and Georg SchnitgerLecture Notes in Computer Science, STACS 2001 2010 206 (2001)
https://doi.org/10.1007/3-540-44693-1_18
STACS 2001
Matthias Krause and Stefan LucksLecture Notes in Computer Science, STACS 2001 2010 419 (2001)
https://doi.org/10.1007/3-540-44693-1_37
A read-once lower bound and a (1,+k)-hierarchy for branching programs
P. Savický and S. ŽákTheoretical Computer Science 238 (1-2) 347 (2000)
https://doi.org/10.1016/S0304-3975(98)00219-9
Numbers, Information and Complexity
Ingo WegenerNumbers, Information and Complexity 615 (2000)
https://doi.org/10.1007/978-1-4757-6048-4_49
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems
Beate Bollig and Ingo WegenerJournal of Computer and System Sciences 61 (3) 558 (2000)
https://doi.org/10.1006/jcss.2000.1733
Linear codes are hard for oblivious read-once parity branching programs
Stasys JuknaInformation Processing Letters 69 (6) 267 (1999)
https://doi.org/10.1016/S0020-0190(99)00027-7
Automata, Languages and Programming
Alexander E. Andreev, Juri L. Baskakov, Andrea E. F. Clementi and José D. P. RolimLecture Notes in Computer Science, Automata, Languages and Programming 1644 179 (1999)
https://doi.org/10.1007/3-540-48523-6_15
Foundations of Software Technology and Theoretical Computer Science
Detlef SielingLecture Notes in Computer Science, Foundations of Software Technology and Theoretical Computer Science 1738 356 (1999)
https://doi.org/10.1007/3-540-46691-6_29
Neither reading few bits twice nor reading illegally helps much
S. Jukna and A. RazborovDiscrete Applied Mathematics 85 (3) 223 (1998)
https://doi.org/10.1016/S0166-218X(98)00042-0
A Lower Bound for Integer Multiplication with Read-Once Branching Programs
Stephen PonzioSIAM Journal on Computing 28 (3) 798 (1998)
https://doi.org/10.1137/S0097539795290349
Automata, Languages and Programming
Stasys Jukna and Stanislav ŽákLecture Notes in Computer Science, Automata, Languages and Programming 1443 259 (1998)
https://doi.org/10.1007/BFb0055059
A simple function that requires exponential size read-once branching programs
Anna GálInformation Processing Letters 62 (1) 13 (1997)
https://doi.org/10.1016/S0020-0190(97)00041-0
Mathematical Foundations of Computer Science 1997
P. Savický and S. ŽákLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1997 1295 478 (1997)
https://doi.org/10.1007/BFb0029991
A lower bound on branching programs reading some bits twice
Petr Savický and Stanislav ŽákTheoretical Computer Science 172 (1-2) 293 (1997)
https://doi.org/10.1016/S0304-3975(96)00183-1
Fundamentals of Computation Theory
Elizaveta A. Okol'nishnikovaLecture Notes in Computer Science, Fundamentals of Computation Theory 1279 376 (1997)
https://doi.org/10.1007/BFb0036199