
05071569
a
05071569
Kennaway, Richard
Severi, Paula
Sleep, Ronan
de Vries, FerJan
Infinitary rewriting: From syntax to semantics.
Middeldorp, Aart (ed.) et al., Processes, terms and cycles: steps on the road to infinity. Essays dedicated to Jan Willem Klop on the occasion of his 60th birthday. Berlin: Springer (ISBN 354030911X/pbk). Lecture Notes in Computer Science 3838, 148172 (2005).
2005
Berlin: Springer
EN
doi:10.1007/11601548
From the introduction: Rewriting is the repeated transformation of a structured object according to a set of rules. This simple concept has turned out to have a rich variety of elaborations, giving rise to many different theoretical frameworks for reasoning about computation. Aside from its theoretical importance, rewriting has also been a significant influence on the design and implementation of real programming languages, most notably the functional and logic programming families of languages. We give an account of a theory of infinitary rewriting, beginning with the initial work done with and inspired by Jan Willem Klop, and ending with some recent work on lambda calculus which derives modeltheoretic notions from the kind of infinite terms which obstruct some traditional theorems of finitary rewriting.