Extension of the hierarchy for \(k\)-OBDDs of small width

DOI10.3103/S1066369X13030067zbMath1290.68040WikidataQ62045231 ScholiaQ62045231MaRDI QIDQ353910

Farid M. Ablayev, K. R. Khadiev

Publication date: 16 July 2013

Published in: Russian Mathematics (Search for Journal in Brave)

zbMATH Keywords

binary decision diagramscommunication complexitybranching programscommunication protocol\(k\)-OBDDOBDD

Mathematics Subject Classification ID

Related Items (8)

On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ New size hierarchies for two way automata ⋮ Width hierarchy for \(k\)-OBDD of small width

Cites Work

• Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs
• Rounds in Communication Complexity Revisited
• Branching Programs and Binary Decision Diagrams

This page was built for publication: Extension of the hierarchy for \(k\)-OBDDs of small width