Infinitary Term Graph Rewriting is Simple, Sound and Complete

Bahr, Patrick

doi:10.4230/LIPIcs.RTA.2012.69

Document

Infinitary Term Graph Rewriting is Simple, Sound and Complete

Author Patrick Bahr

Part of: Volume: 23rd International Conference on Rewriting Techniques and Applications (RTA'12) (RTA 2012)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: International Conference on Rewriting Techniques and Applications (RTA)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2012-05-29

PDF

File

PDF

LIPIcs.RTA.2012.69.pdf

Filesize: 453 kB
16 pages

Document Identifiers

DOI: 10.4230/LIPIcs.RTA.2012.69
URN: urn:nbn:de:0030-drops-34857

Subject Classification

Keywords

term graphs
infinitary rewriting

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

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

Author Details

Patrick Bahr

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail