Graph-Rewriting Petri Nets
Graph-Rewriting Petri Nets
复制标题
图重写 Petri 网
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Andy Schürr
中科院分区：
文献类型：
--
作者：
Géza Kulcsár;Malte Lochau;Andy Schürr
受控图重写增强了普通图重写系统的表达能力（即，图重写规则集）。在这方面，控制图重写的形式化语义基础是不可避免的，作为基于工具的规范和基于图的算法的自动分析的可靠基础。虽然在文献中已经提出了几个有前途的尝试，全面的理论控制图重写捕捉语义的微妙之处，先进的控制结构提供了实用的工具仍然是一个开放的挑战。在本文中，我们提出了图重写Petri网（GPN）作为一个新的基础统一控制流和规则应用语义的控制图重写。GPN实例化着色Petri网与分类的基于DPO的图重写理论，其中令牌颜色表示类型化的图和图态射和转换定义模板的保护图重写规则的应用程序。因此，GPN享有丰富的规范和分析技术的Petri网，包括固有的并发概念。为了证明GPN的表现力，我们提出了一个案例研究的拓扑控制算法的无线传感器网络。
Controlled graph rewriting enhances expressiveness of plain graph-rewriting systems (i.e., sets of graph-rewriting rules) by introducing additional constructs for explicitly controlling graph-rewriting rule applications. In this regard, a formal semantic foundation for controlled graph rewriting is inevitable as a reliable basis for tool-based specification and automated analysis of graph-based algorithms. Although several promising attempts have been proposed in the literature, a comprehensive theory of controlled graph rewriting capturing semantic subtleties of advanced control constructs provided by practical tools is still an open challenge. In this paper, we propose graph-rewriting Petri nets (GPN) as a novel foundation for unifying control-flow and rule-application semantics of controlled graph rewriting. GPN instantiate coloured Petri nets with categorical DPO-based graph-rewriting theory where token colours denote typed graphs and graph morphisms and transitions define templates for guarded graph-rewriting rule applications. Hence, GPN enjoy the rich body of specification and analysis techniques of Petri nets including inherent notions of concurrency. To demonstrate expressiveness of GPN, we present a case study by means of a topology-control algorithm for wireless sensor networks.