Abstract:
For (1,+k)-branching programs and read-k-times branching programs syntactic and nonsyntactic variants can be distinguished. The nonsyntactic variants correspond in a natural way to sequential computations with restrictions on reading the input while lower bound proofs are easier or only known for the syntactic variants. In this paper it is shown that nonsyntactic (1,+k)-branching programs are really more powerful than syntactic (1,+k)-branching programs by presenting an explicitly defined function with polynomial size nonsyntactic (1,+1)-branching programs but only exponential size syntactic (1,+k)-branching programs. Another separation of these variants of branching programs is obtained by comparing the complexity of the satisfiability test for both variants.