Title: Incremental branching programs

Abstract:
Motivated by the Logspace versus P question in complexity theory, 
we introduce incremental branching programs.  These capture the 
best strategy known to space-efficiently solve the P-complete problem 
GEN (given an arbitrary binary operation on {1, 2, ..., n}, does 1 
generate n by iterated product?). We show that our model captures and 
possibly supersedes previously studied structured models of computation 
for GEN, namely marking machines [Cook 74] and Poon's extension [Poon 
93] of jumping automata on graphs [Cook-Rackoff 80].  From these 
relationships, or from known monotone circuit depth lower bounds, we 
derive exponential lower bounds for variants of our model although we 
are unable to prove any strong lower bounds for the most general variant 
of incremental branching programs.

Joint work with Anna Gal and Michal Koucky.