{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:27:10Z","timestamp":1725460030236},"publisher-location":"Berlin\/Heidelberg","reference-count":24,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540582770"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0049340","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:58:16Z","timestamp":1141671496000},"page":"318-333","source":"Crossref","is-referenced-by-count":2,"title":["Incorporating generalized quantifiers and the least fixed point operator"],"prefix":"10.1007","author":[{"given":"Iain A.","family":"Stewart","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1145\/31846.31852","volume":"34","author":"M. Ajtai","year":"1987","unstructured":"Ajtai, M., Gurevich, Y.: Monotone versus positive. J. Assoc. Comput. Mach. 34 (1987) 1004\u20131015","journal-title":"J. Assoc. Comput. Mach."},{"key":"21_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity Theory I","author":"J.L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity Theory I. Springer-Verlag, Berlin (1988)"},{"key":"21_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-75357-2","volume-title":"Structural Complexity Theory II","author":"J.L. Balc\u00e1zar","year":"1990","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity Theory II. Springer-Verlag, Berlin (1990)"},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L.A., Sewelson, V., Wagner, K., Wechsung, G.: The Boolean Hierarchy I: structural properties. SIAM J. Comput. 17 (1988) 1232\u20131252","journal-title":"SIAM J. Comput."},{"key":"21_CR5","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computation, SIAM-AMS Proceedings, Vol. 7, ed. R.M. Karp (1974) 42\u201373"},{"key":"21_CR6","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/3-540-52753-2_38","volume":"440","author":"E. Gr\u00e4del","year":"1990","unstructured":"Gr\u00e4del, E.: On logical descriptions of some concepts in structural complexity theory. Lecture Notes in Computer Science Vol. 440 (1990) 163\u2013175","journal-title":"Lecture Notes in Computer Science"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"Gr\u00e4del, E.: Capturing complexity classes by fragments of second-order logic. Theoret. Comput. Sci. 101 (1992) 35\u201357","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0168-0072(86)90055-2","volume":"32","author":"Y. Gurevich","year":"1986","unstructured":"Gurevich, Y., Shelah, S.: Fixed-point extensions of first-order logic. Ann. Pure Appl. Logic 32 (1986) 265\u2013280","journal-title":"Ann. Pure Appl. Logic"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Inform. Control 68 (1986) 86\u2013104","journal-title":"Inform. Control"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that capture complexity classes. SIAM J. Comput. 16 (1987) 760\u2013778","journal-title":"SIAM J. Comput."},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17 (1988) 935\u2013938","journal-title":"SIAM J. Comput."},{"key":"21_CR12","doi-asserted-by":"crossref","first-page":"139","DOI":"10.2307\/2272354","volume":"39","author":"N.D. Jones","year":"1974","unstructured":"Jones, N.D., Selman, A.L.: Turing machines and the spectra of first-order formulas with equality. J. Symbolic Logic 39 (1974) 139\u2013150","journal-title":"J. Symbolic Logic"},{"key":"21_CR13","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1093\/logcom\/1.3.305","volume":"1","author":"I.A. Stewart","year":"1991","unstructured":"Stewart, I.A.: Comparing the expressibility of languages formed using NP-complete operators. J. Logic Computat. 1 (1991) 305\u2013330","journal-title":"J. Logic Computat."},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1093\/logcom\/1.6.861","volume":"1","author":"I.A. Stewart","year":"1991","unstructured":"Stewart, I.A.: Complete problems involving boolean labelled structures and projection translations. J. Logic Computat. 1 (1991) 861\u2013882","journal-title":"J. Logic Computat."},{"key":"21_CR15","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0022-0000(92)90043-I","volume":"45","author":"I.A. Stewart","year":"1992","unstructured":"Stewart, I.A.: Using the Hamiltonian path operator to capture NP. J. Comput. Systems Sci. 45 (1992) 127\u2013151","journal-title":"J. Comput. Systems Sci."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01200263","volume":"30","author":"I.A. Stewart","year":"1993","unstructured":"Stewart, I.A.: Logical and schematic characterization of complexity classes. Acta Informat. 30 (1993) 61\u201387","journal-title":"Acta Informat."},{"key":"21_CR17","doi-asserted-by":"crossref","first-page":"65","DOI":"10.3233\/FI-1993-18105","volume":"18","author":"I.A. Stewart","year":"1993","unstructured":"Stewart, I.A.: Logical characterizations of bounded query classes I: logspace oracle machines. Fund. Informat. 18 (1993) 65\u201392","journal-title":"Fund. Informat."},{"key":"21_CR18","doi-asserted-by":"crossref","first-page":"93","DOI":"10.3233\/FI-1993-18106","volume":"18","author":"I.A. Stewart","year":"1993","unstructured":"Stewart, I.A.: Logical characterizations of bounded query classes II: polynomialtime oracle machines. Fund. Informat. 18 (1993) 93\u2013105","journal-title":"Fund. Informat."},{"key":"21_CR19","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0304-3975(93)90109-7","volume":"118","author":"I.A. Stewart","year":"1993","unstructured":"Stewart, I.A.: Methods for proving completeness via logical reductions. Theoret. Comput. Sci. 118 (1993) 193\u2013229","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Stewart, I.A.: Logical descriptions of monotone NP problems. J. Logic Computat. (to appear)","DOI":"10.1093\/logcom\/4.4.337"},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01195200","volume":"27","author":"I.A. Stewart","year":"1994","unstructured":"Stewart, I.A.: On completeness for NP via projection translations. Math. Systems Theory 27 (1994) 125\u201315","journal-title":"Math. Systems Theory"},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.: On completeness for NP via projection translations. Theoret. Comput. Sci. 3 (1976) 1\u201322","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR23","unstructured":"Vardi, M.: Complexity of relational query languages. Proc. 14th ACM Ann. Symp. on Theory of Computing (1982) 137\u2013146"},{"key":"21_CR24","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K.W. Wagner","year":"1990","unstructured":"Wagner, K.W.: Bounded query classes. SIAM J. Comput. 19 (1990) 833\u2013846","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049340.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T15:46:50Z","timestamp":1627141610000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540582770"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0049340","relation":{},"subject":[]}}