Expression Reduction Systems and Extensions: An Overview

Glauert, John R. W., Kesner, Delia and Khasidashvili, Zurab (2005) Expression Reduction Systems and Extensions: An Overview. In: Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, 3838 . Springer, Berlin / Heidelberg, pp. 496-553. ISBN 978-3-540-30911-6

Full text not available from this repository. (Request a copy)


Expression Reduction Systems is a formalism for higher-order rewriting, extending Term Rewriting Systems and the lambda-calculus. Here we give an overview of results in the literature concerning ERSs. We review confluence, normalization and perpetuality results for orthogonal ERSs. Some of these results are extended to orthogonal conditional ERSs. Further, ERSs with patterns are introduced and their confluence is discussed. Finally, higher-order rewriting is translated into equational first-order rewriting. The technique develops an isomorphic model of ERSs with variable names, based on de Bruijn indices.

Item Type: Book Section
Faculty \ School: Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Computer Graphics (former - to 2018)
Faculty of Science > Research Groups > Interactive Graphics and Audio
Depositing User: EPrints Services
Date Deposited: 01 Oct 2010 13:41
Last Modified: 16 Jun 2023 00:44
DOI: 10.1007/11601548_22

Actions (login required)

View Item View Item