From infinitary term rewriting to cyclic term graph rewriting and back

Research output: Chapter in Book/Report/Conference proceedingConference abstract in proceedingsResearch


Patrick Bahr

Cyclic term graph rewriting has been shown to be adequate for
simulating certain forms of infinitary term rewriting. These forms
are, however, quite restrictive and it would be beneficial to lift
these restriction at least for a limited class of rewriting
systems. In order to better understand the correspondences between
infinite reduction sequences over terms and finite reductions over
cyclic term graphs, we explore different variants of infinitary term
graph rewriting calculi.

To this end, we study different modes of convergence for term graph
rewriting that generalise the modes of convergence usually considered
in infinitary term rewriting. After discussing several different
alternatives, we identify a complete semilattice on term graphs and
derive from it a complete metric space on term graphs. Equipped with
these structures, we can -- analogously to the term rewriting case --
define both a metric and a partial order model of infinitary term
graph rewriting. The resulting calculi of infinitary term graph
rewriting reveal properties similar to the corresponding infinitary
term rewriting calculi.
Original languageEnglish
Title of host publicationProceedings of the 6th International Workshop on Computing with Terms and Graphs
EditorsRachid Echahed
Number of pages1
Publication date11 Feb 2011
Publication statusPublished - 11 Feb 2011
Event6th International Workshop on Computing with Terms and Graphs - Saarbrücken, Germany
Duration: 2 Apr 2011 → …


Workshop6th International Workshop on Computing with Terms and Graphs
Periode02/04/2011 → …
SeriesElectronic Proceedings in Theoretical Computer Science

Bibliographical note

invited talk

Number of downloads are based on statistics from Google Scholar and

No data available

ID: 34445060