Degrees of Unsolvability in Formal Grammars
Dennis F. Cudia, Wilson E. Singletary · Journal of the ACM · 1968
The following theorem is a refinement of an unsolvability result due to E. Post:For any recursively enumerable degree D of recursive unsolvability there is a recursive class of sequences(of the same length)of nonempty words on an alphabet A such that the Post correspondence decision problem for that class is of degree D. This theorem is proved and then applied to obtain degree analogues of the ambiguity problem and the common program problem for the class of context-free grammars.