在由BDD表示的关系中查找唯一的元组
在由BDD表示的关系中查找唯一的元组
提问于 2013-01-14 11:36:44
假设我使用BDD来表示关系中的元组集。为简单起见，请考虑值为0或1的元组。例如:R= {<0,0,1>，<1,0,1>，<0,0,0>}表示具有三个变量的二进制数据结构中的三元关系，例如x，y和z(每个元组的元素一个变量)。我想要的是实现一个给定bdd的操作，比如for R和一个立方体，当C中的变量被抽象时，C返回R的子集，其中包含唯一的元组。
例如，如果C包含变量x(表示每个元组中的第一个元素)，则函数的结果必须为{<0,0,0>}。请注意，当x被抽象出来时，元组<0,0,1>和<1,0,1>变得“相同”。
现在假设R= {<0,0,1>，<1,0,1>，<0,0,0>，<1,0,0>}，我们想要再次抽象x。在这种情况下，我希望结果是常量false，因为在抽象x之后，R中没有唯一的元组。
任何帮助都是非常感谢的。
回答 1
Stack Overflow用户
回答已采纳
发布于 2014-04-02 19:29:02
这可以通过三个简单的步骤来完成：
使用要抽象的变量的限制值创建两个1：Rx=0=R with x=0 Rx=1
- Rx=1= restricted with x= BDDs
- 将异或运算应用于此新BDDs
- Q = Rx=0 XOR BDDs
- 枚举Q
的所有型号
将此应用于您的示例：
- R = {<0,0,1>，<1,0,1>，<0,0,0>} = (x代码，y代码z)代码(x代码，y代码z)
- Rx=1 = {<0,1>} =(y代码z)
- Rx=0 = {<0,1>，<0,0>} =(y∧z)∨
- q=Rx=1 xor Rx=0 =(y∧，z)
<∧>F231
这里的直觉是XOR将取消在两个BDD中出现的条目。
这很容易(但具有指数复杂度)推广到具有几个抽象变量的情况。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14313049
复制相关文章
相似问题
腾讯云开发者
