Infinitary term graph rewriting is simple, sound and complete

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Patrick Bahr
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.
Original languageEnglish
Title of host publication23rd International Conference on Rewriting Techniques and Applications (RTA'12)
EditorsAshish Tiwari
Number of pages16
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2012
Pages69-84
ISBN (Electronic)978-3-939897-38-5
DOIs
Publication statusPublished - 2012
Event23rd International Conference on Rewriting Techniques and Applications - Nagoya, Japan
Duration: 28 May 20122 Jun 2012
Conference number: 23

Conference

Conference23rd International Conference on Rewriting Techniques and Applications
Nummer23
LandJapan
ByNagoya
Periode28/05/201202/06/2012
SeriesLeibniz International Proceedings in Informatics
Volume15
ISSN1868-8969

    Research areas

  • Faculty of Science - term graphs, infinitary rewriting, simulation, normalising, strong convergence

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 38429358