Expression Reduction Systems and Extensions: An Overview

John R. W. Glauert; Delia Kesner; Zurab Khasidashvili

doi:10.1007/11601548_22

Expression Reduction Systems and Extensions: An Overview

John R. W. Glauert, Delia Kesner, Zurab Khasidashvili

Research output: Chapter in Book/Report/Conference proceeding › Chapter

9 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday
Editors	Aart Middledorp, Vincent van Oostrom, Femke van Raamsdonk, Roel De Vrijer
Place of Publication	Berlin / Heidelberg
Publisher	Springer
Pages	496-553
Number of pages	58
Volume	3838
ISBN (Print)	978-3-540-30911-6
DOIs	https://doi.org/10.1007/11601548_22
Publication status	Published - 2005

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag

Access to Document

10.1007/11601548_22

Cite this

Glauert, J. R. W., Kesner, D., & Khasidashvili, Z. (2005). Expression Reduction Systems and Extensions: An Overview. In A. Middledorp, V. van Oostrom, F. van Raamsdonk, & R. De Vrijer (Eds.), Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday (Vol. 3838, pp. 496-553). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/11601548_22

Glauert, John R. W. ; Kesner, Delia ; Khasidashvili, Zurab. / Expression Reduction Systems and Extensions: An Overview. Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday. editor / Aart Middledorp ; Vincent van Oostrom ; Femke van Raamsdonk ; Roel De Vrijer. Vol. 3838 Berlin / Heidelberg : Springer, 2005. pp. 496-553 (Lecture Notes in Computer Science).

@inbook{799a00e541204939bbe906d6c370de41,

title = "Expression Reduction Systems and Extensions: An Overview",

abstract = "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.",

author = "Glauert, {John R. W.} and Delia Kesner and Zurab Khasidashvili",

year = "2005",

doi = "10.1007/11601548_22",

language = "English",

isbn = "978-3-540-30911-6",

volume = "3838",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "496--553",

editor = "Aart Middledorp and {van Oostrom}, Vincent and {van Raamsdonk}, Femke and {De Vrijer}, Roel",

booktitle = "Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday",

address = "Germany",

}

Glauert, JRW, Kesner, D & Khasidashvili, Z 2005, Expression Reduction Systems and Extensions: An Overview. in A Middledorp, V van Oostrom, F van Raamsdonk & R De Vrijer (eds), Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday. vol. 3838, Lecture Notes in Computer Science, Springer, Berlin / Heidelberg, pp. 496-553. https://doi.org/10.1007/11601548_22

Expression Reduction Systems and Extensions: An Overview. / Glauert, John R. W.; Kesner, Delia; Khasidashvili, Zurab.

Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday. ed. / Aart Middledorp; Vincent van Oostrom; Femke van Raamsdonk; Roel De Vrijer. Vol. 3838 Berlin / Heidelberg : Springer, 2005. p. 496-553 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Expression Reduction Systems and Extensions: An Overview

AU - Glauert, John R. W.

AU - Kesner, Delia

AU - Khasidashvili, Zurab

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11601548_22

DO - 10.1007/11601548_22

M3 - Chapter

SN - 978-3-540-30911-6

VL - 3838

T3 - Lecture Notes in Computer Science

SP - 496

EP - 553

BT - Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday

A2 - Middledorp, Aart

A2 - van Oostrom, Vincent

A2 - van Raamsdonk, Femke

A2 - De Vrijer, Roel

PB - Springer

CY - Berlin / Heidelberg

ER -

Glauert JRW, Kesner D, Khasidashvili Z. Expression Reduction Systems and Extensions: An Overview. In Middledorp A, van Oostrom V, van Raamsdonk F, De Vrijer R, editors, Processes, Terms and Cycles: Steps on the Road to Infinity. Essays dedicated to Jan Willem Klop on the Occasion of His 60th Birthday. Vol. 3838. Berlin / Heidelberg: Springer. 2005. p. 496-553. (Lecture Notes in Computer Science). https://doi.org/10.1007/11601548_22