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.
No takes yet. Share an insight, caveat, or question.
Borodin et al. (1986) studied this question.
Synapse has enriched 4 closely related papers on similar clinical questions. Consider them for comparative context: