1 Department of Computer Science, Faculty of Science, Københavns Universitet2 Department of Computer Science, Faculty of Science, Københavns Universitet
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.
23rd International Conference on Rewriting Techniques and Applications (rta'12), 2012, p. 69-84
The Faculty of Science; term graphs; infinitary rewriting; simulation; normalising; strong convergence
Main Research Area:
Leibniz International Proceedings in Informatics (lipics)