{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:04:15Z","timestamp":1725663855178},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540527534"},{"type":"electronic","value":"9783540471370"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52753-2_38","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:41:56Z","timestamp":1330206116000},"page":"163-175","source":"Crossref","is-referenced-by-count":6,"title":["On logical descriptions of some concepts in structural complexity theory"],"prefix":"10.1007","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"S. Buss and L. Hay, On truth-table reducibility to SAT and the difference hierarchy over NP, Proceedings of 3rd Conference on Structure in Complexity Theory 1988, 224\u2013233.","DOI":"10.1109\/SCT.1988.5282"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"J. Cai and L. Hemachandra, The Boolean hierarchy: hardware over NP, Proceedings of 1st Conference on Structure in Complexity Theory 1986, Lecture Notes in Computer Science Nr. 223, Springer 1986, 105\u2013124.","DOI":"10.1007\/3-540-16486-3_93"},{"key":"10_CR3","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets, SIAM-AMS Proc. 7 (1974), 43\u201373.","journal-title":"SIAM-AMS Proc."},{"key":"10_CR4","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1137\/0213025","volume":"13","author":"E. Grandjean","year":"1984","unstructured":"E. Grandjean, The Spectra of First-Order Sentences and Computational Complexity, SIAM J. Comp. 13 (1984), 367\u2013373.","journal-title":"SIAM J. Comp."},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"E. Grandjean, Universal Quantifiers and Time Complexity of Random Access Machines, Math. Syst. Theory (1985), 171\u2013187.","DOI":"10.1007\/BF01699468"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"E. Grandjean, First-Order Spectra with One Variable, in: E. B\u00f6rger (Ed.), \u201cComputation Theory and Logic\u201d, Lecture Notes in Computer Science Nr. 270, Springer 1987, 166\u2013180.","DOI":"10.1007\/3-540-18170-9_164"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Y. Gurevich, Toward logic tailord for computational complexity, in: M. M. Richter et al. (Eds), Computation and Proof Theory, Springer Lecture Notes in Mathematics Nr. 1104 (1984), 175\u2013216.","DOI":"10.1007\/BFb0099486"},{"key":"10_CR8","unstructured":"Y. Gurevich, Logic and the Challenge of Computer Science, in: E. B\u00f6rger (Ed), Trends in Theoretical Computer Science, Computer Science Press (1988), 1\u201357."},{"key":"10_CR9","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman, Relational Queries Computable in Polynomial Time, Inf. and Control 68 (1986), 86\u2013104.","journal-title":"Inf. and Control"},{"key":"10_CR10","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 J. Comput. 16 (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"key":"10_CR11","unstructured":"N. Immerman, Expressibility and Parallel Complexity, Tech. Report 546, Yale University, Department of Computer Science (1987)."},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"N. Immerman, Expressibility as a Complexity Measure: Results and Directions, Proc. of 2nd Conf. on Structure in Complexity Theory (1987), 194\u2013202.","DOI":"10.1109\/PSCT.1987.10319271"},{"key":"10_CR13","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 complementation, SIAM J. Comput. 17 (1988), 935\u2013939.","journal-title":"SIAM J. Comput."},{"key":"10_CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1090\/psapm\/038\/1020810","volume":"38","author":"N. Immerman","year":"1989","unstructured":"N. Immerman, Descriptive and Computational Complexity, in: J. Hartmanis (Ed.), Computational Complexity Theory, Proc. of AMS Symposia in Appl. Math. 38 (1989), 75\u201391.","journal-title":"Proc. of AMS Symposia in Appl. Math."},{"key":"10_CR15","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. Jones","year":"1977","unstructured":"N. Jones and W. Laaser, Complete problems for deterministic polynomial time, Theoret. Comp. Sci 3 (1977), 105\u2013117.","journal-title":"Theoret. Comp. Sci"},{"key":"10_CR16","unstructured":"R. Karp and R. Lipton, Turing Machines that Take Advice, in: Logic and Algorithmic, Monographie Nr. 30 de L'Enseignement Math\u00e9matique, Gen\u00e8ve 1982, 255\u2013273."},{"key":"10_CR17","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K. Ko","year":"1983","unstructured":"K. Ko, On self-reducibility and weak P-selectivity, J. of Comput. Syst. Sci. 26 (1983), 209\u2013221.","journal-title":"J. of Comput. Syst. Sci."},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/0214003","volume":"14","author":"K. Ko","year":"1985","unstructured":"K. Ko and U. Sch\u00f6ning, On circuit-size complexity and the low hierarchy in NP, SIAM J. Comput. 14 (1985), 41\u201351.","journal-title":"SIAM J. Comput."},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis, The complexity of facets (and some facets of complexity), Proceedings of 14th STOC 1982, 255\u2013260.","DOI":"10.1145\/800070.802199"},{"key":"10_CR20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi, The Method of Forced Enumeration for Nondeterministic Automata, Acta Informatica 26, (1988), 279\u2013284.","journal-title":"Acta Informatica"},{"key":"10_CR21","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(83)90027-2","volume":"27","author":"U. Sch\u00f6ning","year":"1983","unstructured":"U. Sch\u00f6ning, A Low and a High Hierarchy within NP, J. Comput. Syst. Sci. 27 (1983), 14\u201328.","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning, Complexity and Structure, Springer Lecture Notes in Computer Science Nr. 211 (1986).","DOI":"10.1007\/3-540-16079-5"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of Relational Query Languages, Proc. of 14th STOC (1982), 137\u2013146.","DOI":"10.1145\/800070.802186"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"K. Wagner, Bounded Query Computations, Proceedings of 3rd Conference on Structure in Complexity Theory 1988, 260\u2013277.","DOI":"10.1109\/SCT.1988.5286"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"G. Wechsung (and K. Wagner), On the Boolean cloure of NP, Proceedings of FCT 85, Lecture Notes in Computer Science Nr. 199, Springer 1985, 485\u2013493.","DOI":"10.1007\/BFb0028832"}],"container-title":["Lecture Notes in Computer Science","CSL '89"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52753-2_38.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T13:35:40Z","timestamp":1713620140000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52753-2_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540527534","9783540471370"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-52753-2_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}