Infinitary Term Graph Rewriting is Simple, Sound and Complete

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


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