• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract)
【24h】

Logical Locality Entails Frugal Distributed Computation over Graphs (Extended Abstract)

机译：逻辑局部性要求在图上进行节俭的分布式计算（扩展摘要）

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

First-order logic is known to have limited expressive power over finite structures. It enjoys in particular the locality property, which states that first-order formulae cannot have a global view of a structure. This limitation ensures their low sequential computational complexity. We show that the locality impacts as well on their distributed computational complexity. We use first-order formulae to describe the properties of finite connected graphs, which are the topology of communication networks, on which the first-order formulae are also evaluated. We show that over bounded degree networks and planar networks, first-order properties can be frugally evaluated, that is, with only a bounded number of messages, of size logarithmic in the number of nodes, sent over each link. Moreover, we show that the result carries over for the extension of first-order logic with unary counting.
机译：已知一阶逻辑在有限结构上的表达能力有限。它特别具有locality属性，该属性指出一阶公式不能具有结构的全局视图。此限制确保了它们较低的顺序计算复杂度。我们证明了局域性也影响了它们的分布式计算复杂性。我们使用一阶公式来描述有限连通图的属性，这些图是通信网络的拓扑，在该拓扑上也对一阶公式进行了评估。我们表明，在有界度网络和平面网络上，可以很容易地评估一阶属性，即，仅在每个链接上发送的消息数量为一定数量的节点（节点数的大小为对数）。此外，我们证明了该结果对一阶逻辑的扩展具有一元计数。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号