TU Darmstadt / ULB / TUbiblio

Graph-Rewriting Petri Nets

Kulcsar, Geza ; Lochau, Malte ; Schürr, Andy
eds.: Lambers, Leen ; Weber, Jens (2018)
Graph-Rewriting Petri Nets.
11th International Conference on Graph Transformation (ICGT'18).
Conference or Workshop Item, Bibliographie

Abstract

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.

Item Type: Conference or Workshop Item
Erschienen: 2018
Editors: Lambers, Leen ; Weber, Jens
Creators: Kulcsar, Geza ; Lochau, Malte ; Schürr, Andy
Type of entry: Bibliographie
Title: Graph-Rewriting Petri Nets
Language: English
Date: 2018
Publisher: Springer
Event Title: 11th International Conference on Graph Transformation (ICGT'18)
Abstract:

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.

Divisions: 18 Department of Electrical Engineering and Information Technology
18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering > Real-Time Systems
18 Department of Electrical Engineering and Information Technology > Institute of Computer Engineering
DFG-Collaborative Research Centres (incl. Transregio)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > A: Construction Methodology
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > A: Construction Methodology > Subproject A1: Modelling
Date Deposited: 05 Jul 2018 09:41
Last Modified: 27 Nov 2018 09:40
PPN:
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details