×

Combinatorial systems defined over one- and two-letter alphabets. (English) Zbl 0336.02035


MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03D10 Turing machines and related notions
03D03 Thue and Post systems, etc.
03D40 Word problems, etc. in computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Boone, W.W.: Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems. Ann. Math.83 (1966), 520–571. · Zbl 0173.01204 · doi:10.2307/1970478
[2] Büchi, J.R., Hosken, W.H.: Canonical systems which produce periodic sets. Math. Systems Theory4 (1970), 81–90. · Zbl 0188.33104 · doi:10.1007/BF01705888
[3] Cudia, D.F., Singletary, W.E.: The Post correspondence problem. J. Symb. Logic33 (1968), 418–430. · Zbl 0169.31105 · doi:10.2307/2270327
[4] Friedburg, R.M.: Two recursively enumerable sets of incomparable degrees of unsolvability (solution to Post’s problem 1944). Proc. Nat’l. Acad. Sci.43 (1957), 236–238. · Zbl 0080.24302 · doi:10.1073/pnas.43.2.236
[5] Hopcroft,J.E., Ullman,J.D.: Formal Languages and their Relation to Automata. Addison-Wesley, 1969. · Zbl 0196.01701
[6] Hughes, C.E.: Degrees of unsolvability associated with Markov algorithms. Internat. J. Comput. Information Sci.1 (1972), 355–365. · Zbl 0298.02040 · doi:10.1007/BF00987253
[7] Hughes, C.E.: Many-one degrees associated with problems of tag. J. Symb. Logic.38 (1973), 1–17. · Zbl 0272.02062 · doi:10.2307/2271723
[8] Hughes, C.E.: The general decision problem for Markov algorithms with axiom. Notre Dame J. Formal Logic.16 (1975), 208–216. · Zbl 0232.02029 · doi:10.1305/ndjfl/1093891701
[9] Hughes, C.E., Singletary, W.E.: Combinatorial systems with axiom. Notre Dame J. Formal Logic.14 (1973), 354–360. · Zbl 0214.01704 · doi:10.1305/ndjfl/1093890999
[10] Hughes, C.E., Overbeek, R., Singletary, W.E.: The many-one equivalence of some general combinatorial decision problems. Bull. Amer. Math. Soc.77 (1971), 467–472. · Zbl 0216.00903 · doi:10.1090/S0002-9904-1971-12742-8
[11] Mučnik A.A.: On the unsolvability of the problem of reducibility in the theory of algorithms. Dokl. Akad. Nauk SSR108 (1956), 194–197.
[12] Overbeek, Ross: The representation of many-one degrees by the word problem for Thus systems. Proc. London Math. Soc. (3)26 (1973), 184–192. · Zbl 0253.02042 · doi:10.1112/plms/s3-26.1.184
[13] Post, E.L.: Formal reductions of the general combinatorial decision problem. Amer. J. Math.65 (1943), 197–215. · Zbl 0063.06327 · doi:10.2307/2371809
[14] Shepherdson, J.C.: Machine configuration and word problems of given degree of unsolvability. Z. Math. Logik Grundlagen11 (1965), 149–175. · Zbl 0161.00803 · doi:10.1002/malq.19650110210
[15] Singletary, W.E.: The equivalence of some general combinatorial decision problems. Bull. Amer. Math. Soc.73 (1967), 446–451. · Zbl 0169.31201 · doi:10.1090/S0002-9904-1967-11780-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.