OBDD 的规范化推广

OBDD 的规范化推广
A Canonical Generalization of OBDD

arXivLabs是一个框架，允许合作者直接在我们的网站上开发和分享新的arXiv功能。个人和与arXivLabs合作的组织都认同并接受我们开放、社群、卓越和用户数据隐私的价值观。arXiv致力于这些价值观，并且只与秉持这些价值观的合作伙伴合作。您是否有为arXiv社群增加价值的项目想法？了解更多关于arXivLabs的信息。

## Hacker News 讨论：OBDD 的一种新泛化一篇最近的 arXiv 论文“OBDD 的一种规范泛化”在 Hacker News 上引发了讨论。该论文介绍了树决策图 (TDD)，这是一种用于表示布尔函数的新数据结构，旨在结合简洁性和规范性的优点——一种独特的、最小化的表示形式——许多现有的有序二元决策图 (OBDD) 泛化形式都缺乏这一点。作者在回应提问时解释说，TDD 解决了 OBDD 的局限性，尤其是在有效地表示笛卡尔积等函数方面。虽然不如一些替代方案（如命题决策图 (SDD)）那样简洁，但 TDD 具有最小化的优势，从而能够实现一种将合取范式 (CNF) 公式（SAT 求解器的标准输入）转换为 TDD 的实用算法。讨论还涉及了诸如分层集合决策图和三元决策图等相关概念。TDD 的实现目前正在开发中，并计划开源发布，初步结果显示出与现有库（如 CUDD 和 SDD 实现）的比较结果令人鼓舞。该论文已提交至 SAT’26 会议，正在等待评审决定。

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

OBDD 的规范化推广 A Canonical Generalization of OBDD

OBDD 的规范化推广
A Canonical Generalization of OBDD