{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:40:15Z","timestamp":1780382415000,"version":"3.54.1"},"publisher-location":"Berlin\/Heidelberg","reference-count":46,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540582770","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0049333","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:58:16Z","timestamp":1141671496000},"page":"189-222","source":"Crossref","is-referenced-by-count":13,"title":["Oracles and quantifiers"],"prefix":"10.1007","author":[{"given":"J. A.","family":"Makowsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y. B.","family":"Pnueli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"L. Adelman and K. Manders. Reducibility, randomness and intractability. In STOCS'77, pages 151\u2013163. ACM, 1977.","DOI":"10.1145\/800105.803405"},{"key":"14_CR2","unstructured":"J. Barwise and S. Feferman, editors, Model-Theoretic Logics. Perspectives in Mathematical Logic. Springer Verlag, 1985."},{"key":"14_CR3","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"},{"issue":"2","key":"14_CR4","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. K. Chandra","year":"1980","unstructured":"Ashok K. Chandra and David Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156\u2013178, Oct 1980.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"14_CR5","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0022-0000(82)90012-5","volume":"25","author":"A. K. Chandra","year":"1982","unstructured":"Ashok K. Chandra and David Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25(1):99\u2013128, Aug 1982.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR6","unstructured":"C.C. Chang and H.J. Keisler. Model Theory. Studies in Logic, vol 73. North-Holland, 3rd edition, 1990."},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Alternation. Journal of ACM, 28:114\u2013133, 1981.","journal-title":"Journal of ACM"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Monadic second order definable graph transductions. In CAAP'92, volume 581 of Lecture Notes in Computer Science, pages 124\u2013144. Springer, 1992.","DOI":"10.1007\/3-540-55251-0_7"},{"key":"14_CR9","volume-title":"PhD thesis","author":"E. Dahlhaus","year":"1982","unstructured":"E. Dahlhaus. Combinatorial and Logical Properties of Reductions to some Complete Problems in NP and NL. PhD thesis, Technische Universit\u00e4t Berlin, Germany, 1982."},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus. Reductions to NP-complete problems by interpretations. In E. B\u00f6rger et. al., editor, Logic and Machines: Decision Problems and Complexity, volume 171, pages 357\u2013365. Springer Verlag, 1983.","DOI":"10.1007\/3-540-13331-3_51"},{"key":"14_CR11","first-page":"xx","volume":"XX","author":"A. Dawar","year":"1994","unstructured":"A. Dawar. Generalized quantifiers and logical reducibilities. Logic and Computation, XX:xx\u2013yy, 1994, to appear.","journal-title":"Logic and Computation"},{"key":"14_CR12","unstructured":"H.D. Ebbinghaus. Extended logics: The general framework. In Model-Theoretic Logics, Perspectives in Mathematical Logic, chapter 2. Springer Verlag, 1985."},{"key":"14_CR13","unstructured":"H.D. Ebbinghaus, J. Flum, and W. Thomas. Mathematical Logic. Undergraduate Texts in Mathematics. Springer-Verlag, 1980."},{"issue":"4","key":"14_CR14","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1145\/321978.321989","volume":"23","author":"S. Even","year":"1976","unstructured":"S. Even and R.E. Tarjan. A combinatorial problem which is complete in polynomial space. Journal of ACM, 23(4):710\u2013719, 1976.","journal-title":"Journal of ACM"},{"key":"14_CR15","unstructured":"R. Fagin. Generalized first-order spectra and polynomial time recognizable sets. In R. Karp, editor, Complexity of Computation, volume 7 of American Mathematical Society Proc, pages 27\u201341. Society for Industrial and Applied Mathematics, 1974."},{"key":"14_CR16","unstructured":"M.G. Garey and D.S. Johnson. Computers and Intractability. Mathematical Series. W.H. Freeman and Company, 1979."},{"key":"14_CR17","unstructured":"M. Grohe. Linstr\u00f6m-quantifiers that capture fixed-point logics. Preprint, 1994."},{"key":"14_CR18","unstructured":"Y. Gurevich. Logic and the challenge of computer science. In E. B\u00f6rger, editor, Trends in Theoretical Computer Science, Principles of Computer Science Series, chapter 1. Computer Science Press, 1988."},{"issue":"3","key":"14_CR19","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(89)90070-5","volume":"43","author":"L. Hella","year":"1989","unstructured":"L. Hella. Definability hierarchies of generalized quantifiers. Annals of Pure and Applied Logic, 43(3):235\u2013271, 1989.","journal-title":"Annals of Pure and Applied Logic"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Lauri Hella. Logical hierarchies in PTIME. In LiCS'92, pages 360\u2013368. IEEE, 1992.","DOI":"10.1109\/LICS.1992.185548"},{"key":"14_CR21","unstructured":"J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Series in Computer Science. Addison-Wesley, 1980."},{"key":"14_CR22","first-page":"xx","volume":"XX","author":"N. Immerman","year":"1994","unstructured":"N. Immerman and S. Landau. The complexity of iterated multiplication. Information and Computation, XX:xx\u2013yy, 1994, to appear.","journal-title":"Information and Computation"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"N. Immerman. Relational queries computable in polynomial time. In STOC'82, pages 147\u2013152. ACM, 1982.","DOI":"10.1145\/800070.802187"},{"issue":"4","key":"14_CR24","doi-asserted-by":"publisher","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":"14_CR25","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":"14_CR26","doi-asserted-by":"publisher","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":"14_CR27","doi-asserted-by":"crossref","unstructured":"D.S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume 1, chapter 2. Elsevier Science Publishers, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"B. Jenner and Jacobo Tor\u00e1n. Computing functions with parallel queries to NP. In Structure in Complexity Theory, pages 280\u2013291. IEEE, 1994.","DOI":"10.1109\/SCT.1993.336519"},{"key":"14_CR29","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","volume":"32","author":"P. Lindstr\u00f6m","year":"1966","unstructured":"P. Lindstr\u00f6m. First order predicate logic with generalized quantifiers. Theoria, 32:186\u2013195, 1966.","journal-title":"Theoria"},{"key":"14_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.1755-2567.1969.tb00356.x","volume":"35","author":"P. Lindstr\u00f6m","year":"1969","unstructured":"P. Lindstr\u00f6m. On extensions of elementary logic. Theoria, 35:1\u201311, 1969.","journal-title":"Theoria"},{"key":"14_CR31","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":"14_CR32","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0304-3975(78)90003-8","volume":"6","author":"N. Lynch","year":"1978","unstructured":"N. Lynch. Log space machines with multiple oracle tapes. Theoretical Computer Science, 6:25\u201339, 1978.","journal-title":"Theoretical Computer Science"},{"key":"14_CR33","volume-title":"Quantifiers: Generalizations, extensions and and variants of elementary logic","author":"J.A. Makowsky","year":"1993","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":"14_CR34","unstructured":"P. Orponen. General nonrelativizability results for parallel models of computation. In Proceedings, Winter School in Theoretical Computer Science, Lammi, Finland, pages 194\u2013205, 1983."},{"key":"14_CR35","unstructured":"M.A. Rabin. A simple method for undecidability proofs and some applications. In Y. Bar Hillel, editor, Logic, Methodology and Philosophy of Science II, Studies in Logic, pages 58\u201368. North Holland, 1965."},{"key":"14_CR36","doi-asserted-by":"publisher","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":"14_CR37","unstructured":"I. Simon. On some subrecursive reducibilities. PhD thesis, Department of Computer Science, Stanford University, 1977."},{"issue":"3","key":"14_CR38","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1093\/logcom\/1.3.305","volume":"1","author":"I.A. Stewart","year":"1991","unstructured":"I.A. Stewart. Comparing the expressibility of languages formed using NP-complete operators. Journal of Logic and Computation, 1(3):305\u2013330, 1991.","journal-title":"Journal of Logic and Computation"},{"issue":"1","key":"14_CR39","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0022-0000(92)90043-I","volume":"45","author":"I.A. Stewart","year":"1992","unstructured":"I.A. Stewart. Using the hamiltonian path operator to capture NP. Journal of Computer and System Sciences, 45(1):127\u2013151, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR40","doi-asserted-by":"crossref","first-page":"65","DOI":"10.3233\/FI-1993-18105","volume":"18","author":"I.A. Stewart","year":"1993","unstructured":"I.A. Stewart. Logical characterizations of bounded query classes I: Logspace oracle machines. Fundamenta Informaticae, 18:65\u201392, 1993.","journal-title":"Fundamenta Informaticae"},{"key":"14_CR41","doi-asserted-by":"crossref","first-page":"93","DOI":"10.3233\/FI-1993-18106","volume":"18","author":"I.A. Stewart","year":"1993","unstructured":"I.A. Stewart. Logical characterizations of bounded query classes II: Polynomial-time oracle machines. Fundamenta Informaticae, 18:93\u2013105. 1993.","journal-title":"Fundamenta Informaticae"},{"issue":"3","key":"14_CR42","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0168-0072(94)90036-1","volume":"66","author":"I.A. Stewart","year":"1994","unstructured":"I.A. Stewart. Context-sensitive transitive closure operators. Annals of Pure and Applied Logic, 66.3:277\u2013301, 1994.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"1","key":"14_CR43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2273858","volume":"52","author":"L. Stockmeyer","year":"1987","unstructured":"L. Stockmeyer. Classifying the computational complexity of problems. Journal of Symbolic Logic, 52(1):1\u201343, 1987.","journal-title":"Journal of Symbolic Logic"},{"key":"14_CR44","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":"14_CR45","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"W. Wagner","year":"1990","unstructured":"W. Wagner. Bounded query classes. SIAM Journal of Computing, 19:833\u2013846, 1990.","journal-title":"SIAM Journal of Computing"},{"key":"14_CR46","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","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049333.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T23:00:42Z","timestamp":1736290842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540582770"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/bfb0049333","relation":{},"subject":[]}}