A regular (1,+k)-branching program ((1,+k)-ReBP) is an
ordinary branching program with the following restrictions: (i)
along every consistent path at most k variables are tested more
than once, (ii) for each node v on all paths from the source to
v the same set X(v)\subseteq X of variables is tested, and
(iii) on each path from the source to a sink all variables X are
tested.

We show that polynomial size (1,+1)-ReBP-s are more powerful than
polynomial size read-once branching programs and that polynomial size
(1,+(k+1))-ReBP-s are more powerful than polynomial size
(1,+k)-ReBP-s.

We prove lower bound 2^{(n-k)/2-k\log (n^2/k)}/2\sqrt{n} for
k=o(n^2) on the size of any nondeterministic (1,+k)-ReBP
computing permutation function PERM_{n^2} on n^2 arguments. The
proof is based on combination of decomposing of (1,+k)-ReBP with
communication complexity technique.