×

zbMATH — the first resource for mathematics

Strong reducibilities. (English) Zbl 0484.03024

MSC:
03D30 Other degrees and reducibilities in computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03D35 Undecidability and degrees of sets of sentences
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] O. V. Belegradek, \?-degrees of the word problem, Sibirsk. Mat. Zh. 19 (1978), no. 6, 1232 – 1236, 1436 (Russian).
[2] P. F. Cohen, Weak truth-table reducibility and the pointwise ordering of 1-1 recursive functions, Doctoral Dissertation, Univ. of Illinois, Urbana, Illinois, 1975.
[3] A. N. Degtev, Several remarks on retraceable, regressive and pointwise decomposable sets, Algebra i Logika 9 (1970), 651 – 660 (Russian).
[4] A. N. Degtev, Hypersimple sets with retraceable complements, Algebra i Logika 10 (1971), 235 – 246 (Russian). · Zbl 0259.02031
[5] A. N. Degtev, m-powers of simple sets, Algebra and Logic 11 (1972), 74-80. · Zbl 0287.02027
[6] A. N. Degtev, Hereditary sets and tabular reducibility, Algebra and Logic 11 (1972), 145-152. · Zbl 0283.02035
[7] A. N. Dëgtev, \?\?- and \?-degrees, Algebra i Logika 12 (1973), 143 – 161, 243 (Russian).
[8] A. N. Degtëv, Partially ordered sets of 1-degrees that occur in recursively enumerable \?-degrees, Algebra i Logika 15 (1976), no. 3, 249 – 266, 365 (Russian).
[9] A. N. Dëgtev, Minimal 1-degrees, and truth-table reducibility, Sibirsk. Mat. Ž. 17 (1976), no. 5, 1014 – 1022, 1196 (Russian). · Zbl 0356.02037
[10] A. N. Dëgtev, m-degrees of supersets of simple sets, Mat. Zametki 23 (1978), no. 6, 889 – 893 (Russian). · Zbl 0387.03014
[11] A. N. Dëgtev, Three theorems on \?\?-degrees, Algebra i Logika 17 (1978), no. 3, 270 – 281, 357 – 358 (Russian).
[12] S. D. Denisov, The \?-degrees of recursively enumerable sets, Algebra i Logika 9 (1970), 422 – 427 (Russian).
[13] A. N. Degtev, Three theorems on elementary theories and tt-reducibility, Algebra and Logic 13 (1974), 1-2.
[14] J. C. E. Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791 – 796. · Zbl 0056.24902
[15] Ju. L. Eršov, Hyperhypersimple \?-degrees, Algebra i Logika 8 (1969), 523 – 552 (Russian).
[16] Ju. L. Eršov, Inseparable pairs, Algebra i Logika 9 (1970), 661 – 666 (Russian).
[17] Ju. L. Eršov, Positive equivalences, Algebra i Logika 10 (1971), 620 – 650 (Russian).
[18] Ju. L. Eršov, The upper semilattice of numerations of a finite set, Algebra i Logika 14 (1975), no. 3, 258 – 284, 368 (Russian). · Zbl 0342.02027
[19] Ju. L. Eršov and I. A. Lavrov, The upper semilattice \?(\?), Algebra i Logika 12 (1973), 167 – 189, 243 – 244 (Russian).
[20] Ju. L. Eršov, I. A. Lavrov, A. D. Taĭmanov, and M. A. Taĭclin, Elementary theories, Uspehi Mat. Nauk 20 (1965), no. 4 (124), 37 – 108 (Russian). · Zbl 0199.03001
[21] Jeanne Ferrante and Charles W. Rackoff, The computational complexity of logical theories, Lecture Notes in Mathematics, vol. 718, Springer, Berlin, 1979. · Zbl 0404.03028
[22] Richard M. Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Logic 23 (1958), 309 – 316. · Zbl 0088.01601
[23] R. L. Goodstein, Recursive analysis, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Co., Amsterdam, 1961. · Zbl 0217.30202
[24] Peter G. Hinman, Recursion-theoretic hierarchies, Springer-Verlag, Berlin-New York, 1978. Perspectives in Mathematical Logic. · Zbl 0371.02017
[25] Carl G. Jockusch Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420 – 436. · Zbl 0198.32402
[26] Carl G. Jockusch Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229 – 237. · Zbl 0188.02604
[27] Carl G. Jockusch Jr., Degrees in which the recursive sets are uniformly recursive, Canad. J. Math. 24 (1972), 1092 – 1099. · Zbl 0221.02029 · doi:10.4153/CJM-1972-113-9 · doi.org
[28] Carl G. Jockusch Jr. and Robert I. Soare, Post’s problem and his hypersimple set, J. Symbolic Logic 38 (1973), 446 – 452. · Zbl 0279.02023 · doi:10.2307/2273042 · doi.org
[29] S. Kallibekov, Index sets of degrees of unsolvability, Algebra i Logika 10 (1971), 316 – 326 (Russian).
[30] S. Kallibekov, The degrees of recursively enumerable sets, Sibirsk. Mat. Ž. 14 (1973), 421 – 426, 463 (Russian). · Zbl 0275.02039
[31] S. Kallibekov, The degrees of recursively enumerable sets, Sibirsk. Mat. Ž. 14 (1973), 421 – 426, 463 (Russian). · Zbl 0275.02039
[32] A. S. Kechris and D. A. Martin, Infinite games and effective descriptive set theory, Proc. of London Conf. on Analytic Sets, 1978.
[33] G. N. Kobzev, btt-reducibility. I, II, Algebra i Logika 12 (1973), 190 – 204, 244; ibid. 12 (1973), 433 – 444, 492 (Russian).
[34] G. N. Kobzev, btt-reducibility. I, II, Algebra i Logika 12 (1973), 190 – 204, 244; ibid. 12 (1973), 433 – 444, 492 (Russian).
[35] G. N. Kobzev, On r-separable sets (preprint). · Zbl 0355.60029
[36] G. N. Kobzev, The semilattice of tt-degrees, Sakharth. SSR Mecn. Akad. Moambe 90 (1978), no. 2, 281 – 283 (Russian, with English and Georgian summaries). G. N. Kobzev, tt-degrees of recursively enumerable Turing degrees, Mat. Sb. 106(148) (1978), no. 4, 507 – 514 (Russian). · Zbl 0389.03016
[37] G. N. Kobzev, The semilattice of tt-degrees, Sakharth. SSR Mecn. Akad. Moambe 90 (1978), no. 2, 281 – 283 (Russian, with English and Georgian summaries). G. N. Kobzev, tt-degrees of recursively enumerable Turing degrees, Mat. Sb. 106(148) (1978), no. 4, 507 – 514 (Russian). · Zbl 0389.03016
[38] G. N. Kobzev, Recursively enumerable \?\?-degrees, Mat. Zametki 21 (1977), no. 6, 839 – 846 (Russian). · Zbl 0402.03039
[39] G. L. Kurdjumov, An algorithm-theoretic method for the study of homogeneous random media, Dokl. Akad. Nauk SSSR 238 (1978), no. 5, 1047 – 1050 (Russian). · Zbl 0398.68023
[40] A. H. Lachlan, A note on universal sets, J. Symbolic Logic 31 (1966), 573 – 574. · Zbl 0239.02021 · doi:10.2307/2269692 · doi.org
[41] A. H. Lachlan, Initial segments of one-one degrees, Pacific J. Math. 29 (1969), 351 – 366. · Zbl 0182.01603
[42] A. H. Lachlan, Initial segments of many-one degrees, Canad. J. Math. 22 (1970), 75 – 85. · Zbl 0229.02036 · doi:10.4153/CJM-1970-010-6 · doi.org
[43] A. H. Lachlan, Solution to a problem of Spector, Canad. J. Math. 23 (1971), 247 – 256. · Zbl 0272.02064 · doi:10.4153/CJM-1971-024-7 · doi.org
[44] A. H. Lachlan, Recursively enumerable many-one degrees, Algebra i Logika 11 (1972), 326 – 358, 362.
[45] A. H. Lachlan, Two theorems of many-one degrees of recursively enumerable sets, Algebra i Logika 11 (1972), 216 – 229, 239.
[46] A. H. Lachlan, \?\?\?-complete sets are not necessarily \?\?-complete, Proc. Amer. Math. Soc. 48 (1975), 429 – 434. · Zbl 0311.02048
[47] Alistair H. Lachlan, A recursively enumerable degree which will not split over all lesser ones, Ann. Math. Logic 9 (1976), no. 4, 307 – 365. · Zbl 0357.02040 · doi:10.1016/0003-4843(76)90016-4 · doi.org
[48] A. H. Lachlan and R. Lebeuf, Countable initial segments of the degrees of unsolvability, J. Symbolic Logic 41 (1976), no. 2, 289 – 300. · Zbl 0361.02054 · doi:10.2307/2272227 · doi.org
[49] Richard E. Ladner, On the structure of polynomial time reducibility, J. Assoc. Comput. Mach. 22 (1975), 155 – 171. · Zbl 0322.68028 · doi:10.1145/321864.321877 · doi.org
[50] Richard E. Ladner and Leonard P. Sasso Jr., The weak truth table degrees of recursively enumerable sets, Ann. Math. Logic 8 (1975), no. 4, 429 – 448. · Zbl 0324.02028 · doi:10.1016/0003-4843(75)90007-8 · doi.org
[51] Manuel Lerman, Turing degrees and many-one degrees of maximal sets, J. Symbolic Logic 35 (1970), 29 – 40. · Zbl 0198.02503 · doi:10.2307/2271152 · doi.org
[52] S. S. Marčenkov, The existence of recursively enumerable minimal truth-table degrees, Algebra i Logika 14 (1975), no. 4, 422 – 429 (Russian).
[53] S. S. Marchenkov, On the congruence of the upper semilattices of recursively enumerable m-powers and tabular powers, Math. Notes Acad. Sci. USSR 20 (1976), 567-570. · Zbl 0372.02022
[54] S. S. Marchenkov, Tabular powers of maximal sets, Math. Notes Acad. Sci. USSR 20 (1976), 766-770. · Zbl 0378.02021
[55] S. S. Marchenkov, One class of partial sets, Math. Notes Acad. Sci. USSR 20 (1976), 823-825. · Zbl 0396.03035
[56] Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363 – 371. · Zbl 0336.02049 · doi:10.2307/1971035 · doi.org
[57] D. A. Martin, Descriptive set theory, Handbook of Math. Logic, (Barwise ), North-Holland, Amsterdam, 1977, pp. 783-815.
[58] D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205 – 209. · Zbl 0209.01204 · doi:10.2307/2270510 · doi.org
[59] G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289 – 320. · Zbl 0469.03028 · doi:10.1016/0003-4843(79)90011-1 · doi.org
[60] D. P. Miller, Ph. D. dissertation, University of Chicago, 1981.
[61] Webb Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159 – 166. · Zbl 0216.29102
[62] T. G. McLaughlin, A theorem on intermediate reducibilities, Proc. Amer. Math. Soc. 19 (1968), 87 – 90. · Zbl 0295.02024
[63] Anil Nerode and Richard A. Shore, Second order logic and first order theories of reducibility orderings, The Kleene Symposium (Proc. Sympos., Univ. Wisconsin, Madison, Wis., 1978), Stud. Logic Foundations Math., vol. 101, North-Holland, Amsterdam-New York, 1980, pp. 181 – 200. · Zbl 0465.03024
[64] P. G. Odifreddi, Classical recursion theory (to appear). · Zbl 0554.03023
[65] Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284 – 316. · Zbl 0063.06328
[66] Marian Boykan Pour-El, Effectively extensible theories, J. Symbolic Logic 33 (1968), 56 – 68. · Zbl 0179.01903 · doi:10.2307/2270052 · doi.org
[67] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967.
[68] J. M. Rubin, Ph.D. dissertation, Univ. Calif., Berkeley, 1981.
[69] J. R. Shoenfield, Undecidable and creative theories, Fund. Math. 49 (1960/1961), 171 – 179. · Zbl 0096.24302
[70] Robert I. Soare, Recursively enumerable sets and degrees, Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149 – 1181. · Zbl 0401.03018
[71] R. I. Soare, Constructions in the recursively enumerable degrees, CIME Summer School, Bressanone (Italy), 1979 (to appear).
[72] V. D. Solov\(^{\prime}\)ev, \?-reducibility, and hyperhypersimple sets, Probabilistic methods and cybernetics, No. X-XI (Russian), Izdat. Kazan. Univ., Kazan, 1974, pp. 121 – 128.
[73] V. V. V\(^{\prime}\)jugin, Segments of recursively enumerable \?-degrees, Algebra i Logika 13 (1974), no. 6, 635 – 654, 719 (Russian).
[74] C. E. M. Yates, Three theorems on the degrees of recursively enumerable sets, Duke Math. J. 32 (1965), 461 – 468. · Zbl 0134.00805
[75] C. E. M. Yates, On the degrees of index sets, Trans. Amer. Math. Soc. 121 (1966), 309 – 328. · Zbl 0143.25401
[76] C. E. M. Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249 – 266. · Zbl 0185.02201
[77] Paul R. Young, Linear orderings under one-one reducibility, J. Symbolic Logic 31 (1966), 70 – 85. · Zbl 0163.25204 · doi:10.2307/2270621 · doi.org
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.