A hierarchy for (1, +k)-branching programs with respect to k

Branching programs (b. p.'s) or decision diagrams are a general graph-based model of sequential computation. The b. p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for different kinds of restricted b. p.'s are intensively investigated. An important restriction are so called k-b. p.'s, where each computation reads each input bit at most k times. Although, for more restricted syntactic k-b.p.'s, exponential lower bounds are proven and there is a series of exponential lower bounds for 1-b. p.'s, this is not true for general (nonsyntactic) k-b.p.'s, even for k = 2. Therefore, so called (1, +k)-b. p.'s are investigated. For some explicit functions, exponential lower bounds for (1, +k)-b. p.'s are known. Investigating the syntactic (1,+k)-b. p.'s, Sieling has found functions fn,k which are polvnomially easy for syntactic (1,+k)-b. p.'s, but exponentially hard for syntactic (1,+(k-1))-b. p.'s. In the present paper, a similar hierarchy with respect to k is proven for general (nonsyntactic) (1, +k)-b. p.'s.