{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:13:29Z","timestamp":1725664409611},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540601784"},{"type":"electronic","value":"9783540447207"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60178-3_98","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:49:25Z","timestamp":1330278565000},"page":"463-479","source":"Crossref","is-referenced-by-count":4,"title":["Logics capturing relativized complexity classes uniformly"],"prefix":"10.1007","author":[{"given":"J. A.","family":"Makowsky","sequence":"first","affiliation":[]},{"given":"Y. B.","family":"Pnueli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"23_CR1","unstructured":"S. Abiteboul, R. Hull, and V. Vianu. Foundations of Database. Addison Wesley, 1994."},{"key":"23_CR2","unstructured":"J. Barwise and S. Feferman, editors. Model-Theoretic Logics. Perspectives in Mathematical Logic. Springer Verlag, 1985."},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay. Relativizations of the P=? NP question. SIAM Journal for Computing, 4:431\u2013442, 1975.","journal-title":"SIAM Journal for Computing"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"J. Buss. Relativized alternation. In Structure in Complexity Theory, volume 223 of Lecture Notes in Computer Science, pages 66\u2013103. Springer Verlag, 1986.","DOI":"10.1007\/3-540-16486-3_90"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/0022-0000(88)90034-7","volume":"36","author":"J.F. Buss","year":"1988","unstructured":"J.F. Buss. Alternations and space-bounded computations. Journal of Computer and System Sciences, 36:351\u2013378, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR6","unstructured":"A. Dawar. Feasible Computation Through Model Theory. PhD thesis, Department of Computer Science, University of Maryland, 1993."},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"A. Dawar. Generalized quantifiers and logical reducibilities. Logic and Computation, to appear, 1995.","DOI":"10.1093\/logcom\/5.2.213"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"H.D. Ebbinghaus and J. Flum. Finite Model Theory. In preparation, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"23_CR9","unstructured":"H.D. Ebbinghaus, J. Flum, and W. Thomas. Mathematical Logic. Undergraduate Texts in Mathematics. Springer-Verlag, 1980."},{"key":"23_CR10","unstructured":"M.G. Garey and D.S. Johnson. Computers and Intractability. Mathematical Series. W.H. Freeman and Company, 1979."},{"key":"23_CR11","unstructured":"G. Gottlob. Relativized logspace and generalized quantifiers over finite structures. TR CD-TR-95\/76, Technical University of Vienna, 1995."},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"G. Gottlob. Relativized logspace and generalized quantifiers over finite structures. In LiCS'95, to appear. IEEE, 1995.","DOI":"10.1109\/LICS.1995.523245"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Y. Gurevich and S. Shelah. Fixed point extensions of first order logic. Annals of Pure and Applied Logic, 32:265\u2013280, 1986.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"4","key":"23_CR14","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM Journal on Computing, 16(4):760\u2013778, Aug 1987.","journal-title":"SIAM Journal on Computing"},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17:935\u2013938, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"23_CR16","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"N. Immerman. Expressibility and parallel complexity. SIAM Journal on Computing, 18:625\u2013638, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"23_CR17","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0890-5401(90)90006-4","volume":"89","author":"D. Leivant","year":"1990","unstructured":"D. Leivant. Inductive definitions over finite structures. Information and Computation, 89:95\u2013108, 1990.","journal-title":"Information and Computation"},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R.E. Ladner","year":"1976","unstructured":"R.E. Ladner and N. Lynch. Relativization of questions about log-space reducibility. Mathematical Systems Theory, 10:19\u201332, 1976.","journal-title":"Mathematical Systems Theory"},{"key":"23_CR19","unstructured":"J.A. Makowsky and Y.B. Pnueli. Computable quantifiers and logics over finite structures. To appear in \u2018Quantifiers: Generalizations, extensions and and variants of elementary logic', Kluwer Academic Publishers, preliminary version TR 768, Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel, 1993."},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"J.A. Makowsky and Y.B. Pnueli. Oracles and quantifiers. In CSL'93, volume 832 of Lecture Notes in Computer Science, pages 189\u2013222. Springer, 1994.","DOI":"10.1007\/BFb0049333"},{"key":"23_CR21","unstructured":"J.A. Makowsky and Y. Pnueli. Second order logics capturing complexity classes, in preparation, 1995."},{"key":"23_CR22","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/0022-0000(84)90066-7","volume":"28","author":"W.L. Ruzzo","year":"1984","unstructured":"W.L. Ruzzo, J. Simon, and M. Tompa. Space bounded hierarchies and probabilistic computations. Journal of Computer and System Sciences, 28:216\u2013230, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"23_CR23","unstructured":"I. Simon. On some subrecursive reducibilities. PhD thesis, Department of Computer Science, Stanford University, 1977."},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"I. Stewart. Incorporating generalized quantifiers and the least fixed point operator. In CSL'93, volume 832 of Lecture Notes in Computer Science, pages 318\u2013333. Springer, 1994.","DOI":"10.1007\/BFb0049340"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"M. Vardi. The complexity of relational query languages. In STOC'82, pages 137\u2013146. ACM, 1982.","DOI":"10.1145\/800070.802186"},{"key":"23_CR26","doi-asserted-by":"crossref","unstructured":"C.B. Wilson. Parallel computation and the NC hierarchy relativized. In Structure in Complexity Theory, volume 223 of Lecture Notes in Computer Science, pages 362\u2013382. Springer Verlag, 1986.","DOI":"10.1007\/3-540-16486-3_111"}],"container-title":["Lecture Notes in Computer Science","Logic and Computational Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60178-3_98.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:55:50Z","timestamp":1605646550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60178-3_98"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601784","9783540447207"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-60178-3_98","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}