Degrees of Unsolvability in Formal Grammars
- 1 October 1968
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 15 (4) , 680-692
- https://doi.org/10.1145/321479.321490
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.Keywords
This publication has 8 references indexed in Scilit:
- Enumerability · Decidability ComputabilityPublished by Springer Nature ,1965
- On ambiguity in phrase structure languagesCommunications of the ACM, 1962
- On The Ambiguity Problem of Backus SystemsJournal of the ACM, 1962
- A note on phrase structure grammarsInformation and Control, 1959
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)Proceedings of the National Academy of Sciences, 1957
- Recursive Unsolvability of a problem of ThueThe Journal of Symbolic Logic, 1947
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946
- Recursively enumerable sets of positive integers and their decision problemsBulletin of the American Mathematical Society, 1944