Kahrs, Stefan (2007) Infinitary rewriting: meta-theory and convergence. Acta Informatica, 44 (2). pp. 91-121. ISSN 0001-5903.
|
Download (249Kb)
|
![[img]](http://kar.kent.ac.uk/style/images/fileicons/application_pdf.png)
|
|
| Official URL http://dx.doi.org/10.1007/s00236-007-0043-2 |
||
Abstract
When infinitary rewriting was introduced by Kaplan et.al. 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 > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group |
| Depositing User: | Mark Wheadon |
| Date Deposited: | 24 Nov 2008 18:05 |
| Last Modified: | 06 Sep 2011 01:37 |
| Resource URI: | http://kar.kent.ac.uk/id/eprint/14587 (The current URI for this page, for reference purposes) |
- Depositors only (login required):
