Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

The many-one equivalence of some general combinatorial decision problems


Authors: C. E. Hughes, Ross Overbeek and W. E. Singletary
Journal: Bull. Amer. Math. Soc. 77 (1971), 467-472
MSC (1970): Primary 02F30, 02F43; Secondary 02F05, 02F15, 02F25, 02F47
DOI: https://doi.org/10.1090/S0002-9904-1971-12742-8
MathSciNet review: 0281609
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • 1. D. Belsnes and S. O. Aanderaa, Decision problems for tag systems, Notices Amer. Math. Soc. 14 (1967), 950. Abstract #67-698.
  • 2. P. Axt and W. E. Singletary, On deterministic normal systems, Z. Math. Logik Grundlagen Math. 15 (1969), 49-62. MR 265166
  • 3. W. W. Boone, Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems, Ann. of Math. (2) 83 (1966), 520-571; Bull. Amer. Math. Soc. 68 (1962), 616-623. MR 34 #1381. MR 201499
  • 4. D. F. Cudia and W. E. Singletary, The Post correspondence problem, J. Symbolic Logic 33 (1968), 418-430. MR 39 #5367. MR 244050
  • 5. D. F. Cudia and W. E. Singletary, Degrees of unsolvability in formal grammars, J. Assoc. Comput. Mach. 15 (1968), 680-692. MR 38 #5534. MR 237244
  • 6. M. Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill, New York, 1958. MR 23 #A1525. MR 124208
  • 7. P. K. Hooper, Monogenic Post normal systems of arbitrary degree, J. Assoc. Comput. Mach. 13 (1966), 359-363. MR 33 #3846. MR 195648
  • 8. A. A. Markov, Theory of algorithms, Trudy Mat. Inst. Steklov. 42 (1954); English transl., Israel Program Scientific Translations, Jerusalem, 1961. MR 17, 1038; MR 24 #A2527. MR 132690
  • 9. S. Ju. Maslov, On E. L. Post's "tag problem", Trudy Mat. Inst. Steklov, 72 (1964), 57-68; English transl., Amer. Math. Soc. Transl. (2) 97 (1970), 1-14. MR 34 #4129. MR 204285
  • 10. M. 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 25 #3825. MR 140405
  • 11. E. L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197-215. MR 4, 209. MR 7893
  • 12. E. L. Post, A variant of a recursively unsolvable problem, Bull. Amer. Math. Soc. 52 (1946), 264-268, MR 7, 405. MR 15343
  • 13. E. L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1-11. MR 8, 558. MR 20527
  • 14. J. C. Shepherdson, Machine configuration and word problems of given degree of unsolvability, Z. Math. Logik Grundlagen Math. 11 (1965), 149-175. MR 30 #4681. MR 174480
  • 15. W. E. Singletary, The equivalence of some general combinatorial decision problems, Bull. Amer. Math. Soc. 73 (1967), 446-451. MR 35 #1477. MR 210590
  • 16. A. Yasuhara, A remark on Post normal systems, J. Assoc. Comput. Mach. 1 (1967), 167-171. MR 35 #4104. MR 213240

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1970): 02F30, 02F43, 02F05, 02F15, 02F25, 02F47

Retrieve articles in all journals with MSC (1970): 02F30, 02F43, 02F05, 02F15, 02F25, 02F47


Additional Information

DOI: https://doi.org/10.1090/S0002-9904-1971-12742-8

American Mathematical Society