Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657821 | Theoretical Computer Science | 2005 | 12 Pages |
Abstract
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 (â,k)-branching programs and (â¨,k)-branching programs are considered, i.e., branching programs starting with a â- (or â¨-)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 (â,k)- and (â¨,k)-branching programs with respect to k are presented.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Petr Savický, Detlef Sieling,