On oblivious branching programs of linear length

DOI10.1016/0890-5401(91)90039-5MaRDI QIDQ804285zbMATHOpenAlexFDO

Authors Matthias Krause, Stephan Waack

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

Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 17548
• scientific article; zbMATH DE number 4213443
• Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
• scientific article; zbMATH DE number 4172378
• scientific article; zbMATH DE number 827986

Cites work

• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• scientific article; zbMATH DE number 3919835 (Why is no real title available?)
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• scientific article; zbMATH DE number 4072383 (Why is no real title available?)
• scientific article; zbMATH DE number 4094813 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Lower bounds for depth-restricted branching programs
• Lower bounds on the complexity of real-time branching programs
• On the complexity of branching programs and decision trees for clique functions
• Relationships between nondeterministic and deterministic tape complexities
• Word Problems Solvable in Logspace

Cited in

(10)

• On the parallel complexity of linear groups
• Tight Bounds on Oblivious Chaining
• On the descriptive and algorithmic power of parity ordered binary decision diagrams
• scientific article; zbMATH DE number 17548 (Why is no real title available?)
• Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
• scientific article; zbMATH DE number 827986 (Why is no real title available?)
• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
• On approximation by \(^{\oplus}\)-OBDDs
• On relations between counting communication complexity classes

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

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