We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Infinitary rewriting: meta-theory and convergence.
- Authors
Kahrs, Stefan
- Abstract
When infinitary rewriting was introduced by Kaplan et al. (Principles of Programming Languages, ACM, New York, pp. 250–259, 1989) 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.
- Subjects
INFINITARY languages; MATHEMATICAL logic; PROGRAMMING languages; METRIC spaces; TOPOLOGY; STOCHASTIC convergence
- Publication
Acta Informatica, 2007, Vol 44, Issue 2, p91
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-007-0043-2