{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T22:22:49Z","timestamp":1742941369470,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220111"},{"type":"electronic","value":"9783642220128"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22012-8_29","type":"book-chapter","created":{"date-parts":[[2011,6,18]],"date-time":"2011-06-18T03:29:39Z","timestamp":1308367779000},"page":"368-379","source":"Crossref","is-referenced-by-count":2,"title":["Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates"],"prefix":"10.1007","author":[{"given":"Matthew","family":"Anderson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"van Melkebeek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"29_CR1","first-page":"1","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"Ajtai, M.: \u03a31 1-formulae on finite structures. APAL\u00a024(1), 1\u201348 (1983)","journal-title":"APAL"},{"issue":"1","key":"29_CR2","first-page":"168","volume":"74","author":"M. Benedikt","year":"2009","unstructured":"Benedikt, M., Segoufin, L.: Towards a characterization of order-invariant queries over tame structures. JSL\u00a074(1), 168\u2013186 (2009)","journal-title":"JSL"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: Proc. of LICS (2007)","DOI":"10.1109\/LICS.2007.31"},{"key":"29_CR4","unstructured":"Durand, A., Lautemann, C., More, M.: Counting results in weak formalisms. In: Circuits, Logic, and Games. No. 06451 in Dagstuhl Seminar Proc. (2007)"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Dvorak, Z., Kr\u00e1l, D., Thomas, R.: Deciding first-order properties for sparse graphs. In: Proc. of FOCS (2010)","DOI":"10.1109\/FOCS.2010.20"},{"issue":"1","key":"29_CR6","first-page":"13","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst, M., Saxe, J., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. TOCS\u00a017(1), 13\u201327 (1984)","journal-title":"TOCS"},{"key":"29_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-642-04027-6_4","volume-title":"Computer Science Logic","author":"M. Grohe","year":"2009","unstructured":"Grohe, M.: Fixed-point definability and polynomial time. In: Gr\u00e4del, E., Kahle, R. (eds.) CSL 2009. LNCS, vol.\u00a05771, pp. 20\u201323. Springer, Heidelberg (2009)"},{"issue":"1","key":"29_CR8","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1145\/343369.343386","volume":"1","author":"M. Grohe","year":"2000","unstructured":"Grohe, M., Schwentick, T.: Locality of order-invariant first-order formulas. ACM TOCL\u00a01(1), 112\u2013130 (2000)","journal-title":"ACM TOCL"},{"key":"29_CR9","unstructured":"H\u00e5stad, J.: Computational limitations for small-depth circuits. Ph.D. thesis, MIT (1986)"},{"issue":"1-3","key":"29_CR10","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(1-3), 86\u2013104 (1986)","journal-title":"Information and Control"},{"issue":"4","key":"29_CR11","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. SICOMP\u00a016(4), 760\u2013778 (1987)","journal-title":"SICOMP"},{"key":"29_CR12","doi-asserted-by":"publisher","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)"},{"issue":"3","key":"29_CR13","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, Fourier transform, and learnability. JACM\u00a040(3), 620 (1993)","journal-title":"JACM"},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/10703163_10","volume-title":"Computer Science Logic","author":"J.A. Makowsky","year":"1999","unstructured":"Makowsky, J.A.: Invariant definability and P\/poly. In: Gottlob, G., Grandjean, E., Seyr, K. (eds.) CSL 1998. LNCS, vol.\u00a01584, pp. 142\u2013158. Springer, Heidelberg (1999)"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Schweikardt, N., Segoufin, L.: Addition-invariant FO and regularity. In: Proc. of LICS (2010)","DOI":"10.1109\/LICS.2010.16"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Vardi, M.: The complexity of relational query languages. In: Proc. of STOC (1982)","DOI":"10.1145\/800070.802186"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Yao, A.: Separating the polynomial-time hierarchy by oracles. In: Proc. of FOCS (1985)","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22012-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T20:06:49Z","timestamp":1560283609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22012-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220111","9783642220128"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22012-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}