MONADIC RECURSION SCHEMES

More specifically, the basic notions of a Turing Machine, of computable functions and of undecidable properties are needed for Chapter VI (Decision Problems) the definitions of recursive, primitive recursive and partial recursive functions are helpful for Section F of Chapter IV and two of the proofs in Chapter VI. The basic facts regarding regular sets, context-free languages and pushdown store automata are helpful in Chapter VIII (Monadic Recursion Schemes) and in the proof of Theorem 3.14. For Chapter V (Correctness and Program Verification) it is useful to know the basic notation and ideas of the first order predicate calculus a highly abbreviated version of this material appears as Appendix A. 

We shall return to the concept of value languages later in our study of monadic recursion schemes this concept is a powerful tool in studying the relative power of monadic program schemes and monadic recursion schemes. For the present we need only the following simple fact. 

In the special case of monadic recursion schemes, we shall see in Chapter VIII that The classes of monadic recursion schemes and monadic flowchart schemes are incomparable. 

Every monadic recursion scheme can be translated into a flowchart scheme augmented by a simple pushdown store. 

This is not true for monadic recursion schemes. In the monadic case, right linear schemes are intertranslatable with Ianov schemes but the class of linear monadic recursion schemes is more powerful. 

We now focus attention on the special case of monadic recursion schemes. 

Our first result is that the classes of monadic recursion schemes and monadic program schemes are incomparable. We use a somewhat different argument than before to establish the existence of a monadic recursion scheme not translatable into any monadic program scheme. In the case of monadic schemes we save ourselves much notational complication by omitting parentheses and writing F(x) as Fx and f(g(x)) as fgx we often take the additional liberty of emitting the x since its position is obvious. 

A. A MONADIC RECURSION SCHEME WHICH IS NOT FLOWCHARTABLE THEOREM 8.1 The monadic recursion scheme... 

We have shown that the class of monadic recursion schemes is not translatable into the class of monadic program schemes. Before showing that the two classes are in fact incomparable let us consider briefly how we can compute the value of a monadic recursion scheme using a simple pushdown store. 

We can assume that our monadic recursion scheme S has basis functions f, ...,fm and defined functions Fq, ... with Fq initial and that each function is defined by an equation... 

EXAMPLE VIII-1 WHILE SCHEME TO IMPLEMENT A MONADIC RECURSION SCHEME... 

THEOREM 8.2 The class of monadic recursion schemes is effectively translatable into the class of Ianov program schemes augmented by two counters. 

For monadic recursion schemes and certain subcases of monadic program schemes such as Ianov schemes we can also define the interpreted value language. 

To give a uniform definition, let us represent TRUE by 1 and FALSE by 0 and define the interpreted value language L (S) of a monadic recursion scheme S with r tests T-, ...,T as the set of all words of the farm ... 

For monadic recursion schemes S and S it is possible to have L(S) = L(S ) even if S is not strongly equivalent to S - the same output might be given but for different interpretations we saw this in the previous example. 

THEOREM 8.1+ The reversal of the interpreted value language of a monadic recursion scheme is a deterministic context-free language. 

A term in a monadic recursion scheme is right linear if either it contains no defined function letters or else is of the form Fyx for F a defined function letter and y a (possibly empty) string of basis function letters such a term is left linear if it either contains no defined function letters or else is of the form yFx for F a defined function letter and y a (possibly empty) string of basis function letters. A monadic recursion schema S is right linear if in each equation... 

Every context-free language is the value language of sane monadic recursion scheme. 

However not every deterministic context-free language - even if it is in the right format - is the reversal of the interpreted value language of some monadic recursion scheme the regular set xO(fO) is an obvious example. 

These equations form a monadic recursion scheme S(G) and it can be verified... 

THEOREM 8.10 There is a monadic program scheme which is not strongly equivalent to any monadic recursion scheme. 

THEOREM 8.11 The classes of monadic recursion schemes and monadic program schemes are incomparable. 

EXAMPLE VIII-2 - Monadic flowchart scheme P- is not translatable into any strongly equivalent monadic recursion scheme. ... 

Scheme P2 in Example VIII-3 shows that a flowchart scheme may not be translatable into a monadic recursion scheme even if the value language is context-free. The reason is that P2 really combines two schemes. If T(x) = 1, P2...

---