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:https://doi.org/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 URL
http://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
Uncontrolled keywords: infinitary rewriting, closure principles, models
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics
Divisions: Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Stefan Kahrs
Date Deposited: 07 Mar 2013 13:26 UTC
Last Modified: 11 Apr 2013 11:06 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/33337 (The current URI for this page, for reference purposes)
  • Depositors only (login required):