Lower bounds on the complexity of real-time branching programs

DOI10.1051/ita/1988220404471zbMath0664.68046OpenAlexW112636843MaRDI QIDQ3815526

Klaus Kriegel, Stephan Waack

Publication date: 1988

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92316

zbMATH Keywords

lower boundsbranching programsDyck languagedecision graph complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (8)

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ Efficient data structures for Boolean functions ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ On the parallel complexity of linear groups ⋮ Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\) ⋮ On the descriptive and algorithmic power of parity ordered binary decision diagrams ⋮ Coxeter groups and nonuniform complexity ⋮ On oblivious branching programs of linear length

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trade-Offs between Depth and Width in Parallel Computation
• Bounds for Width Two Branching Programs
• Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
• Word Problems Solvable in Logspace

This page was built for publication: Lower bounds on the complexity of real-time branching programs