Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings
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...
Main Authors: | , , , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2015
|
Subjects: | |
Online Access: | http://arxiv.org/abs/1505.01695 |
id |
ftarxivpreprints:oai:arXiv.org:1505.01695 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:1505.01695 2023-11-12T04:12:47+01:00 Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings Bruggink, H. J. Sander König, Barbara Nolte, Dennis Zantema, Hans 2015-05-07 http://arxiv.org/abs/1505.01695 unknown http://arxiv.org/abs/1505.01695 Computer Science - Logic in Computer Science Computer Science - Formal Languages and Automata Theory text 2015 ftarxivpreprints 2023-10-15T01:06:15Z 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 is inspired by the tropical and arctic type graphs of [5] and introduces 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. Text Arctic ArXiv.org (Cornell University Library) Arctic |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Computer Science - Logic in Computer Science Computer Science - Formal Languages and Automata Theory |
spellingShingle |
Computer Science - Logic in Computer Science Computer Science - Formal Languages and Automata Theory Bruggink, H. J. Sander König, Barbara Nolte, Dennis Zantema, Hans Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings |
topic_facet |
Computer Science - Logic in Computer Science Computer Science - Formal Languages and Automata Theory |
description |
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 is inspired by the tropical and arctic type graphs of [5] and introduces 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. |
format |
Text |
author |
Bruggink, H. J. Sander König, Barbara Nolte, Dennis Zantema, Hans |
author_facet |
Bruggink, H. J. Sander König, Barbara Nolte, Dennis Zantema, Hans |
author_sort |
Bruggink, H. J. Sander |
title |
Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings |
title_short |
Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings |
title_full |
Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings |
title_fullStr |
Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings |
title_full_unstemmed |
Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings |
title_sort |
proving termination of graph transformation systems using weighted type graphs over semirings |
publishDate |
2015 |
url |
http://arxiv.org/abs/1505.01695 |
geographic |
Arctic |
geographic_facet |
Arctic |
genre |
Arctic |
genre_facet |
Arctic |
op_relation |
http://arxiv.org/abs/1505.01695 |
_version_ |
1782331122383847424 |