Program schemes, recursion schemes, and formal languages

摘要

This paper presents general methods for studying the problems of translatability between classes of schemes and equivalence of schemes in a given class. There are four methods: applying the theory of formal languages, programming, measuring the complexity of a computation, and “cutting and pasting”. These methods are used to answer several questions of translatability and equivalence for classes of program schemes, program schemes augmented with counters, and recursively defined schemes. In particular, it is shown that (i) the quasirational recursion schemes are translatable into strongly equivalent program schemes, (ii) monadic recursion schemes are translatable into strongly equivalent program schemes with two counters, (iii) there is a monadic recursion scheme not strongly equivalent to any program scheme with one counter.