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 ... more >>>

We present a new lower bound technique for two types of restricted Branching Programs (BPs), namely for read-once BPs (BP1s) with restricted amount of nondeterminism and for (1,+k)-BPs. For this technique, we introduce the notion of (strictly) k-wise l-mixed Boolean functions, which generalizes the concept of l-mixedness defined by Jukna ... more >>>

We propose a generalization of the traditional algorithmic space and time complexities. Using the concept introduced, we derive an unified proof for the deterministic time and space hierarchy theorems, now stated in a much more general setting. This opens the possibility for the unification and generalization of other results that ... more >>>