{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T02:53:51Z","timestamp":1725677631526},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642294846"},{"type":"electronic","value":"9783642294853"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29485-3_3","type":"book-chapter","created":{"date-parts":[[2012,4,25]],"date-time":"2012-04-25T09:03:23Z","timestamp":1335344603000},"page":"24-34","source":"Crossref","is-referenced-by-count":0,"title":["Experimental Descriptive Complexity"],"prefix":"10.1007","author":[{"given":"Marco","family":"Carmosino","sequence":"first","affiliation":[]},{"given":"Neil","family":"Immerman","sequence":"additional","affiliation":[]},{"given":"Charles","family":"Jordan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Cai","year":"1992","unstructured":"Cai, J., F\u00fcrer, M., Immerman, N.: An Optimal Lower Bound on the Number of Variables for Graph Identification. Combinatorica\u00a012(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-15025-8_10","volume-title":"Fields of Logic and Computation","author":"M. Crouch","year":"2010","unstructured":"Crouch, M., Immerman, N., Moss, J.E.B.: Finding Reductions Automatically. In: Blass, A., Dershowitz, N., Reisig, W. (eds.) Fields of Logic and Computation. LNCS, vol.\u00a06300, pp. 181\u2013200. Springer, Heidelberg (2010)"},{"key":"3_CR3","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Holm, B., Laubner, B.: Logics with Rank Operators. In: IEEE Symp. Logic In Comput. Sci., pp. 113\u2013122 (2009)","DOI":"10.1109\/LICS.2009.24"},{"key":"3_CR5","unstructured":"Fagin, R.: Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In: Karp, R. (ed.) Complexity of Computation. SIAM-AMS Proc., vol.\u00a07, pp. 43\u201373 (1974)"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Grohe, M.: Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors. In: IEEE Symp. Logic In Comput. Sci., pp. 179\u2013188 (2010)","DOI":"10.1109\/LICS.2010.22"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Descriptive Complexity. Springer Graduate Texts in Computer Science, New York (1999)","DOI":"10.1007\/978-1-4612-0539-5"},{"issue":"10","key":"3_CR8","first-page":"1127","volume":"42","author":"N. Immerman","year":"1995","unstructured":"Immerman, N.: Descriptive Complexity: A Logician\u2019s Approach to Computation. Notices of the American Mathematical Society\u00a042(10), 1127\u20131133 (1995)","journal-title":"Notices of the American Mathematical Society"},{"issue":"5","key":"3_CR9","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.\u00a017(5), 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_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.\u00a016(4), 760\u2013778 (1987)","journal-title":"SIAM J. Comput."},{"key":"3_CR11","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. Information and Control\u00a068, 86\u2013104 (1986); A preliminary version of this paper appeared in ACM Symp. Theory of Comput., pp. 147\u2013152 (1982)","journal-title":"Information and Control"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-1-4612-4478-3_5","volume-title":"Complexity Theory Retrospective","author":"N. Immerman","year":"1990","unstructured":"Immerman, N., Lander, E.S.: Describing Graphs: A First-Order Approach to Graph Canonization. In: Selman, A. (ed.) Complexity Theory Retrospective, pp. 59\u201381. Springer, Heidelberg (1990)"},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"Ladner, R.: On the structure of polynomial time reducibility. J. Assoc. Comput. Mach.\u00a022(1), 155\u2013171 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"L. Libkin","year":"2004","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer, Heidelberg (2004)"},{"key":"3_CR15","unstructured":"Rogers, G.: What\u2019s Wrong With This Picture?, \n                    \n                      http:\/\/www.garnetrogers.com\/lyrics\/What's%20Wrong%20With%20This%20Picture.txt"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The Method of Forced Enumeration for Nondeterministic Automata. Acta Informatica\u00a026, 279\u2013284 (1988)","journal-title":"Acta Informatica"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Vardi, M.: Complexity of Relational Query Languages. In: ACM Symp. Theory of Comput., pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"},{"issue":"3-4","key":"3_CR18","first-page":"253","volume":"T. XXVIII","author":"L. Valiant","year":"1982","unstructured":"Valiant, L.: Reducibility By Algebraic Projections. L\u2019Enseignement math\u00e9matique\u00a0T. XXVIII(3-4), 253\u2013268 (1982)","journal-title":"L\u2019Enseignement math\u00e9matique"}],"container-title":["Lecture Notes in Computer Science","Logic and Program Semantics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29485-3_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:05:30Z","timestamp":1620111930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29485-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642294846","9783642294853"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29485-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}