  We answer a problem posed in (G\'al, Kouck\'y, McKenzie 2008) regarding a
restricted model of small-space computation, tailored for solving the GEN
problem. They define two variants of "incremental branching programs", the
syntactic variant defined by a restriction on the graph-theoretic paths in the
program, and the more-general semantic variant in which the same restriction is
enforced only on the consistent paths - those that are followed by at least one
input. They show that exponential size is required for the syntactic variant,
but leave open the problem of superpolynomial lower bounds for the semantic
variant. Here we give an exponential lower bound for the semantic variant by
generalizing lower bound arguments, from earlier work, for a similar restricted
model tailored for solving a special case of GEN called Tree Evaluation.
