Weighted Context-Free-Language Ordered Binary Decision Diagrams
summary
Introduces WCFLOBDDs, a hierarchically structured, weighted BDD with a procedure-call mechanism that is canonical and supports polynomial-time operations; proves worst-case separations (best-case double-exponential compression over decision trees and exponential savings over weighted BDDs); implements the data structure and applies it to quantum-circuit simulation where, with a 15-minute timeout, handled qubits are 1–64× that of WBDDs (and 1–128× that of CFLOBDDs), with artifacts available and results reproduced.
AI-written summary · about
chapters (14)
- 0:00Weighted CFG OBDDs intro
- 1:47Need for weighted CFG OBDDs
- 3:32Decision trees to weighted BDDs
- 5:17Weighted BDD properties
- 6:44Hierarchy in weighted CFG OBDDs
- 9:08Why they are called context-free language OBDDs
- 11:17Compression vs other structures
- 13:22Algorithms for weighted CFG OBDDs
- 14:47Quantum simulation app
- 16:56Q&A: Other apps & limits
- 17:40Q&A: Relaxing grammar for scalability
- 18:02Q&A: Circuit structures for compression
- 19:07Q&A: Variable ordering challenges
- 20:34Conclusion & future work
related talks
15mPolynomial Bounds of CFLOBDDs against BDDs
49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the Circuit
24mSymbolic Execution with Separating Decision Diagrams
31mPfComp: A Verified Compiler for Packet Filtering Leveraging Binary Decision Diagr...
25mSolving Queries for Boolean Fault Tree Logic via Quantified SAT
30mMulti-variable Quantification of BDDs in External Memory using Nested Sweeping
16mCertified Decision Procedures for Width-Independent Bitvector Predicates
23mA Weighted Bipolar Argumentation Framework and its ASP-based Implementation