Convergence in Infinitary Term Graph Rewriting Systems is Simple (Extended Abstract)

Patrick Bahr
(Department of Computer Science, University of Copenhagen)

In this extended abstract, we present a simple approach to convergence on term graphs that allows us to unify term graph rewriting and infinitary term rewriting. This approach is based on a partial order and a metric on term graphs. These structures arise as straightforward generalisations of the corresponding structures used in infinitary term rewriting. We compare our simple approach to a more complicated approach that we developed earlier and show that this new approach is superior in many ways. The only unfavourable property that we were able to identify, viz. failure of full correspondence between weak metric and partial order convergence, is rectified by adopting a strong convergence discipline.

In Rachid Echahed and Detlef Plump: Proceedings 7th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2013), Rome, 23th March 2013, Electronic Proceedings in Theoretical Computer Science 110, pp. 17–28.
Published: 25th February 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.110.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org