Degrees of Unsolvability in Formal Grammars

ABSTRACT

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.

REFERENCES

• 1: BAR-HILLEL, Y., PERLES, M., AND SHAMIR, E. On formal properties of simple phrase structure grammars. Z. Phonetik, Sprachwiss. Kommunikationsforsch. 14 (1961), 143-172.
• 2: David G. Cantor, On The Ambiguity Problem of Backus Systems, Journal of the ACM (JACM), v.9 n.4, p.477-479, Oct. 1962 [doi>10.1145/321138.321145]
• 3: CHOMSKY, N. A note on phrase structure grammars. In}orm. Cont. 2 (1959), 393-395.
• 4: Formal properties of grammars. In Luee, R. D., Bush, R. R., and Galanter, E. (Eds.), Handbook of Mathematical Psychology, Vol. II, Wiley, New York, 1963, pp. 323-418.
• 5: DAvis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
• 6: Robert W. Floyd, On ambiguity in phrase structure languages, Communications of the ACM, v.5 n.10, p.526, Oct. 1962 [doi>10.1145/368959.368993]
• 7: FRIEDBERG, R.M. Two reeursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944). Proe. Nat. Acad. Sci. 43 (1957), 236-238.
• 8: HERMES, H. Aufzdhlbarkeit, Entscheidbarkeit, Berechenbarkeit. Springer-Verlag, Berlin, 1961. (Also published in English ed. : Enumerability, Decidability, Computability, Springer- Verlag, Berlin, 1965.)
• 9: KLEENE, S. C. Introduction to Metamathematics. Van Nostrand, Princeton, N. J., 1952.
• 10: MUCNIK, A. A. Negative answer to the problem of reducibility of the theory of algorithms (in Russian). Dokl. Akad. Nauk S.S.S.R. (n.s.) 108 (1956), 194-197.
• 11: POST, E.L. Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc. 50 (1944), 284-316.
• 12: A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946), 264-268.
• 13: Recursive unsolvability of a problem of Thue. J. Symbolic Logic 12 (1947), 1-11.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

General Terms:
Languages, Performance, Theory, Verification