Skip to main content

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:10.1007/s00236-007-0043-2) (KAR id:14587)


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
DOI/Identification number: 10.1007/s00236-007-0043-2
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: 06 May 2020 03:03 UTC
Resource URI: (The current URI for this page, for reference purposes)
Kahrs, Stefan:
  • Depositors only (login required):


Downloads per month over past year