The manyone 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), 467472
References

1. D. Belsnes and S. O. Aanderaa, Decision problems for tag systems, Notices Amer. Math. Soc. 14 (1967), 950. Abstract #67698.
 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, McGrawHill Series in Information Processing and Computers, McGrawHill Book Co., Inc., New YorkTorontoLondon, 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. SchorrKon 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/S000299041946085559
 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/S000299041967117804
 Ann Yasuhara, A remark on Post normal systems, J. Assoc. Comput. Mach. 14 (1967), 167–171. MR 213240, DOI 10.1145/321371.321384
Additional Information
 Journal: Bull. Amer. Math. Soc. 77 (1971), 467472
 MSC (1970): Primary 02F30, 02F43; Secondary 02F05, 02F15, 02F25, 02F47
 DOI: https://doi.org/10.1090/S000299041971127428
 MathSciNet review: 0281609