scientific article

zbMath0558.68044MaRDI QIDQ3347300

Stanislav Zak

Publication date: 1984

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

Turing machinesspace complexitymodel of on-line computation

Mathematics Subject Classification ID

Related Items (21)

The complexity of minimizing and learning OBDDs and FBDDs ⋮ A simple function that requires exponential size read-once branching programs ⋮ Communication Complexity and Lower Bounds on Multilective Computations ⋮ On the hierarchy of nondeterministic branching k-programs ⋮ A lower bound for read-once-only branching programs ⋮ Entropy of contact circuits and lower bounds on their complexity ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ A lower bound on branching programs reading some bits twice ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ BDDs -- design, analysis, complexity, and applications. ⋮ A note on read-$k$ times branching programs ⋮ Lower bounds on the complexity of real-time branching programs ⋮ On the size of binary decision diagrams representing Boolean functions ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams ⋮ Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs ⋮ A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs ⋮ A very simple function that requires exponential size read-once branching programs. ⋮ On oblivious branching programs of linear length ⋮ Lower bounds for linearly transformed OBDDs and FBDDs

This page was built for publication: