• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic
【24h】

Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic

机译：一阶逻辑中用于图微分的量词深度的上界

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We show that on graphs with n vertices the 2-dimensional Weisfei-ler-Leman algorithm requires at most O(n2/log(n)) iterations to reach stabilization. This in particular shows that the previously best, trivial upper bound of O(n2) is asymptotically not tight. In the logic setting this translates to the statement that if two graphs of size n can be distinguished by a formula in first order logic with counting with 3 variables (i.e., in C3) then they can also be distinguished by a C3-formula that has quantifier depth at most O (n2/log(n)).To prove the result we define a game between two players that enables us to decouple the causal dependencies between the processes happening simultaneously over several iterations of the algorithm. This allows us to treat large color classes and small color classes separately. As part of our proof we show that for graphs with bounded color class size, the number of iterations until stabilization is at most linear in the number of vertices. This also yields a corresponding statement in first order logic with counting.Similar results can be obtained for the respective logic without counting quantifiers, i.e., for the logic L3.
机译：我们表明，在具有n个顶点的图上，二维Weisfei-ler-Leman算法最多需要O（n 2 / log（n））迭代以达到稳定。这尤其表明，O（n 2 ）渐近不紧。在逻辑设置中，这转化为以下语句：如果两个大小为n的图形都可以通过一阶逻辑中的公式用3个变量进行计数来区分（即在C中 3 ），那么它们也可以用C来区分 3 量词深度最大为O（n 2 / log（n））。为证明结果，我们在两个参与者之间定义了一个博弈，使我们能够解耦在多次算法迭代中同时发生的流程之间的因果关系。这使我们可以分别处理大颜色分类和小颜色分类。作为证明的一部分，我们显示出对于有界颜色类大小的图，直到稳定化为止的迭代次数最多为顶点数量的线性。这也会在带有计数的一阶逻辑中产生一个对应的语句，无需对数量进行计数即可获得各个逻辑（即逻辑L）的相似结果。 3 。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号