scientific article; zbMATH DE number 4094813

MaRDI QIDQ3821583zbMATH OpenFDO

Authors Matthias Krause

Publication date 1988

zbMATH Keywords

branching programscomplexitylocal networkslower boundsswitching network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 4047113
• An exponential lower bound for real-time branching programs
• Lower bounds on the complexity of real-time branching programs
• scientific article; zbMATH DE number 3890736
• scientific article; zbMATH DE number 3928350
• scientific article; zbMATH DE number 3913677
• scientific article; zbMATH DE number 3919835
• scientific article; zbMATH DE number 706832
• scientific article; zbMATH DE number 5899238
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

Cited in

(10)

• Neither reading few bits twice nor reading illegally helps much
• Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
• A very simple function that requires exponential size read-once branching programs.
• A simple function that requires exponential size read-once branching programs
• Worst case examples for operations on OBDDs
• scientific article; zbMATH DE number 3928350 (Why is no real title available?)
• An exponential lower bound for real-time branching programs
• Lower bounds on the complexity of real-time branching programs
• On the size of binary decision diagrams representing Boolean functions
• On oblivious branching programs of linear length

This page was built for publication:

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