The many-one equivalence of some general combinatorial decision problems

Hughes, C. E.; Overbeek, Ross; Singletary, W. E.

doi:10.1090/S0002-9904-1971-12742-8

The many-one equivalence of some general combinatorial decision problems
HTML articles powered by AMS MathViewer

by C. E. Hughes, Ross Overbeek and W. E. Singletary PDF

Bull. Amer. Math. Soc. 77 (1971), 467-472

References

Paul Axt and W. E. Singletary, On deterministic normal systems, Z. Math. Logik Grundlagen Math. 15 (1969), 49–62. MR 265166, DOI 10.1002/malq.19690150401
William W. Boone, Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems, Ann. of Math. (2) 83 (1966), 520–571. MR 201499, DOI 10.2307/1970478
Dennis F. Cudia and Wilson E. Singletary, The Post correspondence problem, J. Symbolic Logic 33 (1968), 418–430. MR 244050, DOI 10.2307/2270327
Dennis F. Cudia and Wilson E. Singletary, Degrees of unsolvability in formal grammars, J. Assoc. Comput. Mach. 15 (1968), 680–692. MR 237244, DOI 10.1145/321479.321490
Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208
Philip K. Hooper, Monogenic Post normal systems of arbitrary degree, J. Assoc. Comput. Mach. 13 (1966), 359–363. MR 195648, DOI 10.1145/321341.321344
A. A. Markov, Theory of algorithms, Published for The National Science Foundation, Washington, D.C. and The Department of Commerce by The Israel Program for Scientific Translations, Jerusalem, 1961. Translated by Jacques J. Schorr-Kon and PST Staff. MR 0132690
S. Ju. Maslov, On E. L. Post’s “tag problem”, Trudy Mat. Inst. Steklov. 72 (1964), 57–68 (Russian). MR 0204285
Marvin L. Minsky, Recursive unsolvability of Post’s problem of “tag” and other topics in theory of Turing machines, Ann. of Math. (2) 74 (1961), 437–455. MR 140405, DOI 10.2307/1970290
Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197–215. MR 7893, DOI 10.2307/2371809
Emil L. Post, A variant of a recursively unsolvable problem, Bull. Amer. Math. Soc. 52 (1946), 264–268. MR 15343, DOI 10.1090/S0002-9904-1946-08555-9
Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. MR 20527, DOI 10.2307/2267170
J. C. Shepherdson, Machine configuration and word problems of given degree of unsolvability, Z. Math. Logik Grundlagen Math. 11 (1965), 149–175. MR 174480, DOI 10.1002/malq.19650110210
W. E. Singletary, The equivalence of some general combinatorial decision problems, Bull. Amer. Math. Soc. 73 (1967), 446–451. MR 210590, DOI 10.1090/S0002-9904-1967-11780-4
Ann Yasuhara, A remark on Post normal systems, J. Assoc. Comput. Mach. 14 (1967), 167–171. MR 213240, DOI 10.1145/321371.321384