Tree Rewriting Systems, Combinatory Weak Reduction Systems and Type Free Languages¹

Article type: Research Article

Authors: Pettorossi, Alberto

Affiliations: Istituto di Analisi dei Sistemi ed Informatica Roma

Note: [1] This work was supported by the Consiglio Nazionale delle Ricerche (Italy).

Abstract: In this paper we consider combinators as tree transducers: this approach is based on the one-to-one correspondence between terms of Combinatory Logic and trees, and on the fact that combinators may be considered as transformers of terms. Since combinators are terms themselves, we will deal with trees as objects to be transformed and tree transformers as well. Methods for defining and studying tree rewriting systems inside Combinatory Weak Reduction Systems and Weak Combinatory Logic are also analyzed and particular attention is devoted to the problem of finiteness and infinity of the generated tree languages (here defined). This implies the study of the termination of the rewriting process (i.e. reduction) for combinators.

Keywords: Combinatory Logic, Combinatory Weak Reduction Systems, Tree Languages, Tree Transducers, Termination, Rewriting Systems, Type Free Languages

DOI: 10.3233/FI-1982-53-404

Journal: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 279-299, 1982