{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T12:55:48Z","timestamp":1782219348253,"version":"3.54.5"},"reference-count":64,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":5795,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"},{"start":{"date-parts":[[1991,1,1]],"date-time":"1991-01-01T00:00:00Z","timestamp":662688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1991,1]]},"DOI":"10.1002\/malq.19910370702","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T05:50:20Z","timestamp":1180158620000},"page":"97-111","source":"Crossref","is-referenced-by-count":8,"title":["Effectivizing Inseparability"],"prefix":"10.1002","volume":"37","author":[{"given":"John","family":"Case","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"Ambos\u2010Spies K. Three theorems on polynomial degrees of NP\u2010sets. In: Proceedings of the 26th Ann. IEEE Symp. Found. of Comp. Sci (1985) pp.51\u201355.","DOI":"10.1109\/SFCS.1985.61"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"Baker T. P. andJ.Hartmanis Succinctness verifiability and determinism in representations of polynomial time languages. In: Proceedings of the 20th Ann. IEEE Symp. Found of Comp. Sci. (1979) pp.392\u2013396.","DOI":"10.1109\/SFCS.1979.41"},{"key":"e_1_2_1_4_2","volume-title":"Theory of Computation","author":"Brainerd W.","year":"1974"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/321386.321395","article-title":"A machine\u2010independent theory of the complexity of recursive functions","volume":"14","author":"Blum M.","year":"1967","journal-title":"J. ACM"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.2307\/2273381","article-title":"An invariance notion in recursion theory","volume":"47","author":"Byerly R.","year":"1982","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.2307\/2273382","article-title":"Recursion theory and the lambda calculus","volume":"47","author":"Byerly R.","year":"1982","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","first-page":"662","DOI":"10.2307\/2273458","article-title":"Definability of recursively enumberable sets in a class of recursion theoretic structures","volume":"48","author":"Byerly R.","year":"1983","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_9_2","first-page":"499","article-title":"Definability of recursively enumerable sets in abstract computational complexity theory","volume":"30","author":"Byerly R.","year":"1948","journal-title":"This Zeitschrift"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","first-page":"9","DOI":"10.2307\/2274086","article-title":"Some properties of invariant sets","volume":"49","author":"Byerly R.","year":"1984","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF01761704","article-title":"Periodicity in generations of automata","volume":"8","author":"Case J.","year":"1974","journal-title":"Math. Syst. Theory"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/S0019-9958(83)80052-7","article-title":"Pseudo\u2010extensions of computable functions","volume":"56","author":"Case J.","year":"1983","journal-title":"Information and Control"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/321707.321721","article-title":"Subrecursive programming languages. I: Efficiency and program structure","volume":"19","author":"Constable R. L.","year":"1971","journal-title":"J. ACM"},{"key":"e_1_2_1_14_2","first-page":"1235","article-title":"R.e. inseparable general and subrecursive index sets","volume":"48","author":"Case J.","year":"1983","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0022-0000(71)80039-9","article-title":"Subrecursive programming languages II: On program size","volume":"5","author":"Constable R. L.","year":"1971","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1090\/S0002-9947-1955-0067049-X","article-title":"Productive sets","volume":"78","author":"Dekker J.","year":"1955","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1090\/S0002-9947-1958-0097310-7","article-title":"Some theorems on classes of recursively enumerable sets","volume":"89","author":"Dekker J.","year":"1958","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_18_2","volume-title":"Computability, Complexity, and Languages","author":"Davis M.","year":"1983"},{"key":"e_1_2_1_19_2","first-page":"113","volume-title":"Logic Colloquium 69","author":"Friedman H.","year":"1971"},{"key":"e_1_2_1_20_2","first-page":"145","volume-title":"Kurt G\u00f6del, Collected Works","author":"G\u00f6del K.","year":"1986"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0020-0190(85)90026-2","article-title":"Independence results about context\u2010free languages and lower bounds","volume":"20","author":"Hartmanis J.","year":"1985","journal-title":"Information Processing Letters"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1090\/S0002-9947-1965-0195724-1","article-title":"On creative sets and indices of partial recursive functions","volume":"120","author":"Hay L.","year":"1965","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"Hartmanis J. andT. P.Baker Relative succinctness of representations of languages and separation of complexity classes. In: Mathematical Foundations of Computer Science '79 Springer Lecture Notes in Computer Science 74 (1979) pp.70\u201388.","DOI":"10.1007\/3-540-09526-8_6"},{"key":"e_1_2_1_24_2","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"e_1_2_1_25_2","volume-title":"Algebraic Recursion Theory","author":"Ivanov L. L.","year":"1986"},{"key":"e_1_2_1_26_2","volume-title":"Set Theory","author":"Jech Th.","year":"1978"},{"key":"e_1_2_1_27_2","volume-title":"Introduction to Metamathematics","author":"Kleene S. C.","year":"1952"},{"key":"e_1_2_1_28_2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(87)90191-8","article-title":"How to prove representation\u2010independet independence results","volume":"24","author":"Kurtz S.","year":"1987","journal-title":"Information Processing Letters"},{"key":"e_1_2_1_29_2","doi-asserted-by":"crossref","unstructured":"Kowalczyk W. Some connections between presentability of complexity classes and the power of formal systems of reasoning. In: Mathematical Foundations of Computer Science \u203284 Springer Lecture Notes in Computer Science 201 (1984) 364\u2013368.","DOI":"10.1007\/BFb0030318"},{"key":"e_1_2_1_30_2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0304-3975(80)90017-1","article-title":"Indexings of subrecursive classes","volume":"11","author":"Kozen D.","year":"1980","journal-title":"Theor. Comp. Sci."},{"key":"e_1_2_1_31_2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","article-title":"On the structure of polynomial time reducibility","volume":"22","author":"Lander R. E.","year":"1975","journal-title":"J. ACM"},{"key":"e_1_2_1_32_2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1090\/S0002-9947-1976-0403933-6","article-title":"Relativization of the theory of computational complexity","volume":"220","author":"Lynch N. A.","year":"1976","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_33_2","volume-title":"Proceedings Structure in Complexity Theory","author":"Marcoux Y."},{"key":"e_1_2_1_34_2","volume-title":"Introduction to Mathematical Logic","author":"Mendelson E.","year":"1979"},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/S0019-9958(72)90592-X","article-title":"Program size in restricted programming languages","volume":"21","author":"Meyer A. R.","year":"1972","journal-title":"Information and Control"},{"key":"e_1_2_1_36_2","volume-title":"An Introduction to the General Theory of Algorithms","author":"Machtey M.","year":"1978"},{"key":"e_1_2_1_37_2","first-page":"97","article-title":"Creative sets","volume":"1","author":"Myhill J.","year":"1955","journal-title":"This Zeitschrift"},{"key":"e_1_2_1_38_2","first-page":"1479","article-title":"Category methods in recursion theory. Pacific","volume":"11","author":"Myhill J.","year":"1961","journal-title":"J. Math."},{"key":"e_1_2_1_39_2","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","article-title":"Recursively enumerable sets of positive integers and their decision problems","volume":"50","author":"Post E. L.","year":"1944","journal-title":"Bull. Amer. Math. Soc."},{"key":"e_1_2_1_40_2","volume-title":"Progressions of relatively succinct programs in subrecursive hierachies","author":"Royer J.","year":"1986"},{"key":"e_1_2_1_41_2","volume-title":"Intensional Subrecursion and Complexity Theory. Research Notes in Theoretical Science","author":"Royer J.","year":"1989"},{"key":"e_1_2_1_42_2","doi-asserted-by":"crossref","unstructured":"Regan K. W. On diagonalization methods and the structure of language classes. In: Proc. FCT '83 Springer Lecture Notes in Computer Science 158 (1983) 368\u2013380.","DOI":"10.1007\/3-540-12689-9_119"},{"key":"e_1_2_1_43_2","doi-asserted-by":"crossref","unstructured":"Regan K. W. The topology of provability in complexity theory. In: Proc. of the Structure in Complexity Theory Conference Springer Lecture Notes in Computer Science 223 (1986) 291\u2013310.","DOI":"10.1007\/3-540-16486-3_106"},{"key":"e_1_2_1_44_2","unstructured":"Regan K. W. A topology of provability in complexity theory. Technical Report 87\u201355 Mathematical Sciences Institute Cornell University1987."},{"key":"e_1_2_1_45_2","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1090\/S0002-9947-1953-0053041-6","article-title":"Classes of recursively enumerable sets and their decision problems","volume":"74","author":"Rice H. G.","year":"1953","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_46_2","unstructured":"Riccardi G. The Independence of Control Structures in Abstract Programming Systems. PhD Thesis State University of New York at Buffalo1980."},{"key":"e_1_2_1_47_2","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0022-0000(81)90024-6","article-title":"The independence of control structures in abstract programming systems","volume":"22","author":"Riccardi G.","year":"1981","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_48_2","first-page":"285","article-title":"The independence of control structures in programmable numberings of the partial recursive functions","volume":"48","author":"Riccardi G.","year":"1982","journal-title":"This Zeitschrift"},{"key":"e_1_2_1_49_2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.2307\/2964292","article-title":"G\u00f6del numberings of the partial recursive functions","volume":"23","author":"Rogers H.","year":"1958","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_50_2","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers H.","year":"1987"},{"key":"e_1_2_1_51_2","volume-title":"Subrecursion: Functions and Hierarchies","author":"Rose H.","year":"1984"},{"key":"e_1_2_1_52_2","doi-asserted-by":"crossref","unstructured":"Royer J. A Connotational Theory of Program Structure. Springer Lecture Notes in Computer Science 273 (1987).","DOI":"10.1007\/3-540-18253-5"},{"key":"e_1_2_1_53_2","doi-asserted-by":"crossref","first-page":"000","DOI":"10.2307\/2274866","article-title":"Two recursion theoretic characterizations of proof speed\u2010ups","volume":"54","author":"Royer J.","year":"1989","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_54_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(82)90114-1","article-title":"A uniform approach to obtain diagonal sets in complexity classes","volume":"18","author":"Sch\u00f6ning U.","year":"1982","journal-title":"Theor. Comp. Sci."},{"key":"e_1_2_1_55_2","volume-title":"Outline of a mathematical theory of computation","author":"Scott D.","year":"1970"},{"key":"e_1_2_1_56_2","first-page":"342","article-title":"Review of \u201cLimiting recursion\u201d by E. M. Gold and \u201cTrial and error predicates and the solution to a problem of Mostowski\u201d by H. Putnam","volume":"36","author":"Shapiro N.","year":"1971","journal-title":"J. Symbolic Logic"},{"key":"e_1_2_1_57_2","doi-asserted-by":"crossref","first-page":"644","DOI":"10.2307\/1970028","article-title":"On degrees of unsolvability","volume":"69","author":"Shoenfield J. R.","year":"1959","journal-title":"Annals Math."},{"key":"e_1_2_1_58_2","volume-title":"Degrees of Unsolvability","author":"Shoenfield J. R.","year":"1971"},{"key":"e_1_2_1_59_2","volume-title":"Degrees of Unsolvability","author":"Shoenfield J. R.","year":"1971"},{"key":"e_1_2_1_60_2","doi-asserted-by":"crossref","DOI":"10.1515\/9781400882007","volume-title":"Theory of Formal Systems","author":"Smullyan R. M.","year":"1961"},{"key":"e_1_2_1_61_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"Soare R. I.","year":"1987"},{"key":"e_1_2_1_62_2","doi-asserted-by":"crossref","unstructured":"Spreen D. On r.e. inseparability of epo index sets. In: Logic and Machines: Decision Problems and Complexity Springer Lecture Notes in Computer Science 223 (1983) 103\u2013117.","DOI":"10.1007\/3-540-13331-3_36"},{"key":"e_1_2_1_63_2","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1147\/rd.126.0465","article-title":"Algebraically generalized recursive function theory","volume":"12","author":"Strong H.","year":"1968","journal-title":"IBM Journal of Research and Development"},{"key":"e_1_2_1_64_2","first-page":"1","article-title":"Uniformly reflexive structures: On the nature of G\u00f6delizations and relative computability","volume":"144","author":"Wagner E.","year":"1969","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_65_2","volume-title":"General Topology","author":"Willard S.","year":"1970"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19910370702","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19910370702","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19910370702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,23]],"date-time":"2026-06-23T12:36:11Z","timestamp":1782218171000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19910370702"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,1]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,1]]}},"alternative-id":["10.1002\/malq.19910370702"],"URL":"https:\/\/doi.org\/10.1002\/malq.19910370702","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,1]]}}}