The authors have studied many variants of branching programs in a series of papers. Here, they study read-once branching programs, corresponding to logarithmic space-bounded Turing machines that erase each input bit after reading it (eraser machines). Eraser machines are a generalization of the one-way logspace machine [1] and share with that model the characteristics that it is easy to prove lower bounds in the model, and certain complexity classes have complete sets accepted by machines of this type.

The main result presents a set recognized easily by nondeterministic read-once branching programs, whose complement requires exponential size in this model. This result shows that various complexity classes defined by eraser  Turing  machines are distinct, and shows that the Immerman-Szelepcsenyi theorem does not hold in the eraser model.

The results are nice and the paper is well written, but some unfortunate printing errors hurt its clarity. The worst of these typos occur in the equivalent diagrams on the middle of page 268 and the top of page 274; these diagrams are supposed to say that the classes P _{{ ∨ } - BP1} and P _{{ ∧ } - BP1} are incomparable, each properly contain P _BP1, and are each properly contained in P _{{ ∨ , ∧ } - BP1}. Also, at the end of Section 1, the authors refer the reader to a conference paper for an important fact showing that the read-once restriction does not restrict the power of alternating branching programs. Unfortunately, this fact is not at all explicit in the conference paper (it may be more explicit in the forthcoming journal version); a clear exposition can instead be found in Meinel’s monograph on branching programs [2].