Infinitary Term Graph Rewriting is Simple, Sound and Complete

    Research output: Conference Article in Proceeding or Book/Report chapterBook chapterResearchpeer-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.
    Original languageUndefined/Unknown
    Title of host publication23rd International Conference on Rewriting Techniques and Applications (RTA'12)
    EditorsAshish Tiwari
    Number of pages16
    Volume15
    Place of PublicationDagstuhl, Germany
    PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
    Publication date1 May 2012
    Pages69-84
    ISBN (Print)978-3-939897-38-5
    DOIs
    Publication statusPublished - 1 May 2012

    Keywords

    • Infinitary Calculi
    • Term Graph Rewriting
    • Metric Formalisation
    • Partial Order
    • Conservative Extension

    Cite this