# Infinitary rewriting: closure operators, equivalences and models

Kahrs, Stefan (2013) Infinitary rewriting: closure operators, equivalences and models. Acta Informatica, 50 (2). pp. 123-156. ISSN 0001-5903. (doi:10.1007/s00236-012-0174-y) (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided)

 The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. (Contact us about this Publication) Official URLhttp://dx.doi.org/10.1007/s00236-012-0174-y

## Abstract

Infinitary Term Rewriting allows to express infinite terms and transfinite reductions that converge to those terms. Underpinning the machinery of infinitary rewriting are closure operators on relations that facilitate the formation of transfinite reductions and transfinite equivalence proofs. The literature on infinitary rewriting has largely neglected to single out such closure operators, leaving them implicit in definitions of (transfinite) rewrite reductions, or equivalence relations. This paper unpicks some of those definitions, extracting the underlying closure principles used, as well as constructing alternative operators that lead to alternative notions of reduction and equivalence. A consequence of this unpicking is an insight into the abstraction level at which these operators can be defined. Some of the material in this paper already appeared in Kahrs (2010). The paper also generalises the notion of equational model for infinitary rewriting. This leads to semantics-based notions of equivalence that tie in with the equivalences constructed from the closure operators.

Item Type: Article 10.1007/s00236-012-0174-y infinitary rewriting, closure principles, models Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics Faculties > Sciences > School of Computing > Programming Languages and Systems Group Stefan Kahrs 07 Mar 2013 13:26 UTC 29 May 2019 10:02 UTC https://kar.kent.ac.uk/id/eprint/33337 (The current URI for this page, for reference purposes)