Proving termination of graph transformation systems using weighted type graphs over semirings
From MaRDI portal
Publication:2947210
DOI10.1007/978-3-319-21145-9_4zbMATH Open1321.68326arXiv1505.01695OpenAlexW1629743385MaRDI QIDQ2947210FDOQ2947210
Authors: H. J. Sander Bruggink, Barbara König, Dennis Nolte, Hans Zantema 
Publication date: 22 September 2015
Published in: Graph Transformation (Search for Journal in Brave)
Abstract: We introduce techniques for proving uniform termination of graph transformation systems, based on matrix interpretations for string rewriting. We generalize this technique by adapting it to graph rewriting instead of string rewriting and by generalizing to ordered semirings. In this way we obtain a framework which includes the tropical and arctic type graphs introduced in a previous paper and a new variant of arithmetic type graphs. These type graphs can be used to assign weights to graphs and to show that these weights decrease in every rewriting step in order to prove termination. We present an example involving counters and discuss the implementation in the tool Grez.
Full work available at URL: https://arxiv.org/abs/1505.01695
Recommendations
- Termination analysis for graph transformation systems
- Towards a systematic method for proving termination of graph transformation systems
- Max/Plus tree automata for termination of term rewriting
- Weighted automata for proving termination of string rewriting
- Modular termination of graph transformation
Cites Work
- Handbook of Graph Grammars and Computing by Graph Transformation
- Title not available (Why is that?)
- Matrix interpretations for proving termination of term rewriting
- Fundamental Approaches to Software Engineering
- Title not available (Why is that?)
- Termination of String Rewriting with Matrix Interpretations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Arctic Termination ...Below Zero
- Termination Analysis of Model Transformations by Petri Nets
- Termination of cycle rewriting
- Proving termination of graph transformation systems using weighted type graphs over semirings
- Termination analysis for graph transformation systems
- Transforming cycle rewriting into string rewriting
- On termination of graph rewriting
Cited In (8)
- Towards a systematic method for proving termination of graph transformation systems
- Termination analysis for graph transformation systems
- Proving termination of graph transformation systems using weighted type graphs over semirings
- Termination of cycle rewriting by transformation and matrix interpretation
- A flexible and easy-to-use library for the rapid development of graph tools in Java
- Termination of graph transformation systems using weighted subgraph counting
- Kruskal's tree theorem for acyclic term graphs
- From linear term rewriting to graph rewriting with preservation of termination
Uses Software
This page was built for publication: Proving termination of graph transformation systems using weighted type graphs over semirings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947210)
