scientific article; zbMATH DE number 4047113

MaRDI QIDQ3783566zbMATH OpenFDO

Authors Klaus Kriegel, Stephan Waack

Publication date 1987

zbMATH Keywords

decision graphDyck languagesExponential lower boundsreal-time complexity

Mathematics Subject Classification ID

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

Cited in

(6)

• A reducibility concept for problems defined in terms of ordered binary decision diagrams
• A lower bound on branching programs reading some bits twice
• A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
• A very simple function that requires exponential size read-once branching programs.
• scientific article; zbMATH DE number 4094813 (Why is no real title available?)
• A reducibility concept for problems defined in terms of ordered binary decision diagrams

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 Q3783566)