Abstract
Based on a simple metric and a simple partial order on term graphs, we develop two infinitary calculi of term graph rewriting. We show that, similarly to infinitary term rewriting, the partial order formalisation yields a conservative extension of the metric formalisation of the calculus. By showing that the resulting calculi simulate the corresponding well-established infinitary calculi of term rewriting in a sound and complete manner, we argue for the appropriateness of our approach to capture the notion of infinitary term graph rewriting.
| Original language | Undefined/Unknown |
|---|---|
| Title of host publication | 23rd International Conference on Rewriting Techniques and Applications (RTA'12) |
| Editors | Ashish Tiwari |
| Number of pages | 16 |
| Volume | 15 |
| Place of Publication | Dagstuhl, Germany |
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH |
| Publication date | 1 May 2012 |
| Pages | 69-84 |
| ISBN (Print) | 978-3-939897-38-5 |
| DOIs | |
| Publication status | Published - 1 May 2012 |
Keywords
- Infinitary Calculi
- Term Graph Rewriting
- Metric Formalisation
- Partial Order
- Conservative Extension