A Canonical Generalization of OBDD
4 days ago
- #Computational complexity
- #Decision diagrams
- #Boolean functions
- 树决策图（TDD）作为OBDD的泛化被引入，用于建模布尔函数，类似于受限于vtree的d-DNNF。
- TDD保留了可行的操作，如模型计数、枚举、条件化和应用函数，同时比OBDD更简洁。
- 具有树宽k的CNF公式可以由固定参数可处理大小的TDD表示，这是OBDD无法实现的。
- 通过自底向上的方法将CNF公式编译为确定性TDD的过程被分析，将其复杂性与Bova和Szeider定义的因子宽度联系起来。