{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:54:12Z","timestamp":1757627652171,"version":"3.44.0"},"reference-count":34,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1992,4,1]],"date-time":"1992-04-01T00:00:00Z","timestamp":702086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1992,4,1]],"date-time":"1992-04-01T00:00:00Z","timestamp":702086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2004,3,21]],"date-time":"2004-03-21T00:00:00Z","timestamp":1079827200000},"content-version":"vor","delay-in-days":4372,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1992,4]]},"DOI":"10.1016\/0304-3975(92)90078-t","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T00:17:21Z","timestamp":1027642641000},"page":"263-284","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":11,"title":["The p-T-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two-quantifier theory"],"prefix":"10.1016","volume":"97","author":[{"given":"Richard A.","family":"Shore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theodore A.","family":"Slaman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(92)90078-T_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02772668","article-title":"Initial segments of the Turing degrees of size \u21351","volume":"53","author":"Abraham","year":"1986","journal-title":"Israel J. Math."},{"key":"10.1016\/0304-3975(92)90078-T_BIB2","first-page":"198","article-title":"On the structure of polynomial time degrees","volume":"Vol. 166","author":"Ambos-Spies","year":"1984"},{"key":"10.1016\/0304-3975(92)90078-T_BIB3","series-title":"Lehrsthul f\u00fcr Informatik","article-title":"On the structure of polynomial-time degrees of recursive sets (Habilitationschrift)","author":"Ambos-Spies","year":"1984"},{"key":"10.1016\/0304-3975(92)90078-T_BIB4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0019-9958(85)80020-6","article-title":"Sublattices of the polynomial-time degrees","volume":"65","author":"Ambos-Spies","year":"1985","journal-title":"Inform. and Control"},{"key":"10.1016\/0304-3975(92)90078-T_BIB5","series-title":"Ph.D. Dissertation","article-title":"The structure of complexity classes and degrees","author":"Breidbart","year":"1977"},{"key":"10.1016\/0304-3975(92)90078-T_BIB6","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0022-0000(81)90021-0","article-title":"A note on structure and looking back applied to the relative complexity of computable functions","volume":"22","author":"Chew","year":"1981","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(92)90078-T_BIB7","first-page":"151","article-title":"The complexity of theorem proving procedures","author":"Cook","year":"1971","journal-title":"Proc. 3rd Ann. ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(92)90078-T_BIB8","article-title":"Embeddings and extensions of embeddings in r.e.-tt and wtt degrees","volume":"Vol. 1141","author":"Fejer","year":"1985"},{"year":"1978","series-title":"General Lattice Theory","author":"Gr\u00e4tzer","key":"10.1016\/0304-3975(92)90078-T_BIB9"},{"key":"10.1016\/0304-3975(92)90078-T_BIB10","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0304-3975(83)90003-8","article-title":"Oracle-dependent properties of the lattice of NP sets","volume":"24","author":"Homer","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90078-T_BIB11","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"issue":"2","key":"10.1016\/0304-3975(92)90078-T_BIB12","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/1969708","article-title":"The upper semi-lattice of degrees of recursive unsolvability","volume":"59","author":"Kleene","year":"1954","journal-title":"Ann. of Math."},{"key":"10.1016\/0304-3975(92)90078-T_BIB13","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1002\/malq.19680143002","article-title":"Distributive initial segments of the degrees of unsolvability","volume":"14","author":"Lachlan","year":"1968","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"10.1016\/0304-3975(92)90078-T_BIB14","doi-asserted-by":"crossref","first-page":"289","DOI":"10.2307\/2272227","article-title":"Countable initial segments of the degrees of unsolvability","volume":"41","author":"Lachlan","year":"1976","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0304-3975(92)90078-T_BIB15","first-page":"122","article-title":"Polynomial-time reducibility","author":"Ladner","year":"1973","journal-title":"Proc. 5th Ann. ACM Symp. on Theory of Computing"},{"key":"10.1016\/0304-3975(92)90078-T_BIB16","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","article-title":"On the structure of polynomial-time reducibility","volume":"22","author":"Ladner","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(92)90078-T_BIB17","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","article-title":"A comparison of polynomial-time reducibilities","volume":"1","author":"Ladner","year":"1975","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90078-T_BIB18","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(81)90069-4","article-title":"On the structure of sets in NP and other complexity classes","volume":"15","author":"Landweber","year":"1981","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10.1016\/0304-3975(92)90078-T_BIB19","doi-asserted-by":"crossref","first-page":"365","DOI":"10.2307\/1970779","article-title":"Initial segments of the degrees of unsolvability","volume":"93","author":"Lerman","year":"1971","journal-title":"Ann. of Math."},{"key":"10.1016\/0304-3975(92)90078-T_BIB20","series-title":"Perspectives in Mathematical Logic","article-title":"Degrees of Unsolvability","author":"Lerman","year":"1983"},{"key":"10.1016\/0304-3975(92)90078-T_BIB21","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1090\/S0002-9947-1988-0973174-0","article-title":"Decidability and invariant classes for degree theory","volume":"310","author":"Lerman","year":"1988","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0304-3975(92)90078-T_BIB22","first-page":"317","article-title":"The \u201calmost all\u201d theory of subrecursive degrees is decidable","volume":"Vol. 15","author":"Mehlhorn","year":"1974"},{"key":"10.1016\/0304-3975(92)90078-T_BIB23","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0022-0000(76)80035-9","article-title":"Polynomial and abstract subrecursive classes","volume":"12","author":"Mehlhorn","year":"1976","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(92)90078-T_BIB24","doi-asserted-by":"crossref","first-page":"409","DOI":"10.2140\/pjm.1984.115.409","article-title":"Density of a final segment of the truth-table degrees","volume":"115","author":"Mohrherr","year":"1984","journal-title":"Pacific J. Math."},{"key":"10.1016\/0304-3975(92)90078-T_BIB25","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/BF02482893","article-title":"Every finite lattice can be embedded in a finite partition lattice","volume":"10","author":"Pudlak","year":"1980","journal-title":"Algebra Universalis"},{"key":"10.1016\/0304-3975(92)90078-T_BIB26","series-title":"MSI Tech. Report","article-title":"Diagonalization, uniformity, and fixed-point theorems","author":"Regan","year":"1988"},{"key":"10.1016\/0304-3975(92)90078-T_BIB27","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","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90078-T_BIB28","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0304-3975(84)90124-5","article-title":"Minimal pairs for P","volume":"31","author":"Sch\u00f6ning","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(92)90078-T_BIB29","first-page":"252","article-title":"On the theory of polynomial degrees of the recursive sets","author":"Shinoda","year":"1988","journal-title":"Proc. 3rd IEEE Ann. Conf. on Structures in Complexity Theory"},{"key":"10.1016\/0304-3975(92)90078-T_BIB30","first-page":"417","article-title":"On the theory of the PTIME degrees of the recursive sets","volume":"40","author":"Shinoda","year":"1990","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(92)90078-T_BIB31","series-title":"Generalized Recursion Theory II","first-page":"331","article-title":"On the \u2200\u2203 sentences of \u03b1-recursion theory","author":"Shore","year":"1978"},{"key":"10.1016\/0304-3975(92)90078-T_BIB32","first-page":"256","article-title":"Finitely generated codings and the degrees r.e. in a degree d","volume":"84","author":"Shore","year":"1982","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/0304-3975(92)90078-T_BIB33","series-title":"Perspective in Mathematical Logic","article-title":"Recursively Enumerable Sets and Degrees: The Study of Computable Functions and Computably Generated Sets","author":"Soare","year":"1987"},{"issue":"2","key":"10.1016\/0304-3975(92)90078-T_BIB34","doi-asserted-by":"crossref","first-page":"581","DOI":"10.2307\/1969604","article-title":"On degrees of recursive unsolvability","volume":"64","author":"Spector","year":"1956","journal-title":"Ann. of Math."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290078T?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759290078T?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T04:17:58Z","timestamp":1757477878000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759290078T"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,4]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,4]]}},"alternative-id":["030439759290078T"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(92)90078-t","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[1992,4]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"The p-T-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two-quantifier theory","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0304-3975(92)90078-T","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1992 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}