Time-space trade-offs for branching programs

DOI10.1016/0022-0000(86)90004-8MaRDI QIDQ1076517zbMATH OpenOpenAlexFDO

Authors Ingo Wegener

Publication date 1986

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(86)90004-8

zbMATH Keywords

Boolean functioncomplexity of branching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Time-space tradeoffs for branching programs
• Bounds for Width Two Branching Programs
• scientific article; zbMATH DE number 3919835
• scientific article; zbMATH DE number 4055052
• An exponential lower bound for real-time branching programs

Cites work

• scientific article; zbMATH DE number 3913677 (Why is no real title available?)
• scientific article; zbMATH DE number 4007722 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3257409 (Why is no real title available?)
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions

Cited in

(17)

• Space-time trade-offs for stack-based algorithms
• An exponential lower bound for real-time branching programs
• scientific article; zbMATH DE number 4047114 (Why is no real title available?)
• scientific article; zbMATH DE number 58305 (Why is no real title available?)
• scientific article; zbMATH DE number 61460 (Why is no real title available?)
• On the size of binary decision diagrams representing Boolean functions
• Time and space complexity of deterministic and nondeterministic decision trees
• scientific article; zbMATH DE number 3890736 (Why is no real title available?)
• Bounds for Width Two Branching Programs
• On Ajtai's lower bound technique for \(R\)-way branching programs and the Hamming distance problem
• Constructive linear time algorithms for branchwidth
• Time-space tradeoffs for algebraic problems on general sequential machines
• The optimal read-once branching program complexity for the direct storage access function
• Time-space tradeoffs for set operations
• scientific article; zbMATH DE number 4055052 (Why is no real title available?)
• scientific article; zbMATH DE number 3866582 (Why is no real title available?)
• Time-space tradeoffs for branching programs

This page was built for publication: Time-space trade-offs for branching programs

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