Bounds for Width Two Branching Programs
Authors:
- Allan BorodinABAllan Borodin
- Danny DolevDDDanny Dolev
- Faith E. FichFFFaith E. Fich
- Wolfgang PaulWPWolfgang Paul
- 1 May 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (2) , 549-560
Abstract
Branching programs have been studied as a fundamental model for space bounded computations and, in particular, as a model in which to try to establish nontrivial space lower bounds and time-space trade-offs. At present, there still do not exist any results for single output functions. We consider a class of severely constrained programs (those having width 2) and establish characterizations as well as lower bounds for some Boolean functions computable within this model.Keywords
This publication has 9 references indexed in Scilit:
- Bounds for Cube ColoringSIAM Journal on Algebraic Discrete Methods, 1985
- A lower bound on complexity of branching programs1984
- Lower bounds by probabilistic arguments1983
- Bounds for width two branching programs1983
- Multi-party protocols1983
- $\Omega (n\log n)$ Lower Bounds on Length of Boolean FormulasSIAM Journal on Computing, 1982
- Parity, circuits, and the polynomial-time hierarchy1981
- A time-space tradeoff for sorting on non-oblivious machines1979
- Intersection Theorems for Systems of SetsJournal of the London Mathematical Society, 1960