Time-space trade-offs for branching programs

DOI10.1016/0022-0000(86)90004-8zbMath0593.68038OpenAlexW2013173685MaRDI QIDQ1076517

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)

Related Items

Time and space complexity of deterministic and nondeterministic decision trees, Time-space tradeoffs for algebraic problems on general sequential machines, On the size of binary decision diagrams representing Boolean functions, Unnamed Item, Time-space tradeoffs for branching programs

Cites Work

• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item