期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Restricted branching programs are considered in complexity theory in order to study the space complexity of sequential computations and in applications as a data structure for Boolean functions. In this paper (\oplus,k)-branching programs and (\vee,k)-branching programs are considered, i.e., branching programs starting with a \oplus- (or \vee-)node with a fan-out of k whose successors are k read-once branching programs. This model is motivated by the investigation of the power of nondeterminism in branching programs and of similar variants that have been considered as a data structure. Lower bound methods and hierarchy results for polynomial size (\oplus,k)- and (\vee,k)-branching programs with respect to k are presented.
