Bounds for Width Two Branching Programs
Allan Borodin, Danny Dolev, Faith Ellen Fich, Wolfgang J. Paul · SIAM Journal on Computing · 1986
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.