{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:16:00Z","timestamp":1742915760972,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480564"},{"type":"electronic","value":"9783662480571"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48057-1_25","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T01:29:54Z","timestamp":1439170194000},"page":"319-330","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Graphs Identified by Logics with Counting"],"prefix":"10.1007","author":[{"given":"Sandra","family":"Kiefer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erkal","family":"Selman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Arvind, V., K\u00f6bler, J., Rattan, G., Verbitsky, O.: On the power of color refinement. In: FCT 2015, (to appear 2015)","key":"25_CR1","DOI":"10.1007\/978-3-319-22177-9_26"},{"issue":"1","key":"25_CR2","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1137\/120867834","volume":"42","author":"A Atserias","year":"2013","unstructured":"Atserias, A., Maneva, E.N.: Sherali-adams relaxations and indistinguishability in counting logics. SIAM J. Comput. 42(1), 112\u2013137 (2013)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"25_CR3","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1137\/0209047","volume":"9","author":"L Babai","year":"1980","unstructured":"Babai, L., Erd\u00f6s, P., Selkow, S.M.: Random graph isomorphism. SIAM J. Comput. 9(3), 628\u2013635 (1980)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Babai, L., Kucera, L.: Canonical labelling of graphs in linear average time. In: FOCS 1979, pp. 39\u201346. IEEE Computer Society (1979)","key":"25_CR4","DOI":"10.1109\/SFCS.1979.8"},{"key":"25_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-642-40450-4_13","volume-title":"Algorithms \u2013 ESA 2013","author":"C Berkholz","year":"2013","unstructured":"Berkholz, C., Bonsma, P., Grohe, M.: Tight lower and upper bounds for the complexity of canonical colour refinement. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 145\u2013156. Springer, Heidelberg (2013)"},{"issue":"4","key":"25_CR6","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 identifications. Combinatorica 12(4), 389\u2013410 (1992)","journal-title":"Combinatorica"},{"key":"25_CR7","first-page":"604","volume":"3","author":"L-C Chang","year":"1959","unstructured":"Chang, L.-C.: The uniqueness and nonuniqueness of the triangular association scheme. Sci. Record. 3, 604\u2013613 (1959)","journal-title":"Sci. Record."},{"key":"25_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-642-31585-5_25","volume-title":"Automata, Languages, and Programming","author":"A Dawar","year":"2012","unstructured":"Dawar, A., Holm, B.: Pebble games with algebraic rules. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 251\u2013262. Springer, Heidelberg (2012)"},{"issue":"1\u20132","key":"25_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/S0304-3975(98)00308-9","volume":"224","author":"E Gr\u00e4del","year":"1999","unstructured":"Gr\u00e4del, E., Otto, M.: On logics with two variables. Theor. Comput. Sci. 224(1\u20132), 73\u2013113 (1999)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Gr\u00e4del, E., Otto, M., Rosen, E.: Two-variable logic with counting is decidable. In: LICS 1997, pp. 306\u2013317. IEEE Computer Society (1997)","key":"25_CR10"},{"issue":"4","key":"25_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.2307\/420954","volume":"4","author":"M Grohe","year":"1998","unstructured":"Grohe, M.: Finite variable logics in descriptive complexity theory. Bull. Symbolic Log. 4(4), 345\u2013398 (1998)","journal-title":"Bull. Symbolic Log."},{"unstructured":"Grohe, M., Otto, M.: Pebble games and linear equations. In: C\u00e9gielski, P., Durand, A. (eds.) CSL 2012, of LIPIcs, vol. 16, pp. 289\u2013304 (2012)","key":"25_CR12"},{"issue":"1","key":"25_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0070","volume":"129","author":"L Hella","year":"1996","unstructured":"Hella, L.: Logical hierarchies in PTIME. Inf. Comput. 129(1), 1\u201319 (1996)","journal-title":"Inf. Comput."},{"issue":"2","key":"25_CR14","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1214\/aoms\/1177705914","volume":"31","author":"AJ Hoffman","year":"1960","unstructured":"Hoffman, A.J.: On the uniqueness of the triangular association scheme. Ann. Math. Statist. 31(2), 492\u2013497 (1960)","journal-title":"Ann. Math. Statist."},{"doi-asserted-by":"crossref","unstructured":"Kiefer, S., Schweitzer, P., Selman, E.: Graphs identified by logics with counting. CoRR, abs\/1503.08792 (2015). full version of the paper","key":"25_CR15","DOI":"10.1007\/978-3-662-48057-1_25"},{"unstructured":"Kopczynski, E., Tan, T.: Regular graphs and the spectra of two-variable logic with counting. CoRR, abs\/1304.0829 (2013)","key":"25_CR16"},{"doi-asserted-by":"crossref","unstructured":"Krebs, A., Verbitsky, O.: Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. CoRR, abs\/1407.3175 (2014)","key":"25_CR17","DOI":"10.1109\/LICS.2015.69"},{"doi-asserted-by":"crossref","unstructured":"Kucera, L.: Canonical labeling of regular graphs in linear average time. In: FOCS 1987, pp. 271\u2013279. IEEE Computer Society (1987)","key":"25_CR18","DOI":"10.1109\/SFCS.1987.11"},{"unstructured":"Lucas, E.: R\u00e9cr\u00e9ations math\u00e9matiques. 2i\u00e8me \u00e9d., nouveau tirage. Librairie Scientifique et Technique Albert Blanchard, Paris (1960)","key":"25_CR19"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94\u2013112 (2014)","journal-title":"J. Symb. Comput."},{"issue":"3","key":"25_CR21","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0168-0072(96)00047-4","volume":"85","author":"M Otto","year":"1997","unstructured":"Otto, M.: Canonization for two variables and puzzles on the square. Ann. Pure Appl. Logic 85(3), 243\u2013282 (1997)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"3","key":"25_CR22","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s10849-005-5791-1","volume":"14","author":"I Pratt-Hartmann","year":"2005","unstructured":"Pratt-Hartmann, I.: Complexity of the two-variable fragment with counting quantifiers. J. Log. Lang. Inf. 14(3), 369\u2013395 (2005)","journal-title":"J. Log. Lang. Inf."},{"key":"25_CR23","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Pearson, Upper Saddle River (2000)","edition":"2"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48057-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T21:50:43Z","timestamp":1674251443000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48057-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480564","9783662480571"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48057-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}