Infinitary Term Graph Rewriting is Simple, Sound and Complete

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelBidrag til bog/antologiForskningpeer review

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.
OriginalsprogUdefineret/Ukendt
Titel23rd International Conference on Rewriting Techniques and Applications (RTA'12)
RedaktørerAshish Tiwari
Antal sider16
Vol/bind15
UdgivelsesstedDagstuhl, Germany
ForlagSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publikationsdato1 maj 2012
Sider69-84
ISBN (Trykt)978-3-939897-38-5
DOI
StatusUdgivet - 1 maj 2012

Citationsformater