Infinitary rewriting: meta-theory and convergence

Kahrs, Stefan (2007) Infinitary rewriting: meta-theory and convergence. Acta Informatica, 44 (2). pp. 91-121. ISSN 0001-5903. (doi: (Full text available)

Download (300kB) Preview
Official URL


When infinitary rewriting was introduced by Kaplan at the beginning of the 1990s, its term universe was explained as the metric completion of a metric on finite terms. The motivation for this connection to topology was that it allowed to import other well-studied notions from metric spaces, in particular the notion of convergence as a replacement for normalisation. This paper generalises the approach by parameterising it with a term metric, and applying the process of metric completion not only to terms but also to operations on and relations between terms. The resulting meta-theory is studied, leading to a revised notion of infinitary rewrite system. For these systems a method is devised to prove their convergence.

Item Type: Article
Uncontrolled keywords: rewriting topology infinitary
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Faculties > Sciences > School of Computing > Theoretical Computing Group
Depositing User: Mark Wheadon
Date Deposited: 24 Nov 2008 18:05 UTC
Last Modified: 28 Jun 2017 01:06 UTC
Resource URI: (The current URI for this page, for reference purposes)
  • Depositors only (login required):