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
AbstractIn unrestricted branching programs all variables may be tested arbitrarily often on each pat...
We obtain an exponential separation between consecutive levels in the hierarchy of classes of functi...
A longstanding open problem in complexity theory is whether the class Polytime (P) is the same as Lo...
AbstractRestricted branching programs are considered in complexity theory in order to study the spac...
AbstractBranching programs (b.p.'s) or decision diagrams are a general graph-based model of sequenti...
Abstract. Branching programs are a well established computation model for Boolean functions, especia...
AbstractWe prove the first lower bounds for restricted read-once parity branching programs with unli...
Branching programs are a well-established computation model for Boolean functions, especially read-o...
AbstractNondeterministic branching programs introduced by Meinel (1986) proved to be an interesting ...
© 2016, Pleiades Publishing, Ltd.The paper examines hierarchies for nondeterministic and determinist...
AbstractWe compare the complexities of Boolean functions for nondeterministic syntactic read-k-times...
Branching programs are a well-established computation model for boolean functions, especially read-o...
AbstractBranching programs are a well-established computation model for Boolean functions, especiall...
In [3] we exhibited a simple boolean functions f n in n variables such that: 1) f n can be computed ...
AbstractAlmost the same types of restricted branching programs (or binary decision diagrams BDDs) ar...
AbstractIn unrestricted branching programs all variables may be tested arbitrarily often on each pat...
We obtain an exponential separation between consecutive levels in the hierarchy of classes of functi...
A longstanding open problem in complexity theory is whether the class Polytime (P) is the same as Lo...
AbstractRestricted branching programs are considered in complexity theory in order to study the spac...
AbstractBranching programs (b.p.'s) or decision diagrams are a general graph-based model of sequenti...
Abstract. Branching programs are a well established computation model for Boolean functions, especia...
AbstractWe prove the first lower bounds for restricted read-once parity branching programs with unli...
Branching programs are a well-established computation model for Boolean functions, especially read-o...
AbstractNondeterministic branching programs introduced by Meinel (1986) proved to be an interesting ...
© 2016, Pleiades Publishing, Ltd.The paper examines hierarchies for nondeterministic and determinist...
AbstractWe compare the complexities of Boolean functions for nondeterministic syntactic read-k-times...
Branching programs are a well-established computation model for boolean functions, especially read-o...
AbstractBranching programs are a well-established computation model for Boolean functions, especiall...
In [3] we exhibited a simple boolean functions f n in n variables such that: 1) f n can be computed ...
AbstractAlmost the same types of restricted branching programs (or binary decision diagrams BDDs) ar...
AbstractIn unrestricted branching programs all variables may be tested arbitrarily often on each pat...
We obtain an exponential separation between consecutive levels in the hierarchy of classes of functi...
A longstanding open problem in complexity theory is whether the class Polytime (P) is the same as Lo...
Add to ORKG