Modified branching programs and their computational power

zbMath0669.68042MaRDI QIDQ1187665

Christoph Meinel

Publication date: 17 September 1992

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

branching programnonuniform computationlogarithmic space complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items (13)

On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs ⋮ Structure and importance of logspace-MOD class ⋮ Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits ⋮ Lower bounds for the modular communication complexity of various graph accessibility problems ⋮ Synthesis for testability: Binary Decision Diagrams ⋮ On the complexity of constructing optimal ordered binary decision diagrams ⋮ Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access ⋮ Forms of representation for simple games: sizes, conversions and equivalences ⋮ Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree ⋮ Separating complexity classes related to \(\Omega\)-decision trees ⋮ A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy ⋮ A reducibility concept for problems defined in terms of ordered binary decision diagrams ⋮ On the relation between BDDs and FDDs

This page was built for publication: Modified branching programs and their computational power