Nominal rewriting systems
Open Access
- 24 August 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 108-119
Abstract
We present a generalisation of first-order rewriting which allows us to deal with terms involving binding operations in an elegant and practical way. We use a nominal approach to binding, in which bound entities are explicitly named (rather than using a nameless syntax such as de Bruijn indices), yet we get a rewriting formalism which respects α-conversion and can be directly implemented. This is achieved by adapting to the rewriting framework the powerful techniques developed by Pitts et al. in the FreshML project.Nominal rewriting can be seen as higher-order rewriting with a first-order syntax and built-in α-conversion. We show that standard (first-order) rewriting is a particular case of nominal rewriting, and that very expressive higher-order systems such as Klop's Combinatory Reduction Systems can be easily defined as nominal rewriting systems. Finally we study confluence properties of nominal rewriting.Keywords
This publication has 12 references indexed in Scilit:
- The Complexity of Equivariant UnificationLecture Notes in Computer Science, 2004
- Translating Combinatory Reduction Systems into the Rewriting CalculusElectronic Notes in Theoretical Computer Science, 2003
- FreshML2003
- Nominal UnificationLecture Notes in Computer Science, 2003
- A λ-calculus with explicit weakening and explicit substitutionMathematical Structures in Computer Science, 2001
- Higher-order rewrite systems and their confluenceTheoretical Computer Science, 1998
- Modularity of strong normalization in the algebraic-λ-cubeJournal of Functional Programming, 1997
- Polymorphic Rewriting Conserves Algebraic ConfluenceInformation and Computation, 1994
- Combinatory reduction systems: introduction and surveyTheoretical Computer Science, 1993
- Polymorphic rewriting conserves algebraic strong normalizationTheoretical Computer Science, 1991