Modified branching programs and their computational power

MaRDI QIDQ1187665zbMATH OpenFDO

Authors Christoph Meinel

Publication date 17 September 1992

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

zbMATH Keywords

branching programlogarithmic space complexitynonuniform computation

Mathematics Subject Classification ID

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

Review text

This book gives a concise treatment of results concerning the nonuniform computation model of branching programs. Branching programs generalize the concept of decision trees, but are less powerful than Boolean circuits. The relationships to the uniform Turing machine model are explored and exact characterizations, as well as lower and upper bounds, are presented. Among others, the modifications studied in this book consist of read-once-only, nondeterministic, bounded-width, and \(\omega\)- branching programs, and combinations thereof.

Recommendations

• scientific article; zbMATH DE number 18624
• scientific article; zbMATH DE number 4047115
• The power of nondeterminism in polynomial-size bounded-width branching programs
• Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs

Cited in

(18)

• The power of nondeterminism in polynomial-size bounded-width branching programs
• Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
• Separating complexity classes related to -decision trees
• On the complexity of analysis and manipulation of Boolean functions in terms of decision graphs
• A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
• scientific article; zbMATH DE number 4172394 (Why is no real title available?)
• scientific article; zbMATH DE number 58305 (Why is no real title available?)
• Structure and importance of logspace-MOD class
• Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
• scientific article; zbMATH DE number 176163 (Why is no real title available?)
• scientific article; zbMATH DE number 2083801 (Why is no real title available?)
• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• On the relation between BDDs and FDDs (extended abstract)
• 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
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1187665)