Implementing graph algorithms efficiently in a rule-based language is challenging because graph pattern matching is expensive. In this paper, we present a number of linear-time implementations of graph algorithms in GP 2, an experimental programming language based on graph transformation rules which aims to facilitate program analysis and verification. We focus on two classes of rule-based graph programs: graph reduction programs which check some graph property, and programs using a depth-first search to test some property or perform an operation such as producing a 2-colouring or a topological sorting. Programs of the first type run in linear time without any constraints on input graphs while programs of the second type require input graphs of bounded degree to run in linear time. Essential for achieving the linear time complexity are so-called rooted rules in GP 2, which, in many situations, can be matched in constant time. For each of our programs, we prove both correctness and complexity, and also give empirical evidence for their run time.


翻译:在基于规则的语言中高效实施图形算法是困难的,因为图形模式匹配费用昂贵。 在本文中,我们展示了以图形转换规则为基础的GP 2中一些线性时间执行图形算法的实验性编程语言,该语言以图形转换规则为基础,目的是便利程序分析和核实。我们侧重于两类基于规则的图表程序:用于检查某些图形属性的图形减少程序,以及使用深度第一搜索程序测试某些属性或进行生成 2 色或地形排序等操作的程序。第一种类型的程序在线性时间运行,输入图没有任何限制,而第二种类型的程序则需要具有约束度的输入图,以线性时间运行。实现线性时间复杂性的关键是在GP 2中所谓的扎根规则,在许多情况下,这些规则可以随时匹配。对于我们的每一个程序,我们都证明了其正确性和复杂性,并提供了运行时间的经验证据。

0
下载
关闭预览

相关内容

专知会员服务
41+阅读 · 2020年10月13日
系列教程GNN-algorithms之六:《多核卷积拓扑图—TAGCN》
专知会员服务
50+阅读 · 2020年8月8日
迁移学习简明教程,11页ppt
专知会员服务
108+阅读 · 2020年8月4日
一份简单《图神经网络》教程,28页ppt
专知会员服务
126+阅读 · 2020年8月2日
开源书:PyTorch深度学习起步
专知会员服务
51+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
36+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
【论文】图上的表示学习综述
机器学习研究会
15+阅读 · 2017年9月24日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
Arxiv
0+阅读 · 2021年2月21日
Arxiv
0+阅读 · 2021年2月20日
Arxiv
0+阅读 · 2021年2月15日
Heterogeneous Graph Transformer
Arxiv
27+阅读 · 2020年3月3日
Arxiv
92+阅读 · 2020年2月28日
Arxiv
4+阅读 · 2019年4月17日
VIP会员
相关VIP内容
专知会员服务
41+阅读 · 2020年10月13日
系列教程GNN-algorithms之六:《多核卷积拓扑图—TAGCN》
专知会员服务
50+阅读 · 2020年8月8日
迁移学习简明教程,11页ppt
专知会员服务
108+阅读 · 2020年8月4日
一份简单《图神经网络》教程,28页ppt
专知会员服务
126+阅读 · 2020年8月2日
开源书:PyTorch深度学习起步
专知会员服务
51+阅读 · 2019年10月11日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
36+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
94+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
【论文】图上的表示学习综述
机器学习研究会
15+阅读 · 2017年9月24日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】深度学习目标检测概览
机器学习研究会
10+阅读 · 2017年9月1日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Layer Normalization原理及其TensorFlow实现
深度学习每日摘要
32+阅读 · 2017年6月17日
相关论文
Top
微信扫码咨询专知VIP会员