RANK 2 INTERSECTION TYPE ASSIGNMENT IN TERM REWRITING SYSTEMS

Article type: Research Article

Authors: Bakel, Steffen van

Affiliations: Dipartimento di Informatica, Università degli Studi di Torino. Corso Svizzera 185, 10149 Torino, Italia. E-mail: bakel@di.unito.it

Abstract: A notion of type assignment on Curryfied Term Rewriting Systems is introduced that uses Intersection Types of Rank 2, and in which all function symbols are assumed to have a type. Type assignment will consist of specifying derivation rules that describe how types can be assigned to terms, using the types of function symbols. Using a modified unification procedure, for each term the principal pair (of basis and type) will be defined in the following sense: from these all admissible pairs can be generated by chains of operations on pairs, consisting of the operations substitution, copying, and weakening. In general, given an arbitrary typeable GTRS, the subject reduction property does not hold. Using the principal type for the left-hand side of a rewrite rule, a sufficient and decidable condition will be formulated that typeable rewrite rules should satisfy in order to obtain this property.

DOI: 10.3233/FI-1996-26204

Journal: Fundamenta Informaticae, vol. 26, no. 2, pp. 141-166, 1996