Lambda-Representable Functions over Term Algebras

Masako Takahashi

(Tokyo Institute of Technology)

In this paper, we study lambda-representability (by simply typed lambda-calculus) of functions over open/closed term algebras. By extending the standard notion of lambda-representation of closed terms to open terms, and extending the notion of lambda-represen- table functions accordingly, we first give a recursion-theoretic characterization of the class of lambda-representable functions over open term algebras. Then, based on this result, we obtain two characterizations of the class of lambda-representable functions over closed term algebras. As a related topic, in the Appendix we give a simple recursion-theoretic characterization of the set of computable functions on words.
Tuesday 2nd November 1999, 15:00
Seminar Room 322
Department of Computer Science