LIPIcs.RTA.2012.69.pdf
- Filesize: 453 kB
- 16 pages
Document
Infinitary Term Graph Rewriting is Simple, Sound and Complete
Author
-
Part of:
Volume:
23rd International Conference on Rewriting Techniques and Applications (RTA'12) (RTA 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Rewriting Techniques and Applications (RTA) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-05-29
Cite As Get BibTex
Patrick Bahr. Infinitary Term Graph Rewriting is Simple, Sound and Complete. In 23rd International Conference on Rewriting Techniques and Applications (RTA'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 15, pp. 69-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.RTA.2012.69
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.
Subject Classification
Keywords
- term graphs
- infinitary rewriting
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads