Simple context-free languages and free monadic recursion schemes

A context-free language is said to be simple if it is accepted by a single-state deterministic pushdown store acceptor that operates in real-time and accepts by empty store. While the problem remains open of deciding whether or not the language accepted by a deterministic pushdown store acceptor is simple, it is shown that this problem is equivalent to another problem in schemata theory. This question is that of determining whether or not a monadic recursion scheme has a strongly equivalent free scheme.This research was supported in part by the National Science Foundation, Grant No. NSF GJ-803 and DCR74-15091.