Simple languages and free schemes
Emily P. Friedman · 1976
A context-free language is said to be simple if it is accepted by a single-state deterministic push-down 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.