From higher-order to first-order rewriting
We show how higher-order rewriting may be encoded into first-order rewriting modulo an equational theory ε. We obtain a characterization of the class of higher-order rewriting systems which can be encoded by first-order rewriting modulo an empty theory (that is, ε =ø). This class includes of course...
Guardado en:
Autores principales: | , , |
---|---|
Formato: | SER |
Materias: | |
Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03029743_v2051LNCS_n_p47_Bonelli |
Aporte de: |
Sumario: | We show how higher-order rewriting may be encoded into first-order rewriting modulo an equational theory ε. We obtain a characterization of the class of higher-order rewriting systems which can be encoded by first-order rewriting modulo an empty theory (that is, ε =ø). This class includes of course the λ-calculus. Our technique does not rely on a particular substitution calculus but on a set of abstract properties to be verified by the substitution calculus used in the translation. © Springer-Verlag Berlin Heidelberg 2001. |
---|