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.