期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
