四叉树作为抽象域的新方法：弱关系域和布尔公式的应用

理论计算机科学电子笔记267（2010）89-100www.elsevier.com/locate/entcs作为抽象域的Jacob M. Howe豪1，4英国伦敦城市大学计算机系安迪·金1，3，5和查尔斯·劳伦斯-琼斯2，6英国肯特大学计算机学院摘要四叉树作为一种表示二维空间区域的方法，在计算机图形学和空间数据库中得到了广泛的应用。 这种分层数据结构足够灵活，可以支持非凸和即使是不连通的区域，因此很自然地会问这种数据结构是否可以形成抽象的领域。 本文对这一问题进行了探讨，并提出四叉树是一种新的方法弱关系域，而它们的层次结构自然适合于用布尔函数表示。关键词：弱关系域，抽象解释，四叉树，布尔公式。1引言基于抽象解释的程序分析需要一个抽象域。最早描述的域之一是多面体[9]，最近的工作研究了多面体的子类，称为弱关系域（示例包括[6，15，16，17，21]）。 弱关系域的动机是成本多面体域操作：弱关系域限制了可以表达的变量之间的依赖性，以便实现易处理的域操作，同时保持足够的表达性以使其有用。本文提出了一个新的抽象域的基础上著名的数据结构的四叉树[11]。域属于弱关系域1这项工作得到EPSRC项目EP/E033105/1和EP/E034519/1的支持2由努费尔德科学奖学金资助3部分由英国皇家学会工业奖学金资助4电子邮件地址：jacob@soi.city.ac.uk5电子邮件：a.m. kent.ac.uk6电子邮件：clawrencejones@gmail.com1571-0661© 2010 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2010.09.00890J.M. Howe等人/理论计算机科学电子笔记267（2010）89×家庭，但它的表示不是线性不等式。这种表示意味着可以自然地表示不相交的、非线性的和非凸的区域，但是这种不稳定性是有代价的。本文对四叉树在实际分析中的适用性持中立态度。这是一个文件，渴望促进空间抽象和布尔公式之间的关系的讨论。尽管如此，本文还是做出了以下贡献：• 介绍了一种基于四叉树的• 讨论了如何表示这个域，并详细说明了如何使用布尔公式来实现，无论是二元决策图[3]还是（非规范）合取范式[14]中本文的结构如下：第2节回顾了四叉树的定义，并介绍了使用它们作为抽象域的基本思想;第3节和第4节正式介绍了域及其操作;第5节讨论了使用布尔数据结构的四叉树编码，第6节和第7节总结了相关工作的调查，并讨论了新域的优点和缺点。2个四叉树四叉树是一个树，其中每个节点有四个孩子;它被解释为一个正方形分解成更小的正方形，根是最大的，包含正方形。一个节点对应于一个正方形，它的子节点对应于通过将包含正方形的正方形平均分成四个而获得的四个正方形。在[10]之后，子节点从右上角逆时针排序，如下所示东北西北西南东南在这项工作中，兴趣不仅在于将一个正方形分解成更多的正方形，而且在于这些正方形是否是某些感兴趣区域的一部分。因此，四叉树的叶子将被标记为0或1，以指示相应的正方形是否是感兴趣区域的一部分四叉树是潜在的有限数据结构，因为正方形可以不断细分。然而，这项工作，像其他人一样[19]，是关于机器整数的分析。 这给出了一个最小的有意义的正方形，即11. 后来在这项工作中，将考虑其最小正方形具有较大尺寸的四叉树。因此，最小正方形大小将由其宽度的对数来描述NWNESWSEJ.M. Howe等人/理论计算机科学电子笔记267（2010）8991××−××并且这将被称为四叉树的粒度。例如，粒度为2的四叉树的最小平方尺寸为4 4。 一个具有给定粒度的四叉树是有限的。假设粒度是一个非负整数g，具有2n 2n平方根的四叉树在最大深度n g处具有叶子，其中根被认为是深度零。考虑将8 × 8网格分解为11个单元的以下分解，其中暗单元是感兴趣的区域它可以由以下四叉树表示（粒度为0）：001 1 1 10 1 1 1 1 0 1 001 0这种分解的性质与用于表达析取性质的BDD相呼应[8，13]。第5节将进一步探讨这一联系。3四叉树格本节正式介绍了四叉树的格。这个定义引入了四叉树作为纯粹的空间对象（事实上，将它们从树的表示中分离出来），因为这提供了对格的最自然的描述四叉树描述了一个规则的正方形网格中的二维正方形集合。网格的每个轴用于捕获一个分析变量。当然，可能有许多分析变量，因此域需要0000092J.M. Howe等人/理论计算机科学电子笔记267（2010）89XYXYXYXYC−XYXYXYn我XYxjxk∈Q∈Q∈QXYn我XYXYXYXj=1 JJxkxlKLXX来捕捉更高维度的关系。虽然四叉树域元素是纯空间的，但直观地说，这些元素源自四叉树的集合，集合中的每个四叉树都在一对变量上。变量对不一定是不相交的，因此域元素中的各种四叉树通过它们在高维空间中的交集相互作用。该域是弱关系的，因为高维关系是由四叉树上的二维关系导出的。3.1四叉树首先，给出了二维四叉树的空间定义。 然后将其用作任意维数定义的基础令X={x1，... x d}是变量的有限集合。设I=[min，max）<$Q表示一个区间，使得min，max ∈ Z，且max=min+2 n，其中n ∈ N.起点是Cn，i的定义，其中x，y∈ X，由I× I网格（其轴为x和y）分解产生的所有正方形的集合，其中粒度为i。当i≤n时，定义为：C i，i={{x，y}} |min ≤ x

下载后可阅读完整内容，剩余1页未读，立即下载