Introduction to the OBDD algorithm for the ATP community
Introduction to the OBDD algorithm for the ATP community
复制标题
ATP社区OBDD算法简介
DOI：
10.1007/bf00881842
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
J. S. Moore
中科院分区：
文献类型：
--
作者：
J. S. Moore
我们用自动推理界熟悉的术语来描述R. E. Bryant于1986年发表的决定命题等价的基于图的算法。这种基于有序二进制决策图（obdd）的算法是已知最快的确定两个命题表达式是否等价的方法之一，在这类问题上通常比大多数自动定理证明系统快数百或数千倍。OBDD是一种标准化的IF （' IF -then-else '）表达式，其中任何分支上的测试都按照先前选择的固定顺序升序进行。这样的IF表达式代表了命题表达式的规范形式。有三个编码技巧可以非常有效地操作规范IF表达式。首先，可以利用测试是有序的这一事实，将两个规范化表达式快速组合起来，形成它们的析取（合取、异或等）的规范化形式。第二，应该为每个不同的规范IF表达式分配一个唯一的整数索引，以便能够快速识别相同的形式。第三个技巧是组合规范化子术语term的操作应该“备记”或缓存，这样如果将来需要相同的操作，其结果可以被查找而不是重新计算。
We describe in terms familiar to the automated reasoning community the graph-based algorithm for deciding propositional equivalence published by R. E. Bryant in 1986. Such algorithms, based onordered binary decision diagrams orOBDDs, are among the fastest known ways to decide whether two propositional expressions are equivalent and are generally hundreds or thousands of times faster on such problems than most automatic theorem-proving systems. An OBDD is a normalized IF (‘if-then-else’) expression in which the tests down any branch are ascending in some previously chosen fixed order. Such IF expressions represent a canonical form for propositional expressions. Three coding tricks make it extremely efficient to manipulate canonical IF expressions. The first is that two canonicalized expressions can be rapidly combined to form the canonicalized form of their disjunction (conjunction, exclusive-or, etc.) by exploiting the fact that the tests are ordered. The second is that every distinct canonical IF expression should be assigned a unique integer index to enable fast recognition of identical forms. The third trick is that the operation in which one combines canonicalized subterms term should be ‘memo-ized’ or cached so that if the same operation is required in the future its result can be looked up rather than recomputed.
DOI：
10.1016/j.mce.2004.09.001
发表时间：
2004-10
期刊：
IOP Conference Series: Materials Science and Engineering
影响因子：
--
作者：
Joan Waugh
通讯作者：
Joan Waugh