On oblivious branching programs of linear length

DOI10.1016/0890-5401(91)90039-5zbMath0727.68038OpenAlexW2054843454MaRDI QIDQ804285

Stephan Waack, Matthias Krause

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90039-5

zbMATH Keywords

decision graphsgraph accessibility problemsword problem of the free group

Mathematics Subject Classification ID

Related Items (7)

On relations between counting communication complexity classes ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ On approximation by \(^{\oplus}\)-OBDDs ⋮ On the parallel complexity of linear groups ⋮ Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams ⋮ Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for depth-restricted branching programs
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Relationships between nondeterministic and deterministic tape complexities
• On the complexity of branching programs and decision trees for clique functions
• Lower bounds on the complexity of real-time branching programs
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Word Problems Solvable in Logspace

This page was built for publication: On oblivious branching programs of linear length